16장 링크리스트

5. 링크드 리스트
: 링크드 리스트(linked list)는 C에서 쉽게 구현할 수 있는 유용한 데이터 저장방법이다. 왜 포인터에 대한 주제를 다루면서 링크드 리스트를 언급하는 것일까? 잠시 후에 배울 것처럼 포인터는 링크드 리스트의 핵심이다.

단순 링크드 리스트, 이중 링크드 리스트, 이진 트리를 포함하여 많은 종류의 링크드 리스트가 있다. 각각의 형태는 데이터를 저장할 필요가 있는 특별한 경우에 적절히 사용된다. 이런 링크드 리스트에서 공통적인 사항은 데이터 항목 간의 결합이 데이터 항목 자체 내에 포함되어 있는 정보에 의해 포인터의 형식으로 정의된다는 것이다. 이런 사실은 데이터 항목 간의 결합이 배열의 배치와 저장을 기반으로 하는 배열과 링크드 리스트를 분명히 구분하는 기준이다. 이 단원에서는 가장 간단한 형태의 링크드 리스트이고 간단히 링크드 리스트라고도 하는 단순 링크드 리스트에 대해서 설명한다.

5.1 링크드 리스트의 기초
: 링크드 리스트의 각 데이터 항목은 구조체에 포함되어 있다. 구조체는 데이터를 저장하는 데 필요한 요소들을 가지고 있다. 어떤 데이터 요소를 가지는지는 프로그램에 따라 달라진다. 링크드 리스트에는 한 가지 요소가 추가되는데 바로 포인터이다. 이 포인터는 링크드 리스트에서 연결 방법을 제공한다. 다음은 간단한 예제이다.

   struct person{
      char name[20];
      struct person *next;
   };

 이 코드는 person이라는 구조체를 정의한다. 데이터만을 이야기한다면 person은 단지 20개 의 요소로 구성되는 문자형 배열을 가진다. 여러분은 일반적으로 이런 간단한 데이터에 대해 링크드 리스트를 사용하지 않겠지만, 여기서는 예로 들어 설명하는 것이므로 실용성에 대해서는 생각할 필요가 없다. person 구조체는 person형의 포인터를 가진다. 다시 말해서 같은 형의 다른 구조체에 대한 포인터이다. 이것은 person형의 각 구조체가 데이터의 모음을 가질 뿐 아니라 다른 person 구조체를 지적할 수 있음을 뜻한다. <그림 15.7>은 이런 구조체가 링크드 리스트에서 서로 연결되는 방법을 보여준다.

<그림 15.7> 링크드 리스트에서의 연결 상태

<그림 15.7>에서 각 person구조체가 다음 person 구조체를 지적한다는 것에 주목하기 바란다 마지막 person구조체는 어떤 것도 지적하지 않는다. 링크드 리스트에서 마지막 요소는 NULL의 값으로 할당되는 포인터 요소에 의해 정의된다.

* 참고
: 링크드 리스트에서 하나의 요소가 되는 각 구조체를 링크드 리스트의 링크(link), 노드(node) , 요소(element)라고 한다.

 여러분은 링크드 리스트에서 마지막 링크가 어떻게 구분되는지 배웠다. 첫번째 링크는 어떻게 구분될까? 첫 번째 링크는 헤드 포인터(head pointer)라는 특별한 포인터(구조체가 아닌 포인터)에 의해 구분된다. 헤드 포인터는 항상 링크드 리스트에서 첫번째 링크를 지적한다. 첫 번째 링크는 두 변째 링크에 대한 포인터를 가지고, 두 번째 링크는 세 번째에 대한 포인터를 가지고, 이런 연결 상태는 포인터가 NULL인 마지막 링크를 만날 때까지 계속된다. 만약 전체 링크드 리스트가 비어 있다면, 즉 어떤 링크도 없다면 헤드 포인터가 NULL로 설정된다. <그림 15.8>은 링크드 리스트가 시작되기 전과 링크드 리스트에 첫 번째 링크가 추가된 후의 헤드 포인터를 보여준다.

<그림 15.8> 링크드 리스트의 헤드 포인터

