C언어 단일 연결리스트(Singly linked lists in C)

C언어 단일 연결리스트(Singly linked lists in C)

- 연결리스트는 객체가 선형순서로 정렬되는 자료구조이다.

- 배열의 인덱스가 아닌 각 객체의 포인터에 의해 연결리스트의 순서가 결정된다.

- 연결리스트는 동적 구조를 위해 간단하고 유연한 표현을 제공한다.

- HEAD 포인터가 리스트의 맨 앞을 가르키고, 각 노드가 다음 노드를 가르킨다.

[ Fig. 1 ] Singly linked list

 

1. 동작 원리

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

(2 - 1) 삽입 명령시 새로운 노드를 생성하고, key 값을 입력한다.

(2 - 2) HEAD 포인터가 가르키는 노드가 없을 경우 HEAD 포인터에 노드를 연결한다.

(2 - 3) or 연결리스트의 가장 마지막 부분에 노드를 연결한다.

(3 - 1) 제거 명령시 제거하려는 key 값과 HEAD가 가르키는 노드의 key값이 같으면 제거한다.

(3 - 2) or 다음 노드로 이동하면서 동일한 key값을 가진 노드를 찾아 제거한다.

(3 - 3) 찾지 못한다면 -1를 반환한다.

(4) 현재 연결되어있는 모든 노드를 출력한다.

2. 함수 설명

insert_node( NODE **, int) : 노드를 연결리스트에 삽입하는 기능으로 동작원리 (2)에 해당한다.

delete_node( NODE **, int) : 연결리스트로부터 제거하려는 key값을 가진 노드를 제거하는 기능으로 동작원리 (3)에 해당한다.

display_node( NODE *) : 연결리스트의 모든 노드를 출력한다.

3. 전체 소스 코드

#include <stdio.h> #include <malloc.h> typedef struct node{     int key;     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, 30);     delete_node( &H, 10);     display_node( H);     delete_node( &H, 15);     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->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; } /*     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;         }         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;             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;     printf("HEAD > ");     while( temp != NULL)     {         printf("%3d", temp->key);         temp    = temp->next;     }     printf(" END.\n"); }

 

4. 실행 결과