std::list — 양방향 연결 리스트 컨테이너

std::vector는 연속된 메모리를 사용하기 때문에 Random Access와 순차 탐색 성능이 뛰어나다.

하지만 중간에 원소를 삽입하거나 삭제하면 뒤쪽 원소를 이동해야 한다.

 

std::list는 이러한 문제를 다른 방식으로 해결한다.

원소를 연속적으로 저장하는 대신 각각의 원소를 독립적인 Node로 만들고, Node끼리 연결한다.

이번 글에서는 std::list의 구조와 특징, Iterator 안정성, splice()와 sort() 같은 고유 기능을 살펴보고 마지막으로 vector와 비교한다.

 

---

1. std::list가 필요한 이유

1-1. vector의 중간 삽입·삭제 비용

vector는 원소를 연속해서 저장한다.

[10][20][30][40] // 20과 30 사이에 25를 넣으려면

        ↓

[10][20][25][30][40] // 뒤쪽 원소를 이동해야 한다.

 

 

따라서 중간 삽입은 일반적으로:

O(N)

 

 

삭제 역시 동일하다.

[10][20][30][40]

20 삭제

[10][30][40] // 뒤쪽 원소를 앞으로 이동시켜야 한다.

 

---

 

1-2. 원소를 이동하지 않는 자료구조

Linked List는 원소를 연속해서 저장하지 않는다.

대신 각 원소를 Node에 저장하고 Node끼리 연결한다.

[A] ⇄ [B] ⇄ [C]

B와 C 사이에 X를 삽입하면:

[A] ⇄ [B] ⇄ [X] ⇄ [C]

기존 C 이후의 원소들을 이동할 필요가 없다.

 

연결 관계만 수정하면 된다.

 

STL에서는 이러한 양방향 연결 리스트를:

std::list

로 제공한다.

 

---

2. std::list란

std::list 역시 vector, deque와 마찬가지로 Sequence Container에 속한다.

하지만 데이터 저장 방식은 완전히 다르다.

각 원소를 독립적인 Node에 저장하고 이전 Node와 다음 Node를 연결하는 Doubly Linked List 기반의 Sequence Container다.

 

대표적인 사용 방법은 다음과 같다.

std::list<int> Numbers = {
    10, 20, 30
};

 

 

---

2-1. Doubly Linked List

각 Node는 개념적으로 다음 정보를 가진다.

┌───────────────────┐
│ Prev Pointer      │
│ Data              │
│ Next Pointer      │
└───────────────────┘

따라서 양방향으로 이동할 수 있다.

[A] ⇄ [B] ⇄ [C]

 

---

3. 내부 구조

3-1. Node 구조

다음 list가 있다고 하자.

std::list<int> Numbers = {
    10, 20, 30
};

개념적으로:

[Prev | 10 | Next]
        ⇅
[Prev | 20 | Next]
        ⇅
[Prev | 30 | Next]

형태로 연결되어 있다.

---

3-2. 비연속 메모리

각 Node는 메모리상 서로 다른 위치에 존재할 수 있다.

0x1000             0x8700             0x3200

[10] ───────────→ [20] ───────────→ [30]

따라서:

Begin + Index * sizeof(T)

같은 방식으로 원하는 원소의 주소를 계산할 수 없다.

---

3-3. Bidirectional Iterator

std::list는 Bidirectional Iterator를 제공한다.

따라서:

++It;
--It;

처럼 앞뒤로 한 칸씩 이동할 수 있다.

 

하지만:

It += 10; // n칸 떨어진 위치로 직접 이동할 수 있는 Random Access Iterator 를 요구함

처럼 원하는 위치로 즉시 이동하는 Random Access는 지원하지 않는다.

 

---

 

4. 주요 특징

4-1. Random Access를 지원하지 않는다

다음 코드는 사용할 수 없다.

std::list<int> Numbers = {
    10, 20, 30
};

Numbers[2]; // 불가능

 

n번째 원소로 이동하려면 순차적으로 이동해야 한다.

auto It = Numbers.begin();

// Iterator를 지정한 거리만큼 이동시키는 함수
std::advance(It, 2);

 

이 경우 시간복잡도는:

O(N)

이다.

 

list의 Random Access가 O(N)인 것이 아니라, Random Access 자체를 지원하지 않으며 n번째 위치까지 이동하는 데 O(N)이 필요하다.

 

---

4-2. 삽입·삭제 위치를 알면 O(1)

다음 상태에서:

[A] ⇄ [B] ⇄ [C]