5.2 링크드 리스트 다루기
: 링크드 리스트를 사용할 때에는 각 링크를 추가, 삭제, 변경할 수 있다. 링크를 변경하는 것은 크게 어렵지 않다. 그러나 링크를 추가하고 삭제하는 것은 약간 복잡하다. 앞에서도 설명했듯이 링크드 리스트에서 링크들은 포인터로 연결된다. 링크를 추가하고 삭제하는 것은 대부분 이런 포인터를 다루는 일이다. 각 링크는 링크드 리스트의 시작, 중간, 마지막에 추가될 수 있다. 어디에 추가하느냐에 따라 포인터를 변경하는 방법이 달라진다. 이 장에서는 간단한 링크드 리스트 예제와 함께 더욱 복잡한 프로그램을 살펴볼 것이다. 그러나 복잡한 프로그램을 설명하기 전에 링크드 리스트를 사용할 때 필요한 동작을 하나씩 살펴보도록 하자. 이 단원에서는 앞에서 사용했던 person 구조체를 계속해서 사용할 것이다.
 
▶ 준비 작업
: 링크드 리스트를 사용하려면 링크드 리스트에서 사용할 데이터 구조체를 정의할 필요가 있고 헤드 포인터를 선언할 필요가 있다. 링크드 리스트는 비어있는 상태로 시작하므로 헤드 포인터는 NULL로 초기화되어야 한다. 또한, 링크를 추가하는 데 사용할 링크드 리스트의 구조체형에 대한 포인터를 추가로 선언해야 한다. 잠시 후에 설명할 것처럼 하나 이상의 포인터가 필요하다. 다음은 예제이다.

  struct person{
      char name[20];
      struct person *next;
   };
   struct person *new;
   struct person *head;
   head = NULL;

▶ 링크드 리스트의 시작 부분에 링크 추가하기
: 만약 헤드 포인터가 NULL이면 링크드 리스트는 비어 있는 것이고 새로운 링크는 유일한 멤버가 될 것이다. 헤드 포인터가 NULL이 아니라면 링크드 리스트는 이미 하나 이상의 링크를 가지고 있는 것이다. 어떤 경우든지 링크드 리스트의 시작 부분에 새로운 링크를 추가하는 방법은 똑같다.

① malloc()을 사용하여 메모리 공간을 할당하며 구조체형 변수를 생성한다.

② 새로운 링크의 next 포인터를 헤드 포인터의 현재 값으로 설정한다. 이 값은 링크드 리스트가 비어 있다면 NULL이 될 것이고, 그렇지 않다면 현재 첫 번째 링크의 주소가 될 것이다.

③ 헤드 포인터가 새로운 요소를 지적하게 한다.

다음은 이런 작업을 수행하는 코드이다.

   new = (person*)malloc(sizeof(struct person));
   new -> next = head;
   head = new;

malloc()은 새로운 링크를 위한 메모리를 할당하는 데 사용된다는 것에 주목하기 바란다. 각 새로운 링크를 추가할 때 단지 해당 링크에 필요한 메모리만이 할당된다. calloc() 함수를 사용할 수도 있을 것이다. 두 함수의 차이점에 주의할 필요가 있다. 주요 차이점은 calloc()이 새로운 링크를 초기화한다는 것이다. malloc()은 새로운 링크를 초기화하지 않는다.

▶ 링크드 리스트의 마지막에 링크 추가하기
: 링크드 리스트의 마지막에 추가하기 위해서는 헤드 포인터에서 시작하고 마지막 링크를 찾을 때까지 링크드 리스트를 통해 차례대로 진행할 필요가 있다. 마지막 링크를 발견하면 다음과 같은 단계를 따른다.

① malloc()을 사용하여 메모리 공간을 할당하며 구조체형 변수를 생성한다.

② 마지막 링크의 next 포인터가 새로운 링크를 지적하게 설정한다. 새로운 링크의 주소는 malloc()에 의해 복귀된다.

③ 새로운 링크가 링크드 리스트에서 마지막 항목이라는 것을 표시하기 위해 새로운 링크의 next 포인터를 NULL로 설정한다.

다음은 코드이다.

   person *current;
   …
   current = head;
   while(current -> next != NULL)
   current = current -> next;
   new = (person*)malloc(sizeof(struct person));
   current -> next = new;
   new -> next = NULL;

▶ 링크드 리스트의 중간에 링크 추가하기
: 힝크드 리스트를 사용하다 보면 대개는 링크드 리스트의 중간에 어디든지 링크를 추가하게 될 것이다. 정확히 새로운 링크가 위치되는 곳은 링크드 리스트를 어떻게 사용하느냐에 따라 다르다. 예를 들어, 하나 이상의 데이터 요소에 따라 링크드 리스트를 정렬한다면 링크를 추가하고 나서 정렬해야 하므로 새로운 링크의 위치가 달라진다. 다음과 같이 진행하기 바란다.

