[Data Structure] 선형 자료구조

배열

배열은 가장 기초적인 선형 자료구조다.

배열의 원소들은 메모리 상의 연속된 위치에 저장된다. 이 특성 덕분에 캐시의 효율성을 극대화 할 수 있다. 캐시는 보통 메모리의 일정 영역을 저장해놓기 때문에 배열같이 연속적인 위치에 저장된 데이터의 경우 더 빠른 속도로 접근이 가능하다.

배열의 원소들은 각각 인덱스로 구분 가능하다. 주어진 인덱스에 있는 원소를 반환하거나 변경하는 동작을 O(1)에 할 수 있다.

배열은 선언할 때 배열의 크기를 지정해야 한다는 문제점을 가지고 있다. 처음 선언한 크기보다 더 많은 자료를 집어넣을 수 없다.

 

동적 배열 (Dynamic Array)

배열의 크기를 변경할 수 없다는 문제를 해결하기 위해 크기가 변경되는 '동적 배열'이 고안됐다.

배열의 특성을 그대로 이어받지만 추가적인 특성을 갖게된다.

일단 당연하게도 배열의 크기를 변경할 수 있다. 배열의 크기를 변경할 때는 원래 있던 배열에 추가적인 자료를 붙이지 않는다. 새로운 배열을 만든 후 원래 배열의 원소들을 복사하고, 새 배열을 참조하도록 바꿔치기 하는 방식으로 동작한다. 때문에 배열의 크기를 변경하면 배열 크기 N에 비례하는 시간이 걸리게 된다.

주어진 원소를 배열의 맨 끝에 추가해 배열의 크기를 늘리는 연산도 가능하다. 이 연산은 상수 시간에 가능하다.

 

연결 리스트 (Linked List)

배열 원소들의 순서를 유지하면서 임의의 위치에 원소를 삽입, 삭제하는 것은 시간이 오래 걸린다. 해당 위치 뒤에 원소들을 당겨주거나 밀어주거나 해야하기 때문이다. 이 작업은 평균적으로 원소 개수에 선형 비례하는 시간이 걸린다.

이 문제를 해결하기 위해 고안된 자료구조가 연결 리스트다.

연결 리스트를 사용하면 특정 위치에 삽입과 삭제를 상수 시간에 할 수 있다.

배열은 메모리의 연속적인 위치에 원소들이 저장되어있는 반면, 연결 리스트는 원소들이 메모리 여기저기 흩어져 있고 각 원소들이 다음 원소를 가리키는 포인터를 가지는 방식으로 구현된다.

원소들이 여기저기 흩어져있기 때문에 특정 원소를 찾기 위해서는 머리부터 시작해 하나씩 포인터를 따라가며 찾아야한다.

연결 리스트가 임의의 위치에 원소를 삽입, 삭제하는 것을 빠르게 하기 위한 자료구조라고 했으나 엄밀히 말하면 경우에 따라 다르다.

연결 리스트에서 원소를 삽입, 삭제하기 위해 해당 노드를 찾아가는 과정까지 포함하면 O(N)의 시간복잡도를 가지기 때문이다. 만약, 맨 앞과 맨 뒤에 삽입/삭제한다면 O(1)에 수행할 수 있기 때문에 배열보다 빠르다.

 

동적 배열 vs 연결 리스트

동적 배열은 삽입/삭제를 할 일이 거의 없거나, 배열의 끝에서만 하면 될 경우에는 연결 리스트보다 더 효율적이다.

반면, 임의의 원소를 접근하는 것이 아니라 모든 원소들을 순회하며 삽입과 삭제를 한다면 연결 리스트가 더 좋은 선택이다.