[C++] vector 와 list의 차이 정리

오늘은 STL의 순차 컨테이너 중 vector와 list의 차이를 정리해보려고 한다.

둘 다 여러 개의 원소를 저장하는 컨테이너지만,
내부적으로 데이터를 저장하는 방식이 다르기 때문에 성능 특성도 크게 다르다.

특히 메모리 배치 방식이 다르기 때문에
원소 접근, 삽입과 삭제, 캐시 효율, iterator 무효화 여부에서도 차이가 발생한다.

아래 두 컨테이너의 특징, 내부 구조, 원소 추가 시 동작, 그리고 컨테이너 선택 기준을 정리해보았다.

---

vector

vector는 연속적인 메모리 공간에 데이터를 저장하는 동적 배열이다.

배열처럼 원소들이 메모리상에 연속적으로 배치되기 때문에
인덱스를 이용한 접근이 빠르다.

std::vector<int> v = {1, 2, 3, 4, 5};

std::cout << v[2] << std::endl;

vector는 [] 연산자를 통해 특정 위치의 원소에 바로 접근할 수 있다.

내부적으로는 대략 다음과 같은 방식으로 위치를 계산한다.

시작 주소 + 객체 크기 * index

따라서 임의 접근이 O(1)에 가능하다.

---

vector의 특징

vector의 특징은 다음과 같다.

• 연속적인 메모리 공간에 원소를 저장한다.
• [] 연산자로 특정 위치에 빠르게 접근할 수 있다.
• 주소가 연속되어 있어 캐시 효율이 좋다.
• push_back은 평균적으로 O(1)이다.
• 중간 삽입 / 삭제는 O(N)이다.
• 재할당이 발생하면 기존 iterator, pointer, reference가 무효화될 수 있다.

---

vector의 내부 구조

vector는 내부적으로 보통 다음과 같은 포인터 정보를 가진다.

• 시작 주소
• 마지막 원소 다음 주소
• 할당된 메모리의 끝 주소

이 주소들을 보통 begin, end, capacity_end 와 같은 이름으로 저장한다.
이를 이용해 size와 capacity를 계산할 수 있다.

size = end - begin
capacity = capacity_end - begin

size는 실제 원소 개수이고, capacity는 현재 재할당 없이 저장할 수 있는 최대 원소 개수이다.

---

vector에 원소를 추가할 때

vector에 push_back으로 원소를 추가할 때,
현재 capacity가 충분하다면 이미 할당된 공간 뒤에 원소를 추가하고 평균적으로 O(1)이다.

하지만 capacity를 초과하면 다음 과정이 필요하다.

1. 더 큰 메모리 블록을 새로 할당한다. 보통 1.5 ~ 2배 정도로 증가한다.
2. 기존 원소들을 새 메모리로 이동 또는 복사한다.
3. 기존 메모리를 해제한다.
4. 새 원소를 추가한다.

이 경우 기존 원소 전체를 옮겨야 하므로 O(N)이 된다.
또한 메모리 위치가 바뀌기 때문에 기존 iterator, pointer, reference가 무효화될 수 있다.

---

list

list는 비연속적인 메모리 공간에 원소를 저장하는 양방향 연결 리스트이다.
각 원소는 노드 형태로 존재하며, 각 노드는 이전 노드와 다음 노드를 가리키는 포인터를 가진다.

즉, vector처럼 원소들이 메모리상에 연속적으로 배치되어 있지 않다.

---

list의 특징

list의 주요 특징은 다음과 같다.

• 비연속적인 메모리 공간에 노드 단위로 원소를 저장한다.
• 양방향 연결 리스트 구조이다.
• 특정 위치에 접근하려면 iterator를 이동하며 순회해야 한다.
• 삽입 / 삭제할 위치를 알고 있다면 O(1)에 처리할 수 있다.
• 삽입 / 삭제가 일어나도 기존 iterator와 reference가 대부분 유지된다.
• 각 노드마다 prev, next 포인터가 필요하므로 추가 메모리 비용이 있다.

---

list의 내부 구조

list는 보통 내부적으로 sentinel 역할을 하는 노드 또는 그에 준하는 head / tail 정보를 가진다.

