list와 vector의 차이를 비교하는 글은 아주 많다. 대부분 C++ STL 기준으로 쓰여있지만, 본질은 더블 링크드 리스트와 동적 배열의 비교로 봐야 한다.

하지만 많은 글에서 시간 복잡도(Big-O)만 언급할 뿐, 진짜 중요한 메모리 할당 비용과 캐시 효율에 대한 언급이 없어 아쉬웠다. 이 글에서 그 부분을 제대로 정리해본다.

---

흔한 오해: 시간 복잡도 (Big-O) 비교

일반적으로 두 자료구조는 이렇게 비교된다.

구분	vector (동적 배열)	list (링크드 리스트)
인덱스 접근	O(1)	O(n)
끝 삽입/삭제	O(1) (Amortized)	O(1)
중간 삽입/삭제	O(n)	O(1)

여기까지만 보면 list가 중간 삽입/삭제에 압도적으로 유리해 보인다. 하지만 실제 성능은 전혀 다르다.

시간 복잡도를 넘어 메모리 할당, 캐시 관점에서 접근하는 것이 더 올바르다.

---

진짜 차이: 메모리와 캐시

1. list: 비싼 힙 메모리 할당과 파편화

list는 노드(Node) 기반 구조다. 원소를 하나 추가할 때마다 힙(Heap) 메모리 할당과 해제가 발생한다.

• 비싼 비용: 힙 메모리 관리는 필요시 시스템 콜(System Call)을 동반하는, 복잡도를 떠나 그냥 아주 비싼 작업이다. list의 O(1) 삽입/삭제는 vector의 O(1)과는 비교도 안 되게 느리다.
• 메모리 파편화: 각 노드가 메모리 공간에 흩어져서 할당된다. 이는 두 가지 문제를 일으킨다.
  1. 메모리 오버헤드: 각 원소는 데이터 외에 이전/다음 노드를 가리키는 포인터 공간(8 or 16 bytes)을 추가로 차지한다.
  2. 캐시 효율 저하: 데이터가 메모리에 흩어져 있으니, 순차적으로 순회하더라도 캐시 라인을 제대로 활용할 수 없다. 결국 캐시 미스(Cache Miss)가 빈번하게 발생해 CPU가 RAM에 접근해야 하므로 성능이 크게 떨어진다.

2. vector: 압도적인 캐시 효율

vector는 모든 원소가 메모리상에 연속으로 존재한다.

• 캐시 친화적: 하나의 원소에 접근하면, 그 주변의 다른 원소들도 함께 캐시 라인에 올라온다. 따라서 순차적으로 순회할 때 거의 대부분의 데이터 접근이 캐시에서 처리(Cache Hit)된다.
• 저렴한 할당 비용: 메모리 재할당이 일어날 때를 제외하면, 단순히 포인터를 이동하며 원소를 추가하므로 비용이 매우 저렴하다.

이런 이유로 성능이 중요한 코드에서는 대부분 vector를 사용한다.

---

vector의 단점을 극복하는 최적화 기법

vector의 유일한 약점인 ‘중간 삭제’와 ‘메모리 재할당’ 비용은 몇 가지 기법으로 해결할 수 있다.

1. 정렬이 필요할 때
   • 정렬 상태를 유지하겠다고 중간 삽입/삭제를 남발하는 것보다, 그냥 맨 뒤에 다 추가하고 필요할 때 한 번에 정렬(std::sort)하는 것이 훨씬 빠르다.
2. 메모리 재할당/복사 비용 줄이기
   • reserve()를 사용해 필요한 메모리를 미리, 크게 할당해두면 불필요한 재할당과 복사 비용을 없앨 수 있다.
   • 더 나아가, vector 자체를 미리 여러 개 만들어두고 돌려쓰는 객체 풀링(Object Pooling)을 적용해 메모리 할당/해제 비용 자체를 없앨 수도 있다.
3. 중간 삭제 비용 줄이기
   • Swap and Pop: 삭제할 원소를 맨 뒤 원소와 맞바꾼(swap) 뒤, 맨 뒤 원소를 제거(pop_back)하는 기법. O(1)에 삭제가 가능하지만, 원소의 순서가 깨지기 때문에 사용처는 제한적이다.
4. 여러 스레드에서의 경쟁 문제
   • 하나의 vector를 여러 스레드가 접근하면 락(Lock) 경쟁이 발생한다. 이때 vector를 두 개 두고(더블 버퍼링) 하나는 읽기용, 하나는 쓰기용으로 사용하는 방식으로 락을 피할 수 있다.

여기서 더 나아가

vector는 메모리 응집도와 캐시 효율(캐시 히트율 높음 + 캐시 메모리 효율 또한 높음) 덕분에, 제한적인 케이스에서는 해시 테이블(unordered_map)보다 빠를 수도 있다.