C언어로 자료구조 만들기 - 링크드 리스트(Linked List)

이번에는 지난 포스트에 이어서 C언어로 자료구조를 구현해볼 텐데, 이번에는 링크드 리스트다. 양 옆으로 삽입과 삭제가 가능한 양방향 링크드 리스트를 구현하고, 또한 중간에 데이터를 삽입과 삭제가 가능하도록 만든다.

링크드 리스트(Linked List)

링크드 리스트는 정적 배열과 데크와는 다르게 주소값을 서로 연결하여 구성되어 있다. 따라서 메모리 공간이 연속으로 구성되어 있지는 않으며 독립적으로 구성하되, 대신 다음과 이전 주소를 노드에 저장하여 다음 노드와 이전 노드에 접근할 수 있도록 논리적으로 연결된 구조로 표현한다. 

 

Node.h

링크드 리스트에는 노드가 필요하다. 배열처럼 인덱싱을 통해 바로 값을 넣지 않는다. 노드에는 값, 이전 노드의 주소값, 다음 노드의 주소값이 들어가며 이는 구조체로 표현한다.

 

create_node() 함수를 통해 노드를 생성하고 돌려줄 수 있다. 이 함수는 링크드 리스트를 포함한 여러 자료구조에서 사용할 것이다.

typedef struct __Node__ Node;

typedef struct __Node__ {
  Node* prev;
  void* element;
  Node* next;
} Node;

Node* create_node(void*);

/**
 * Create a Node
 *
 * @public
 */
Node* create_node(void* element) {
  Node* node = (Node*) malloc(sizeof(Node));
  node->next = NULL;
  node->element = element;
  node->prev = NULL;

  return node;
}

List

정적 배열 및 데크처럼 가변인자를 통해 데이터를 받을 수 있다. 그러나 이 녀석의 사이즈는 배열의 사이즈와는 다르며 자료구조의 논리적 길이의 불과하다. 값을 넣을 때는 아래에서 언급하게 될 ls_push_back() 함수를 사용한다.

typedef struct __List__ {
  size_t length;

  Node* front;
  Node* back;
} List;

List list(size_t size, ...);

/**
 * Create Linked List
 *
 * @public
 */
List list(size_t size, ...) {
  List ls = { .length = 0, .front = NULL, .back = NULL };
  va_list ap;
  va_start(ap, size);
  for (int i = 0; i < size; i++) {
    ls_push_back(&ls, va_arg(ap, void*));
  }
  va_end(ap);
  return ls;
}

ls_*

링크드 리스트를 위해 구현하게 될 함수는 다음과 같으며 모든 함수를 다 살펴본다. 다음 자료구조는 큐, 스택인데 그것은 링크드 리스트를 기반으로 만들 것이기 때문에 그만큼 분량이 줄어든다. 앞, 뒤, 특정 위치에 값을 넣고 삭제, 반복자로 순회할 수 있고, 링크드 리스트를 비울 수 있다.

void  ls_push_front(List*, void*);
void  ls_pop_front(List*);
void  ls_push_back(List*, void*);
void  ls_pop_back(List*);

void  ls_insert(List*, Node*, void*);
void  ls_erase(List*, Node*);

Node* ls_at(List*, void*);
void  ls_clear(List*);

Node* ls_begin(List*);
Node* ls_end(List*);
Node* ls_next(Node*);
Node* ls_prev(Node*);

int   ls_done(Node*);

ls_push_front(List*, void*), ls_pop_front(List*, void*)

링크드 리스트의 제일 앞에 값을 추가하고 삭제한다. 제일 앞에 값을 추가하는 행위는 노드를 하나 생성하고, 기존의 제일 앞에 있던 노드의 주소값을 현재 추가할 노드의 next 에 추가하고, 기존의 노드의 prev 에 새로 추가할 노드의 주소값을 넣어주면 된다. 그러니까 코드를 보자. 리스트가 비어있는 상태라면 뒤에 노드를 추가한다.

 

/**
 * Push new node at Front
 *
 * @public
 */