B와 C 사이에 X를 넣으면:

[A] ⇄ [B] ⇄ [X] ⇄ [C]

연결 정보만 변경한다.

 

따라서 삽입 위치 Iterator를 이미 가지고 있다면:

Numbers.insert(It, 25);

삽입 자체는:

O(1)

이다.

 

삭제도 마찬가지다.

Numbers.erase(It);

삭제 위치 Iterator가 이미 있다면 O(1)이다.

 

다만 삭제할 원소를 먼저 찾아야 한다면:

auto It = std::find(
    Numbers.begin(),
    Numbers.end(),
    20
);

탐색에 O(N)이 필요하다.

 

---

4-3. 앞·뒤 삽입과 삭제가 O(1)

std::list는 앞과 뒤 모두에서 삽입과 삭제를 O(1)에 수행할 수 있다.

Numbers.push_front(10);
Numbers.push_back(40);

Numbers.pop_front();
Numbers.pop_back();

 

반면, vector는 뒤쪽 삽입과 삭제만 지원한다.

 

다만 list가 앞뒤 삽입·삭제에 유리하다고 해서 항상 더 빠른 것은 아니다. 실제 성능은 Cache Locality, Node Allocation, 순회 빈도 등의 영향도 함께 받는다.

---

4-4. 메모리 오버헤드

각 Node는 데이터 이외에도 연결 정보를 가지고 있어야 한다.

Prev Pointer
Data
Next Pointer

따라서 vector보다 원소당 메모리 오버헤드가 크다.

 

특히 작은 타입일수록 이 차이가 커질 수 있다.

예를 들어 64-bit 환경에서 포인터 하나가 일반적으로 8Byte라면:

int Data        4Byte
Prev Pointer    8Byte
Next Pointer    8Byte

에 padding 등도 추가될 수 있다.

*padding : 메모리 정렬(alignment)을 맞추기 위해 객체 내부에 끼워 넣는 사용하지 않는 바이트

 

실제 Node 크기는 구현체와 alignment에 따라 달라진다.

---

 

4-5. Reallocation이 없다

vector는 capacity가 부족하면 더 큰 연속 저장 공간으로 이동해야 한다.

하지만 list는 새로운 Node를 하나 생성해 연결하면 된다.

기존

[A] ⇄ [B] ⇄ [C]

새 Node 삽입

[A] ⇄ [B] ⇄ [X] ⇄ [C]

따라서 vector와 같은 전체 저장 공간 Reallocation은 발생하지 않는다.

---

4-6. Iterator / Reference Invalidation

list는 Iterator 안정성이 높은 편이다.

새로운 원소를 삽입해도 20 Node의 위치는 바뀌지 않는다. 따라서 It은 계속 유효하다.

즉:

list에 원소를 삽입해도 기존 원소를 가리키는 Iterator와 Reference는 일반적으로 무효화되지 않는다.

 

삭제에서도 해당 원소를 가리키던 Iterator와 Reference만 무효화되고, 다른 Node를 가리키던 Iterator는 유지된다.

정리하면:

삽입
→ 기존 Iterator / Reference 유지

삭제
→ 삭제된 원소를 가리키던 것만 무효화

---

4-7. 주요 멤버 함수

함수	시간복잡도	역할
Random Access	지원하지 않음
n번째 원소까지 이동	O(N)
front()	O(1)	첫 번째 원소 접근
back()	O(1)	마지막 원소 접근
push_front()	O(1)	앞쪽 삽입
push_back()	O(1)	뒤쪽 삽입
pop_front()	O(1)	첫 번째 원소 제거
pop_back()	O(1)	마지막 원소 제거
insert()	O(1)	Iterator 위치에 삽입, 위치를 알고 있을 때
erase()	O(1)	Iterator 위치의 원소 제거, 위치를 알고 있을 때
clear()	O(N)	모든 원소 제거
size()	O(1)	원소 개수 반환
empty()	O(1)	비어 있는지 확인
splice()	overload에 따라 다름	Node 연결 변경
sort()	O(N log N)	list 자체 정렬

insert()와 erase()의 O(1)은 위치 Iterator를 이미 알고 있을 때 기준이다.

 

---

5. list::splice()

splice()는 std::list의 대표적인 고유 기능이다.

기존 원소를 복사하거나 이동 생성하지 않고 Node 자체의 연결 관계를 변경하여 다른 위치로 옮긴다.

std::list<int> A = {
    1, 2, 3
};

std::list<int> B = {
    10, 20, 30
};

