[1. 리스트, 스택, 큐] 선형 자료 구조

선형 자료 구조는 크게 연속된 구조와 연결된 구조로 분류할 수 있다.

 

연속된 구조 (contiguous data structure)

모든 원소를 단일 메모리 청크에 저장하는 것

data[0]	data[1]	data[2]	data[3]
Base Address	BA + sizeof(type)	BA + 2 * sizeof(type)	BA + 3 * sizeof(type)

위 그림처럼 단일 메모리 청크 내에 각각의 원소가 저장된 메모리 공간이 존재한다.

각 원소에 접근할 때에는 BA + i * sizeof(type)을 이용하여 O(1)로 데이터에 접근할 수 있다.

 

배열은 정적 배열(static array)와 동적 배열(dynamic array)로 나눌 수 있다.

 

1. 정적 배열

- 선언된 블록이 끝나면 소멸된다.

- 선언

int arr[size];

- 스택(stack) 메모리 영역에 할당되기 때문에 함수를 벗어날 때 자동으로 해제된다.

 

 

2. 동적 배열

- 프로그래머가 생성할 시점과 해제할 시점을 자유롭게 결정할 수 있다.

- 선언

int* arr = new int[size];

- 힙(heap) 영역에 할당되기 때문에 사용자가 직접 해제하기 전까지 유지된다.

 

배열과 같이 연속된 자료구조에서는 각 원소가 서로 인접해 있다.

하나의 원소에 접근할 때 그 옆에 있는 원소들도 함께 캐시(cache)로 가져오게 되는데, 이 때문에 주변 원소에 접근할 때 매우 빠르게 동작할 수 있다. 이를 캐시 지역성(cache locality)이라고 하며, 배열은 캐시 지역성이 좋다.

 

연결된 자료 구조 (linked data structures)

node에 데이터를 저장하고, 서로 다른 메모리 위치에 데이터가 저장된다.

각각의 node는 저장할 data와 다음 노드를 가리키는 포인터(next)를 가진다.

맨 마지막 노드에는 다음 노드의 포인터 대신 자료 구조의 끝을 나타내는 NULL을 가진다.

연결 리스트에서 특정 원소에 접근하기 위해서는 시작 부분부터 next 포인터를 따라 이동해야 하므로 O(n)의 시간복잡도를 갖는다.

 

연결 리스트에 새 원소를 추가하는 과정은 다음과 같다.

위 그림처럼 새로운 노드의 next가 다음 노드를 가리키도록 연결하고, 전 node의 next가 새로 추가되는 node를 가리키도록 수정하면 된다.

기존 원소를 제거하는 과정도 next 포인터를 수정하여 연결 리스트에 연결되어 있지 않도록 수정하면 된다.

 

연결 리스트에서는 원소가 연속적으로 저장되지 않기 때문에 캐시 지역성을 기대할 수 없다.

배열과 연결 리스트에서 모든 원소를 차례대로 방문하는 작업은 이론적으로 같은 시간복잡도를 갖지만, 캐시 지역성이 없는 연결 리스트의 성능이 조금 떨어진다.

 

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

 

연속된 자료 구조	연결된 자료 구조
모든 데이터가 메모리에 연속적으로 저장된다.	데이터는 노드에 저장되고, 노드는 메모리 곳곳에 흩어져 있다.
임의 원소에 즉각적으로 접근할 수 있다.	임의 원소에 접근하는 것은 선형 시간 복잡도를 가지며 느리다.
캐시 지역성으로 인해 모든 데이터를 순회하는 것이 빠르다.	캐시 지역성이 없어 모든 데이터를 순회하는 것이 느리다.
데이터 저장에 정확한 데이터 크기의 메모리를 사용한다.	각 노드에서 포인터 저장을 위해 여분의 메모리를 사용한다.

 

시간 복잡도를 비교해보면 다음과 같다.

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

 

각 상황에 맞는 알맞은 자료 구조를 사용해야 한다.