① 리스트에서 새로운 링크가 그 다음에 위치될 기존의 링크를 찾는다. 이것을 표식 요소(marker element)라고 하자.

② malloc()을 사용하여 메모리 공간을 할당하며 구조체형 변수를 생성한다.

③ 표식 요소의 next 포인터가 새로운 링크를 지적하게 한다. 새로운 링크의 주소는 malloc()에 의해 반환된다.

④ 새로운 링크의 next 포인터를 표식 요소가 지적하던 기존의 링크를 지적하게 설정한다. 다음은 예제 코드이다.

   person *marker;
   /* 링크드 리스트에서 원하는 위치를 지적하도록 표식을 설정하는 코드 */
   …
   new = (LINK)malloc(sizeof(PERSON));
   new -> next = marker -> next;
   marker -> next = new;

▶ 링크드 리스트에서 링크 삭제하기
: 링크드 리스트에서 링크를 삭제하는 것은 포인터를 다루면 될 정도로 간단한 문제이다. 정확한 과정은 링크드 리스트에서 링크의 위치에 따라 다르다.

·첫 링크를 삭제하기 위해서 헤드 포인터가 링크드 리스트에서 두 번째 링크를 지적하도록 설정한다.

·마지막 링크를 삭제하기 위해서 마지막 바로 앞의 링크의 next 포인터를 NULL로 설정한다

·다른 어떤 링크를 삭제하기 위해서 삭제되는 바로 앞 링크의 next 포인터를 삭제되는 바로 다음 링크를 지적하도록 설정한다.

다음은 링크드 리스트에서 첫 링크를 삭제하는 코드이다.

  head = head -> next;

다음은 링크드 리스트에서 마지막 링크를 삭제하는 코드이다.

   person *current1, *current2;
   current1 = head;
   current2 = current1 -> next;
   while (current2 -> next != NULL)
   {
      current1 = current2;
      current2 = current1 -> next;
   }
   current1 -> next = NULL;
   if(head == current1)
     head = null;

마지막으로, 다음 코드는 링크드 리스트에서 특정 링크를 삭제한다.

   person *current1, *current2;
   /* current1이 삭제되는 바로 앞 링크를 지적하도록 설정하는 코드 */
   current2 = current1 -> next;
   current1 -> next = current2 -> next;

어느 부분에서 링크를 삭제하든지 삭제된 링크는 여전히 메모리에 남아 있지만 링크드 리스트에서 지적하는 포인터가 없으므로 제거된다. 실제 프로그래밍에서는 "삭제된" 링크가 차지하던 메모리를 해제시켜 확보하기 원할 것이다. free() 함수를 이용하면 되는데, 자세한 내용은 나중에 "메모리 다루기"에서 설명할 것이다.

5.3 간단한 링크드 리스트 예제
: <리스트 15.12>는 링크드 리스트를 사용하는 기본적인 방법을 보여준다. 이 프로그램은 사용자 입력을 받아들이지 앟고 대부분의 기본적인 링크드 리스트 작업에 요구되는 코드를 보여주는 것 외에 특별한 동작을 수행하지 않으며 예제로만 사용되는 것이다.

이 프로그램은 다음과 같은 작업을 수행한다.

① 링크드 리스트를 위한 구조체와 포인터를 정의한다.

② 링크드 리스트에 첫 링크를 추가한다.

③ 링크드 리스트의 마지막에 링크를 추가한다.

④ 링크드 리스트의 중간에 링크를 추가한다.

⑤ 링크드 리스트의 내용을 화면에 출력한다.

<리스트 15.12> 링크드 리스트의 기초

