[자료구조]0X04연결리스트

.·2023년 1월 12일

연결리스트

: 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장

1. 성질

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

배열 vs 연결 리스트

임의의 위치에 원소 추가/제거 구현

#include <iostream>
using namespace std;

const int MX = 1000005;
int dat[MX], pre[MX], nxt[MX];
int unused = 1; // 메모리 주소

void insert(int addr, int num){ // addr 뒤에 원소를 추가
    dat[unused] = num;
    pre[unused] = addr;
    nxt[unused] = nxt[addr];
    if(nxt[addr] != -1) pre[nxt[addr]] = unused; // 리스트의 마지막에 원소를 추가할 떄 예외처리 해줘야 함
    nxt[addr] = unused;
    unused++;
}

void erase(int addr){
    nxt[pre[addr]] = nxt[addr];
    if(nxt[addr] != -1) pre[nxt[addr]] = pre[addr]; // 리스트의 마지막 원소 제거할 때 예외처리 해줘야 함
}

void traverse(){
    int cur = nxt[0];
    while(cur != -1){
        cout << dat[cur] << ' ';
        cur = nxt[cur];
    }
    cout << "\n\n";
}

2. 종류

단일 연결 리스트: 각 원소가 자신의 다음 원소의 주소를 들고 있음
이중 연결 리스트: 각 원소가 이전 원소와 다음 원소의 주소를 들고 있음
원형 연결 리스트: 끝이 처음과 연결(단일/이중 모두 가능)

3. STL list

push_back, pop_back, push_front, pop_front는 모두 O(1)
iterator가 주소 역할 ex)iterator iter = list.begin()

주의
1. erase은 제거한 다음 위치의 원소를 반환함
2. insert(cur, data)은 cur앞에 추가함 => dummy node가 마지막에 있음

4. 연습문제

백준 1406 에디터
https://www.acmicpc.net/problem/1406

i) STL 풀이
list의 dummy node가 마지막에 있음을 확인

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    list<char> l;
    string s;
    int m;
    char cmd;
    cin >> s >> m;
    for(char c:s) {
        l.push_back(c);
    }
    auto iter = l.end();

    for(int i=0; i<m; i++) {
        cin >> cmd;
        if(cmd == 'P') {
            char a;
            cin >> a;
            l.insert(iter, a); // iter앞에 원소를 추가함
        }
        else if(cmd == 'L') {
            if(iter != l.begin())   iter--;
        }
        else if(cmd == 'D') {
            if(iter != l.end()) iter++;
        }
        else {
            if(iter != l.begin()) {
                iter--;
                iter = l.erase(iter);
            }
        }
    }
    for(auto e:l) { // 연결리스트 출력
        cout << e;
    }
}

ii) 직접 연결리스트 구현하여 풀이
list의 dummy node가 처음에 있음을 확인

#include <iostream>
using namespace std;

const int MX = 1000005;
char dat[MX];
int pre[MX];
int nxt[MX];
int unused = 1;

void insert(int addr, int num) { // addr뒤에 원소를 추가함 => dummy node가 맨 앞에 있음
  dat[unused] = num;
  pre[unused] = addr;
  nxt[unused] = nxt[addr];
  if(nxt[addr] != -1) pre[nxt[addr]] = unused;
  nxt[addr] = unused;
  unused++;
}

void erase(int addr) {
  nxt[pre[addr]] = nxt[addr];
  if(nxt[addr] != -1) pre[nxt[addr]] = pre[addr];
}

void traverse() {
  int cur = nxt[0];
  while(cur != -1) {
      cout << dat[cur];
      cur = nxt[cur];
  }
  cout << "\n";
}

int main() {
  ios::sync_with_stdio(0);
  cin.fill(0);

  fill(pre, pre+MX, -1);
  fill(nxt, nxt+MX, -1);
  string s;
  int m;
  cin >> s >> m;
  int cur = 0;
  for(auto c : s) {
      insert(cur, c);
      cur++;
  }

  while(m--) {
      char op;
      cin >> op;
      if(op == 'P') {
          char add;
          cin >> add;
          insert(cur, add);
          cur = nxt[cur];
      }
      else if(op == 'L') {
          if(pre[cur] != -1)  cur = pre[cur];
      }
      else if(op == 'D') {
          if(nxt[cur] != -1)  cur = nxt[cur];
      }
      else {
          if(cur != 0) {
              erase(cur);
              cur = pre[cur];
          }
      }
  }
  traverse();
}