[C++] STL 자료구조: List

list는 양방향 연결 리스트(doubly-linked list)로 구현되어있는 자료구조로 임의 위치의 삽입과 삭제를 O(1)에 지원한다.

<성질>

- 이전 노드와 다음 노드에 대한 링크를 각 노드마다 저장하고 있다.

list의 각 노드들은 메모리 상에서 떨어진 위치에 존재하며 한 노드를 삽입하거나 삭제해도 다른 노드들의 위치에는 영향이 없다.

삽입, 삭제 시 변화하는 값은 오직 이전 노드와 다음 노드를 가리키는 링크들로, 한 노드를 삽입 또는 삭제하는 경우 자신과 그 주변 노드들의 링크만 수정하면 된다. 이를 이용해 list는 원소의 삽입, 삭제가 이루어진다.

노드들이 메모리 상에 인접해있지 않다는 성질때문에 list는 i번째 원소에 바로 접근하는 연산을 지원하지 않는다.  원소의 삽입, 삭제는 해당 원소의 위치를 알고 있을 때만 O(1)이며, 만약 위치를 모른다면 i번의 증감 연산을 통해 노드를 찾아줘야 한다.

​

-임의 위치의 원소에 []연산자를 이용해 접근할 수 없으며 각 원소에 접근할 땐 앞에서부터 하나씩 탐색해야 한다는 단점이 있다.

따라서 list는 1)중간 위치에서 삽입, 삭제가 빈번하게 일어나고, 2)데이터에 랜덤하게 접근하는 경우가 많지 않을 때 사용되는데, 이러한 문제가 많지 않아서 자주 사용되진 않는다.

+) 만약 다음 원소쪽으로의 이동, 삽입, 삭제 연산만 필요하다면 forward_list를 사용할 수 있다. forward_list는 singly-linked list로 구현되어서 메모리와 속도 면에서 장점을 가지지만 잘 사용되지 않는다.

 

<생성자>

1. list<int> L; : 비어있는 리스트 생성

2. list<int> L(n); 또는 list<int> L(n, val); : val이 n개 채워진 리스트 생성

3. list<int> L{ 1, 2, 3 }; 또는 list<int> L = { 1, 2, 3 }; : 리스트 초기화

 

<멤버 함수>

int main() {

fastio;

list<int> L = { 1, 2, 3 }; // 초기화

auto it = next(L.begin()); // (*it == 2); next()는 반복자(iterator)를 이동시키는 함수 / begin부터 다음 원소를 가리키는 반복자 반환

auto it2 = L.insert(it, 10); // L = { 1, 10, 2, 3 }, *it2 == 10, *it == 2

 

it = prev(it); // *it == 10

it = L.erase(it); // L = { 1, 2, 3 }, *it == 2

}

 

- push_back : 마지막 위치에 원소를 삽입. O(1)

- push_front : 시작 위치에 원소를 삽입. O(1)

- pop_back : 마지막 위치의 원소를 삭제. O(1)

- pop_front : 시작 위치의 원소를 삭제. O(1)

- insert : 매개변수로 받은 iterator 위치의 앞에 원소를 삽입. O(1)

- erase : 매개변수로 받은 iterator 위치의 원소를 삭제 후 원래 위치의 다음 원소의 iterator를 반환. O(1)

​

- size : list의 크기를 size_t 자료형으로 반환.

- empty : list가 비어있는지 여부를 bool 자료형으로 반환.

- resize : list의 크기를 변경.

- clear : list의 모든 원소를 삭제.

​

- begin : list의 첫 번째 원소를 가리키는 iterator를 반환.

- end : list의 마지막 원소의 다음 칸을 가리키는 iterator를 반환.

- rbegin : begin의 reverse_iterator 버전.

- rend : end의 reverse_iterator 버전.

- front : list의 첫 번째 원소를 reference로 반환. O(1)

- back : list의 마지막 원소를 reference로 반환. O(1)

​

- sort : list 내의 원소를 정렬. O(nlogn)

 

insert(it, val): it의 앞에 val을 삽입하며 it은 원래 원소를 가리키고, insert는 새로 삽입한 원소를 가리키는 iterator를 반환

예를 들어"ab"에서 it이 'b'를 가리킬 때 auto it2 = L.insert(it, 'c')를 한 경우 "acb"가 되며 it은 'b'를 가리키고, it2는 'c'를 가리킨다

​

erase(it): it가 가리키는 원소를 삭제하며 그 다음 위치의 원소를 가리키는 iterator를 반환한다.

예를 들어 "abc"에서 it이 'b'를 가리킬 때 auto it2 = L.erase(it)을 한 경우 "ac"가 되며 it2는 'c'를 가리킨다.

이때 it는 무효화(invalidated)되기 때문에 *it, it++등으로 사용하면 UB(undefined behavior)를 발생시키며 일반적으로

it = L.erase(it)으로 사용한다.

 

