[알고리즘 공부] 실전 알고리즘 4강-연결 리스트

바킹독님이 올려주신 [실전 알고리즘] 영상을 보면서 공부한것을 기록
모든 사진은 바킹독님의 블로그에서 가져왔습니다.
https://blog.encrypted.gg/

---

정의

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

성질

1. k번째 원소를 확인/변경하기 위해서는 O(k)가 필요
2. 임의의 위치에 원소를 추가/제거는 O(1) -> 연결리스트의 장점
3. 원소들이 메모리 상에 연속해있지 않아서 cache hit rate가 낮지만 할당이 다소 쉬움

종류

1. 단일 연결 리스트(singly linked list) - 각 원소가 자신의 다음 원소의 주소를 들고 있는 연결리스트
2. 이중 연결 리스트(doubly linked list) - 각 원소가 자신의 이전 원소와 다음 원소의 주소를 들고 있는 연결리스트 ex) STL의 list
3. 원형 연결 리스트(circular linked list) - 끝이 처음과 연결 되어 있는 연결리스트

배열 vs 연결리스트

기능과 구현

k번째 원소를 확인/변경하기 위해서는 첫번째 원소가 가리키는 주소부터 k번째 원소까지 찾아가야하므로 O(k)의 시간이 소요된다.
전체 길이가 n이라고 할때 평균 시간복잡도는 O(n/2)이므로 O(n)이 된다.

임의의 위치에 원소를 추가할때는 배열처럼 뒤에 있는 원소를 전부 옮길 필요가 없으며 다음원소의 주소만 변경해주면 되기때문에 시간복잡도가 O(1)이 된다.
단 추가하고자 하는 위치의 주소를 알고 있을때만 O(1)이다. 주소를 모를 경우에는 주소까지 찾아가야하는 시간이 소요되기 때문에 O(1)이라고 할 수가 없다.

임의의 위치에 있는 원소를 제거할때는 전에 있는 원소가 가리키는 주소를 제거하고자 하는 원소가 가리키는 주소로 변경해주면 되기에 시간복잡도는 O(1)이다.

연결리스트는 메모장을 구현할때 유용하게 쓰일수 있다.
메모장에서 임의의 위치에 문자를 추가/제거할때 배열로 구현되어있다고 한다면 매번 O(n)의 시간복잡도가 소요되지만 이를 연결리스트로 구현한다면 시간복잡도가 O(1) 이므로 효율적이라고 볼 수 있다.

야매 연결리스트 구현

이는 메모리 누수 문제가 있는 구현방식이므로 실무에서는 사용하면 안된다.

#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) {
    if (nxt[addr] != -1)pre[nxt[addr]] = pre[addr];
    nxt[pre[addr]] = nxt[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();
}

list로 구현

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

int main(void) {
    list<int> L = { 1,2 }; // 1 2
    //iterator가 주소역할
    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 << ' ';
}