연결 리스트

연결 리스트

원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조, 원소들은 이곳 저곳에 흩어져 있음

 

성질

• k번째 원소를 확인/변경하기 위해 O(k) 필요
• 임의의 위치에 원소를 추가/제거는 O(1)
• 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당 다소 쉬움

 

 

연결 리스트의 종류

 

단일 - 각 원소가 자신의 다음 원소의 주소

이중 - 각 원소가 자신의 이전 원소와 다음 원소의 주소 list

원형 - 끝과 처음 연결

 

 

배열 vs 연결리스트

 

 

 

 

list

#include <bits/stdc++.h>
using namespace std;

int main(void) {
  list<int> L = {1,2}; // 1 2
  list<int>::iterator t = L.begin(); // t는 1을 가리키는 중
  L.push_front(10); // 10 1 2
  cout << *t << '\n'; // t가 가리키는 값 = 1을 출력
  L.push_back(5); // 10 1 2 5
  L.insert(t, 6); // t가 가리키는 곳 앞에 6을 삽입, 10 6 1 2 5
  t++; // t를 1칸 앞으로 전진, 현재 t가 가리키는 값은 2
  t = L.erase(t); // t가 가리키는 값을 제거, 그 다음 원소인 5의 위치를 반환
                  // 10 6 1 5, t가 가리키는 값은 5
  cout << *t << '\n'; // 5
  for(auto i : L) cout << i << ' ';
  cout << '\n';
  for(list<int>::iterator it = L.begin(); it != L.end(); it++)
    cout << *it << ' ';
}

 

 

백준 1406번 (에디터)

#include <bits/stdc++.h>

using namespace std;



int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    list<char> l;
    string s;
    cin>>s;
    for(auto st : s){
        l.push_back(st);
    }
    int M;
    cin>>M;
    auto idx = l.end();
    char cmd;
    char addChar;
    for(int i=0;i<M;i++){
        cin>>cmd;
        switch (cmd) {
            case 'L':
                if(idx!=l.begin()){
                    idx--;
                }
                break;
            case 'D':
                if(idx!=l.end()){
                    idx++;
                }
                break;
            case 'B':
                if(idx!=l.begin()){
                    idx--;
                    idx = l.erase(idx);
                }
                break;
            case 'P':
                cin>>addChar;
                l.insert(idx, addChar);
                break;

        }
    }
    for(char c: l){
        cout<<c;
    }
    return 0;
}

 

 

 

손코딩 문제

시작점 저장해뒀다가 동일한 노드가 나올때까지 계속 다음 노드로

 

 

 

한 칸씩 가는 커서와 두 칸씩 가는 커서를 동일한 시작점에서 출발시키면 사이클이 있을 경우 두 커서 반드시 만남.

만약 사이클 없으면 두 커서는 만나지 못하고 연결 리스트에 끝에 도달

 

 

참고 - https://blog.encrypted.gg/