4.2 동적 배열과 연결 리스트
동적 배열과 연결 리스트의 차이를 정리한 다음 표를 살펴봅시다.
▼ 표 4-1 동적 배열과 연결 리스트의 차이
|
|
동적 배열 |
연결 리스트 |
|
삽입 및 삭제 |
O(n) |
O(1) |
|
탐색 |
O(1) |
O(n) |
1. 삽입 및 삭제
동적 배열은 배열의 마지막에 데이터를 추가하거나 삭제하는 경우를 제외하고 O(n)의 성능을 가지는 반면, 연결 리스트는 단지 연산 상수 한 번만으로도 데이터를 추가하거나 삭제할 수 있습니다. 당연히 빅오는 O(1)입니다.
2. 탐색
동적 배열은 인덱싱이라는 단 한 번의 강력한 연산으로 해당 인덱스의 데이터에 접근할 수 있었습니다. 빅오는 O(1)이지요. 하지만 연결 리스트는 해당 요소의 데이터에 접근하기 위해 처음부터 모든 노드를 차례로 순회해야 했습니다. 빅오는 O(n)입니다.
이처럼 동적 배열과 연결 리스트의 특징은 정반대입니다. 자료 구조의 특징을 잘 이해했나요? 그렇다면 상황에 맞게 알맞은 자료 구조를 선택할 수 있습니다.
Tip 연결 리스트는 어디에 쓰나요?
연결 리스트는 그 자체만으로는 동적 배열에 비해 쓰임새가 적은 편입니다. 삽입과 삭제가 빈번한 경우에 사용을 고민해 볼 수 있겠지요. 연결 리스트를 사용한 예로는 OS에서 힙 메모리를 할당 및 해제할 때 이중 연결 리스트로 구현한 경우가 있습니다. 연결 리스트가 중요한 이유는 다른 자료 구조를 구현하는 토대가 되기 때문인데요. 뒤에서 배울 트리는 대부분 연결 리스트로 구현됩니다.