[자료구조] C++ Container Library : Sequential Containers - list

C++ 표준 라이브러리(STL)의 일부인 컨테이너 라이브러리 중 순차 컨테이너(Sequential Containers)에 해당하는 std::list에 대해 정리한 글입니다.

---

📚 std::list

📖 std::list

• 이중 연결 리스트(Doubly Linked List) 구조를 기반으로 한 컨테이너
• 모든 원소가 서로 앞뒤로 연결되어 있음
• 중간 삽입 및 삭제가 매우 효율적으로 동작

std::vector, std::deque와 가장 큰 차이점
➡️ std::list는 메모리가 연속적이지 않고, 각 원소가 다음 혹은 이전 원소를 가리키는 포인터를 가지고 있다.

📌 std::list 사용 예시 코드

#include <list>    // 필수 헤더
#include <iostream>
using namespace std;

int main() {
    list<int> lst;

    lst.push_back(1);
    lst.push_front(0);
    lst.push_back(2);

    for (list<int>::iterator it = lst.begin(); it != lst.end(); ++it) {
        cout << *it << " ";
    }
}

• <list> 헤더를 추가해서 사용 가능

---

📖 std::list의 내부 구조

std::link의 내부 구조

구성 요소	설명
노드 (Node)	데이터 + 이전 노드 포인터 + 다음 노드 포인터
head	첫 번째 노드를 가리킨다.
tail	마지막 노드를 가리킨다.

• 각 원소마다 메모리 주소가 따로 존재
• 중간 삽입이나 삭제할 때 포인터만 바꿔주면 됨

📌 노드(Node) 구조

struct Node {
    Node* prev;   // 이전 노드 포인터
    Node* next;   // 다음 노드 포인터
    T data;       // 실제 데이터
};

• 하나의 노드는 이전 노드 포인터(Node* prev), 다음 노드 포인터(Node* next), 그리고 실제 데이터(T data)를 포함

---

📖 std::list의 시간 복잡도

• push_front() / push_back() : $ O(1) $
• pop_front() / pop_back() : $ O(1) $
• 중간 삽입 및 삭제 : $ O(1) $
• 임의 접근 (Random Access, operator[]) : 불가능 ( $ O(N) $으로 느림 )

✔️ 중간 삽입 및 삭제는 매우 빠름 (상수 시간복잡도)

❌ 임의 접근(Random Acceess) 불가 ➡️ 배열과 같이 [i]로 접근 불가

---

📖 std::list의 주요 함수

• push_front(val) / push_back(val) : 맨 앞 / 맨 뒤에 원소(val) 추가
• pop_front() / pop_back() : 맨 앞 / 맨 뒤 원소 삭제
• insert(iterator, val) : iterator 위치에 원소(val) 삽입
• erase(iterator) : iterator 위치의 원소 삭제
• size() : 원소 개수 반환
• clear() : 모든 원소 삭제

---

📖 std::list 사용 시 주의할 점

• 임의 접근이 불가능
• 포인터 기반이라 메모리 공간 낭비가 발생할 수 있음 (next / prev 포인터 때문)
• 캐시 효율이 떨어질 수 있음 ➡️ vector는 메모리 연속이라 캐시 히트율이 좋지만, list는 분산 저장되어 캐시 효율이 저하될 수 있음

캐시 히트율 (Cache Hit Rate)
📌 CPU가 요청한 데이터가 Cach 안에 이미 존재하는 비율을 의미
✅ 캐시 히트 : Cache 안에 데이터가 존재 (빠른 접근 가능)
✅ 캐시 미스 : Cache 안에 데이터가 없음 (RAM까지 느리게 접근)
➡️ 캐시 히트율이 높은 프로그램이 빠른 프로그램

📌 std::list는 왜 캐시 히트율이 낮을까?

• vector는 메모리가 연속적 ➡️ 원소들을 읽을 때 Cache Line 하나에 다 들어올 수 있음 ➡️ 빠름
• list는 원소가 각 메모리에 흩어져 있음 ➡️ 원소를 읽을 때마다 새로운 메모리 접근이 필요 ➡️ Cache Line 재사용 불가 ➡️ 느림

