std::list

list의 본질

• std::list는 양방향 연결 리스트입니다.
• 원소는 연속 메모리가 아니라 노드로 흩어져 있고, 포인터로 연결됩니다.
• 앞/뒤 삽입(push_front, push_back)은 O(1)입니다.
• reserve/capacity 개념이 없습니다.

---

vector vs list 핵심 비교

항목	vector	list
메모리 구조	연속 메모리	노드 연결
임의 접근 v[i]	O(1)	미지원 (O(N) 이동 필요)
중간 삽입/삭제	O(N) (원소 이동)	위치를 알고 있으면 O(1)
캐시 친화성	매우 좋음	상대적으로 불리
이터레이터 안정성	재할당/중간 수정에 취약	삭제된 원소 외 대체로 안정적

vector vs list 구조 비교

[ vector ]  연속 메모리, 인덱스 O(1) 접근
  ┌───┬───┬───┬───┬───┐
  │ 0 │ 1 │ 2 │ 3 │ 4 │  v[2] → 바로 접근
  └───┴───┴───┴───┴───┘

[ list ]  노드 연결, N번째 접근 O(N)
  head → [10]↔[20]↔[30]↔[40]↔[50] → tail
           3번째 접근 = next 3번 따라가야 함

---

시간 복잡도 감각

연산	복잡도	비고
push_front, push_back	O(1)	앞/뒤 삽입
insert(it), erase(it)	O(1)	해당 위치(it)를 이미 알고 있을 때
find, count	O(N)	순차 탐색
sort() (멤버 함수)	O(N log N)	list 전용 정렬
N번째 접근	O(N)	operator[] 미지원

---

알고리즘 사용 시 주의점

list<int> lst{4, 1, 3, 2};

// std::sort(lst.begin(), lst.end()); // X: RandomAccessIterator 필요
lst.sort(); // O(N log N), list 전용 멤버 정렬

// binary_search는 사용 가능하지만(list 이터레이터는 bidirectional)
// 이동 비용 때문에 실무 이점이 작습니다.
bool ok = binary_search(lst.begin(), lst.end(), 3); // 정렬되어 있다는 가정 필요

• list는 std::sort가 아니라 list::sort()를 사용해야 합니다.
• 탐색 성능이 중요하면 보통 vector + sort + binary_search 조합이 더 유리합니다.

---

list 전용으로 특히 유용한 기능

• splice: 노드를 다른 리스트로 복사 없이 이동
• merge: 정렬된 두 리스트 병합
• unique: 연속 중복 제거
• remove, remove_if: 조건 기반 삭제

list<int> a{1, 2, 3};
list<int> b{10, 20};

auto it = a.begin();
++it; // 2
b.splice(b.end(), a, it); // a의 2를 b 끝으로 이동

---

언제 list를 선택할까?

list가 유리한 경우:

• 순회 중 중간 삽입/삭제가 매우 빈번함
• 이터레이터/참조를 오래 들고 있어야 함(주소 안정성 중요)
• 인덱스 기반 접근이 거의 없음

vector가 유리한 경우:

• 조회/순회가 많고 성능이 중요함
• 임의 접근이 자주 필요함
• 특별한 이유가 없다면 기본 컨테이너로 vector를 우선 고려

---

C# 대응 + 체크 질문

• C++ list ≈ C# LinkedList
• C++ vector ≈ C# List

체크 질문 (스스로 답해보기)

• list에서 중간 삽입이 빠른데도 기본 컨테이너가 보통 vector인 이유는?
• list 정렬에 std::sort가 아닌 list::sort()를 써야 하는 이유는?
• "위치를 이미 알고 있을 때" insert/erase가 O(1)이라는 뜻을 설명할 수 있는가?

---