/* 링크드 리스트의 기본적인 사용 방법을     보여주는 예제 */  #include <stdlib.h>  #include <stdio.h>  #include <string.h>  /* 링크드 리스트인 data 구조체 */  struct data {     char name[20];     struct data *next;  };  /* 구조체에 대한 typedef형을 정의하고 포인터를 사용해서 지적한다. */  typedef struct data PERSON;  typedef PERSON *LINK;  main()  {     /* head, new, current 요소 포인터 */     LINK head = NULL;     LINK new = NULL;     LINK current = NULL;     /* 첫 번째 요소를 추가한다. */     /* 이 예제에서는 링크드 리스트가 항상 비어 있지만        비어 있는 것으로 가정하지 않는다. */     new = (LINK)malloc(sizeof(PERSON));     new -> next = head;     head = new;     strcpy(new -> name, "Abigail");     /* 링크드 리스트의 마지막에 요소를 추가한다. */     /* 링크드 리스트에 최소한 하나의 요소가 있다고 가정한다. */     current = head;     while(current -> next != NULL)     {        current = current -> next;     }     new = (LINK)malloc(sizeof(PERSON));     current -> next = new;     new -> next = NULL;     strcpy(new -> name, "Catherine");     /* 링크드 리스트의 두 번째 위치에 새로운 요소 추가 */     new = (LINK)malloc(sizeof(PERSON));     new -> next = head -> next;     head -> next = new;     strcpy(new -> name, "Beatrice");     /* 모든 데이터 항목을 차례대로 출력 */     current = head;     while(current != NULL)     {        printf("\n%s", current -> name);        current = current -> next;     }     printf("\n");     return(0);  }

=> 아마도 최소한 코드의 일부분을 이해할 수 있을 것이다. 9번째 줄부터 12번째 줄까지는 링크드 리스트를 위한 데이터 구조를 선언한다. 16번째 줄과 17번째 줄은 데이터 구조체와 데이터 구조체에 대한 포인터를 위한 typedef문을 정의한다. 이런 typedef가 반드시 필요하지는 않지만 struct data 대신에 PERSON을 사용하고, struct data* 대신에 LINK를 사용하게 해주므로 코드를 단순화할 수 있을 것이다.

22번째 줄부터 24번째 줄까지는 헤드 포인터를 선언하고 링크드 리스트를 다룰 때 사용할 다른 한 쌍의 포인터를 선언한다. 모든 포인터는 NULL로 초기화된다.

30번째 줄부터 33번째 줄까지는 링크드 리스트의 시작 부분에 새로운 링크를 추가한다. 30번째 줄은 새로운 데이터 구조체를 할당한다. malloc()의 결과가 성공적이라고 가정한다는 것에 주목하기 바란다. 실제 프로그래밍에서는 이렇게 가정해서는 안된다.

31번째 줄은 이 새로운 구조체의 next 포인터가 헤드 포인터를 지적하도록 설정한다. 왜 단순히 이 포인터에 NULL을 설정하지 않을까? 링크드 리스트가 현재 비어 있기 때문이다. 이 코드는 링크드 리스트에 이미 다른 링크가 있더라도 그대로 사용할 수 있을 것이다. 새로운 첫 링크는 여러분이 원하는 대로 이전의 첫 번째 링크를 지적하게 될 것이다.

32번째 줄은 헤드 포인터가 새로운 링크를 지적하게 하고, 33번째 줄은 링크에 임의의 데이터를 저장한다.

링크드 리스트의 마지막에 새로운 링크를 추가하는 것은 약간 더 복잡하다. 예제에서는 링크드 리스트에 하나의 링크만 존재하지만 실제로 프로그램을 작성할 때에는 이런 사실을 알 수 없으므로 전체 링크드 리스트에서 마지막 링크를 찾을 때까지 반복해야 한다. next 포인터가 NULL을 지적하는 링크가 마지막 링크이다. 이런 과정은 38번째 줄부터 42번째 줄까지 수행된다. 일단 마지막 링크를 찾았다면 새로운 데이터 구조를 할당하고, 이전의 마지막 링크가 새로운 구조체를 지적하게 하고, 새로운 링크의 next 포인터를 NULL로 설정하면 된다. 이것은 44번째 줄부터 47번째 줄까지의 동작이다.

다음 작업은 링크드 리스트의 중간에 링크를 추가하는 일이다. 이 예제에서는 두 번째 위치에 링크를 추가하면 된다. 50번째 줄에서 새로운 데이터 구조체를 할당하고 나서 새로운 링크의 next 포인터가 두 번째로 사용되는 링크를 지적하도록 설정한다. 그리고 51번째 줄에서 두 번째 링크를 세 번째 링크로 만들며, 52번째 줄에서 첫 링크의 next 포인터가 새로운 링크를 지적하게 한다.

마지막으로, 프로그램은 링크드 리스트의 모든 내용을 출력한다. 헤드 포인터가 지적하는 링크에서부터 NULL 포인터로 표시되는 마지막 링크를 찾을 때까지 전체 링크드 리스트를 통해서 차례대로 진행하면 된다. 56번째 줄부터 61번째 줄까지 이런 작업을 수행하고 있다.

