C++ 기준 다음의 헤더파일을 사용하면 쉽게 이용할 수 있다.
#include <vector>
#include <list>
둘 다 선형 자료구조이지만, 둘의 차이점은 명확하다.
벡터
벡터는 배열을 이용해 만든 자료구조이다.
따라서 원소들은 메모리의 연속된 위치에 저장된다.
그래서 주어진 위치의 원소를 반환하거나 변경하는 동작을 O(1)에 할 수 있다.(index를 사용하기 때문!)
시간복잡도
- resize() : O(N) (새 배열을 만들고, 기존 배열의 원소들을 하나씩 복사하기 때문)
- append() : O(1)
*append()를 상수 시간안에 구현하려면, 처음 벡터를 선언할 때 미리 여유용량(capacity)을 확보해서 선언한다.
만약 capacity가 다 찬다면, 배열을 추가로 동적 할당한다.
이때, 기존 용량만큼 새로 할당하기 때문에(할당할때마다 용량이 두 배씩 커짐), 시간복잡도는 평균적으로 선형 시간을 가지게 된다.
연결 리스트
자료구조 시간에 배웠었던 doubly linked list로 구현이 되어있다.
노드들이 포인터를 가지고 서로를 연결하고 있다.
노드의 구조는 다음과 같다.
struct ListNode{
int element; //담고있는 원소
ListNode* left, right; //이전 노드와 다음 노드를 가리키는 포인터
};각 노드들이 서로의 꼬리의 꼬리를 물고 있는 구조이다.
따라서 벡터나 배열에서 쓰던 인덱스를 사용할 수 없고, 노드를 탐색하거나 수정하려면 첫 노드부터 원하는 노드가 나올 때까지 일일이 탐색해야한다.
대신 리스트 중간에서 삽입, 삭제가 이루어지는 경우 벡터나 배열보다 훨씬 빠르다. 삭제했던 원소를 원복시키는 연산도 더 빠르다.
정리
| 작업 | 동적 배열 | 연결 리스트 |
| 이전 원소/다음 원소 찾기 | O(1) | O(1) |
| 맨 뒤에 원소 추가/삭제하기 | O(1) | O(1) |
| 맨 뒤 이외의 위치에 원소 추가/삭제하기 | O(n) | O(1) |
| 임의의 위치의 원소 찾기 | O(1) | O(n) |
| 크기 구하기 | O(1) | O(n) 혹은 구현에 따라 O(1) |
결론
앵간하면 벡터쓰는데, 삽입/삭제 연산이 빈번한 경우 리스트를 사용하자.
