std::list

코딩 테스트를 위한 자료 구조와 알고리즘 with C++

 

 

std::forward_list의 단점

• 성능상 이유로 마지막에 원소 추가, 역방향 진행, 크기 반환 등을 지원하지 않는다.
• 빠른 원소 삽입에 적합한 컨테이너는 아니다.

 

std::list

• STL에서 제공하는 이중 연결 리스트 컨테이너이다.
• 양방향 반복자를 제공한다.
• 마지막에 원소 추가, 크기 반환을 지원한다.

 

std::list의 성능

• 삽입, 삭제 연산시 2개의 포인터를 처리해야 하므로 std::forward_list보다는 시간이 좀 더 걸린다.
• 크기를 저장하므로 크기 반환은 O(1)에 수행된다.
• 원소의 삽입 삭제는 O(1)에 수행된다.
  (삽입할 위치 전의 반복자를 알고 있다는 전제 하에)
• 특정 위치의 원소를 참조하기 위해서는 반복자를 직접 진행해야 하며 O(n) 복잡도를 갖는다.

 

std::list의 원소 삽입 의사 코드

insert(it, val):
    node = new Node {val, null, null}
    
    node->next = it
    node->prev = it->prev
    it->prev->next = node
    it->prev = node

 

#include <iostream>
#include <list>

using namespace std;

ostream& operator<<(ostream& os, const list<int>& lst)
{
    for (int e : lst)
        cout << e << ' ';

    return os;
}

void main()
{
    list<int> lst = {1, 2, 3, 4, 5};

    // 맨 앞에 0 추가
    lst.emplace_front(0);
    cout << lst << endl;

    // 맨 뒤에 6 추가
    lst.emplace_back(6);
    cout << lst << endl;

    // 맨 뒤에 7 추가
    lst.emplace(lst.end(), 7);
    cout << lst << endl;

    // 2번째 위치에 8 추가
    lst.emplace(next(lst.begin()), 8);
    cout << lst << endl;

    // 맨 앞 원소 삭제
    lst.pop_front();
    cout << lst << endl;

    // 맨 뒤 원소 삭제
    lst.pop_back();
    cout << lst << endl;

    // 1번째 ~ 3번째 원소 삭제
    // lst.begin() + 3은 지원하지 않는다.
    lst.erase(lst.begin(), next(lst.begin(), 3));
    cout << lst << endl;

    // 첫 번째 원소
    cout << lst.front() << " " << *lst.begin() << endl;

    // 마지막 원소
    cout << lst.back() << " " << *lst.rbegin() << endl;

    cout << "크기: " << lst.size() << endl;
}

 

출력

0 1 2 3 4 5 
0 1 2 3 4 5 6 
0 1 2 3 4 5 6 7 
0 8 1 2 3 4 5 6 7 
8 1 2 3 4 5 6 7 
8 1 2 3 4 5 6 
3 4 5 6 
3 3
6 6
크기: 4