연결 리스트(list) in C++

문제

https://www.acmicpc.net/problem/5397

코드

#include <bits/stdc++.h>

using namespace std;

int n;
list<char> link_l;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("input.txt", "rt", stdin);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        string in;
        cin >> in;
        auto it = link_l.begin();
        for (auto ch: in) {
            if (ch == '<') {
                if (it != link_l.begin()) it--;
            }
            else if (ch == '>') {
                if (it != link_l.end()) it++;
            }
            else if (ch == '-') {
                if (it != link_l.begin()) {
                    auto temp = it;
                    temp--;
                    link_l.erase(temp);
                }
            }
            else {
                link_l.insert(it, ch);
            }
        }
        for (auto ch : link_l) {
            cout << ch;
        }
        cout << '\n';
        link_l.clear();
    }

    return 0;
}

• 연결리스트의 삽입/삭제 시간 복잡도는 O(1)으로, 배열의 삽입/삭제 시간 복잡도인 O(N)보다 훨씬 짧다.
• list<char> link_l : 링크드리스트 선언
• link_l.begin() : 연결 리스트의 시작 부분
• link_l.end() : 연결 리스트의 끝 부분
• link_l.insert(it, ch) : it이 가리키는 부분에, ch를 삽입
• link_l.erase(temp) : temp가 가리키는 부분을 삭제
  ex) 출력
  해당 문제 페이지에서의, 입력예시1에 대한 출력 결과