auto It = B.begin();
++It;

// It → 20

A.splice(
    A.end(),
    B,
    It
);

 

결과:

// B가 소유하던 노드를 A 쪽으로 넘기는 것

A
[1] ⇄ [2] ⇄ [3] ⇄ [20]

B
[10] ⇄ [30]

 

단일 원소를 옮기는 경우 O(1)에 수행할 수 있다.

단, splice()의 모든 overload가 무조건 O(1)은 아니다. 범위를 옮기는 경우에는 상황에 따라 이동하는 원소 수에 비례하는 비용이 발생할 수 있다.

 

---

7. list::sort()

7-1. 왜 std::sort()를 사용할 수 없는가?

vector에서는 다음이 가능하다.

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

std::sort(
    Numbers.begin(),
    Numbers.end()
);

하지만 list에서는 사용할 수 없다.

std::list<int> Numbers = {
    4, 1, 3, 2
};

// 불가능
std::sort(
    Numbers.begin(),
    Numbers.end()
);

---

7-2. Iterator Category 차이

std::sort()는 Random Access Iterator를 요구한다.

즉:

It + N;
It - N;
It2 - It1;

같은 연산이 가능해야 한다.

vector의 Iterator는 이를 지원한다.

하지만 list는 Bidirectional Iterator만 제공한다.

++It;
--It;

만 가능하기 때문에 std::sort()의 요구조건을 만족하지 못한다.

---

7-3. list::sort()

대신 list 자체가 정렬 함수를 제공한다.

Numbers.sort();

내림차순도 가능하다.

Numbers.sort(
    std::greater<int>()
);

시간복잡도는:

O(N log N)

이다.

 

핵심은:

list라서 std::sort()를 못 쓰는 것이 아니라, std::sort()가 요구하는 Random Access Iterator를 list가 제공하지 않기 때문이다.

 

---

8. Big-O와 실제 성능은 다를 수 있다

8-1. list의 O(1) 삽입이 항상 빠른 것은 아니다

표만 보면:

vector 중간 삽입
O(N)

list 중간 삽입
O(1)

이므로 list가 훨씬 좋아 보인다.

 

하지만 현실에서는 반드시 그렇지 않다.

먼저 list의 O(1)은 삽입 위치 Iterator를 이미 알고 있을 때다.

 

삽입 위치를 먼저 찾는다면:

Search O(N)
+
Insert O(1)

이다.

그리고 실제 성능에는 Big-O 외에도 메모리 접근 방식이 큰 영향을 준다.

---

8-2. Cache Locality

vector는 원소가 연속되어 있다.

[A][B][C][D][E]

CPU가 A를 읽을 때 주변 데이터도 Cache Line 단위로 가져올 수 있다.

따라서 이후 B, C를 읽을 때 Cache Hit가 발생할 가능성이 높다.

 

반면 list는:

[A] ───→ [B] ───→ [C]

처럼 다음 Node가 메모리 어디에 존재할지 보장되지 않는다.

---

8-3. 시간 지역성과 공간 지역성

시간 지역성 — Temporal Locality

최근 사용한 데이터를 가까운 시간 안에 다시 사용할 가능성이 높다는 특성이다.

for (int i = 0; i < 1000; ++i)
{
    Sum += Player.Health;
}

같은 데이터를 반복적으로 사용한다.

 

공간 지역성 — Spatial Locality

특정 메모리에 접근했다면 주변 메모리에도 곧 접근할 가능성이 높다는 특성이다.

[A][B][C][D]
 ↑
A 접근 후 B, C 접근

vector 순회가 대표적이다.

list는 Node가 비연속적으로 존재할 수 있기 때문에 이 공간 지역성을 활용하기 상대적으로 어렵다.

---

8-4. Pointer Chasing

list를 순회하려면 계속 다음 Node의 Pointer를 따라가야 한다.

Node
 ↓
Next Pointer
 ↓
다른 메모리 위치
 ↓
Next Pointer
 ↓
다른 메모리 위치

이러한 접근을 Pointer Chasing이라고 한다.

Node가 캐시에 없다면 매번 메모리 접근 지연이 발생할 수 있다.

---

8-5. Node Allocation 비용

vector는 보통 하나의 연속된 저장 공간을 관리한다.

반면 list는 일반적으로 Node 단위의 메모리 할당이 필요하다.

따라서 다음과 같은 추가 비용이 발생할 수 있다.

Node Allocation
Deallocation
Allocator Metadata
Memory Fragmentation

결국:

