1. 연속된 자료 구조(배열) vs 연결된 자료 구조(링크 리스트) (C++)

선형 자료 구조

---

1. 선형 자료 구조란? 자료를 구성하는 데이터를 순차적으로 나열한 방식이다.
   예를 들어 {1 ,a ,2 ,l} 라는 자료들이 있다고 가정하고 이를 연속적으로 1 - a - 2 - l  이렇게 나열하는 표현하는 방식을 선형 하다라고 한다.
   대표적인 선형 자료 구조로는 배열,리스트,스택,큐 가 있다.
   
   
2. 선형 자료 구조의 종류 
   크게 연속된 자료 구조와 연결된 자료구조로 나뉜다.

---

연속된 자료 구조

1. 연속된 자료 구조
   
   연속된 자료구조는 모든 원소를 단일 메모리에 저장을 하며 이를 밑에 다이어그램으로 보여준 것이다.
   

   data [0]

   data [1]

   data [2]

   data [2]

   arr                             arr + sizeof(type)       arr + 2*sizeof(type)   arr + 2*sizeof(type)   
   
   시작 주소: arr
   원소 하나에 필요한 메모리 크기: sizeof(type)
   
   여기서 각각의 원소는 같은 type을 사용하기에 이를 sizeof(type) 으로 표현한다. (type에는 int, double, char 등등..)
   그래서 현재 원소가 4개 이므로 순차적으로 각 인덱스의 번호 * sizeof(type) 를 첫주소 arr에 더해준 것이다.
   
   만약 임의의 원소에 접근시 특정 주소만 알면 바로 접근이 가능하기에 시간복잡도는 big-O 표기법에 의해 O(1)이다.
   
   
2. 연속된 자료 구조의 유형
   1. 정적 배열: 선언된 블록이 자동으로 해제되며 stack 메모리 영역에 할당된다.
      ex) int arr[size];
   2. 동적 배열: 프로그래머가 생성할 시점과 해제를 자유롭게 지정할 수 있으며 heap 영역에 할당된다.
      ex) int *arr=new int[size];
3. 캐시 지역성
   각 원소가 서로 인접해 있기에 하나의 원소를 가져오면 그 옆에 있는 원소 몇 개도 캐시로 가져오기에 캐시 지역성이 존재

---

연결된 자료 구조

1. 연결된 자료 구조
   
   연결된 자료 구조란 노드라고 하는 여러 개의 메모리에 데이터를 저장하며, 이때 저장된 데이터는 서로 다른 메모리 위치에 데이터가 저장이 되는 방식이다.
   
   밑에는 이를 표현한 다이어 그램이다.
   
   
   이와 같은 형태를 연결 리스트라 한다.
   연결 리스트의 기본 구조에서 노드는 data와 다음을 가리킬 포인터인 next를 가지고 있으며 맨 끝에는 있는 노드는 더 이상 가리킬 곳이 없으므로 NULL을 가진다.
   
   연결된 자료 구조는 연속된 자료 구조와 달리 임의의 원소에 접근할려면 노드의 맨 첫번째 즉 head 부분 부터 탐색을 해야 하기에 노드 수의 비례해 시간복잡도는 O(n)이 된다.
   
   하지만 연속된 자료 구조와 달리 삽입과 삭제는 빠르게 이루어진다.
   예를들어 삽입의 경우
   위와 같은 그림에서 현재 새로운 원소를 삽입할 노드를 생성하고, 이 노드가 들어가기 위해 기존에 포인터들을 수정을 해야한다.
   먼저 index=2가 index=3를 가리키게 만든 후 index=1이 가리키고 있는 현재 포인터를 제거 한다.
   후에 index=1은 index=2를 가리키게 만들면 끝이난다.
   
   제거의 경우도 이와 비슷하게 제거 하고 싶은 노드의 포인터를 양쪽으로 끊고 메모리를 해제하면 된다.
   
   
2. 캐시 지역성
   노드가 가리키는 곳을 직접 방문하지 않는 이상 원소를 캐시로 가져올 수 없으므로 캐시 지역성은 없다.

---

연속된 자료 구조 vs 연결된 자료 구조

1. 비교

   연속된 자료 구조	연결된 자료 구조
   모든 데이터가 메모리에 연속적으로 저장.	데이터는 노드에 저장되어 메모리 곳곳에 흩어져 있을 수 있음.
   임의 원소에 즉각적으로 접근 가능.	임의 원소에 접근하는 것은 선형 시간 복잡도를 가져 상대적으로 느리다.
   데이터가 연속적으로 저장되어 있어, 캐시 지역성 효과를 얻어 모든 데이터를 순회 하는 것이 매우 빠름.	캐시 지역성 효과가 없어 데이터를 순회 할때 느림.
   데이터 저장을 위해 정확한 데이터 크기의 메로를 사용.	각 노드는 포인터 저장을 위해 data에 필요한 메모리 이상의 메모리를 사용한다.

2. 시간 복잡도 비교
   
   

파라미터	배열	연결 리스트
임의 접근	O(1)	O(n)
맨 뒤에 원소 삽입	O(1)	O(1)
중간에 원소 삽입	O(n)	O(1)
캐시 지역성	있음	없음