[자료구조] 3주차 - 연결 리스트 (Linked list)

Linked List

• 원소들이 메모리에서 임의의 위치에 배치되어 있음
• 한 원소는 다음 원소를 가리키는 주소 (link, pointer)를 가지고 있음(포인터 기반의 자료구조)
• node = data + link, node는 메모리의 임의의 위치에 배치됨

단일 연결 리스트 (singly linked list) : node 당 하나의 link

0. 정의

   class node { data_type item; node *link; };
   class hnode { node *link; };

1. 생성

   void main ( ) { hnode first; }

2. 검색 (선형 탐색만 가능) 보류

   node *hnode::search( data_type item ) {
       return this->link->search ( item ); 
   }
   node *node::search( data_type item ) { 
       //  1. Find a proper position
       node *curr= this; 
       while ( curr!= NULL ) {
           if ( curr->item == item )
               return curr;  // Found
           curr= curr->link; 
       } return NULL;      // Not found }

3. 추가

   1. 데이터를 추가할 적절한 위치를 결정
   2. 데이터를 저장할 새로운 노드를 생성
   3. 새로운 노드가 연결 리스트에 포함되도록 링크를 갱신

   void hnode::insert ( data_type item ) {
       this->link->insert ( item ); 
   }
   void node::insert ( data_type item ) {
       //  1. 적절한위치를결정 
       node *curr= this;
       while ( curr->link != NULL ) {
           if ( curr->link->item > item ) 
               break; curr= curr->link; 
       } 
       //  2. 새로운노드를생성
       node *nnode= new node;
       nnode->item = item; 
       //  3. 링크를갱신
       nnode->link = curr->link;
       curr->link = nnode;
   }

   첫 번째 노드 앞에 추가하는 경우, 리스트에 처음 추가하는 경우, 마지막 노드 뒤에 추가하는 경우 등 예외 처리 필요

4. 제거

   1. 제거할 원소를 찾음
   2. 링크를 갱신해서 제거할 원소를 리스트에서 분리
   3. 제거된 노드의 메모리를 free

   void hnode::delete ( data_type item ) { 
       this->link->delete ( item ); 
   }
   void node::delete ( data_type item ) {
       //  1. 제거할원소를찾음
       node *curr= this; 
       while ( curr->link != NULL ) {
           if ( curr->link->item == item )
               break;
           curr= curr->link; 
       } //  2. 링크를갱신
       node *dnode= curr->link;
       curr->link = dnode->link;
       //  3. 제거된node를free
       free ( dnode); 
   }

   첫 번째 노드를 제거하는 경우, 빈 리스트에서 제거하는 경우, 제거할 값이 없는 경우 등 예외 처리 필요

이중 연결 리스트 (doubly linked list) : node 당 두 개의 링크

다음 (next, rlink) node를가리 키는 link, 전(prev, llink) node를가리 키는 link

0. 정의

   class node { data_type item; node *llink, *rlink; };
   class hnode { node *link; }

1. 추가

   void node::insert ( data_type item ) { 
       //  1. 적절한위치를결정 
       node *curr= this;
       while ( curr->rlink!= NULL ) { 
           if ( curr->rlink->item > item )
               break;
           curr= curr->rlink; 
       } 
       //  2. 새로운노드를생성
       node *nnode= new node;
       nnode->item = item;
       //  3. 링크를갱신
       //     rlink 방향
       nnode -> rlink = curr->rlink;
       curr -> rlink = nnode;
       //     llink 방향
       nnode -> llink = curr;
       nnode -> rlink -> llink = nnode;
   }    

   첫 번째 노드 앞에 추가하는 경우, 처음 추가하는 경우, 마지막 노드 뒤에 추가하는 경우 등 예외 처리 필요

2. 제거

   void node::delete ( data_typeitem ) {
       //  1. 제거할원소를찾음 
       node *curr= first;
       while ( curr->rlink!= NULL ) {
           if ( curr->rlink->item == item )
               break;
           curr= curr->rlink;
       }
       //  2. 링크를갱신
       node * dnode = curr -> rlink;
       curr -> rlink = dnode -> rlink
       curr -> rlink -> llink = dnode -> llink;
       //  3. 제거된node를free
       free ( dnode);
   }

   첫 번째 노드를 제거하는 경우, 빈 리스트에서 제거하는 경우, 마지막 노드를 제거하는 경우 등 예외 처리 필요

단일/ 연결 리스트의 검색, 추가 제거 연산의 시간 복잡도는 모두 O(n)