Array와 Linked list

array와 linked list가 둘다 선형 자료구조라 그런지, 이 둘의 비교대조가 기술면접의 단골 질문인 것 같다. 머리속에서 가물가물한 온갖 트리들과는 다르게 이쪽은 지금도 확실히 기억나니 한번 정리해보자.

 

array는 엘레먼트에의 액세스가 시간복잡도 O(1)의 상수 시간에 가능한 선형 자료구조이다. 이를 가능케 하기 위해 각 엘레먼트는 물리적으로 정렬되어 있다. 예를 들어 8바이트 char* 포인터를 저장하는 array의 경우, array의 시작인 0번째 원소의 주소가 X라면 10th 엘레먼트는 X+80바이트의 위치에 액세스하는 것으로 접근이 가능하다.

가장 단순한 자료구조이긴 하지만, 이 O(1)의 액세스를 유지하기 위해 원소의 삽입과 삭제 시에는 재편이 필요하다. 예를 들어 100개의 엘레먼트를 가진 array에서 20번째 엘레먼트를 삭제 시, 뒤의 80개의 엘레먼트는 빈 칸을 메우기 위해 재정렬이 필요하며 이는 O(n)의 시간복잡도로 표현된다. 삽입도 마찬가지.

따라서 array는 선형구조의 중간에 삽입이나 삭제가 반복되는 데이터의 관리에는 유용하지 않다. 예를 들어 메모리 동적 할당 시스템을 best fit으로 구현할 경우, 이를 위해 명시적 가용리스트는 가용 공간의 크기로 정렬된 상태를 유지해야 하고, 새 메모리가 할당, 해제될때마다 선형구조의 중간에 삽입과 삭제가 이루어지게 되며 이를 array로 구현시에는 시간을 잡아먹는다.

 

이런 비효율을 개선하기 위해 삽입과 삭제에 특화된 선형 자료구조가 Linked list이다. 이는 트리를 구성할 때처럼 각 노드 객체가 자신의 연결 정보를 가지는 것으로 구현이 가능한데, 이렇게 구현할 시 노드의 삭제연산은 그 노드와 연결된 prev, next 노드를 서로 연결하는 것으로 간단히 구현이 가능하고, 삽입연산 역시 삽입해야할 위치의 두 노드의 연결을 끊어 삽입할 노드와 연결하는 것으로 구현이 가능하다. 이는 시간복잡도 O(1)으로 표현된다.

하지만 Linked list는 당연하게도 각 노드가 물리적으로 정렬되어있지 않기 때문에, n번째 노드에 액세스하려면 명시적으로 관리하는 0번째 노드(혹은 마지막 노드)부터 n번의 연산으로 간선을 이동해야 한다. 이는 시간복잡도 O(n)으로 표현된다.

따라서 Linked list는, 삽입과 삭제는 잦지만 값 수정 등을 위한 엘레먼트에의 액세스는 거의 없거나 끝점에서만 이루어지는 데이터일 때 사용하는 것이 효율적이다. 상기한 가용 용량에 따라 정렬된 명시적 가용리스트나, OS시스템의 priority에 의해 정렬된 ready list 등.

 

한줄로 요약해서 데이터가 정적이고 탐색/타겟팅 수정만 잦다면 array를 쓰고, 데이터에 동적인 삽입, 삭제가 잦다면 linked list를 쓰는 것이 효율적일 것이다.