연결 리스트 (Linked List)
또 다른 리스트 구현 방법
동적 배열로 구현한 리스트에서는 리스트의 개념과 동적 배열을 이용한 구현 방법을 살펴보았다.
동적 배열로 구현한 리스트는 원소를 연속된 메모리 공간에 저장한다.
저장 공간이 부족하면 더 큰 배열을 새로 할당하고 기존 원소를 복사해 공간을 늘린다.
이런 저장 방식 덕분에 인덱스로 원소에 빠르게 접근할 수 있지만, 삽입하거나 삭제할 때는 위치에 따라 기존 원소를 옮겨야 한다.
연결 리스트(Linked List)는 원소를 메모리에 연속해서 저장하지 않고, 원소를 담은 각 노드(Node)를 서로 연결해 리스트를 구현한다.
연결 리스트는 노드를 연결하는 방향에 따라 여러 방식으로 구현할 수 있다.
각 노드가 다음 노드만 가리키는 방식을 단방향 연결 리스트(Singly Linked List)라고 한다.
각 노드가 이전 노드와 다음 노드를 모두 가리키는 방식을 양방향 연결 리스트(Doubly Linked List)라고 한다.
이 글에서는 단방향 연결 리스트 중에서도 더미 노드를 사용하는 방식으로 리스트를 구현한다.
동적 배열로 구현한 리스트와 연결 리스트로 구현한 리스트는 원소 접근, 삽입, 삭제, 순회와 같은 주요 연산을 같은 인터페이스로 제공한다.
따라서 main 함수에서 포함하는 헤더 파일만 array_list.h에서 linked_list.h로 바뀌었을 뿐, 리스트 함수를 호출하는 부분은 이전 글과 거의 같다.
그러나 같은 연산이라도 내부에서 처리하는 방식과 시간 복잡도는 달라진다.
또한 연결 리스트에는 배열의 용량에 해당하는 개념이 없으므로, 현재 할당된 배열의 용량을 확인하던 list_capacity 함수도 사라졌다.
먼저 소스 코드를 확인한 뒤, 연결 리스트의 구조에 대해 더 알아보자.
소스 코드
아래 코드는 학습용 코드로, 핵심 동작에 집중하기 위해 메모리 할당이 성공하고 각 함수가 올바른 순서로 호출된다고 가정한다.
main.c
#include <stdio.h>
#include <stdlib.h>
#include "linked_list.h"
void print_list(List* list)
{
ListData data;
printf("List (size: %d)\n", list_size(list));
printf(" data: ");
if (list_first(list, &data))
{
printf("%d", data);
while (list_next(list, &data))
printf(", %d", data);
}
printf("\n");
}
int main(void)
{
List list;
ListData data;
/* 1. Initialize the list. */
list_init(&list);
printf("1) Empty list\n");
print_list(&list);
/* 2. Append data. */
list_append(&list, 10);
list_append(&list, 20);
list_append(&list, 30);
list_append(&list, 40);
printf("\n2) After appending 10, 20, 30, and 40\n");
print_list(&list);
/* 3. Prepend data and insert data at a specified index. */
list_prepend(&list, 5);
list_insert_at(&list, 3, 25);
printf("\n3) After prepending 5 and inserting 25 at index 3\n");
print_list(&list);
/* 4. Read data by index. */
if (list_get(&list, 3, &data))
{
printf("\n4) Data at index 3: %d\n", data);
}
/* 5. Remove data by index and receive the removed value. */
if (list_remove_at(&list, 2, &data))
{
printf("\n5) Removed data at index 2: %d\n", data);
print_list(&list);
}
/* 6. Iterate with the cursor and remove every value of 30 or greater. */
if (list_first(&list, &data))
{
do
{
if (data >= 30)
{
list_remove_current(&list, &data);
}
}
while (list_next(&list, &data));
}
printf("\n6) After removing values greater than or equal to 30\n");
print_list(&list);
/* 7. Release the dynamically allocated memory. */
list_destroy(&list);
return EXIT_SUCCESS;
}linked_list.h
#ifndef LINKED_LIST_H
#define LINKED_LIST_H
typedef int ListData;
typedef struct Node
{
ListData data;
struct Node* next;
} Node;
typedef struct LinkedList
{
Node* head;
Node* tail;
Node* previous;
Node* current;
int size;
} LinkedList;
typedef LinkedList List;
int list_init(List* list);
void list_destroy(List* list);
int list_size(const List* list);
/* Insertion operations */
int list_prepend(List* list, ListData data);
int list_append(List* list, ListData data);
/* Index-based operations */
int list_get(const List* list, int index, ListData* out_data);
int list_insert_at(List* list, int index, ListData data);
int list_remove_at(List* list, int index, ListData* out_data);
/* Cursor-based iteration */
int list_first(List* list, ListData* out_data);
int list_next(List* list, ListData* out_data);
int list_remove_current(List* list, ListData* out_data);
#endif /* LINKED_LIST_H */linked_list.c
#include <stdlib.h>
#include "linked_list.h"
int list_init(List* list)
{
if (list == NULL)
return 0;
list->head = (Node*)malloc(sizeof(Node));
if (list->head == NULL)
return 0;
list->head->next = NULL;
list->tail = list->head;
list->previous = NULL;
list->current = NULL;
list->size = 0;
return 1;
}
void list_destroy(List* list)
{
Node* current;
Node* next;
if (list == NULL)
return;
current = list->head;
while (current != NULL)
{
next = current->next;
free(current);
current = next;
}
list->head = NULL;
list->tail = NULL;
list->previous = NULL;
list->current = NULL;
list->size = 0;
}
int list_size(const List* list)
{
return list->size;
}
int list_prepend(List* list, ListData data)
{
Node* new_node = (Node*)malloc(sizeof(Node));
if (new_node == NULL)
return 0;
new_node->data = data;
new_node->next = list->head->next;
list->head->next = new_node;
if (list->size == 0)
list->tail = new_node;
list->size++;
return 1;
}
int list_append(List* list, ListData data)
{
Node* new_node = (Node*)malloc(sizeof(Node));
if (new_node == NULL)
return 0;
new_node->data = data;
new_node->next = NULL;
list->tail->next = new_node;
list->tail = new_node;
list->size++;
return 1;
}
int list_get(const List* list, int index, ListData* out_data)
{
if (index < 0 || index >= list->size)
return 0;
const Node* node = list->head->next;
for (int i = 0; i < index; i++)
node = node->next;
*out_data = node->data;
return 1;
}
int list_insert_at(List* list, int index, ListData data)
{
if (index < 0 || index > list->size)
return 0;
Node* new_node = (Node*)malloc(sizeof(Node));
if (new_node == NULL)
return 0;
Node* prev_node = list->head;
for (int i = 0; i < index; i++)
prev_node = prev_node->next;
new_node->data = data;
new_node->next = prev_node->next;
prev_node->next = new_node;
if (index == list->size)
list->tail = new_node;
list->size++;
return 1;
}
int list_remove_at(List* list, int index, ListData* out_data)
{
if (index < 0 || index >= list->size)
return 0;
Node* prev_node = list->head;
for (int i = 0; i < index; i++)
prev_node = prev_node->next;
Node* target_node = prev_node->next;
prev_node->next = target_node->next;
if (target_node == list->tail)
list->tail = prev_node;
*out_data = target_node->data;
free(target_node);
list->size--;
return 1;
}
int list_first(List* list, ListData* out_data)
{
if (list->head->next == NULL)
return 0;
list->previous = list->head;
list->current = list->head->next;
*out_data = list->current->data;
return 1;
}
int list_next(List* list, ListData* out_data)
{
if (list->current->next == NULL)
return 0;
list->previous = list->current;
list->current = list->current->next;
*out_data = list->current->data;
return 1;
}
int list_remove_current(List* list, ListData* out_data)
{
Node* del_node = list->current;
*out_data = del_node->data;
if (del_node == list->tail)
list->tail = list->previous;
list->previous->next = del_node->next;
list->current = list->previous;
free(del_node);
list->size--;
return 1;
}연결 리스트의 구조
코드에서 먼저 살펴볼 부분은 구조체 Node의 정의다.
typedef struct Node
{
ListData data;
struct Node* next;
} Node;처음 보면 Node를 정의하는 중에 다시 Node가 등장하는 것처럼 보여 낯설게 느껴질 수 있다.
하지만 next가 저장하는 것은 Node 자체가 아니라 Node의 주소를 담는 struct Node*이다.
만약 next가 포인터가 아니라 Node 자체를 저장한다면 하나의 Node 안에 다른 Node가 끝없이 포함되는 모양이 된다.
Node
├─ data
└─ Node
├─ data
└─ Node
...이런 구조체는 크기를 결정할 수 없으므로 멤버로 선언할 수 없고, 결국 컴파일 오류가 발생한다.
반면 포인터의 크기는 가리키는 자료형의 크기와 관계없다.
예를 들어 char는 1바이트지만 char*의 크기는 char의 크기와 관계없이 프로그램이 실행되는 환경에 따라 달라진다.
일반적으로 포인터는 32비트 환경에서 4바이트, 64비트 환경에서 8바이트를 차지한다.
따라서 struct Node의 정의가 완료되기 전에도 struct Node*의 크기는 알 수 있으므로 이를 멤버로 선언할 수 있다.
배열은 원소를 하나의 연속된 메모리 공간에 저장한다.
따라서 공간을 할당할 때 그 공간이 어디까지 이어질지 정하기 위해 배열의 크기를 지정해야 한다.
반면 연결 리스트는 전체 크기를 미리 정하지 않고 필요할 때마다 Node를 하나씩 만든다.
각 Node가 배열의 원소처럼 연속된 메모리 공간에 배치된다는 보장은 없다.
대신 각 Node의 next에 다음 Node의 주소를 저장해 서로 연결한다.
Node Node Node
+------+-------+ +------+-------+ +------+-------+
| data | next +---->| data | next +---->| data | next +----> NULL
+------+-------+ +------+-------+ +------+-------+동적 배열은 새로운 원소를 빠르게 추가할 수 있도록 현재 저장된 데이터보다 더 큰 공간을 할당해 두는 경우가 많다.
반면 연결 리스트는 데이터가 추가될 때마다 Node를 하나씩 할당하므로 동적 배열처럼 미리 확보해 둔 여유 공간이 생기지 않는다.
동적 배열의 실제 메모리 사용량은 할당된 용량에 따라 달라지므로 연결 리스트와 단순하게 비교하기는 어렵다.
다만 배열의 용량과 저장된 데이터의 수가 같다면, 연결 리스트는 각 Node에 ListData data뿐만 아니라 다음 노드를 가리키는 Node* next도 저장하므로 배열보다 더 많은 메모리를 사용한다.
시간 복잡도
연결 리스트는 필요한 연산과 사용 목적에 따라 다양한 방식으로 구현할 수 있다.
여기서는 head와 tail을 모두 관리하는 단방향 연결 리스트의 시간 복잡도를 다룬다.
접근
list_get 함수는 지정한 인덱스의 값을 조회한다.
동적 배열에 저장된 값은 메모리에 연속해서 배치되지만, 연결 리스트의 각 Node는 그렇지 않다.
따라서 더미 Node의 next가 가리키는 첫 번째 Node부터 시작해 원하는 인덱스의 Node에 도달할 때까지 next를 따라가야 한다.
첫 번째 Node가 저장한 값은 O(1)의 시간에 조회할 수 있지만, 뒤쪽 인덱스의 값일수록 더 많은 Node를 거쳐야 한다.
그러므로 인덱스로 값을 조회하는 시간 복잡도는 최선의 경우 O(1), 평균과 최악의 경우 O(n)이다.
삽입
연결 리스트는 삽입 위치에 따라 접근해야 하는 Node와 갱신해야 하는 포인터가 달라진다.
맨 앞에 삽입
Before insertion:
head tail
| |
v v
[dummy node] ---> [first node] ---> ... ---> [last node] ---> NULL
After insertion:
head tail
| |
v v
[dummy node] ---> [new_node] ---> [old first node] ---> ... ---> [last node] ---> NULLnew_node의 next가 기존의 첫 번째 Node를 가리키게 한 뒤 head의 next가 new_node를 가리키도록 바꾼다.
head를 통해 삽입할 위치에 바로 접근할 수 있으므로 시간 복잡도는 O(1)이다.
중간에 삽입
예를 들어 네 개의 값 A, B, C, D를 각각 저장한 노드가 연결되어 있다고 가정하자.
인덱스 2에 있는 노드 앞에 새 노드를 삽입한다.
새 노드는 기존 C 노드가 있던 자리에 삽입되어 B 노드와 C 노드 사이에 연결된다.
Before insertion:
head tail
| |
v v
[dummy node] ---> [0: A] ---> [1: B] ---> [2: C] ---> [3: D] ---> NULL
After insertion:
head tail
| |
v v
[dummy node] ---> [0: A] ---> [1: B] ---> [2: new_node] ---> [3: C] ---> [4: D] ---> NULLnew_node의 next가 C를 저장한 Node를 가리키게 한 뒤, B를 저장한 Node의 next가 new_node를 가리키도록 바꾼다.
각 Node의 논리적인 위치를 인덱스로 나타내면 삽입 후 C와 D를 저장한 Node의 인덱스는 하나씩 증가한다.
이는 삽입으로 각 Node의 논리적인 위치가 달라진 것일 뿐, 동적 배열처럼 기존 값을 다른 메모리 위치로 옮기는 작업이 일어난 것은 아니다.
삽입할 위치 앞의 Node를 알고 있다면 두 next 포인터만 바꾸면 되므로 삽입 자체는 O(1)에 동작한다.
하지만 삽입할 위치 앞의 Node를 모른다면 head부터 next를 따라가며 찾아야 한다.
따라서 삽입할 위치를 찾는 과정까지 포함한 시간 복잡도는 평균과 최악의 경우 O(n)이다.
맨 뒤에 삽입
Before insertion:
head tail
| |
v v
[dummy node] ---> ... ---> [last node] ---> NULL
After insertion:
head tail
| |
v v
[dummy node] ---> ... ---> [old tail node] ---> [new_node] ---> NULL기존의 마지막 Node의 next가 new_node를 가리키게 한 뒤 tail을 new_node로 바꾼다.
tail을 통해 삽입할 위치에 바로 접근할 수 있으므로 시간 복잡도는 O(1)이다.
삭제
연결 리스트는 삭제 위치에 따라 접근해야 하는 Node와 갱신해야 하는 포인터가 달라진다.
맨 앞에서 삭제
Before deletion:
head tail
| |
v v
[dummy node] ---> [del_node] ---> [next node] ---> ... ---> [last node] ---> NULL
After deletion:
head tail
| |
v v
[dummy node] ---> [next node] ---> ... ---> [last node] ---> NULLhead의 next가 del_node의 next가 가리키는 Node를 가리키도록 바꾼 뒤 del_node를 메모리에서 해제한다.
head를 통해 삭제할 위치에 바로 접근할 수 있으므로 시간 복잡도는 O(1)이다.
중간에서 삭제
예를 들어 네 개의 값 A, B, C, D를 각각 저장한 노드가 연결되어 있다고 가정하자.
인덱스 2에 있는 노드를 삭제한다.
Before deletion:
head tail
| |
v v
[dummy node] ---> [0: A] ---> [1: B] ---> [2: C] ---> [3: D] ---> NULL
After deletion:
head tail
| |
v v
[dummy node] ---> [0: A] ---> [1: B] ---> [2: D] ---> NULLB를 저장한 Node의 next가 D를 저장한 Node를 가리키게 한 뒤 C를 저장한 Node를 메모리에서 해제한다.
삭제할 위치 앞의 Node를 알고 있다면 next 포인터 하나만 바꾸면 되므로 삭제 자체는 O(1)에 동작한다.
하지만 삭제할 위치 앞의 Node를 모른다면 head부터 next를 따라가며 찾아야 한다.
따라서 삭제할 위치를 찾는 과정까지 포함한 시간 복잡도는 평균과 최악의 경우 O(n)이다.
맨 뒤에서 삭제
Before deletion:
head tail
| |
v v
[dummy node] ---> ... ---> [prev_node] ---> [del_node] ---> NULL
After deletion:
head tail
| |
v v
[dummy node] ---> ... ---> [prev_node] ---> NULLprev_node의 next를 NULL로 바꾼 뒤 tail을 prev_node로 바꾸고 del_node를 메모리에서 해제한다.
tail을 통해 삭제할 위치에 바로 접근할 수 있지만, 단방향 연결 리스트에서는 prev_node로 이동할 수 없다.
따라서 head부터 next를 따라 prev_node를 찾아야 하므로 시간 복잡도는 O(n)이다.