➡️ 즉, list는 캐시 미스가 많이 나오기 때문에 CPU가 매번 메모리(RAM)에 접근해야 함 (캐시 히트율이 낮음)

---

📚 std::forward_list

📖 std::forward_list

➡️ C++11부터 새롭게 추가된 컨테이너

• 단일 연결 리스트(Singly Linked List)를 기반으로 하는 C++ 표준 컨테이너
• std::list보다 가벼운 구조를 가짐
• 메모리 사용량을 줄이기 위해 만들어졌으며, 이전 노드 포인터가 없어 뒤로 이동할 수 없다.

📌 std::forward_list 사용 예시 코드

#include <forward_list>   // 필수 헤더
#include <iostream>
using namespace std;

int main() {
    forward_list<int> fl = {1, 2, 3};

    fl.push_front(0);  // 앞에 삽입

    auto it = fl.begin();  
    ++it;  // 1 가리킴
    fl.insert_after(it, 5);  // 1 다음에 5 삽입

    for (int val : fl) {
        cout << val << " ";
    }
    
    return 0;
}

• <forward_list> 헤더를 추가하여 사용 가능

---

📖 std::list vs std::forward_list

항목	list	forward_list
구조	이중 연결 리스트	단일 연결 리스트
이동	양방향 (앞 뒤 이동 가능)	단방향 (뒤로만 이동 가능)
메모리	next + prev 포인터 필요	next 포인터 필요
삽입 및 삭제	$ O(1) $ (앞 뒤 이동 가능)	$ O(1) $ (뒤로만 이동 가능)
임의 접근	불가능	불가능
메모리 사용량	더 많음	더 적음

• forward_list는 메모리를 절약하고 싶을 때 유리
• 양방향 이동은 불가능

---

📖 std::forward_list의 내부 구조

std::forward_list의 내부 구조

• 각 노드(Node)마다 메모리 주소가 따로 존재
• 중간 삽입 또는 삭제하는 경우, 연결된 노드(Node)의 포인터만 바꿔주면 됨
• std::list와 달리, 이전 노드 포인터를 저장하는 포인터가 존재하지 않음

📌 노드(Node) 구조

struct Node {
    Node* next;   // 다음 노드 포인터
    T data;       // 실제 데이터
};

• 하나의 노드(Node)는 다음 노드 포인터(Node* next)와 실제 데이터(T data)를 가지는 구조체
• 이전 노드 포인터가 없기 때문에 항상 앞에서 뒤로만 이동할 수 있음

---

📖 std::forward_list의 시간 복잡도

• push_front() : $ O(1) $
• pop_front() : $ O(1) $
• insert_after() : $ O(1) $
• erase_after() : $ O(1) $
• 임의 접근 : 불가능 (순차 접근, $ O(N) $)

---

📖 foward_list의 주요 함수

• push_front(val) : 맨 앞에 원소(val) 삽입
• pop_front() : 맨 앞 원소 삭제
• insert_after(iterator, val) : iterator 다음 위치에 원소(val) 삽입
• earse_after(iterator) : iterator 다음 원소 삭제
• before_begin() : 첫 원소 앞의 "가상 위치"를 가리키는 특수 iterator

📌 함수 사용 시 주의사항

• insert_after()와 earse_after() 함수는 인자로 넘겨준 iterator 다음 위치에 있는 원소(노드)에 대해 작업이 수행

➡️ std::forward_list는 이전 노드에 대한 포인터가 없기 때문에 현재 위치에 삽입 및 삭제가 불가능하다.

---

📖 forward_list 사용 시 주의할 점

• 역방향 이동 불가능
• 중간 삽입 및 삭제 시 현재 위치 바로 뒤만 조작 가능
• front 삽입 / 삭제를 매우 빠르게 해야하는 경우 적합
• size() 함수가 없음 ➡️ 크기를 알기 위해서는 순회가 필요 ➡️ std::distance(begin(), end())로 크기를 따로 구해야 함

---