5.4 링크드 리스트 구현하기
: 이제 링크드 리스트에 링크를 추가하는 방법을 보았으므로 실제로 사용하는 방법을 살펴볼 필요가 있다. <리스트 15.13>은 5개의 항목을 가지는 링크드 리스트를 사용하는 다소 긴 프로그램이다. 입력된 문자들은 링크드 리스트를 사용해서 메모리에 저장된다. 이런 문자들은 단지 이름, 주소, 다른 어떤 데이터를 표현할 정도로 간단하다. 예제를 가능한 한 쉽게 만들기 위해 한 문자씩 저장하도록 하겠다.

이 링크드 리스트 프로그램을 복잡하게 만드는 원인은 문자를 입력하고 나서 링크를 정렬하기 때문이다. 물론 이 기능이 프로그램을 상당히 가치있게 만드는 특징이기도 하다. 각 링크들은 값에 다라 시작, 중간, 마지막에 추가되고 링크드 리스트 전체는 항상 정렬된다. 만약 간단히 링크를 마지막에 추가하는 프로그램을 작성했다면 전체적인 구조는 훨씬 더 간단할 것이다. 그러나 프로그램은 그리 유용하지 않을 것이다.

<리스트 15.13> 문자들의 링크드 리스트 구현하기  
 

/*====================================================*   * 프로그램 : list1513.c                               *   * 도서명   : C 언어 21일 완성                       *   * 목적     : 링크드 리스트 구현하기                 *   *====================================================*/  #include <stdio.h>  #include <stdlib.h>  #define NULL  #define NULL 0  #endif  /* 링크드 리스트로 사용되는 구조체 */  struct list  {     int ch;   /* char형을 저장할 int형 선언 */     struct list *next_rec;  };  /* 구조체와 포인터에 대한 typedef형 */  typedef struct list LIST;  typedef LIST *LISTPTR;  /* 함수 원형 */  LISTPTR add_to_list(int, LISTPTR);  void show_list(LISTPTR);  void free_memory_list(LISTPTR);  int main(void)  {     LISTPTR first = NULL;   /* 헤드 포인터 */     int i = 0;     int ch;     char traash[256];   /* stdin 버퍼를 정리한 */     while(i++ < 5)   /* 주어진 5항목을 근거로 링크드 리스트를 구성 */     {        ch = 0;        printf("\nEnter character %d, ", i);        do        {           printf("\nMust be a to z: ");           ch = getc(stdin);   /* 버퍼에서 다음 문자를 구함 */           gets(trash);   /* 버퍼에서 trash를 제거 */        } while((ch < 'a' || ch > 'z') && (ch < 'A' || ch > 'Z'));        first = add_to_list(ch, first);     }     show_list(first);    /* 전체 링크드 리스트를 출력 */     free_memory_list(first);    /* 모든 메모리를 해제 */     return(0);  }  /*====================================================*   * 함수   : add_to_list()   * 목적   : 링크드 리스트에 새로운 링크를 추가   * 입력값 : int ch = 저장할 문자              LISTPTR first = 원래 헤드 포인터의 주소   * 복귀값 : 헤드 포인터의 주소(first)   *====================================================*/  LISTPTR add_to_list(int ch, LISTPTR first)  {     LISTPTR new_rec = NULL;    /* 새로운 링크의 주소를 저장 */     LISTPTR tmp_rec = NULL;    /* 임시 포인터를 저장 */     LISTPTR prev_rec = NULL;     /* 메모리 할당 */     new_rec = (LISTPTR)malloc(sizeof(LIST));     if(!new_rec)    /* 메모리 할당 불가 */     {        printf("\nunable to allocate memory!\n");        exit(1);     }     /* 새로운 링크의 데이터 설정 */     new_rec -> ch = ch;     new_rec -> next_rec = NULL;     if(first == NULL)   /* 링크드 리스트에 첫 링크 추가 */     {        first = new_rec;        new_rec -> next_rec = NULL;   /* 불필요하지만 안전을 보장함 */     }     else   /* 첫 링크가 아니면 */     {        /* 첫 링크 앞인지 확인 */        if(new_rec -> ch < first -> ch)        {           new_rec -> next_rec = first;           first = new_rec;        }        else   /* 중간이나 긑에 추가됨 */        {           tmp_rec = first -> next_rec;           prev_rec = first;           /* 링크가 추가되는 곳을 확인 */           if(tmp_rec == NULL)           {              /* 끝에 두 번째 링크를 추가 */              prev_rec -> next_rec = new_rec;           }           else           {              /* 중간에 추가하는지 확인 */              while(tmp_rec -> next_rec != NULL)              {                 if(new_rec -> ch < tmp_rec -> ch)                 {                    new_rec -> next_rec = tmp_rec;                    if(new_rec -> next_rec != prev_rec -> next_rec)                    {                       printf("ERROR");                       gets(stdin);                       exit(0);                    }                    prev_rec -> next_rec = new_rec;                    break;   /* 링크가 추가되고 while을 마침 */                 }                 else                 {                    tmp_rec = tmp_rec -> next_rec;                    prev_rec = prev_rec -> next_rec;                 }              }              /* 끝에 추가하는지 확인 */              if(tmp_rec -> next_rec == NULL)              {                 if(new_rec -> ch < tmp_rec -> ch)   /* 끝에서 두 번째 위치 */                 {                    new_rec -> next_rec = tmp_rec;                    prev_rec -> next_rec = new_rec;                 }                 else   /* 끝 위치 */                 {                    tmp_rec -> next_rec = new_rec;                    new_rec -> next_rec = NULL;   /* 중복 작업 */                 }              }           }        }     }     return(first);  }  /*====================================================*   * 함수 : show_list   * 목적 : 링크드 리스트의 정보 출력   *====================================================*  void show_list(LISTPTR first)  {     LISTPTR cur_ptr;     int counter = 1;     printf("\n\nRec addr Position Data Next Rec addr\n");     printf("======== ========  ====  ==============\n");     cur_ptr = first;     while(cur_ptr != NULL)     {        printf("  %x  ", cur_ptr);        printf("     %2i     %c", counter++, cur_ptr -> ch);        printf("      %x   \n", cur_ptr -> next_rec);        cur_ptr = cur_ptr -> next_rec;     }  }  /*====================================================*   * 함수 : free_memory_list   * 목적 : 링크드 리스트를 위해 정리된 모든 메모리 해제   *====================================================*  void free_memory_list(LISTPTR first)  {     LISTPTR cur_ptr, next_rec;     cur_ptr = first;    /* 처음에서 시작 */     while(cur_ptr != NULL)    /* 링크드 리스트의 끝까지 진행 */     {        next_rec = cur_ptr -> next_rec;    /* 다음 링크의 주소 구하기 */        free(cur_ptr);     /* 현재 링크 해제 */        cur_ptr = next_rec;   /* 현재 링크 정리 */     }  }

