[자료구조] Linked List

• 본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다.
• 따라서 완벽하지 않은 부분이 있을 수 있습니다.
• 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다.

링크드 리스트의 개념

링크드 리스트는 데이터를 순서대로 저장해준다.
계속해서 새로운 요소를 추가할 수 있다. 배열과는 다르게 각 요소는 사실상 독립적인 레퍼런스에 위치해있다.
각 요소를 노드라고 하고, data 속성과 next 속성을 보유한다. next에는 다음 노드에 대한 레퍼런스가 들어있다.
따라서 실제 메모리에 각 노드들이 여기저기에 흩어져있어도 next속성을 통해 이어진 것처럼 활용할 수 있다.

링크드 리스트의 구현

class Node {
    int a;
    Node *n;
}

• 노드는 해당 노드가 가진 데이터와 다음노드의 주소를 보유한다.
• 데이터는 a로, 다음노드의 주소는 n으로 표시했다.

class List {
    List();
    ~List();
    int Search();
    int Insert();
    int Delete();

    Node *head;
}

List::List() {
    head = NULL;
}
List::~List() {
    Node *p, *q;
    p = head;
    while (p != NULL) {
        q = q -> n; // n은 노드 클래스에서 다음 주소를 나타냈다.
        delete p;
        p = q;        
    }
}

• 링크드 리스트는 Search, Insert, Delete 세가지 기능을 가지고 있고,

탐색, 삽입, 삭제의 구현

int List::Search(int x, Node **p, Node **l) {
    *p = NULL;
    *l = this->head;
    while (*l != NULL) {
        if ((*l) -> a > x) return 0;
        else if ((*l) -> a == x) return 1;
        else {
            *p = *l; 
            *l = *l->n; 
        }
    }
    return 0;
}

Node *P, *L;
res = A.Search(8, &P, &L);

• p에는 탐색한 값의 직전 값이 들어간다.
• l에는 현재 탐색중이던 값이 들어간다.
• 성공이면 1, 실패면 0을 리턴한다.
• 위 예시의 탐색 결과가 성공적으로 마쳤다면, P에는 8의 직전노드가, L에는 8에 해당하는 노드가 들어있다.

int List::Insert(int x) {
    Node *P, *L, *N;
    res = Search(x, &P, &L); // Search 내부적으로 P와 L의 값을 할당함
    if (!res) {
        N = new Node; // 새로운 노드 생성
        N->a = x; // 새로운 노드의 N에 데이터 삽입
        if (P == NULL) this->head = N; // P가 NULL이면 N을 그냥 head로 처리
        else P->n = N; // P의 다음노드를 N으로
        N->n = L; // N의 다음노드를 L로
    } 
    else return -1;
}

• Search의 코드를 활용한다.
• 하지만 앞선 Search 코드에서 보았듯이 P는 얼마든지 NULL일 가능성이 있다.
• 따라서 해당 경우들을 나눠서 구현한다.

int List::Delete(int x, Node **d) {
    Node *P, *L;
    res = Search(x, &P, &L); // Search 내부적으로 P와 L의 값을 할당함
    if (res) {
        *d = L; // 삭제 노드를 담을 곳인 d에 최종 노드인 L을 넣어준다.
        if (P == NULL) head = L->n; // 노드 연결 끊기
        else P->n = L->n; // 노드 연결 끊기
    }
    else return -1;
}

• 삭제는 삭제할 값에 해당하는 노드가 존재해야 가능하다.
• cf. 마이너스 무한대 노드, 플러스 무한대 노드를 추가해놓고 시작하면 P와 L에 대한 예외처리가 좀 더 용이해진다.
• 서큘러 링크드 리스트, 더블리 링크드 리스트 등으로 성능 개선을 할수도 있다.

링크드 리스트의 성능

• Sorted : 탐색 O(n), 삽입 O(n), 삭제 O(n)
• Unsorted : 탐색 O(n), 삽입 O(1) 중복거를시 O(n), 삭제 O(n)
• LRU(Least Recently Used, Paper on Desktop) : 최근 사용한 노드를 헤드로 이동,
• LRU 최악 : 탐색 O(n), 삽입 O(1) 중복거를시 O(n), 삭제 O(n)
• LRU 기대 : 사용 빈도에 따라 다르다. 최근 사용한 값을 자주 사용하게 될수록 유리

VS std::vector

• Vector : Variable Size Array -> 사이즈가 바뀔 수 있다.
• Sorted : 탐색 O(log n), 삽입 O(log n + n), 삭제 O(log n + n)
• Unsorted : 탐색 O(n), 삽입 O(n), 삭제 O(n)

---

• 스택을 이러한 '링크드 리스트'로 구현할 수도 있다.
• 앞쪽 노드를 제일 나중에 들어간 노드로 처리하는 등의 처리를 생각해볼 수 있다.
• 큐도 마찬가지이다.
• 마지막 노드를 tail 포인터로 설정하는 등의 처리를 생각해볼 수 있다.

More

• Free Blcok List on File System에 사용
• 다항식 표현에 사용 (각 항을 수로 표현, N차항~0차항)
• Sparse Matrix에 사용
• Memory Allocation에 사용 (링크로 빈 공간을 탐색)
• Skip List에 사용 (Binary search와 유사하게, 일정구간 스킵하고 찾는 값보다 큰지 작은지 체크가능)
• Fractal(그림 반복)에 사용
• B+Tree (트리에서 같은 레벨의 노드들을 링크를 통해 일렬로 연결가능)