[C++] STL list

C++ STL의 list는 이중 연결 리스트(doubly linked list)를 구현한 컨테이너이다.

기본 개념

std::list는 이중 연결 리스트를 기반으로 하며, 각 노드는 이전 노드와 다음 노드를 가리키는 포인터를 가지고 있어 리스트 내에서 양방향으로 이동이 가능하다는 특징이 있다.

빠른 삽입/삭제 (O(1))

list의 가장 큰 장점은 임의 위치에서의 삽입과 삭제가 매우 빠르다는 점이다. 예를 들어, 어떤 노드를 가리키는 반복자(iterator)만 알고 있다면, 해당 위치에 새 노드를 끼워 넣거나 제거하는 작업은 포인터 조작만으로 가능하므로 O(1)의 시간 복잡도를 가진다.

느린 임의 접근 (O(n))

반면, list는 임의 접근(random access)이 불가능하다. vector처럼 v[3]와 같이 인덱스로 접근하는 문법이 따로 없고 항상 반복자(iterator)를 사용해서 순차적으로 접근해야 한다.

list는 내부적으로 포인터를 기반으로 연결된 구조이기 때문에, 인덱스를 통해 바로 해당 위치에 접근할 수 없고, 앞에서부터 차례로 이동해야만 한다. 이로 인해 접근 시간은 O(n)의 시간 복잡도를 가진다.

헤더 및 선언

#include <list>

std::list<int> l; // int형을 저장하는 리스트

주요 멤버 함수

함수명	설명
push_back(val)	끝에 요소 추가
push_front(val)	앞에 요소 추가
pop_back()	끝 요소 제거
pop_front()	앞 요소 제거
insert(pos, val)	pos 앞에 val 삽입
erase(pos)	pos 위치 요소 삭제
clear()	모든 요소 제거
size()	요소 개수 반환
empty()	리스트가 비어 있는지 확인
front() / back()	첫 / 마지막 요소 반환
sort()	정렬 (<algorithm> 없이 사용 가능)
reverse()	역순 정렬
remove(val)	값이 val인 모든 요소 삭제

사용 예시

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> l = {1, 2, 3};
    list<int>::iterator it = l.begin(); // 첫 번째 요소를 가리킴
    it++; // 두 번째 요소를 가리킴(2)

    l.insert(it, 10); // 2 앞에 10 삽입 -> {1, 10, 2, 3}
    it = l.erase(it); // 2 삭제 -> {1, 10, 3}

    cout << *it << "\n"; // 3 출력

    for (it = l.begin(); it != l.end(); it++) {
        cout << *it << " ";
    } // 1 10 3 출력

    return 0;
}

🔽 출력 :

3
1 10 3

여기서 erase() 함수는 삭제한 다음 반복자의 위치를 반환한다. 이 반환값을 생성한 반복자에 재할당해줘야 해당 반복자를 계속 사용할 수 있다. 위 예제에서 it = l.erase(it); 이후에 it은 3을 가리키고 있는 상태이다.

for (it = l.begin(); it != l.end(); it++) {
    cout << *it << " ";
}

이 코드는 반복자(iterator)로 컨테이너를 순회할 때 쓰는 가장 기본적인 코드로, 컨테이너의 모든 요소를 방문할 수 있다.

for (auto it : l) {
    cout << it << " ";
}

간단하게 향상된 for 문으로 위와 같이 컨테이너의 요소를 방문할 수도 있다.

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> l;

    l.push_back(1);
    l.push_back(2);
    l.push_back(3);

    cout << "첫 번째 요소: " << l.front() << "\n";

    l.pop_back();

    cout << "마지막 요소: " << l.back() << "\n";

    l.push_front(10);

    cout << "리스트 요소: ";

    for (auto it : l) {
        cout << it << " ";
    }

    return 0;
}

🔽 출력 :

첫 번째 요소: 1
마지막 요소: 2
리스트 요소: 10 1 2

vector와의 차이점

항목	vector	list
내부 구조	동적 배열	이중 연결 리스트
임의 접근	빠름 (O(1))	느림 (O(n))
중간 삽입/삭제	느림 (O(n))	빠름 (O(1))
메모리 효율성	상대적으로 좋음	포인터 공간 추가로 비효율적
정렬	<algorithm> 필요	멤버 함수로 sort() 제공

마무리

• 삽입/삭제 연산이 많고 순차 접근 위주, 중간 요소를 자주 삽입/삭제하는 상황에 적합
• 임의 접근은 느림
• 메모리 낭비가 있을 수 있음 (포인터 2개 저장)