[Data Structure] Singly Linked List (2)

지난 포스트에서 단일 연결 리스트의 소개와 배열과 비교했을때의 차이에 대해서 간략하게 적었다. 그 때 다뤘던 내용을 바탕으로 C 코드를 작성해보고자 한다. 우선 지난 포스트에서 소개한 것에 더 추가해 이해에 쉽게끔 몇가지 개념을 추가로 구현하려고 한다.

 - head/tail node : 이전에도 설명했다시피 연결 리스트의 시작과 끝을 나타내는 요소이다. 단 이 요소들은 목적이 단순히 시작과 끝을 나타내는 것이기 때문에 데이터를 저장하지는 않는다.

 - head/tail pointer : 말그대로 첫번째와 마지막 요소를 가리키는 포인터다.

 - node count : 연결 리스트내에서 실제로 데이터를 가지고 있는 요소의 갯수를 나타낸 것인데, 만약 연결 리스트를 삭제할때나 뭔가 탐색을 할때 사용할 수 있다.

 우선 개념적으로 봤을때 정의가 필요한 요소는 연결리스트를 구성하는 요소(Node)와 전체 연결리스트에 대한 구조체 정의가 필요하고, 요소에는 요소 자체가 가지는 데이터와 다음 요소를 가리키는 next 포인터가 필요할 것이다. 또한 앞에서 설명한 head와 tail node를 가리키는 pointer를 전체 연결 리스트가 가지고 있어야 할 것이고, 얼마나 유효한 데이터 크기가 있는지를 나타내는 정보도 연결리스트 구조체에 담겨있어야 한다. 그 내용은 다음과 같다.

typedef struct _node Node;
 
struct _node{
    int data;            // data
    Node *next;            // next pointer
};
 
typedef struct _list{
    Node *head;            // head pointer
    Node *tail;            // tail pointer
    int size;            // size of linked list
}List;

 이제 연결리스트가 정상적으로 동작하기 위한 함수가 어떤게 있는지를 정의할 수 있어야 한다. 물론 이렇게 정의한 함수는 header file에 prototype 형식으로 넣을 수 있어야 한다.

 큰 맥락에서 가장 중요한 기능은 추가/삭제/탐색/출력 정도이고, 덧붙이면 추가를 head node의 다음에 하느냐, 혹은 tail node의 바로 앞에 할 것이냐의 기능도 추가할 수 있을 것이다. 또한 연결 리스트내의 구성물을 정렬하는 것도 필요한 기능이 되겠다. 그래서 크게 정의한 기능과 함수의 원형은 다음과 같다.

typedef struct _node Node;
 
struct _node{
    int data;            // data
    Node *next;            // next pointer
};
 
typedef struct _list{
    Node *head;            // head pointer
    Node *tail;            // tail pointer
    int size;            // size of linked list
}List;
 
int createList(List *lp);
int insertFirst(List *lp, int data);
int insertLast(List *lp, int data);
int removeNode(List *lp, int data);
Node *searchNode(List *lp, int data);
 
void sortList(List *lp);
void showList(List *lp);
void removeList(List *lp);

 위의 내용들이 header에 들어갈 내용이다. 이제 source code에서 원형을 구현해주면 된다.

createList의 구현은 다음과 같다.

#include <stdio.h>
#include <stdlib.h>
 
#include "sll.h"
 
int createList(List *lp)
{
    if(lp == NULL){
        return -1;
    }
 
    lp->head = (Node *)malloc(sizeof(Node));
    if(lp->head == NULL){
        return -1;
    }
 
    lp->tail = (Node *)malloc(sizeof(Node));
    if(lp->tail == NULL){
        free(lp->head);
        return -1;
    }
 
    lp->head->next = lp->tail;
    lp->tail->next = lp->tail;
    lp->size = 0;
 
    return 0;
}

 line 8~10 : 우리는 우선 Linked List를 만들기 위한 함수의 인자로 어떤 포인터를 받아오게끔 했다. 포인터의 의미는 잘 알겠지만, 메모리 상에서 원하는 데이터가 저장된 주소를 찾는 것일텐데, 이 값이 NULL이라는 의미는 데이터가 저장된 주소가 NULL이라는 뜻일 것이고, 보통 시스템은 해당 영역은 접근 불가능한 영역으로 지정하고, 여기에 접근할 경우 exception을 발생시킨다.(NULL pointer exception) 대부분의 경우라면 이 조건 구문을 넘어가겠지만, 만에 하나 해당 주소가 NULL로 할당되는 심각한 오류를 방지하기 위해서 위와 같은 조건 구문을 삽입한다. 보통 포인터를 인자로 받는 함수라면 이런 예외처리를 필요하다고 생각한다.
(추가로 궁금한 사람은 Null pointer에 대한 설명을 참고하면 좋을거 같다.)

 line 12~14 : 이전 이론에서도 설명했다시피 우리가 Linked List를 생성할 때 만들어야 할 것은 데이터를 갖고 있지 않은 head와 tail node를 만드는 것이다. 그리고 그 Node는 데이터와 다음 Node를 가리키는 포인터를 가지고 있어야 하는데, 일반적으로 Memory 상에 해당 구조체 만큼의 메모리 영역을 할당받아 그곳에 저장한다. 이때 malloc이란 c function이 사용되었는데, 메모리에서 정상적으로 size만큼의 영역을 할당받았을 경우 할당된 영역의 첫번째 주소를 반환한다. 역시 이 값이 NULL이라는 의미는 정상적으로 할당이 되지 않았다는 의미이므로 예외 처리를 해줘야 한다.

 line 17~19 : 12~14 줄과 동일하게 tail node를 생성하는 과정인데, NULL일 경우 처리되는 과정이 한가지 더 추가되어 있다. 가령 tail에 대해서 할당을 못받았을 경우를 가정하면, 해당 상황은 이미 head node를 할당 받은 상황이 된다. Memory management의 원칙 중 하나는 반드시 할당 받은 영역은 빠져나가기 전에 free를 통해서 할당받은 메모리를 해제시켜줘야 한다는 것이고, 지금 이 과정은 앞에서 할당받은 head node를 해제시켜주는 처리구문이 되겠다.

 line 23~25 : 여기까지 오면 적어도 Linked List의 head Node와 tail Node는 생성된 상태이다. 하지만 이론에서도 언급한 바와 같이 현재 상태는 데이터 Node가 포함되어 있지 않은 상태이다. 결국 Linked List의 제일 첫번째 Node인 head는 바로 다음 Node로써 tail을 가리키는 것이다. 그리고 Linked List의 구현 방법에 따라서 Tail Node의 Next Node를 NULL로 처리할 수도 있지만 여기서는 자기 자신을 가리키는 것으로 처리 되었다. 
 그리고 마지막으로 현재 data node가 없는 상태이므로 linked list의 size는 0이 된다.