C언어 원형 이중 연결리스트(Circular, doubly linked lists in C)

C언어 원형 이중 연결리스트(Circular, doubly linked lists in C)

- 이중 연결리스트의 구조에서 가장 처음과 마지막 노드가 서로 연결 되어있는 구조

- 시작 위치를 알기 위해 연결리스트의 맨 앞에 NULL 노드를 추가

[ Fig. 1 ] 원형 이중 연결리스트, site: introduction to algorithm 3/E

 

1. 동작 원리

(1) NULL 노드를 생성하고 초기화하고 HEAD 포인터가 이를 가르키게 한다.

(2-1) 삽입 명령시 새로운 노드를 생성한다.

(2-2) NULL 노드의 이전 노드를 새로 생성한 노드로 지정하고, 새로 생성한 노드의 다음 노드를 NULL 노드로 지정한다.

(2-3) 연결리스트의 가장 마지막 노드를 찾아서, 이 노드의 다음 노드를 새로 생성한 노드로 지정한다.

(2-4) 새로 생성한 노드의 이전 노도를 현재 가장 마지막 노드로 지정한다.

(3-1) 삭제 명령시 NULL 노드의 다음 노드부터 탐색을 시작한다.

(3-2) 제거하려는 key값을 가진 노드를 발견하면, 이 노드의 이전 노드와 다음 노드를 서로 가르키게 한다.

(3-3) 그리고 노드를 제거 한다. (메모리 반환)

(4) NULL 노드의 다음 노드를 추적하며 key 값을 출력한 후, NULL 노드의 이전 노드를 추적하며 key 값을 출력한다.

2. 함수 설명

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

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

void display_node( NODE *) : 연결리스트의 모든 노드들을 출력하는 함수로 동작원리 (4)에 해당한다.

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 = (NODE *)malloc(sizeof(NODE));     // initialize the starting node.     H->key  = NULL;     H->next = H;     H->prev = H;     insert_node( &H, 10);     insert_node( &H, 20);     insert_node( &H, 30);     insert_node( &H, 40);     delete_node( &H, 30);     display_node( H);     delete_node( &H, 40);     delete_node( &H, 10);     display_node( H);     delete_node( &H, 20);     display_node( H);     insert_node( &H, 50);     insert_node( &H, 80);     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;     printf("INSERT [%d]\n", key);     new_node->next  = temp;     new_node->key   = key;     temp->prev      = new_node;     // find the last node.     while( temp->next != *n)     {         temp    = temp->next;     }     new_node->prev  = temp;     temp->next  = new_node; } /*     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 *h = (*n)->next;   // head     NODE *t = *n;           // tail     printf("DELETE [%d]\n", key);     // if variable 'h' is not starting node.     while( h != *n)     {         if( h->key == key)         {             t->next         = h->next;             h->next->prev   = t;             free(h);             return 0;         }         h   = h->next;         t   = t->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->next;     printf("S > ");     // display all nodes along next.     while( temp != n)     {         printf("%3d", temp->key);         temp    = temp->next;     }     printf(" > < ");     temp    = temp->prev;     // display all nodes along previous.     while( temp != n)     {         printf("%3d", temp->key);         temp    = temp->prev;     }     printf(" < E.\n"); }

 

 

4. 실행 결과