![[자료구조] 연결 리스트 - Linked List (C, Python)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2F2PEEX%2FbtsGx1de05E%2FpIZFcNB1nraWILExVBHWGK%2Fimg.jpg)
[자료구조] 연결 리스트 - Linked List (C, Python)◎ 자료구조와 알고리즘/자료구조 이론2024. 4. 12. 12:52
Table of Contents
반응형
🖥️ 들어가며
리스트는 프로그래밍에서 매우 중요한 자료 구조 중 하나입니다. 이는 순서가 있는 데이터의 집합을 관리하기 위한 방법으로, 데이터를 효율적으로 저장하고 검색, 수정, 삭제하는 작업을 수행할 수 있도록 돕습니다. 리스트는 크게 두 가지 유형으로 나눌 수 있습니다.
순차 리스트 (Sequential List)
- 순차 리스트는 가장 기본적인 형태의 리스트로, 배열을 기반으로 구현됩니다. 배열의 인덱스를 사용하여 데이터에 접근하기 때문에 특정 위치의 데이터를 빠르게 찾거나 읽어올 수 있습니다. 이러한 특성 덕분에 생성 및 데이터 검색(또는 출력) 작업은 순차 리스트에서 매우 효율적으로 이루어집니다.
- 그러나 순차 리스트는 데이터의 삽입이나 삭제가 비효율적입니다. 특히 리스트의 중간에서 삭제나 삽입 연산을 수행할 경우, 이후의 모든 데이터를 이동시켜야 하기 때문에 상당한 비용이 소모됩니다.
연결 리스트 (Linked List)
- 연결 리스트는 순차 리스트의 이러한 단점을 극복하기 위해 개발된 구조입니다.
- 연결 리스트에서는 데이터를 메모리의 여러 위치에 동적으로 할당하고, 각 데이터(노드)는 다음 데이터의 위치 정보를 포함합니다. 이 위치 정보는 보통 포인터를 사용하여 다음 노드를 가리킵니다.
- 연결 리스트와 순차 리스트는 대조되는 장단점을 가지기 때문에, 연결 리스트는 노드 삽입 및 삭제가 용이하고 데이터 구조의 크기를 유연하게 조정할 수 있다는 장점을 가집니다.
노드의 구조
노드는 연결 리스트의 기본 단위로, 두 부분으로 구성됩니다.
- 데이터를 저장하는
item 필드 - 다음 노드의 주소를 저장하는
next 필드
이 노드를 여러 개 이어 붙이면, 아래 그림과 같이 됩니다.
이런 구조 덕에 연결 리스트는 메모리가 허용하는 만큼 계속 확장할 수 있습니다.
HEAD 포인터- 첫 번째 노드의 주소를 가리키는 포인터라고 생각하면 됩니다.
데이터가 들어있다고 가정하면 아래와 같은 그림이 됩니다.
물론 예시를 들었을 뿐 메모리가 항상 이렇게 연속적이지는 않습니다.
연결 리스트 구현
C
가장 통상적인 방법은 구조체를 활용하는 방안입니다.
노드 구조체를 선언해 안쪽에 next 필드 와 item 필드 를 선언하고 이를 계속 재사용하는 방식입니다.
typedef struct node {
int item;
struct node *next;
} Node;구현해야 하는 함수들
isEmpty
노드가 비어있는지 확인합니다.
HEAD 포인터가 NULL이면 비어있다고 간주합니다.
int isEmpty(Node *head) {
if (head == NULL)
return 1;
else
return 0;
}createNode
노드를 생성합니다. 동적으로 생성하기 위해 malloc 을 사용합니다.
Node *createNode(int item) {
Node *newNode = (Node *)malloc(sizeof(Node));
// 메모리 할당 실패
if (newNode == NULL)
return -1;
newNode->item = item;
newNode->next = NULL;
return newNode;
}InsertNode
노드를 삽입합니다. 노드를 삽입하는 데는 3가지 경우가 생길 수 있습니다.
- 맨 앞에 새로운 노드 삽입
- 맨 뒤에 새로운 노드 삽입
- 중간에 새로운 노드 삽입
우선 위 작업을 수행하기 위해서는, 기초 작업이 필요합니다.
Node *newnode = createNode(item);
Node *pre_node = *head; // 이전 노드
Node *pos_node = *head; // 현재 노드
for (int count = 0; count < pos - 1; count++)
pre_node = pre_node->next;
for (int count = 0; count < pos; count++)
pos_node = pos_node->next;중요한 부분은 for 문 구간입니다. 쉽게 그림으로 설명하겠습니다.
아래 그림에서는 pos 가 3일 경우를 예시로 들었습니다.
- 이 아이디어는
2. 맨 뒤에 새로운 노드 삽입과3. 중간에 새로운 노드 삽입를 위한 아이디어입니다.- 맨 뒤에 넣을 때는 맨 뒤 노드가
pos가 됩니다. - 중간에 넣을 때는 넣고 싶은 위치의 노드가
pos, 그 앞 노드가pre가 되므로 서로의Next 필드를 연결할 수 있습니다.
- 맨 뒤에 넣을 때는 맨 뒤 노드가
1. 맨 앞에 새로운 노드 삽입
비교적 간단합니다.
- 새로운 노드의
NEXT필드를 현재HEAD포인터가 가리키는 주소로 변경합니다. - 현재
HEAD포인터를 새로 추가한 노드로 변경합니다.
코드상으로는 다음과 같습니다.
if (pos == 0) { // 맨 앞에 삽입
newnode->next = *head;
*head = newnode;
}2. 맨 뒤에 새로운 노드 삽입
- 맨 뒤의 노드의
Next 필드를 새로운 노드를 가리키도록 합니다.
코드는 다음과 같습니다.
else if (pos == NULL) { // 맨 뒤에 삽입
pos_node->next = newnode;
}3. 중간에 새로운 노드 삽입
- 새로 생성한 노드의
Next 필드가pos_node를 가리키도록 합니다. pre_node의Next 필드가 새로운 노드를 가리키도록 합니다.
코드는 다음과 같습니다.
else { // 중간에 삽입
newnode->next = pos_node;
pre_node->next = newnode;
}insertNode 코드 전문
void insertNode(Node **head, int item, int pos) {
Node *newnode = createNode(item);
Node *pre_node = *head; // 이전 노드
Node *pos_node = *head; // 현재 노드
for (int count = 0; count < pos - 1; count++)
pre_node = pre_node->next;
for (int count = 0; count < pos; count++)
pos_node = pos_node->next;
if (pos == 0) { // 맨 앞에 삽입
newnode->next = *head;
*head = newnode;
} else if (pos == NULL) { // 맨 뒤에 삽입
pos_node->next = newnode;
} else { // 중간에 삽입
newnode->next = pos_node;
pre_node->next = newnode;
}
}deleteNode
노드를 추가도 했으니, 삭제도 할 수 있어야 진정한 연결리스트라 할 수 있을 것입니다.
노드의 삽입 과정은 3개의 분기가 있었지만 다행히 삭제는 2개의 분기만 고려하면 됩니다.
우선 초기 설정입니다. insertNode 와 거의 유사합니다.
Node *deleted_node;
Node *pre_node = *head;
Node *pos_node = *head;
for (int count = 0; count < pos - 1; count++)
pre_node = pre_node->next;
for (int count = 0; count < pos; count++)
pos_node = pos_node->next;1. 처음 위치의 노드 제거
간단합니다. 그냥
HEAD포인터가 삭제할 노드의 다음 노드를 가리키도록 합니다.- 삭제할 노드는
free합니다.
코드는 다음과 같습니다.
if (pos == 0) { // 맨 앞 삭제
deleted_node = *head;
*head = (*head)->next;
free(deleted_node);
}2. 그 외 위치의 노드 제거
pre_node의next를pos_node의next로 변경합니다.- 삭제할 노드를
free합니다.
코드는 다음과 같습니다.
else { // 중간 & 맨 뒤 삭제
deleted_node = pos_node;
pre_node->next = pos_node->next;
free(deleted_node);
}printList
모든 노드를 순회하며 값을 출력합니다.
void printList(Node *head) {
Node *current = head;
while (current != NULL) {
printf("%d -> ", current->item);
current = current->next;
}
printf("NULL\n");
}코드 전문
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int item;
struct node *next;
} Node;
int isEmpty(Node *head) {
if (head == NULL)
return 1;
else
return 0;
}
Node *createNode(int item) {
Node *newNode = (Node *)malloc(sizeof(Node));
// 메모리 할당 실패
if (newNode == NULL)
return NULL;
newNode->item = item;
newNode->next = NULL;
return newNode;
}
void insertNode(Node **head, int item, int pos) {
Node *newnode = createNode(item);
Node *pre_node = *head; // 이전 노드
Node *pos_node = *head; // 현재 노드
for (int count = 0; count < pos - 1; count++)
pre_node = pre_node->next;
for (int count = 0; count < pos; count++)
pos_node = pos_node->next;
if (pos == 0) { // 맨 앞에 삽입
newnode->next = *head;
*head = newnode;
} else if (pos == NULL) { // 맨 뒤에 삽입
pos_node->next = newnode;
} else { // 중간에 삽입
newnode->next = pos_node;
pre_node->next = newnode;
}
}
void deleteNode(Node **head, int pos) {
Node *deleted_node;
Node *pre_node = *head;
Node *pos_node = *head;
for (int count = 0; count < pos - 1; count++)
pre_node = pre_node->next;
for (int count = 0; count < pos; count++)
pos_node = pos_node->next;
if (pos == 0) { // 맨 앞 삭제
deleted_node = *head;
*head = (*head)->next;
free(deleted_node);
} else { // 중간 & 맨 뒤 삭제
deleted_node = pos_node;
pre_node->next = pos_node->next;
free(deleted_node);
}
}
void printList(Node *head) {
Node *current = head;
while (current != NULL) {
printf("%d -> ", current->item);
current = current->next;
}
printf("NULL\n");
}
int main() {
Node *head = NULL;
// 노드 삽입
insertNode(&head, 10, 0);
insertNode(&head, 20, 1);
insertNode(&head, 30, 2);
printList(head); // 출력: 10 -> 20 -> 30 -> NULL
// 노드 삭제
deleteNode(&head, 1); // 20 삭제
printList(head); // 출력: 10 -> 30 -> NULL
// 더 많은 노드 삽입
insertNode(&head, 40, 2); // 30 뒤에 40 삽입
insertNode(&head, 50, 1); // 10 뒤에 50 삽입
printList(head); // 출력: 10 -> 50 -> 30 -> 40 -> NULL
// 프로그램 종료 전 모든 노드 메모리 해제
while (!isEmpty(head)) {
deleteNode(&head, 0);
}
return 0;
}개선된 코드 전문
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int item;
struct node *next;
} Node;
int isEmpty(Node *head) {
return head == NULL;
}
Node *createNode(int item) {
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) {
printf("메모리 할당 실패\n");
return NULL;
}
newNode->item = item;
newNode->next = NULL;
return newNode;
}
void insertNode(Node **head, int item, int pos) {
Node *newNode = createNode(item);
if (newNode == NULL) {
return;
}
if (pos == 0) { // 맨 앞에 삽입
newNode->next = *head;
*head = newNode;
} else {
Node *current = *head;
for (int i = 0; i < pos - 1 && current != NULL; i++) {
current = current->next;
}
if (current == NULL) {
printf("위치 오류: 리스트 길이보다 큰 위치입니다\n");
free(newNode);
} else {
newNode->next = current->next;
current->next = newNode;
}
}
}
void deleteNode(Node **head, int pos) {
if (*head == NULL) {
printf("리스트가 비어 있습니다.\n");
return;
}
Node *deletedNode;
if (pos == 0) { // 맨 앞 삭제
deletedNode = *head;
*head = (*head)->next;
} else {
Node *current = *head;
for (int i = 0; i < pos - 1 && current->next != NULL; i++) {
current = current->next;
}
if (current->next == NULL) {
printf("위치 오류: 리스트 길이보다 큰 위치입니다\n");
return;
}
deletedNode = current->next;
current->next = current->next->next;
}
free(deletedNode);
}
void printList(Node *head) {
Node *current = head;
while (current != NULL) {
printf("%d -> ", current->item);
current = current->next;
}
printf("NULL\n");
}
int main() {
Node *head = NULL;
// 노드 삽입
insertNode(&head, 10, 0);
insertNode(&head, 20, 1);
insertNode(&head, 30, 2);
printList(head); // 출력: 10 -> 20 -> 30 -> NULL
// 노드 삭제
deleteNode(&head, 1); // 20 삭제
printList(head); // 출력: 10 -> 30 -> NULL
// 더 많은 노드 삽입
insertNode(&head, 40, 2); // 30 뒤에 40 삽입
insertNode(&head, 50, 1); // 10 뒤에 50 삽입
printList(head); // 출력: 10 -> 50 -> 30 -> 40 -> NULL
// 프로그램 종료 전 모든 노드 메모리 해제
while (!isEmpty(head)) {
deleteNode(&head, 0);
}
return 0;
}
Python
파이썬도 대충 원리는 비슷합니다. 대신 C언어와 다르게 free 작업을 하지 않아도 되기에 조금 더 간결하게 작성할 수 있습니다.
코드 전문
class Node:
"""노드 클래스. 연결 리스트의 기본 요소."""
def __init__(self, item):
self.item = item # 노드가 저장할 데이터
self.next = None # 다음 노드를 가리키는 참조, 초기에는 None
class LinkedList:
"""연결 리스트 클래스. 노드들을 연결하여 리스트를 구현."""
def __init__(self):
self.head = None # 리스트의 첫 번째 노드를 가리킴
def insert(self, item, pos):
"""주어진 위치에 새 노드를 삽입."""
new_node = Node(item) # 새 노드 생성
if pos == 0: # 맨 앞에 삽입하는 경우
new_node.next = self.head
self.head = new_node
else: # 중앙이나 맨 뒤에 삽입하는 경우
prev = None
current = self.head
current_pos = 0
while current_pos < pos and current is not None:
prev = current
current = current.next
current_pos += 1
if current_pos < pos:
raise IndexError("위치 오류: 리스트 길이보다 큰 위치입니다")
if current is None: # 맨 뒤에 삽입하는 경우
prev.next = new_node
else: # 중간에 삽입하는 경우
new_node.next = current
prev.next = new_node
def delete(self, pos):
"""주어진 위치의 노드를 삭제."""
if self.head is None:
raise ValueError("List is empty")
if pos == 0:
# 맨 앞의 노드를 삭제하는 경우
self.head = self.head.next
else:
prev = None
current = self.head
current_pos = 0
while current_pos < pos and current.next is not None:
prev = current
current = current.next
current_pos += 1
if current.next is None and current_pos < pos:
raise IndexError("위치 오류: 리스트 길이보다 큰 위치입니다")
prev.next = current.next
def __iter__(self):
"""반복자 메서드. 연결 리스트를 순회할 수 있게 해줌."""
current = self.head
while current:
yield current.item
current = current.next
def __str__(self):
"""연결 리스트를 문자열로 표현하여 출력. 예: 10 -> 20 -> 30 -> NULL"""
return " -> ".join(str(item) for item in self) + " -> NULL"
# 사용 예시
if __name__ == "__main__":
ll = LinkedList()
ll.insert(10, 0)
ll.insert(20, 1)
ll.insert(30, 2)
print(ll) # 출력: 10 -> 20 -> 30 -> NULL
ll.delete(1)
print(ll) # 출력: 10 -> 30 -> NULL
ll.insert(40, 2)
ll.insert(50, 1)
print(ll) # 출력: 10 -> 50 -> 30 -> 40 -> NULL
반응형
'◎ 자료구조와 알고리즘 > 자료구조 이론' 카테고리의 다른 글
| [OS] 메모리 관리 (Memory Management) (0) | 2024.05.01 |
|---|---|
| [자료구조] 큐 (Queue) - 배열로 구현 (C, Python) (0) | 2024.04.14 |
| [자료구조] 스택 - Stack (C, Python) (0) | 2024.04.13 |
| [자료구조] 순환 (Recursion) (0) | 2022.01.18 |
@Reo :: 코드 아카이브
자기계발 블로그
![[OS] 메모리 관리 (Memory Management)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FA6sxD%2FbtsG6gzDpka%2Fweu0prc6Fby0dK3BaQZQ11%2Fimg.png)
![[자료구조] 큐 (Queue) - 배열로 구현 (C, Python)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FnPhwI%2FbtsGCYTX9Zg%2FRf0bNL9LuHXG2yfR5kmk5K%2Fimg.jpg)
![[자료구조] 스택 - Stack (C, Python)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2F5k6E4%2FbtsGDzsKwIM%2Fk2H00TOIxNeuPbDBGIYHDk%2Fimg.jpg)
![[자료구조] 순환 (Recursion)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FddfWIF%2Fbtrq5psJd7D%2FNNvPA7hPlW52p4AoQp5iD0%2Fimg.png)