[자료구조] 연결 리스트 - Linked List (C, Python)


floatFirstTOC: right

🖥️ 들어가며 순차 리스트 (Sequential List)연결 리스트 (Linked List)노드의 구조 연결 리스트 구현 C 구현해야 하는 함수들 isEmpty createNode InsertNode 1. 맨 앞에 새로운 노드 삽입 2. 맨 뒤에 새로운 노드 삽입 3. 중간에 새로운 노드 삽입 insertNode 코드 전문 deleteNode 1. 처음 위치의 노드 제거 2. 그 외 위치의 노드 제거 printList 코드 전문 개선된 코드 전문 Python 코드 전문

🖥️ 들어가며

리스트는 프로그래밍에서 매우 중요한 자료 구조 중 하나입니다. 이는 순서가 있는 데이터의 집합을 관리하기 위한 방법으로, 데이터를 효율적으로 저장하고 검색, 수정, 삭제하는 작업을 수행할 수 있도록 돕습니다. 리스트는 크게 두 가지 유형으로 나눌 수 있습니다.

순차 리스트 (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

[자료구조] 연결 리스트 - Linked List (C, Python)

🖥️ 들어가며

순차 리스트 (Sequential List)

연결 리스트 (Linked List)

노드의 구조

연결 리스트 구현

C

구현해야 하는 함수들

isEmpty

createNode

InsertNode

1. 맨 앞에 새로운 노드 삽입

2. 맨 뒤에 새로운 노드 삽입

3. 중간에 새로운 노드 삽입

insertNode 코드 전문

deleteNode

1. 처음 위치의 노드 제거

2. 그 외 위치의 노드 제거

printList

코드 전문

개선된 코드 전문

Python

코드 전문

댓글

`isEmpty`

`createNode`

`InsertNode`

`insertNode` 코드 전문

`deleteNode`

`printList`