[연결리스트]

연결 리스트의 성질

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

---

배열 vs 연결 리스트

|---|배열|연결리스트|
|K번째 원소에 접근|O(1)|O(K)|
|임의 위치에 원소 추가/제거|O(N)|O(1)|
|추가적으로 필요한 공간(overhead)|X|O(N)|

---

예제

#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){
    dat[unused] = num;
    pre[unused] = addr;
    nxt[unused] = nxt[addr];
    nxt[addr] = unused;
    pre[nxt[addr]] = unused; // if(nxt[addr] != -1) 조건이 있어야 한다!
    unused++;
}

void erase(int addr){
    nxt[pre[addr]] = nxt[addr];
    pre[nxt[addr]] = pre[addr];
    unused--;
}
}

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

#include <list>
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 << ' ';
}

• .begin() 은 맨 처음 원소를 리턴한다.
• .push_front(), push_back()은 각각 맨 앞, 맨 뒤에 원소를 추가한다.
• .pop_front(), pop_back()은 각각 맨 앞, 맨 뒤에 원소를 삭제한다.
• c++11이상부터 iterator 대신 auto i를 이용해서 for문을 돌 수 있다.
• .insert(&p,x)는 p주소 앞에 원소 x를 삽입한다.

---

연습문제

Q1. 원형 연결 리스트내의 임의의 노드가 하나 주어졌을 때 해당 연결리스트의 길이를 구하는 방법은 ?

Q2. 서로 다른 노드에서 출발해서 어느 한 노드에서 만나는 연결리스트가 있다. 이떄 만나는 노드를 구하는 방법은?

Q3. 주어진 연결리스트에서 사이클이 있는지 판별하는 방법은?