연결 리스트가 배열보다 항상 삽입이 빠른가?

항상 빠르지는 않으며, 삽입하려는 위치를 찾는 탐색 비용에 따라 더 느려질 수 있다. 넣을 자리의 노드를 이미 쥐고 있으면 가운데라도 O(1)이다. 자리를 찾아가는 것부터 세면 O(N)이라 배열과 다를 것이 없다.

배열과 연결 리스트의 연산별 시간 복잡도를 비교하면 다음과 같다.

연결 리스트는 임의의 위치에 삽입할 때 먼저 그 위치까지 노드를 타고 이동해야 한다. 탐색에 O(N)의 시간이 걸리므로, 삽입 자체는 O(1)이라도 총 시간 복잡도는 O(N)이 된다.

반면 배열은 탐색은 O(1)로 빠르지만 삽입 시 뒤의 원소들을 한 칸씩 밀어내는 쉬프트 비용 때문에 O(N)이 걸린다. 결국 데이터가 무작위로 위치할 때는 두 자료구조 모두 한계가 있다.

양 끝의 삽입과 삭제에서 노드를 이미 쥐고 있다면 연결 리스트는 요소를 옮기지 않는다. 큐(Queue)를 연결 리스트로 구현하는 이유다.