void ls_push_front(List* list, void* element) {
  Node* node = create_node(element);
  if (list->front != NULL) {
    node->next = list->front;
    node->prev = NULL;
    list->front->prev = node;
  } else if (list->front == NULL && list->back == NULL) {
    list->back = node;
  }
  list->front = node;
  list->length++;
}

/**
 * Remove node at Front
 *
 * @public
 */
void ls_pop_front(List* list) {
  Node* node = list->front;
  if (list->front->next != NULL) {
    list->front = list->front->next;
    list->front->prev = NULL;
  } else {
    list->back = NULL; list->front = NULL;
  }
  free(node);
  list->length--;
}

값을 삭제하는 상황에서는 노드를 생성하는 것이 아니므로 맨 앞의 노드를 가져온다. 삭제하려는 노드의 다음이 존재한다면 front 를 해당 노드와 변경하고 prev 값을 NULL 로 변경한다. 만약에 노드가 하나 뿐이라면 값을 NULL 로 초기화하고 메모리를 해제한다.

 

데크랑 비교해보라. 데크보다 코드의 길이는 길지만, 연산의 횟수가 다르다. 즉, 링크드 리스트는 데이터의 삽입과 삭제에서 배열 기반 자료구조보다 탁월한 성능을 보인다.

ls_push_back(List*, void*), ls_pop_back(List*, void*)

링크드 리스트의 뒤에서 작업을 하기 위해서 할 일도 사실 앞에서 하는 것과 유사하다. 차이가 있다면 front 에서 처리하던 것을 back 에서 처리한다는 점이다.

 

값을 추가하는 상황에서 기존의 리스트에 노드가 있다면 그 노드는 현재 생성한 노드의 이전 노드가 될 것이므로 포인터를 수정한다. 기존 노드의 다음 노드로 생성한 노드를 지정하고, 마지막으로 링크드 리스트의 마지막 노드를 생성한 노드로 바꿔준다.

/**
 * Push new node at Back
 *
 * @public
 */
void ls_push_back(List* list, void* element) {
  Node* node = create_node(element);
  if (list->back != NULL) {
    node->prev = list->back;
    node->next = NULL;
    list->back->next = node;
  } else if (list->front == NULL && list->back == NULL) {
    list->front = node;
  }
  list->back = node;
  list->length++;
}

/**
 * Remove node at Back
 *
 * @public
 */
void ls_pop_back(List* list) {
  Node* node = list->back;
  if (list->back->prev != NULL) {
    list->back = list->back->prev;
    list->back->next = NULL;
  } else {
    list->back = NULL; list->front = NULL;
  }
  free(node);
  list->length--;
}

값을 삭제할 때는 맨 뒤의 노드를 얻어오고, 기존 리스트의 맨 뒤의 노드를 더 이전의 노드로 변경한뒤, 가져왔던 노드의 메모리를 해제한다.

 

ls_insert(List*, Node*, void*), ls_erase(List*, Node*)

링크드 리스트에서 삽입과 삭제를 할 떄 살펴봐야 할 점은, 특정 위치를 지우는 것이 아니라, 특정 노드를 지우는 것이다. 메모리의 주소 자체는 독립적으로 존재하고 있으므로 위치를 특정하여 지우는 것을 할 수 없다. 즉, 배열처럼 인덱싱을 해서 다이렉트로 접근할 수는 없다.

 

하지만 삽입과 삭제를 할 때 링크드 리스트의 장점이 발휘되는데, 바로 연결된 포인터만 바꿔주면 아주 간편하다는 점이다. 앞과 뒤가 아닌 중간에서 삽입과 삭제를 하더라도 포인터랑 바꿔주면 된다.

/**
 * Insert new node at before the node
 *
 * @public
 */
void ls_insert(List* list, Node* iter, void* element) {
  if (iter == list->front) {
    ls_push_front(list, element);
  } else {
    Node* node = create_node(element);

    node->prev = iter->prev;
    node->next = iter;
    iter->prev->next = node;
    iter->prev = node;
    list->length++;
  }
}

