연결리스트

 연결리스트
 원소를 저장 할 때에 다음 원소의 주소를 함께 저장
 메모리 상에는 여기저기 흩어져있음

 성질
 1. k번째 원소를 찾기 위해 O(k)의 시간이 필요
 2. 임의의 위치에 원소를 추가/제거가 O(1)
 3. Cache Hit Rate가 낮지만 할당이 쉬움

 종류
 1. 단일 연결리스트 다음 원소의 주소를 들고잇음
 2. 이중 연결리스트 다음 원소와 이전 원소의 주소를 모두 들고잇음
 3. 원형 연결리스트 끝이 처음과 이어져 있음 원을 이루는 리스트는 이중일수도 있고 단일일수도 있음
 

 stl에 있는 list 는 이중 연결 리스트

 배열과 연결리스트는 모두 선형 자료구조

 

야매 연결리스트 

#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];

    if (nxt[addr] != -1) { 
        // 맨 마지막 원소의 뒤에 새 원소를 추가하는 상황일 경우
        // 삽입할 위치의 다음 원소가 존재하지 않는데 이 부분을 unused로 처리해버리면
        // pre[-1] = unused; 가 돼서 에러 !
        pre[nxt[addr]] = unused;
    }
    nxt[addr] = unused;

    unused++;
}

void erase(int addr) {
    nxt[pre[addr]] = nxt[addr];
    if (nxt[addr] != -1) {
        // 0번지에 dummy node 를 넣어놔서 pre[addr] 은 -1이 될 수 없음
        // nxt[addr] 은 마지막 원소를 지우는 경우 -1이 될 수 있기 때문에
        // insert랑 마찬가지로 pre[-1]=pre[addr]; 이 될 수 있음
        pre[nxt[addr]] = pre[addr];
    }
}

void traverse() {
    int cur = nxt[0]; // 첫번째 원소의 인덱스를 cur 에 넣어줌
    while (cur != -1) { // cur이 마지막 원소가 될때까지
        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();
}