-> 입력 / 출력

  Enter character 1,
  Must be a to z: q

  Enter character 2,
  Must be a to z: b

  Enter character 3,
  Must be a to z: z

  Enter character 4,
  Must be a to z: c

  Enter character 5,
  Must be a to z: a

  Rec addr    Position    Data    Next Rec addr
  ========    ========    ====    ==============
  C3A        1           a       C22
  C22        2           b       C32
  C32        3           c       C1A
  C1A        4           q       C2A
  C2A        5           z       0

=> 분석
: 이 프로그램은 링크드 리스트에 링크를 추가하는 것을 보여준다. 예제를 이해하기는 어려울 것이다. 그러나 자세히 분석해 보면 앞에서 설명하는 링크를 추가하는 세 가지 방법을 모두 다루고 있음을 알 수 있다. 이 프로그램은 링크드 리스트의 시작, 중간, 마지막에 새로운 링크를 추가하는데 사용할 수 있다. 또한, 시작 부분에 추가되는 첫 링크와 중간에 추가되는 두 번째 링크를 새로 추가하는 경우에 대해서 중점적으로 다루고 있다. <리스트 15.13>의 시작 부분에 있는 내용들은 익숙하므로 쉽게 이해할 수 있을 것이다. 9번째 줄부터 14번째 줄까지는 NULL값이 이미 정의되어 있는지 확인해본다. 만약 그렇지 않다면 10번째 줄은 NULL값을 0으로 정의한다. 14번째 줄부터 22번째 줄까지는 링크드 리스트를 위한 구조체를 정의하고, 구조체와 포인터를 쉽게 사용할 수 있도록 하기 위해서 typedef를 사용하고 있다. main()함수는 이해하기 쉽다. first라는 헤드 포인터가 31번째 줄에서 선언된다. 이 포인터가 NULL로 초기화된다는 것에 주목하지 바란다. 여러분은 결코 포인터를 초기화하지 않은 상태로 내 버려두어서는 안된다는 것을 기억하기 바란다. 36번째 줄부터 49번째 줄까지는 사용자로부터 5문자를 읽어들이는 while 순환문이 있다. 다섯 번을 반복하는 이 외부 while 순환문 내에서 do...while은 입력된 각 문자가 영문자인지 확인하는 역할을 한다. 내부 순환문 대신에 isalpha()함수를 사용할 수도 있을 것이다. 데이터를 읽어들이고 나면 add_to_list()가 호출된다. 링크드 리스트의 시작에 대한 포인터와 링크드 리스트에 추가되는 데이터가 함수로 전달된다. main() 함수는 링크드 리스트의 데이터를 출력하기 위해 show_list()를 호출하고, 링크드 리스트에서 링크를 저장하기 위해 할당된 모든 메모리를 해제하는 free_memory_list()를 호출하면 끝난다. 이런 함수들은 비슷한 방법으로 동작한다. 각각은 헤드 포인터인 first를 사용하여 링크드 리스트의 링크드 리스트의 처음에서 시작한다. while 순환문은 특정 링크에 서 next_ptr 값을 사용하여 다음 링크로 진행한다. next_ptr이 NULL과 같을 때 링크드 리스트의 마지막에 도달한 것이므로 함수는 종료된다. 이 리스트에서 가장 중요하고 가장 복잡한 함수는 56번째 줄부터 149번째 줄까지의 add_to_list()이다. 66번째 줄부터 68번째 줄까지는 세 개의 서로 다른 링크를 지적하는 데 사용할 세 포인터를 선언한다. new_rec 포인터는 추가되는 새로운 링크를 지적할 것이다. tmp_rec 포인터는 링크드 리스트에서 기준이 되는 현재 링크를 지적할 것이다. 링크드 리스트에 하나 이상의 링크가 있다면 prev_rec 포인터는 기준이 되는 현재 링크 앞의 링크를 지적하는 데 사용된다.