int main() {

fastio;

list<int> L = { 1, 2, 3, 4 }; // initializer_list

 

auto it = L.begin(); // *it == 1

advance(it, 3); // *it == 4 (오른쪽 3)

advance(it, -2); // *it == 2 (왼쪽 2)

it = prev(it); // *it == 1 ( 왼쪽 1)

it = next(it); // *it == 2 (오른쪽 2)

 

cout << "dist : " << distance(L.begin(), it) << '\n'; // 1 (begin부터 2까지)

cout << "dist : " << distance(it, L.begin()) << '\n'; // UB (2가 더 오른쪽에 있다) == 항상 양수만 생각

}

 

list의 iterator는 bidirectional iterator로 L.begin() + 3 등의 + 연산을 지원하지 않는다.

따라서 it을 이동시키기 위해선 it++ 또는 it--를 사용해야 하는데, 이때 증감연산자 대신 prev, next 함수를 사용하면 편하다.

만약 여러 칸을 이동해야 한다면 advance를 사용할 수 있다. 이때 advance의 시간복잡도는 O(n)이다.

한칸 씩 이동 시 it++, it--이 좋고 여러 칸 이동하면 advance를 이용하자

​

마찬가지로 list의 iterator는 iterator간의 - 연산을 지원하지 않아서 it - v.begin() 등으로 인덱스를 구할 수 없다.

이때는 O(n)의 시간복잡도를 갖는 distance를 이용하면 된다.

 

int main() {

fastio;

list<int> L = { 3, 1, 2 };

L.sort();

for (auto& i : L) cout << i << ' '; cout << '\n'; // 1 2 3

L.sort(greater<>{}); // 내림차순 정렬

for (auto& i : L) cout << i << ' '; cout << '\n'; // 3 2 1

}

list는 random access iterator가 없어서 sort 대신 L.sort()를 사용해야 한다.

L.sort는 첫 번째 인자로 cmp(정렬 순서를 결정하는 비교 함수(comparison function))를 넣어줄 수 있으며 생략하는 경우 less<>{}가 default parameter로 들어간다. 이는 오름차순 정렬이다.

L.sort는 merge sort로 구현되어있으며 시간복잡도는 O(nlogn)이다.

 

<백준>

1406번)

#include <bits/stdc++.h>

#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

int main(){

    fastio;

    string str;

    list<char> lst;

    cin>>str;

    for(int i=0; i<str.size(); i++){

        lst.push_back(str[i]);

    }

    int n;

    cin>>n;

    for(auto it=lst.end(); n--;){

        char a,x; cin>>a;

        if(a=='L'){ if (it!=lst.begin()) it--;}

        else if(a=='D') {if(it != lst.end()) it++;}

        else if(a=='B') {if(it != lst.begin()) it=lst.erase(prev(it));}

        else{cin>>x; lst.insert(it, x);}

    }

    cout<<string(lst.begin(), lst.end())<<'\n';

}

5397번)

int main(){
   fastio;
    int num;
    cin>>num;
    while(num--){
        string a;
        cin>>a;
        list <char> psswrd;
        auto it = psswrd.end();
for (const auto& c : a) {
if (c == '<') { if (it != psswrd.begin()) it--; }
else if (c == '>') { if (it != psswrd.end()) it++; }
else if (c == '-') { if (it != psswrd.begin()) it = psswrd.erase(prev(it)); }
else psswrd.insert(it, c);
}
        cout<<string(psswrd.begin(), psswrd.end())<<'\n';
    }
}

for (const auto& c: a)  auto는 컴파일러에게 변수의 형식을 추론하도록 하는 키워드이다. 상수 참조(const &c)는 변수의 값이 변경되지 않고, 해당 변수를 다른 곳에서 참조할 수 있음을 나타낸다.  주로 함수 매개변수로 전달하거나, 읽기 전용으로 변수를 사용할 때 사용된다. 여기에서 const auto& c는 반복할 때마다 c가 a의 요소를 참조하도록 한다.

 

2346번)

list를 연습하는 문제이지만 deque로 푸는게 더 나은 문제인 거 같아서 구글링해서 deque로 풀었다.

 

#include <bits/stdc++.h>

#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

 

 

int main(){

    fastio;

    int n;

    deque <pair<int, int>> dq;

    cin>>n;

    for(int i=0; i<n; i++){

        int tmp;

        cin>>tmp;

        dq.push_back(make_pair(tmp, i+1));

//string 으로 1~n을 따로 저장하는 것보다 낫다

//make_pair는 #include utility에 있는 기능

    }

    while(true){

        int cnt = dq.front().first;

        cout<<dq.front().second<<" ";

        dq.pop_front();

        if(dq.empty()) break;

        if(cnt>0){

            for(int i=0; i<cnt-1; i++){

                dq.push_back(dq.front());

                dq.pop_front();

            }

        }

        else{

            for(int i=cnt; i<0; i++){

                dq.push_front(dq.back());

                dq.pop_back();

            }

        }

    }

}