/**
 * Remove node
 *
 * @public
 */
void ls_erase(List* list, Node* iter) {
  if (iter == list->front) {
    ls_pop_front(list);
  } else if (iter == list->back) {
    ls_pop_back(list);
  } else {
    iter->prev->next = iter->next;
    iter->next->prev = iter->prev;

    free(iter);
    list->length--;
  }
}

링크드 리스트에 데이터를 넣을 때, 현재 노드의 앞쪽에 넣는데 iter 파라매터는 바로 뒤의 노드를 지정한다. 링크드 리스트의 맨 앞의 노드와 넣으려는 노드가 동일 한 경우, 맨 앞에 노드를 새로 생성해서 넣어주고, 그렇지 않은 경우 노드를 새로 생성하여 iter 의 앞 쪽에 넣는다.

 

값을 삭제할 때는 파라매터로 넘어오는 노드를 삭제하게 된다. 맨 앞과 맨 뒤라면 ls_pop_front(), ls_pop_back() 등으로 처리하고 그렇지 않다면 포인터를 바꿔주고 메모리를 해제한다.

ls_clear(List*)

이 함수는 링크드 리스트를 비운다. 맨 앞에서 비워도 되고 맨 뒤에서부터 비워도 된다. 중요한 것은 모든 노드의 메모리가 해제되어야 한다는 점이다.

/**
 * Clear Linked List
 *
 * @public
 */
void ls_clear(List* list) {
  size_t s = list->length;
  for (size_t i = 0; i < s; i++) {
    ls_pop_back(list);
  }
}

ls_begin(List*), ls_next(List*), ls_end(List*), ls_prev(List*), ls_done(Node*)

리스트의 반복자의 구현은 다음과 같다. 함수는 많지만 내용이 아주 간단해서 설명이 필요없을 정도다.

/**
 * Get front node
 *
 * @public
 */
Node* ls_begin(List* list) {
  return list->front;
}

/**
 * Get next node
 *
 * @public
 */
Node* ls_next(Node* iter) {
  return iter->next;
}

/**
 * Get back node
 *
 * @public
 */
Node* ls_end(List* list) {
  return list->back;
}

/**
 * Get prev node
 *
 * @public
 */
Node* ls_prev(Node* iter) {
  return iter->prev;
}

/**
 * is Done
 *
 * @public
 */
int ls_done(Node* iter) {
  if (iter == NULL) {
    return 1;
  }
  return 0;
}

ls_at(void*)

링크드 리스트에서 특정 값을 가진 노드를 찾는다. 반복자를 먼저 소개한 이유는, 여기서 반복자를 사용하여 노드를 검색하기 때문이다. 배열기반과 차이점이 보이는가? 배열은 그냥 인덱스로 접근하면 되지만 링크드 리스트는 순차 탐색하여 하나하나 검증한다. 그래서 링크드 리스트는 검색이 느리다.

/**
 * Get node with element
 *
 * @public
 */
Node* ls_at(List* list, void* element) {
  for (Node* iter = ls_begin(list); 1 != ls_done(iter); iter = ls_next(iter)) {
    if (iter->element == element) {
      return iter;
    }
  }
  return NULL;
}

어떻게 사용해볼까?

링크드 리스트의 사용하는 방법 그 자체는 단순하기 때문에 값을 추가해서 반복자로 돌며 마지막에는 노드를 전부 정리하는 예제로 포스트를 마무리한다.

List ls = list(1, "Hello, world!");
ls_push_front(&ls, "Example");

for (Node* iter = ls_begin(&ls); 1 != ls_done(iter); iter = ls_next(iter)) {
  // Example
  // Hello, world!
  printf("%s", (const char*) iter->element);
}

ls_clear(&ls);

더 읽을거리

C언어로 자료구조 만들기 - 트리(BST, Binary Search Tree)

C언어로 자료구조 만들기 - 큐(Queue), 스택(Stack)

C언어로 자료구조 만들기 - 정적 배열(Fixed Array), 데크(Deque)