연결리스트(Linked list) 란?
구조체를 활용한 연결 리스트(Linked list using structure)
연결 리스트에 대해 알아보기 전에 이것을 왜 사용하는지 부터 알아보도록 하겠습니다. 이전에 정적 메모리...
blog.naver.com
연결 리스트를 왜 배우는가에 대한 내용은 위 포스팅을 참조해주시면 됩니다. 연결 리스트(Linked List) 란 노드가 연결되어 있는 구조로 각 노드는 데이터와 포인터를 가집니다. 즉 각 노드가 데이터와 포인터를 가지고 연결되어 있는 방식으로 데이터를 저장하는 자료구조 를 연결 리스트 라고 합니다.
맨 처음의 노드는 head 포인터가 가리키고 있으며, 다음 노드를 가리키는 포인터는 다음 노드의 데이터의 주소를 값으로 가집니다.
단순 연결리스트 (Singly Linked list)
연결리스트 중에서 한 방향으로만 연결이 되어 있는, 위의 예시와 같은 연결 리스트를 단순 연결리스트라고 합니다. 단점이 많지만 가장 단순한 연결리스트이므로 한번 구현해보면서 연결리스트를 이해해보도록 합시다.
노드의 구성
typedef int element;
typedef struct Node { // 노드 타입을 구조체로 정의
element data;
struct Node* next;
};먼저 노드의 구성입니다. int 를 굳이 element 로 나눠서 쓴 이유는 데이터의 종류가 바뀔 때 구조체가 아니라 element 만 바꿔서 사용할 수 있게 한 겁니다. 각 노드는 저장할 데이터와 다음 노드를 가리키는 포인터로 이루어져 있습니다.
연결리스트의 초기화 ( init )
Node* head;
void init() {
head = NULL;
}첫번째 노드를 가리킬 포인터인 head 포인터를 전역 변수로 선언하고 init() 함수를 통해 NULL 포인터로 초기화 할 수 있게 합니다. 굳이 이렇게 함수로 안하고 main 함수 내에서 Node* head = NULL; 로 입력해도 됩니다.
연결리스트의 삽입 ( insert )
연결 리스트에서는 삽입과 삭제 연산을 이해하는 것이 메인이라고 할 정도로 중요합니다. 노드를 삽입하는 방법부터 구현해볼 건데
1. 가장 앞에 노드를 삽입 하는 경우
2. 맨 뒤에 노드를 삽입하는 경우
3. 중간에 노드를 삽입하는 경우
로 나눠서 구현해보겠습니다.
1.1 가장 앞에 노드를 삽입하는 경우 ( 연결리스트가 비어 있는 경우 )
첫 번째 노드를 추가하는 것은 쉽습니다. 새로운 노드를 동적 할당하고, 동적 할당 받은 노드에 데이터를 입력하고, head 가 새로운 노드를 가리키게 하면 되는 것이죠. 그 전에 확인해야 하는 것은 연결리스트가 비어있나? 체크를 하는 것입니다. 연결리스트의 초기화에서 head = NULL; 로 초기화 했었는데요, 앞으로도 연결리스트의 마지막 포인터는 null 을 가리킵니다. 즉 head == NULL 이라면 현재 연결리스트가 비어있는 상황이라는 것을 의미합니다.
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = 100;
newNode->next = NULL;
if (head == NULL) {
head = newNode;이 과정을 코드로 나타내면 위와 같습니다. 노드를 동적 할당 받고(생성) newNode 포인터에 저장합니다. 그 이후 newNode->data, newNode->next 를 통해 데이터를 써주고 NULL 포인터를 입력해줍니다. 마지막으로 head 포인터가 NULL 이라면 즉 연결리스트가 비어있다면 head 가 newNode 를 가리키도록 합니다. if 문이 닫히지 않은 건 아래의 케이스들을 추가로 구현할 예정이기 때문입니다.
1.2 가장 앞에 노드를 삽입하는 경우 ( 연결리스트가 비어 있지 않은 경우 )
새로운 노드를 동적할당 받고, 데이터까지 입력해주는 것은 똑같습니다. 그 이후 해야 하는 것은 head 포인터가 가리키고 있는 노드를 newNode 의 next 포인터가 가리키게 하는 것 입니다.
그 이후 head 가 newNode 를 가리키게 하면 삽입이 끝납니다.
이 때 주의할 점은 꼭 새로 만든 노드의 포인터가 원래 head 가 가리키고 있던 노드를 가리킨 이후에 head 포인터를 새로 만든 newNode 를 가리키게 해야한다는 점입니다. 만약 이 순서를 반대로 해버린다면, 즉 newNode 를 만들고 head 포인터가 가리키는 노드를 가리키기 이전에 head 포인터를 먼저 newNode 를 가리키게 만들면
위 그림 같은 상황이 발생합니다. 이렇게 되면 100 의 데이터를 가지는 노드의 주소를 찾을 방법이 없기 때문에 newNode 의 포인터로 100의 데이터를 가지고 있는 노드를 가리킬 수 없습니다. 따라서 꼭 순서를 맞춰서 삽입을 해야 합니다.
Node* insert_first(Node* head, element data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
if (head == NULL)
{ // 가장 앞에 노드를 삽입하는 경우 ( 연결리스트가 비어 있는 경우 )
newNode->next = NULL;
head = newNode;
}
else
{ // 가장 앞에 노드를 삽입하는 경우 ( 연결리스트가 비어 있지 않은 경우 )
newNode->next = head;
head = newNode;
}
return head; // 변경된 head 포인터 반환
}위의 과정을 모두 포함한 맨 앞에 노드를 추가하는 코드입니다.
2. 가장 뒤에 노드를 삽입하는 경우
마지막에 노드를 추가하는 경우는 newNode 를 만들고 연결리스트의 마지막 노드의 next 포인터가 newNode 를 가리키게 하면 됩니다. 이는 다음에 알아볼 중간에 노드를 삽입하는 함수와 함께 하나의 함수로 선언할 수 있습니다.
3. 중간에 노드를 삽입하는 경우
가장 헷갈릴 수 있는 부분입니다. 숫자로 순서를 나타내보면
1. newNode 를 생성하고 데이터 입력
2. newNode 의 next 포인터를 선행 노드가 가리키는 노드를 가리키게 한다.
3. 선행 노드의 next 포인터로 newNode 를 가리킨다.
이 과정을 함수로 만들면 다음과 같습니다. 헤드 포인터, 선행 노드의 포인터, 값을 인자로 사용합니다.
Node* insert(Node* head, Node* pre, element value)
{
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
if (pre->next == NULL) { // 선행 노드가 마지막 노드라면
pre->next = newNode;
newNode->next = NULL;
}
else { // 선행 노드가 마지막 노드가 아니라면 (중간 삽입)
newNode->next = pre->next;
pre->next = newNode;
return head;
}
}
연결리스트의 삭제 ( delete )
삭제도 과정의 순서가 중요합니다.
1. 삭제할 노드를 찾고 임시 저장한다.
2. 삭제할 노드의 앞의 포인터로 삭제할 노드의 포인터가 가리키던 노드를 가리킨다.
3. 1번 과정을 통해 저장한 메모리를 해제한다.
이 중에서도 분류해서 가장 맨 앞의 노드를 삭제하는 것, 중간의 노드를 삭제하는 것, 마지막의 노드를 삭제하는 것으로 나눠서 확인해보겠습니다.
가장 맨 앞의 노드 삭제
Node* delete_first(Node* head)
{
Node* cur;
if (head == NULL) return NULL;
cur = head;
head = cur->next;
free(cur);
return head;
}중간의 노드 삭제 / 마지막 노드 삭제
// pre 가 가리키는 노드의 다음 노드를 삭제한다.
Node* Delete(Node* head, Node* prev)
{
Node* cur;
cur = prev->next;
prev->next = cur->next;
free(cur);
return head;
}
전체 코드
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct Node { // 노드 타입을 구조체로 정의
element data;
struct Node* next;
};
void init(Node* head) {
head = NULL;
}
Node* insert_first(Node* head, element data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
if (head == NULL)
{ // 가장 앞에 노드를 삽입하는 경우 ( 연결리스트가 비어 있는 경우 )
newNode->next = NULL;
head = newNode;
}
else
{ // 가장 앞에 노드를 삽입하는 경우 ( 연결리스트가 비어 있지 않은 경우 )
newNode->next = head;
head = newNode;
}
return head; // 변경된 head 포인터 반환
}
// 노드 pre 뒤에 새로운 노드 삽입
Node* insert(Node* head, Node* pre, element value)
{
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
if (pre->next == NULL) { // 선행 노드가 마지막 노드라면
pre->next = newNode;
newNode->next = NULL;
}
else { // 선행 노드가 마지막 노드가 아니라면 (중간 삽입)
newNode->next = pre->next;
pre->next = newNode;
return head;
}
}
Node* delete_first(Node* head) {
Node* cur;
if (head == NULL) return NULL;
cur = head;
head = cur->next;
cur->next = NULL; // cur 변수를 NULL로 설정
free(cur);
return head;
}
Node* Delete(Node* head, Node* prev) {
if (prev == NULL || prev->next == NULL) return head; // 예외 처리
Node* cur = prev->next;
prev->next = cur->next;
cur->next = NULL; // cur 변수를 NULL로 설정
free(cur);
return head;
}
void print_list(Node* head)
{
for (Node* p = head; p != NULL; p = p->next)
printf("[%d]->", p->data);
printf("NULL \n");
}
int main(void) {
Node* head = NULL;
for (int i = 1; i < 6; i++)
{
head = insert_first(head, i);
print_list(head);
}
printf("\n");
insert(head, head->next, 9);
print_list(head);
Delete(head, head->next->next);
print_list(head);
printf("\n");
for (int i = 1; i < 6; i++)
{
head = delete_first(head);
print_list(head);
}
return 0;
}
참고 문헌 : C언어로 쉽게 풀어쓴 자료구조 - 생능출판
'C 자료구조' 카테고리의 다른 글
| [C 자료구조] 그래프 ADT 구현 : 인접행렬 / 인접리스트 (2) | 2023.05.25 |
|---|---|
| [C 자료구조] 그래프(Graph)의 종류 : 인접 행렬(Adjacent matrix) vs 인접 리스트(Adjacent list) (1) | 2023.05.24 |
| [C 자료구조] 큐(Queue) - 연결리스트 구현 (0) | 2023.05.24 |
| [C 자료구조] 큐(Queue) - 선형큐 / 원형큐 배열 구현 (0) | 2023.05.23 |
| [C 자료구조] 스택(Stack) (3) | 2023.05.22 |