C언어 이중 연결리스트(Doubly linked lists in C)

C언어 이중 연결리스트(Doubly linked lists in C)

- 연결 리스트의 한 종류이다.

- 각 노드가 자신의 다음 노드 및 자신의 이전 노드를 가르킨다.

[ Fig. 1 ] Doubly linked list, site : introduction to algorithms 3/E

 

1. 동작 원리

(1) 연결리스트의 가장 처음을 가르키는 HEAD 포인터를 초기화한다.

(2 - 1) 삽입 명령시 연결리스트의 가장 마지막 노드를 찾는다.

(2 - 2) 연결된 노드가 없을 경우, HEAD가 새로 생성한 노드를 가르키게 한다.

(2 - 2) 연결된 노드가 있을 경우 가장 마지막 노드 다음에 새로 생성한 노드를 연결하고, 새로 생성한 노드가 마지막 노드를 가르키게 한다.

(3 - 1) 제거 명령시 제거하려는 key 값을 가진 노드를 찾는다.

(3 - 2) 가장 처음 노드가 해당 key 값을 가진 노드일 경우 다음 노드가 NULL을 가르키게 한 후 노드를 제거한다.

(3 - 3) or 지우려는 key 값을 가진 노드를 찾아서 해당 노드의 이전 노드와 다음 노드를 연결 시킨 후 해당 노드를 제거한다.

(4) 연결리스트를 앞에서 부터 출력한 후, 뒤에서부터 다시 출력한다.

2. 함수 설명

void insert_node( NODE **, int) : 연결리스트에 노드를 추가하는 함수로 동작원리 (2)에 해당한다.

int delete_node( NODE **, int) : 연결리스트에서 노드를 제거하는 함수로 동작원리 (3)에 해당한다.

display_node( NODE *) : 연결리스트의 모든 노드들을 앞에서 부터, 그리고 뒤에서 부터 총 두 번 출력한다.

3. 함수 구현

#include <stdio.h> #include <malloc.h> typedef struct node{     int key;     struct node *prev;     struct node *next; }NODE; void insert_node( NODE **, int); int delete_node( NODE **, int); void display_node( NODE *); int main( void) {     NODE *H = NULL; // HEAD     insert_node( &H, 10);     insert_node( &H, 30);     insert_node( &H, 20);     insert_node( &H, 50);     display_node( H);     delete_node( &H, 10);     display_node( H);     delete_node( &H, 20);     display_node( H);     delete_node( &H, 30);     display_node( H);     delete_node( &H, 50);     display_node( H);     return 0; } /*     insert_node( NODE **, int)     insert a key on the back of the linked list. */ void insert_node( NODE **n, int key) {     NODE *new_node  = (NODE *)malloc(sizeof(NODE));     NODE *temp      = *n;         new_node->next  = NULL;     new_node->prev  = NULL;     new_node->key   = key;     printf("INSERT [%d]\n", key);     // there is not any node.     if( temp == NULL)     {         *n  = new_node;         return;     }     // find the last node in the linked list.     while( temp->next != NULL)     {         temp    = temp->next;     }     temp->next      = new_node;     new_node->prev  = temp; } /*     delete_node( NODE **, int)     delete the key that you want from the linked list.     if the key is removed, this function will return 0.     if it is not, this function will return -1. */ int delete_node( NODE **n, int key) {     NODE *temp  = *n;     NODE *f     = NULL;     printf("DELETE [%d]\n", key);     // if the key that you want to remove is located firstly.     if( (*n)->key == key)     {         if( (*n)->next != NULL)         {             *n  = (*n)->next;                 (*n)->prev  = NULL;         }         else         {             *n  = NULL;         }         free(temp);         return 0;     }     while( temp->next != NULL)     {         // if find the key that you want to remove         if( (temp->next)->key == key)         {             f   = temp->next;             temp->next          = (temp->next)->next;             (temp->next)->prev  = temp;             free(f);             return 0;         }         temp    = temp->next;     }     printf("Can't find the key!\n");     return -1; } /*     display_node( NODE *)     display all node in the linked list. */ void display_node( NODE *n) {     NODE *temp  = n;     NODE *p     = NULL;     printf("HEAD > ");     // print all nodes from the left to the right.     while( temp != NULL)     {         printf("%3d", temp->key);         p       = temp;         temp    = temp->next;     }     printf(" || ");     // print all nodes from the right to the left.     while( p != NULL)     {         printf("%3d", p->key);         p       = p->prev;     }     printf(" END.\n"); }

 

4. 실행 결과