[1. 리스트, 스택, 큐] C++ std::list

std::list

---

std::forward_list는 아주 기본적인 형태로 구현된 연결 리스트이다. 

리스트 끝에 원소 추가, 역방향 이동, 리스트 크리 반환 등의 기능은 제공하지 않는다. (메모리와 성능 유지를 위해)

forward_list는 반복자의 기능도 적다.

이러한 forward_list의 단점을 보완하기 위해 C++ 은 std::list를 제공한다.

std::list는 양쪽 방향으로 연결된 이중 연결 리스트(doubly-linked list) 구조로 되어 있어 더 많은 기능을 제공하지만 메모리는 조금 더 사용한다.

struct doubly_linked_list_node{
    int data;
    doubly_linked_list_node* next;
    doubly_linked_list_node* prev;
};

prev 포인터가 있기 때문에 역방향으로 이동할 수 있으며 맨 마지막 원소와 리스트 크기를 따로 저장하여 push_back, size 등의 함수를 지원한다.

 

멤버 함수

대부분은 forward_list의 함수와 같거나 유사하다.

after로 끝나는 forward_list의 함수들을 _after로 끝나지 않도록 바뀐다. 

push_back(), emplace_back(), pop_back() 등의 함수를 제공한다.

아래와 같이 예제 코드를 작성할 수 있다.

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

int main(){
    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}
    cout << "삽입 & 삭제 후 리스트: ";
    for(auto i : list1)
        cout << i << " ";
}

forward_list와 비교했을 때, push_front(), insert(), pop_front(), erase()의 함수 시간 복잡도는 서로 같지만, list에서는 더 많은 연산이 필요하다. list는 두 개의 포인터를 갖기 때문에 각 연산마다 두 개의 포인터를 관리해야 하기 때문이다.

 

양방향 반복자 (bidirectional iterators)

std::list에서는 양방향 반복자를 사용한다. 따라서 std::forward_list 보다는 제약이 적다. (역방향으로의 이동이 가능하다.) 하지만 임의 접근 반복자보다는 유연하지 않아 특정 위치로 한 번에 이동하는 것은 불가능하다. 

따라서 양방향 반복자로 특정 위치로 이동하는 작업은 선형 시간 복잡도를 갖는다.

 

반복자 무효화

vector::push_back() 과 같은 함수에서는 경우에 따라 새로 메모리 공간을 할당하고 기존의 모든 원소를 새 메모리 공간으로 복사하는 동작이 발생한다. 이 때 기존에 사용하던 반복자, 포인터, 참조 등은 모두 무효화된다. 이런 식으로 발생하는 반복자 무효화는 std::list에서는 발생하지 않는다.