sentinel 노드는 실제 데이터를 저장하지 않는 빈 노드이며,
리스트의 시작과 끝을 관리하는 역할을 한다.

개념적으로는 다음과 같다.

• sentinel의 next는 첫 번째 원소를 가리킨다.
• sentinel의 prev는 마지막 원소를 가리킨다.
• 리스트가 비어 있다면 sentinel은 자기 자신을 가리킨다.

또한 구현에 따라 size 정보를 따로 가지고 있을 수 있다.

---

list에 원소를 추가할 때

list에 원소를 추가하면 보통 다음 과정이 일어난다.

1. 새로운 노드를 동적 할당한다.
2. 새 노드에 데이터를 저장한다.
3. 앞 노드와 뒤 노드의 next, prev를 수정한다.
4. 새 노드를 리스트에 연결한다.

즉, list는 원소를 추가할 때마다 새로운 노드를 위한 메모리 할당이 발생할 수 있다.

삽입 위치를 이미 알고 있다면 연결만 바꾸면 되므로 O(1)이지만,
메모리 할당 자체는 비용이 큰 동작이기 때문에
항상 vector보다 빠르다고 볼 수는 없다.

---

언제 vector를 사용할까?

다음과 같은 경우에는 vector가 적합하다.

• 인덱스로 원소에 자주 접근해야 할 때
• 순차적으로 데이터를 저장하고 순회할 때
• 삽입 / 삭제보다 조회가 많을 때
• 캐시 효율이 중요한 경우
• 데이터 개수를 어느 정도 예측할 수 있을 때

대부분의 경우 기본 선택지는 vector가 되는 경우가 많다.

특히 원소들이 연속된 메모리에 저장되기 때문에 순회 성능이 좋고, 캐시 효율도 높다.

---

언제 list를 사용할까?

다음과 같은 경우에는 list를 고려할 수 있다.

• 중간 삽입 / 삭제가 자주 발생할 때
• 삽입 / 삭제할 위치의 iterator를 이미 알고 있을 때
• 기존 iterator나 reference가 최대한 유지되어야 할 때

하지만 단순히 중간 삽입 / 삭제가 있다는 이유만으로
무조건 list가 더 빠르다고 볼 수는 없다.

list는 원소마다 별도의 노드 할당이 필요하고,
메모리가 흩어져 있어 캐시 효율이 낮을 수 있기 때문이다.

---

정리

vector와 list는 모두 STL 컨테이너지만
내부 구조가 다르기 때문에 성능 특성도 다르다.

vector

• 연속적인 메모리 공간을 사용한다.
• 임의 접근이 O(1)이다.
• 캐시 효율이 좋다.
• push_back은 평균적으로 O(1)이다.
• 중간 삽입 / 삭제는 O(n)이다.
• 재할당 시 iterator, pointer, reference가 무효화될 수 있다.

list

• 비연속적인 노드 구조를 사용한다.
• 인덱스를 이용한 임의 접근이 불가능하다.
• 삽입 / 삭제 위치를 알고 있으면 O(1)에 처리할 수 있다.
• 삽입 / 삭제 시 기존 iterator와 reference가 대부분 유지된다.
• 노드마다 추가 포인터 메모리가 필요하다.
• 원소 추가마다 메모리 할당이 발생할 수 있다.

---

마무리

이번에 vector와 list를 비교하면서
단순히 삽입 / 삭제 시간 복잡도만 보고 컨테이너를 선택하면 안 된다는 것을 느꼈다.

list는 중간 삽입 / 삭제가 O(1)이라고 하지만 그 위치를 찾는 데는 O(N)이 걸릴 수 있고,
노드마다 메모리 할당이 발생하며 캐시 효율도 좋지 않을 수 있다.

반대로 vector는 중간 삽입 / 삭제가 느릴 수 있지만 연속된 메모리 구조 덕분에 접근과 순회 성능이 좋다.

앞으로 컨테이너를 선택할 때는 삽입 / 삭제가 많은지, 임의 접근이 필요한지,
캐시 효율과 iterator 무효화까지 함께 고려해서 선택해야겠다.