[ 자료구조 ] Linked List

Linked List

• 연속적인 노드
• Node : unit of storage (item)
• Nodes are linked with pointers 

 

Linked list는 배열과 다르게 메모리 아무데나 있을 수 있다. 대산 한 노드에 가면(=한 노드의 주소를 알아서 그곳의 내용을 읽으면) 다음에 갈 노드의 주소가 적혀있다. 즉 노드들이 포인터들도 연결이 되어 있는 것이다.

 

Linked List의 노드의 구조를 살펴보면 다음과 같다.

 

Whole List

 

 

 

이런식으로 구성이 되어있다. (화살표 등은 사람이 보기 쉽게 표현한것이다.) 마지막 노드에는 더이상 갈 곳이 없으므로 null값을 넣는다. 첫번째 노드로 갈때는 어쩔수 없이 그 노드가리키는 포인터를 가지고 있어야 한다.

 

Code for List

class Node {
    int a; // data
    Node *n; // 다음노드에 대한 주소
}; 

class List {
    List::List();
    List::~List();
    int Search(...);
    int Insert(...);
    int Delete(...);
    
    Node *head;

};

List::List()
{
    head = NULL;
}

List::~List()
{
    Node *p, *q;
    p = head; //p가 같은 곳을 가리키게 됨.
    
    while( p != NULL){            
        q = p -> n
        delete p; // p가 가리키고 있는 곳이 delete
        p = q;
    }
}
...
    // examples
    List A;
    A.head= NULL;
    A.Search(8);​

 

 

Search Code

int List::Search(int x, Node **p, Node **l) //x는 찾을 값 ㅣ이 현재 보고 있는 node
//p가 직전에 본 node
{
    *p = NULL;
    *l = 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); // res == 0 이면 실패 res == 1 이면 성공​

 

 Insert 그림

 

insert 작업을 할떄는 그림과 같이 연두색 화살표를 만들고 기존 검은색 화살표를 없애면 된다. 

 

Insert Code

int List::Insert( int x ) 
{
    Node *P, *L, *N;
    res = search(x, &P, &L);
    if(res == 0 ){
        N = new Node; // 새로운 노드 할당
        N -> a = x;
        if(P == NULL) head = N; else P -> n = N;
        N -> n = L;
    }
}

 

Delete 그림

 

 

Delete Code

int Delete( int x , Node **d) 
{
     Node *P, *L;
    res = search(x, &P, &L);
    if (res == 1) {
        *d = L;
        if(P == NULL) head = L->n; else P->n = L->n;
    
    }
    else return -1;
}​

 

Performance( 성능 평가 )

• Sorted(정렬)
  • Search: O(n) , Insert: S + O(1)  , Delete: S + O(1)
• UnSorted(정렬 X)
  • Search: O(n) , Insert: S + O(1) or O(1) , Delete: S + O(1)
• LRU (Least Recently Used, Paper on Desktop) : 사용한 노드를 head로 이동
• =>자주 사용하는 값을 앞으로 놓자
  • 최악- Search: O(n), Insert: O(1) , Delete: S + O(1)
  • 기대- 사용 빈도에 따라 크게 다름.