71번째 줄은 추가되는 새로운 링크를 위한 메모리를 할당한다. new_rec 포인터는 malloc()에 의해 반환되는 값으로 설정된다. 메모리가 할당될 수 없다면 74번째 줄과 75번째 줄은 에러 메시지를 출력하고 프로그램을 마친다. 만약 메모리가 성공적으로 할당되었다면 프로그램은 계속된다.

79번째 줄은 구조체에 이 함수로 전달된 데이터를 저장한다. 이렇게 하기 위해서 단순히 함수로 전달된 문자 ch를 새로운 링크의 문자 필드인 new_rec -> ch로 설정하면 된다. 더 복잡한 프로그램에서는 여러 필드를 설정해야 할 것이다. 80번째 줄은 새로운 링크가 임의의 위치를 지적하지 않도록 next_rec을 NULL로 설정한다.

82번째 줄은 링크드 리스트에 어던 링크가 있는지 확인하면서 '링크 추가' 과정을 시작한다. 만약 헤드 포인터 first가 NULL로 지적되면, 즉 추가되는 링크가 링크드 리스트의 첫 번째 링크이면 헤드 포인터는 단순히 새로운 포인터로 설정되고 작업은 끝난다. 만약 새로운 링크가 처음이 아니면 함수는 87번째 줄의 else 내에서 계속 진행한다.

90번째 줄은 새로운 링크가 링크드 리스트의 시작 부분으로 이동되어야 하는지 확인해본다. 앞에서 배웠듯이 이것은 링크를 추가하는 세 가지 경우의 하나이다. 만약 링크를 처음에 위치시킨다면 92번째 줄은 새로운 링크의 next_rec 포인터가 이전의 '처음' 링크를 지적하게 한다. 그리고 나서 93번째 줄은 포인터 first가 새로운 링크를 지적하게 한다. 이렇게 해서 링크드 리스트의 시작 부분에 새로운 링크가 추가된다. 만약 새로운 링크가 비어 있는 링크드 리스트에 추가되는 첫 번째 링크가 아니고 기존 링크드 리스트의 첫 번째 위치에 추가되는 것도 아니라면 일크드 리스트의 중간이나 마지막에 위치하는 것임을 알 수 있다. 97번째 줄과 98번째 줄은 앞에서 선언한 tmp_rec와 prev_rec 포인터를 설정한다. 포인터 tmp_rec는 링크드 리스트에서 두 번째 링크의 주소로 설정되고, prev_rec는 링크드 리스트에서 첫 번째 링크로 설정된다. 링크드 리스트에 단지 하나의 링크만 있다면 tmp_rec가 NULL과 같아진다는 것에 주의하기 바란다. tmp_rec가 NULL로 설정되는 첫 링크의 next_ptr로 설정되기 때문이다.

