바킹독의 실전 알고리즘 : 연결 리스트

정의와 성질

연결 리스트의 성질

1. k번째 원소를 확인/변경하기 위해 O(k)
2. 이미 정한 위치에 추가 및 제거는 O(1)
3. 메모상에 연속된 데이터는 아니라서 cache hit rate는 낮고, 할당은 쉬움

연결리스트 종류

1. 단일 연결 리스트
2. 이중 연결 리스트 : 양방향으로 연결되어 있어서 이전 이후 원소 주소를 둘 다 들고 있다.
3. 원형 연결 리스트 : 사이클 돈다 생각하면 편하다.

기능과 구현

struct NODE {
    struct NODE *prev, *next;
    int data;
};

손코딩 문제 1

원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때 해당 List의 길이를 효율적으로 구하는 방법?

효율적으로 구하라 -> 시간복잡도와 공간복잡도를 생각해봐야 한다. 동일한 노드가 나올 때까지 계속 다음 노드로 가면 된다. O(1), O(N)

손코딩 문제 2

각 연결 포인터가 가리키는 주소가 같아지는 순간이 교차점인데 A,B의 길이가 다르니까 더 긴 길이를 차만큼 빼줘서 동시에 도달할 수 있도록 한다. O(A+B)로 전체 노드 길이를 알기위한 순회는 필요하다.

손코딩 문제 3

주어진 연결 리스트 안에 사이클이 있는지 판단하라.
O(N)으로 주소 다 기록해놓고 이전에 나왔던 주소가 있는지 체킹하면 될 거 같은데.. 공간 복잡도 O(1) 방법이 있다고 한다.
Floyd's cycle-finding algorithm으로 한 칸씩 이동하는 slow pointer와 두 칸씩 이동하는 fast pointer를 두면 사이클 내에서 꼭 같은 노드에서 만나게 된다.

야매 연결 리스트 예시

// http://boj.kr/5c97cb6a88324537a722e8de9169e2ab
#include <bits/stdc++.h>
using namespace std;

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

void insert(int addr, char num){
  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 traversal(){
  int cur = nxt[0];
  while(cur != -1){
    cout << dat[cur];
    cur = nxt[cur];
  }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  fill(pre,pre+MX,-1);
  fill(nxt,nxt+MX,-1);
  string init;
  cin >> init;
  int cursor = 0;
  for(auto c : init){
    insert(cursor, c);
    cursor++;
  }  
  int q;
  cin >> q;
  while (q--) {
    char op;
    cin >> op;
    if (op == 'P') {
      char add;
      cin >> add;
      insert(cursor, add);
      cursor = nxt[cursor];
    }
    else if (op == 'L') {
      if (pre[cursor] != -1) cursor = pre[cursor];
    }
    else if (op == 'D') {
      if (nxt[cursor] != -1) cursor = nxt[cursor];
    }
    else { // 'B'
      if (pre[cursor] != -1) {
        erase(cursor);
        cursor = pre[cursor];
      }
    }
  }
  traversal();
}