|
파라미터 |
배열 |
연결 리스트 |
|
임의 접근 |
O(1) |
O(n) |
|
맨 뒤에 원소 삽입 |
O(1) |
O(1) |
|
중간에 원소 삽입 |
O(n) |
O(1) |
|
캐시 지역성 |
있음 |
없음 |
▲ 그림 1-5 다양한 연산에 대한 배열과 연결 리스트의 시간 복잡도
배열과 연결 리스트는 매우 범용적이며 많은 응용 프로그램에서 데이터를 저장하는 용도로 사용되고 있습니다. 그러므로 이들 자료 구조의 구현은 버그가 없어야 하며, 최대한 효율적으로 동작해야 합니다. 사용자가 직접 이들 자료 구조를 구현하지 않아도 되도록 C++는 std::array, std::vector, std::list 같은 다양한 자료 구조 클래스를 제공합니다. 이제부터 이들 자료 구조 클래스에 대해 자세히 알아보겠습니다.