102번째 줄은 이런 경우를 확인하고 있다. 만약 tmp_rec가 NULL이면 새로운 링크가 링크드 리스트에 추가되는 두 번째 링크라는 것을 알 수 있다. 새로운 링크가 첫 링크 앞에 위치되지 않는다는 것을 이미 알고 있으므로 마지막 링크가 되는 것이다. 이렇게 하기 위해서 단순히 prev_rec -> next_ptr을 새로운 링크로 설정하면 되고 작업은 끝난다. 만약 tmp_rec 포인터가 NULL이 아니라면 이미 링크드 리스트에 두 개 이상의 링크가 있다는 것을 알 수 있다. 110번째 줄부터 129번째 줄까지에 있는 while 순환문은 새로운 링크가 위치되어야 하는 곳을 결정하기 위해 링크의 나머지 부분을 차례대로 확인한다. 112번째 줄은 새로운 링크의 데이터 값이 현재 지적되는 링크보다 작은지 확인해본다. 만약 데이터 값이 작다면 여기에 링크를 추가하면 된다. 그러나 새로운 링크의 데이터가 현재 링크의 데이터보다 크다면 링크드 리스트의 다음 링크를 살펴볼 필요가 있다. 126번째 줄과 127번째 줄은 포인터 tmp_rec와 next_rec를 다음 링크로 설정한다. 만약 문자가 현재 링크의 문자보다 '작다면' 링크드 리스트의 중간에 링크를 추가하기 위해 앞에서 설명했던 방법을 따르면 된다. 이것은 114번째 줄부터 122번째 줄까지 나타나 있다. 114번째 줄에서 새로운 링크의 next 포인터를 현재 링크의 주소 tmp_rec와 같게 설정한다. 121번째 줄은 이전 링크의 next 포인터가 새로운 링크를 지적하도록 설정한다. 그리고 나서 작업이 끝난다. 코드는 while 순환문을 마치기 위해 break문을 사용한다.

앞에서 설명한 내용은 링크드 리스트의 중간에 추가되는 새로운 링크를 다루는 것이다. 만약 링크드 리스트의 마지막에 도달했다면 110번째 줄부터 129번째 줄까지의 while 순환문 은 링크를 추가하지 않고 끝날 것이다. 132번째 줄부터 144번째 줄까지는 링크를 마지막에 추가하는 작업을 수행한다.

만약 링크드 리스트의 마지막 링크에 도달하면 tmp_rec -> next_rec는 NULL과 같아질 것이다. 132번째 줄은 이것을 확인한다. 134번째 줄은 링크가 마지막 링크의 앞이나 뒤에 위치되어야 하는지 확인한다. 만약 새로운 링크가 마지막 링크 다음으로 가야 한다면 링크의 next_rec를 132번째 줄에서 새로운 링크로 설정하고 새로운 링크의 next 포인터를 142번째 줄에서 NULL로 설정한다.

▶ <리스트 15.13> 수정하기
: 링크드 리스트는 상당히 어려운 주제이다. 그러나 <리스트 15.13>에서 볼 수 있듯이 일정한 순서대로 데이터를 저장하는 가장 좋은 방법이기도 하다. 링크드 리스트에서 어디든지 새로운 데이터 항목을 추가하는 것이 쉬우므로 링크드 리스트로 데이터 항목의 목록을 정렬해서 사용하는 것이 배열을 사용하는 것보다 훨씬 더 간단하다. 앞의 예제는 이름, 전화번호, 다른 어떤 데이터를 정렬하도록 쉽게 수정할 수 있다. 또한, 앞의 프로그램에서는 오름차순(A에서 Z)으로 정렬했지만 내림차순(Z에서 A)으로 정렬하도록 수정하는 것도 어렵지 않다.

▶ 링크드 리스트에서 삭제하기
: 링크드 리스트에 정보를 추가하는 기능은 기본적이지만 가끔 정보를 제거하기 원할 때가 있을 것이다. 링크나 요소를 삭제하는 것은 추가하는 것과 비슷하다. 여러분은 링크드 리스트의 시작, 중간, 마지막에서 링크를 삭제할 수 있다. 각각의 경우에 적절한 포인터를 조절하면 된다. 또한, 삭제된 링크가 차지하고 있던 메모리를 해제시킬 필요가 있다.