[바킹독 알고리즘] 0x04강:Linked List

연결리스트

성질

1. k 번째 원소 확인/변경 위해 O(k) 필요
2. 임의의 위치에 원소 추가, 제거가 O(1) (추가/제거하는 위치를 알고있는 경우)
3. Cache rate hit은 낮지만 할당이 좋다.

→ 임의의 위치에 원소 추가하거나 제거하는 연산이 많을경우 연결리스트 사용 좋다.

연결리스트 종류: 단일 연결리스트/이중연결 리스트/환형 연결리스트

배열 vs 연결리스트

연결리스트 구현

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

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

void insert(int addr, int 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 traverse(){
  int cur = nxt[0];
  while(cur != -1){
    cout << dat[cur] << ' ';
    cur = nxt[cur];
  }
  cout << "\\n\\n";
}

void insert_test(){
  cout << "****** insert_test *****\\n";
  insert(0, 10); // 10(address=1)
  traverse();
  insert(0, 30); // 30(address=2) 10
  traverse();
  insert(2, 40); // 30 40(address=3) 10
  traverse();
  insert(1, 20); // 30 40 10 20(address=4)
  traverse();
  insert(4, 70); // 30 40 10 20 70(address=5)
  traverse();
}

void erase_test(){
  cout << "****** erase_test *****\\n";
  erase(1); // 30 40 20 70
  traverse();
  erase(2); // 40 20 70
  traverse();
  erase(4); // 40 70
  traverse();
  erase(5); // 40
  traverse();
}

int main(void) {
  fill(pre, pre+MX, -1);
  fill(nxt, nxt+MX, -1);
  insert_test();
  erase_test();
}

STL List

 

문제 풀이 현황

연습 문제 ✔	1406	에디터	정답 코드
기본 문제 ✔	5397	키로거	정답 코드
기본 문제	1158	요세푸스 문제	정답 코드, 별해 1, 별해 2