Linked List (연결리스트)

Table of Contents

1. 연결 리스트(Linked List)란?

연결 리스트(Linked List)는 데이터를 저장하는 선형 자료구조 중 하나로, 각 요소(Node)가 다음 요소를 가리키는 포인터를 포함하는 방식으로 연결되어 있는 구조입니다. 배열과 달리 요소가 연속된 메모리 공간에 저장되지 않고, 동적으로 메모리를 할당받아 유연하게 크기를 조정할 수 있습니다.

2. 연결 리스트의 개념 및 적용 분야

(1) 개념

연결 리스트는 여러 개의 노드(Node)로 구성되며, 각 노드는 데이터(Data)와 다음 노드를 가리키는 포인터(Next)로 이루어져 있습니다.

연결 리스트의 종류는 다음과 같습니다.

단일 연결 리스트(Singly Linked List): 각 노드가 다음 노드만 가리키는 구조
이중 연결 리스트(Doubly Linked List): 각 노드가 이전 및 다음 노드를 모두 가리키는 구조
원형 연결 리스트(Circular Linked List): 마지막 노드가 첫 번째 노드를 가리키는 구조

(2) 적용 분야

데이터 삽입과 삭제가 빈번한 경우 (예: 운영 체제의 메모리 관리, 프로세스 관리)
동적 메모리 할당이 필요한 경우 (예: 그래프(Graph) 구현, 해시 테이블(Hash Table) 충돌 해결)
스택(Stack)과 큐(Queue)와 같은 동적 자료구조 구현

3. 연결 리스트 구현 방법

연결 리스트는 주로 구조체(struct) 또는 클래스를 사용하여 구현됩니다. 기본적인 단일 연결 리스트(Singly Linked List)의 구현 방법을 예제로 설명하면 다음과 같습니다.

(1) 노드(Node) 구조 정의

struct Node {
    int data;      // 데이터 저장
    Node* next;    // 다음 노드를 가리키는 포인터
};

(2) 노드 추가 및 삭제

// 새 노드 추가 (리스트 끝에 추가)
void append(Node*& head, int newData) {
    Node* newNode = new Node();
    newNode->data = newData;
    newNode->next = nullptr;

    if (head == nullptr) {
        head = newNode;
        return;
    }

    Node* temp = head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }
    temp->next = newNode;
}

// 노드 삭제
void deleteNode(Node*& head, int key) {
    Node* temp = head;
    Node* prev = nullptr;

    if (temp != nullptr && temp->data == key) {
        head = temp->next;
        delete temp;
        return;
    }

    while (temp != nullptr && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == nullptr) return;

    prev->next = temp->next;
    delete temp;
}

4. 배열 리스트(Array List)와 연결 리스트(Linked List)의 비교

비교 항목	배열 리스트(Array List)	연결 리스트(Linked List)
메모리 할당	고정 크기 할당(연속된 메모리 공간 사용)	동적 크기 할당(노드별 개별 메모리 할당)
삽입/삭제 성능	중간 삽입/삭제 시 많은 데이터 이동 필요	중간 삽입/삭제가 빠름 (포인터 변경만 필요)
접근 속도	O(1) (인덱스로 바로 접근 가능)	O(n) (처음부터 순차적으로 탐색)
메모리 사용 효율	오버헤드 없음 (포인터 필요 없음)	오버헤드 있음 (포인터 저장 공간 필요)