자료구조 6주차

자료구조 6주차

Linked List

• 배열의 문제
  • 사이즈를 늘릴 때 힘들다…
  • 배열을 키울려면 다른 곳에다 새로 만들 수 밖에 없다.
• 사이즈 바꾸는 것을 해결하기 위해 사용되는 Linked List

---

• Contents
  • Definition of Linked List(정의)
  • Implementation(이행)
  • Performance(성능)
  • Sample Application(+다양한 적용 기술들)

---

Definition of Linked List

• Consists of Nodes
  • Node : Unit of storage (item)
  • Nodes are linked with pointers ( 다음 노드를 가리키기 위한 포인터 )
    • Linked List는 배열처럼 연속된 주소를 가지고 있지 않고, 여기저기 흩어져 있다.
• 다시 한 번 리마인드!
  • 주소 ( 메모리 상의 자리 ) , 포인터 ( 주소를 가지고 있는 변수 )

---

• Code for Node

class Node{
    int a;
    Node *n; // Node n; 은 컴파일 에러!
};

• Code for List (pseudo code)
  • Search
    • ‘p’, ‘l’은 ‘Node *’타입의 포인터 변수들을 가리키는 포인터
    • *p, *l은 Node * 타입의 포인터 변수들을 간접 참조하는 것이 된다.

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

    Node *head;
};

...
    List A;
    A.head = NULL; if(A.Search(8)){...};

int List::Search(int x, Node** p_post, Node** l_post) {
    // 현재 p_post, l_post은 Node를 가리키는 주소를 가진 변수의 '주소'이다.
    *p_post = NULL;
    *l_post = this->head;
    while (*l_post != NULL) {
        if ((*l_post)->a > x)return 0;
        else if ((*l_post)->a == x)return 1;
        else {
            *p_post = *l_post;
            *l_post = (*l_post)->n;
        }
    }
    return 0;
}

int main(){
    List A...
    Node *p, *q;
    int check = search(8, &p, &q); 
// Node의 주소를 가리키는 p, q의 주소를 함수의 인자로 전달
// 탐색이 성공적으로 마쳤다면, p에는 8의 직전노드가, l에는 8에 해당하는 노드가 들어있다.

내 필기

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

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로
                return 1;
    } 
    else return -1;
}

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

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

---

• 성능
  • 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 기대 : 사용 빈도에 따라 다르다. 최근 사용한 값을 자주 사용하게 될수록 유리

---

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

---

Full Code

#include <bits/stdc++.h>    

using namespace std;

class Node {
public:
    int data;
    Node* next;
};

class List {
public:
    Node* head;
    List() :head(NULL) {};
    int Search(int x, Node** P, Node** L);
    int Insert(int x);
    int Delete(int x, Node** d);
    void print();
};

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

int List::Insert(int x){
    Node* N;
    Node* p, * l;
    int res = Search(x, &p, &l);
    if (res != 1) {
        N = new Node;
        N->data = x;
        if (p == NULL) {
            this->head = N;
        }
        else {
            p->next = N;
        }
        N->next = l;
        return 1;
    }
    else {
        return 1;
    }
}

int List::Delete(int x, Node** d) {
    Node* p, * l;
    int res = Search(x, &p, &l);
    if (res == 1) {
        *d = l;
        if (p == NULL) {
            this->head = l->next;
            return 0;
        }
        else {
            p->next = l->next;
            return 0;
        }
    }
    else {
        return -1;
    }
}

void List::print() {
    Node* d;
    d = this->head;
    while (d!= NULL) {
        cout << d->data << " ";
        d = d->next;
    }
    cout << "\n";
}
int main() {
    List A;
    A.Insert(1);
    A.Insert(3);
    A.Insert(2);
    A.print();
    Node* deleteNode;
    A.Delete(2, &deleteNode);
    delete deleteNode;
    A.print();
    return 0;
}