실제 성능에서는 시간복잡도뿐 아니라 Cache Locality, Allocation 비용, 원소 크기, 접근 패턴까지 고려해야 한다.

 

---

9. std::forward_list

std::forward_list는:

Singly Linked List 기반의 Sequence Container다.

 

list는 양방향이다.

[A] ⇄ [B] ⇄ [C]

 

forward_list는 한 방향으로만 연결된다.

[A] → [B] → [C]

 

각 Node는 개념적으로:

Data
Next Pointer

만 가지고 있다.

따라서 list보다 연결 정보에 필요한 메모리 오버헤드를 줄일 수 있다.

---

9-1. list와 forward_list 비교

	std::list	std::forward_list
구조	Doubly Linked List	Singly Linked List
Node Pointer	Prev + Next	Next
Iterator	Bidirectional	Forward
++It	O	O
--It	O	X
push_front()	O(1)	O(1)
push_back()	O(1)	제공하지 않음 head만 관리하고 tail을 별도로 관리하지 않도록 설계됨
Random Access	지원하지 않음	지원하지 않음
메모리 오버헤드	상대적으로 큼	상대적으로 작음

---

9-2. insert_after() / erase_after()

forward_list는 이전 Node로 이동할 수 없다.

[A] → [B] → [C]
       ↑
       It

B 뒤에 X를 넣는 것은 쉽다.

[A] → [B] → [X] → [C]

 

하지만 B 앞에 삽입하려면 A의 Next를 수정해야 한다.

그런데 현재 B만 알고 있다면 이전 Node인 A를 바로 찾을 수 없다.

 

그래서:

insert_after();
erase_after();

인터페이스를 사용한다.

---

9-3. size()가 없다

std::forward_list에는 size() 멤버 함수가 없다.

원소 개수를 O(1)에 반환하려면 컨테이너가 별도의 원소 개수 상태를 유지해야 한다.

forward_list는 최소한의 메모리 오버헤드를 목표로 하기 때문에 이를 제공하지 않는다.

필요하다면:

std::distance(
    List.begin(),
    List.end()
);

로 계산할 수 있지만:

O(N)

이 필요하다.

 

---

10. vector vs list

10-1. 구조 및 시간복잡도 비교

	std::vector	std::list
내부 구조	동적 배열	양방향 연결 리스트
원소 저장	연속	비연속
Random Access	O(1)	지원하지 않음
n번째 원소 접근	O(1)	O(N)
Search	O(N)	O(N)
중간 삽입	O(N)	Iterator가 있다면 O(1)
중간 삭제	O(N)	Iterator가 있다면 O(1)
push_back()	Amortized O(1)	O(1)
push_front()	O(N)	O(1)

---

10-2. Iterator 안정성 비교

	vector	list
삽입	Reallocation/원소 이동으로 무효화 가능	기존 원소 유지
삭제	삭제 위치 이후 무효화	삭제된 원소만 무효화
Reallocation	발생 가능	없음

---

10-3. 메모리 및 캐시 특성

	vector	list
Cache Locality	좋음	일반적으로 좋지 않음
Pointer Chasing	없음	있음
원소별 Pointer	없음	Prev / Next
메모리 오버헤드	상대적으로 작음	큼
Allocation	연속 저장 공간 중심	Node 단위 할당

 

---

정리

std::list는 양방향 연결 리스트 기반의 Sequence Container다.

[A] ⇄ [B] ⇄ [C]

연속된 메모리를 사용하지 않기 때문에 Random Access는 지원하지 않지만, 삽입·삭제 위치 Iterator를 알고 있다면 Node의 연결 관계만 변경하여 O(1)에 처리할 수 있다.

또한 Reallocation이 없기 때문에 기존 Iterator와 Reference의 안정성이 높다는 특징이 있다.

 

반면:

Node Pointer 오버헤드
Pointer Chasing
낮은 공간 지역성
Node Allocation 비용

등으로 인해 실제 순회 성능은 vector보다 불리한 경우가 많다.

 

그래서 list는 Big-O만 보고 선택하는 자료구조가 아니라, Iterator 안정성이나 Node 단위 연결 작업이 실제 요구사항에 맞는지를 보고 선택하는 것이 중요하다.

 

forward_list는 여기서 Prev Pointer를 제거한 더 가벼운 단방향 연결 리스트다.

 

다음 글에서는 vector처럼 Random Access를 지원하면서도 앞과 뒤의 삽입·삭제를 효율적으로 수행하는 std::deque의 구조를 살펴본다.