📌 std::list
: 양쪽 방향으로 연결된 리스트
: 이중 연결 리스트(double-linked list) 구조
✔️
std::forward_list에 비해 메모리를 조금 더 사용한다!
1. 노드 기본 형태
struct doubly_linked_list_node
{
int data;
doubly_linked_list_node* next;
doubly_linked_list_node* prev;
};✔️ 이중 연결 리스트 노드는 이전 노드를 가리키는 포인터가 있다.
-> 포인터를 이용하여 역방향으로 이동할 수 있으며, 맨 마지막 원소와 리스트 크기를 따로 저장하여 빠른 pushback() 또는 size() 함수를 지원할 수 있다.
✔️ 템플릿 매개변수로 사용자 정의 할당자를 지정할 수 있다.
2. std::list 멤버 함수
✔️ 대부분의 함수가 std::forward_list와 같거나 유사하지만, 약간의 차이가 있다.
1) std::forward_list에서 _after로 끝나는 함수는 std::list에서 _after로 끝나지 않는 형태로 바뀐다.
-> insert_after()와 emplace_after() 함수는 insert()와 emplace() 함수와 대응된다.
2) std::list에서는 원소 이동을 역방향으로도 할 수 있으므로 원소 삽입을 위해 특정 원소의 이전 원소 반복자를 제공하지 않아도 된다. (대신 정확하게 새로운 원소가 삽입될 위치를 가리키는 반복자를 함수 인자로 전달한다.)
3) std::list는 빠른 push_back(), emplace_back(), pop_back() 함수를 제공한다.
<원소 삽입 및 삭제를 위한 코드 작성 방법>
#include <iostream>
#include <list>
int main()
{
//리스트 생성 및 새로운 원소 추가
std::list<int〉 list1 = {1, 2, 3, 4, 5};
list1.push_back(6); // {1, 2, 3, 4, 5, 6}
list1.insert(next(list1.begin()), 0); // {1, 0, 2, 3, 4, 5, 6}
list1.insert(list1.end(), 7); // {1, 0, 2, 3, 4, 5, 6, 7}
//리스트 맨 뒤 원소 제거
list1.pop_back(); // {1, 0, 2, 3, 4, 5, 6}
std::cout << "삽입 & 삭제 후 리스트: ";
for (auto i : list1)
std::cout << i << " ";
}✔️ 출력 결과
- 삽입 & 삭제 후 리스트: 1 0 2 3 4 5 6
❗️ 이중 연결 리스트에서 포인터를 관리하기 위해서는 단일 연결 리스트보다 대략 두 배의 연산을 수행해야 한다.
✔️
std::forward_list와std::list의 push_front(), insert(), pop_front(), erase() 함수 시간 복잡도는 서로 같지만, 실제로는std::list에서 좀 더 많은 연산이 필요하다.
-> 이유 :std::list는 각각의 노드에 두 개의 포인터를 가지고 있고, 삽입 또는 삭제 연산 시 두 개의 포인터를 관리해야 하기 때문이다.
2. 양방향 반복자
- std::list의 반복자는 배열 기반의 임의 접근 반복자와 std::forward_list 기반의 순방향 반복자 중간 정도의 유연성을 가지고 있다.
📌 백준 문제 풀이
