[바킹독의 실전 알고리즘] 0x04강 - 연결리스트

연결리스트

원소들을 저장할 때 그 다음 원소가 있는 위치를 포함하는 방식으로 저장하는 자료구조

ex. 메모장

성질

1. k번째 원소를 확인 / 변경 -> O(k) 필요
   • 첫 번째부터 순차적으로 방문해야 함 (첫 번째 원소의 주소만 알고 있음)
   • N개의 원소 -> 평균적으로 2/N 시간 => O(N)
2. 임의의 위치에 원소 추가 / 임의 위치의 원소 제거 -> O(1)
   • 다음 원소의 주소만 변경해주면 됨 (추가하고 싶은 위치의 주소를 알고 있는 경우)
3. 원소들이 메모리 상에 연속 X -> Cache hit rate ↓ But, 할당 다소 쉬움

배열 vs. 연결리스트

-> 선형 자료구조

vs. 비선형 자료구조: 트리, 그래프, 해쉬

 

종류

• 단일 연결 리스트(Singly Linked List)
  • 각 원소가 다음 원소의 주소를 들고 있는 연결 리스트
• 이중 연결 리스트(Doubly Linked List)
  • 자신의 이전 원소, 다음 원소 주소를 둘 다 들고 있는 연결 리스트
  • (-) 메모리를 추가로 더 써야함
• 원형 연결 리스트(Circular Linked List)
  • 끝이 처음과 연결된 연결 리스트

// 연결 리스트의 구현
struct NODE {
	struct NODE *prev, *next;
    	int data;
};

// 야매 연결 리스트
const int MX = 1000005;
int data[MX], pre[MX], nxt[MX];
int unused = 1;

fill(pre, pre+MX, -1);
fill(nxt, nxt+MX, -1);

dummy node를 두지 않으면 삽입 / 삭제 구현할 때 원소가 아예 없는 경우에 대한 예외처리 해야함

// traverse 함수
void traverse() {
	// 원소들의 주소가 담겨서 이동
        int cur = nxt[0]; 
        while(cur != -1) {
            cout << dat[cur] << ' ';
            cur = nxt[cur];
        }
        cout << "\n\n";
}

구현

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

const int MX = 1000005;
int data[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;
    unused++;
}

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

void traverse() {

}

void insert_test() {

}

void erase_test() {

}

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

 

if(nxt[addr] != -1) 처리
-> pre[addr] != -1는 왜 체크 안하고 nxt[addr]만 체크?
=> dummy node의 존재 -> 어떤 원소를 지우더라도 pre[addr] != -1이 보장
However, 제일 마지막 원소를 지우는 상황에서 값이 -1일 수 있음

---

STL list

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 << ' ';
}

push_back, pop_back, push_front, pop_front => O(1)
iterator -> 주소 역할 (auto t = L.begin -> C++11 이상)
erase -> 제거한 다음 원소의 위치 반환

---

연습문제

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

정답
동일한 노드가 나올 때까지 계속 다음 노드로 가면 됨
공간복잡도 O(1), 시간복잡도 O(N)

손코딩 문제 2
중간에 만나는 두 연결 리스트의 시작점들이 주어졌을 때 만나는 지점을 구하는 방법

정답
일단 두 시작점 각각에 대해 끝까지 진행시켜서 각각의 길이 구함
그 후 다시 두 시작점으로 돌아와서 더 긴쪽을 둘의 차이만큼 앞으로 먼저 이동시켜놓고
두 시작점이 만날 때까지 두 시작점을 동시에 한 칸씩 전진시키면 됨
공간복잡도 O(1), 시간복잡도 O(A+B)

손코딩 문제3
주어진 연결 리스트 안에 사이클이 있는지 판단하라

정답
Floyd's cycle-finding algorithm
-> 한 칸씩 가는 커서와 두 칸씩 가는 커서를 동일한 시작점에서 출발 
=> 사이클 O -> 반드시 만나게 됨 (사이클 X -> 만나지 X, 연결 리스트 끝에 도달)
공간복잡도 O(1), 시간복잡도 O(N)

---