연결 리스트의 정의
연결 리스트(Linked List)는 "노드(Node)"라고 불리우는 일종의 상자들의 집합이라 할 수 있습니다. 물리적으로 흩어져있는 자료들을 줄로 연결하여 하나로 묶는 자료구조 형태를 "연결 리스트"라고 합니다.
위의 그림과 같이 노드는 메모리의 어떤 위치에나 있을 수 있습니다. 노드는 "데이터 필드"와 "링크 필드"로 분류됩니다.
데이터 필드에는 우리가 저장하고자 하는 데이터가 들어갑니다. 그림과 같이, "Hi", "How" 등 문자열 자료가 들어갈 수도 있고, 정수와 같은 숫자가 들어갈 수도 있습니다. 링크 필드에는 다른 노드를 가리키는 줄이 저장됩니다. 각 노드를 연결하는 줄은 "포인터"로 구현할 수 있습니다. 이를 통해서 다음 노드로 갈 수 있습니다.
연결 리스트에서는 반드시 첫 번째 노드를 알아야 전체 노드에 접근할 수 있기에, 연결 리스트마다 첫 번째 노드를 가리키는 변수가 필요합니다. 이를 "헤드 포인터"라고 합니다. 그리고 연결 리스트의 마지막 노드의 링크필드에는 NULL 값이 들어가게 되는데 그 이유는 더 이상 연결할 노드가 없기 때문입니다.
연결 리스트의 노드들은 필요할 때마다 "malloc" 함수를 통하여 동적으로 생성됩니다.
연결 리스트의 종류는 다음과 같습니다. "단순 연결 리스트(Singly Linked List)", "이중 연결 리스트(Doubly Linked List)", "원형 연결 리스트(Circular Linked List)" 이들은 링크가 연결되는 방법에 따라 분류한 것들입니다. 이번 시간에는 단순 연결 리스트만 다룰 것입니다.
연결 리스트의 삽입과 삭제
연결 리스트의 삽입과 삭제는 "링크"를 통하여 이루어집니다.
삽입 연산 (Insert)
연결 리스트의 노드 사이에 새로운 노드를 삽입하고자 한다면, 먼저 삽입하고자 하는 위치의 선행 노드를 알아야 합니다. 그림을 통하여 설명하도록 하겠습니다.
- 91이라는 데이터를 가진 선행 노드의 링크는 23 데이터를 가진 노드를 가리키고 있습니다.
- 새로운 노드의 링크를 23 데이터를 가진 노드를 가리키도록 합니다.
- 선행 노드(91)의 링크는 더 이상 23 데이터 노드를 가리키지 않고 새로운 노드를 가리키도록 합니다.
이 과정을 통하여 연결 리스트의 삽입 연산을 진행할 수 있습니다. 새로운 데이터를 삽입한 후, 다른 노드들을 이동시킬 필요가 없다는 것이 연결 리스트의 큰 장점입니다.
삭제 연산 (Delete)
연결 리스트의 삭제 연산은 삽입 연산보다 더 간단합니다. 삽입 연산과 마찬가지로 삭제하고자 하는 위치의 선행 노드를 알아야 합니다.
- 선행 노드의 링크는 삭제하고자 하는 노드를 가리키고 있습니다.
- 선행 노드의 링크는 삭제하고자 하는 노드의 다음 노드를 가리키도록 합니다.
- 그 후 삭제하고자 하는 노드의 링크를 끊습니다.
삽입 연산과 같이 데이터를 삭제한 후, 다른 노드들을 이동시킬 필요가 없다는 것이 연결 리스트의 큰 장점입니다.
단순 연결 리스트 구현
지금부터 단순 연결 리스트를 C언어로 직접 구현해보겠습니다.
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct ListNode { // 노드 타입
element data;
struct ListNode *link;
} ListNode;
// 오류 처리 함수
void error(char *message) {
fprintf(stderr, "%s\n", message);
exit(1);
}
// 첫 번째 노드 삽입 함수
ListNode* insert_first(ListNode *head, int value) {
ListNode *p = (ListNode *)malloc(sizeof(ListNode)); // 동적 메모리 할당
p->data = value;
p->link = head; // 헤드 포인터의 값 복사
head = p; // 헤드 포인터 변경
return head; // 변경된 헤드 포인터 반환
}
// pre 노드 뒤에 새로운 노드 삽입
ListNode* insert(ListNode *head, ListNode *pre, int value) {
ListNode *p = (ListNode *)malloc(sizeof(ListNode)); // 동적 메모리 할당
p->data = value;
p->link = pre->link; // 헤드 포인터의 값 복사
pre->link = p; // 헤드 포인터 변경
return head; // 변경된 헤드 포인터 반환
}
// 첫 번째 노드 삭제 함수
ListNode* delete_first(ListNode *head) {
ListNode *removed;
if (head == NULL) return NULL;
removed = head; // 헤드 포인터의 값을 removed에 복사
head = removed->link; // 헤드 포인터의 값을 removed->link로 변경
free(removed); // 삭제할 노드의 동적 메모리 반환
return head; // 변경될 헤드 포인터 반환
}
// pre 노드의 다음 노드 삭제
ListNode* delete(ListNode *head, ListNode *pre) {
ListNode *removed;
removed = pre->link;
pre->link = removed->link; // pre 노드의 링크 필드가 removed 링크 필드가 가리키는 노드를 가리키도록 변경
free(removed); // 삭제할 노드의 동적 메모리 반환
return head; // 변경될 헤드 포인터 반환
}
// 리스트 출력 함수
void print_list(ListNode *head) {
for (ListNode *p = head; p != NULL; p = p->link)
printf("%d -> ", p->data);
printf("NULL \n");
}
// 테스트 프로그램
int main() {
ListNode *head = NULL;
for (int i = 0; i < 5; i++) {
head = insert_first(head, i); // insert_first()가 반환된 헤드 포인터를 head에 대입
print_list(head);
}
for (int i =0; i < 5; i++) {
head = delete_first(head);
print_list(head);
}
return 0;
}