배열 vs 연결리스트 시간복잡도 비교
배열과 연결리스트의 차이는 시간복잡도 표로 한 번에 볼 수 있지만, 표만 외우면 헷갈리기 쉽다. 핵심은 배열은 “위치 계산”에 강하고, 연결리스트는 “연결 변경”에 강하다는 점이다.
배열은 인덱스로 원하는 위치를 바로 계산할 수 있다. 그래서 arr[i]처럼 특정 위치에 접근하는 연산은 O(1)이다. 반대로 연결리스트는 head부터 시작해서 다음 노드를 하나씩 따라가야 하므로, 특정 위치 접근은 O(n)이다.
값을 탐색하는 경우에는 둘 다 보통 O(n)이다. 배열도 원하는 값이 어디 있는지 모르면 처음부터 비교해야 하고, 연결리스트도 노드를 순서대로 따라가며 확인해야 한다.
삽입과 삭제는 “이미 위치를 알고 있는가”가 중요하다. 배열의 앞이나 중간에 값을 넣으면 뒤의 요소들을 한 칸씩 밀어야 한다. 삭제할 때도 빈 공간을 메우기 위해 뒤의 요소들을 앞으로 당겨야 한다. 그래서 앞/중간 삽입과 삭제는 O(n)이다.
연결리스트는 노드 참조를 이미 알고 있다면 연결만 바꾸면 된다. 앞에 새 노드를 붙이는 작업은 newNode.next = head, head = newNode로 끝난다. 이중 연결리스트에서 특정 노드를 삭제하는 것도 양쪽 노드의 prev, next를 바꾸면 된다. 이 경우 삽입과 삭제 자체는 O(1)이다.
다만 “중간의 몇 번째 위치에 넣는다”처럼 위치를 먼저 찾아야 한다면 이야기가 달라진다. 연결리스트는 그 위치까지 이동하는 데 O(n)이 먼저 든다. 그래서 연결리스트의 중간 삽입이 항상 배열보다 빠르다고 말하면 부정확하다.
자주 비교하는 연산
면접이나 코딩 테스트에서 빠르게 정리해야 한다면 아래 정도만 기억해도 충분하다.
- 인덱스 접근: 배열은 O(1), 연결리스트는 O(n)
- 값 탐색: 배열과 연결리스트 모두 O(n)
- 맨 앞 삽입/삭제: 배열은 O(n), 연결리스트는 O(1)
- 맨 뒤 삽입: 동적 배열은 amortized O(1), tail이 있는 연결리스트는 O(1)
- 맨 뒤 삭제: 배열은 O(1), 단일 연결리스트는 보통 O(n), 이중 연결리스트는 O(1)
- 중간 삽입/삭제: 배열은 요소 이동 때문에 O(n), 연결리스트는 위치 탐색까지 포함하면 O(n)
여기서 가장 자주 놓치는 부분은 중간 삽입/삭제다. 연결리스트는 “노드 참조를 이미 알고 있을 때” 연결 변경이 O(1)이고, “몇 번째 노드인지 찾아야 할 때”는 탐색 비용 때문에 O(n)이다.
동적 배열의 맨 뒤 추가는 왜 평균 O(1)인가
동적 배열은 맨 뒤에 원소를 추가할 때 보통 O(1)이다. 여유 공간이 있으면 빈 칸에 넣고 size만 늘리면 된다. 문제는 용량이 꽉 찼을 때다. 이때는 더 큰 배열을 만들고 기존 원소를 모두 복사하므로 한 번의 추가가 O(n)이 된다.
하지만 용량을 1.5배나 2배로 늘리면 확장은 가끔만 일어난다. 긴 구간에서 보면 복사 비용이 여러 add 연산에 나뉘어 들어가므로 평균적으로는 O(1)에 가깝다. 그래서 ArrayList.add()의 시간복잡도를 amortized O(1)이라고 말한다.
실제 성능에서는 캐시가 크게 작용한다
시간복잡도는 입력 크기가 커질 때의 성장률을 보는 도구다. 하지만 같은 O(n)이라도 실제 속도는 많이 다를 수 있다. 배열은 메모리에 연속으로 놓여 있어 CPU 캐시를 잘 탄다. 순차 순회에서는 다음 원소가 이미 캐시에 올라와 있을 가능성이 높다.
연결리스트는 노드가 흩어져 있을 수 있고, 각 노드마다 다음 주소를 따라가야 한다. 이 포인터 추적은 캐시 미스를 만들기 쉽다. 그래서 단순 순회나 일반적인 리스트 작업에서는 연결리스트보다 배열 기반 구조가 더 빠른 경우가 많다.
면접에서 말할 포인트
배열은 인덱스 접근이 O(1)이고 캐시 효율이 좋지만, 앞이나 중간 삽입/삭제는 요소 이동 때문에 O(n)이다. 연결리스트는 노드 참조를 알고 있으면 삽입/삭제가 O(1)이지만, 위치를 찾는 데 O(n)이 들 수 있다. 동적 배열의 맨 뒤 추가는 확장 시 O(n)이지만 여러 번의 추가를 평균 내면 amortized O(1)이다.