연결 리스트(Linked List): 동적 데이터 구조의 핵심 개념과 활용

🔹 연결 리스트란?

1. 연결 리스트(Linked List)의 정의

연결 리스트(Linked List)는 각 요소(노드)가 포인터를 사용하여 다음 노드를 가리키는 데이터 구조입니다. 배열과 달리 연속된 메모리 공간을 요구하지 않으며, 동적 크기 조절이 가능합니다.

✅ 연결 리스트의 주요 특징:

• 동적 크기 조정 가능: 필요할 때마다 노드를 추가하거나 제거 가능
• 삽입 및 삭제 연산이 빠름(O(1)): 포인터 변경만으로 간단히 가능
• 메모리 할당이 분산됨: 배열처럼 연속된 메모리 할당이 필요하지 않음
• 임의 접근이 어려움(O(n)): 순차적으로 노드를 탐색해야 원하는 데이터에 접근 가능

📌 연결 리스트는 삽입/삭제가 빈번한 데이터 구조에서 유용하지만, 배열보다 데이터 접근 속도가 느립니다.

---

🔹 연결 리스트의 주요 유형

1. 단일 연결 리스트(Singly Linked List)

✅ 각 노드가 데이터와 다음 노드를 가리키는 포인터를 가지는 기본적인 연결 리스트

✔️ 단일 연결 리스트 예제 (Python):

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        temp = self.head
        while temp.next:
            temp = temp.next
        temp.next = new_node

    def display(self):
        temp = self.head
        while temp:
            print(temp.data, end=" -> ")
            temp = temp.next
        print("None")

ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.display()  # 출력: 10 -> 20 -> 30 -> None

📌 단일 연결 리스트는 메모리를 절약하지만, 역방향 탐색이 어렵습니다.

2. 이중 연결 리스트(Doubly Linked List)

✅ 각 노드가 이전 노드와 다음 노드를 가리키는 포인터를 가지는 연결 리스트

✔️ 이중 연결 리스트 예제 (Python):

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        temp = self.head
        while temp.next:
            temp = temp.next
        temp.next = new_node
        new_node.prev = temp

    def display(self):
        temp = self.head
        while temp:
            print(temp.data, end=" <-> ")
            temp = temp.next
        print("None")

dll = DoublyLinkedList()
dll.append(10)
dll.append(20)
dll.append(30)
dll.display()  # 출력: 10 <-> 20 <-> 30 <-> None

📌 이중 연결 리스트는 역방향 탐색이 가능하지만, 추가적인 포인터 저장 공간이 필요합니다.

3. 원형 연결 리스트(Circular Linked List)

✅ 마지막 노드가 첫 번째 노드를 가리키는 연결 리스트

✔️ 원형 연결 리스트 예제 (Python):

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head
        else:
            temp = self.head
            while temp.next != self.head:
                temp = temp.next
            temp.next = new_node
            new_node.next = self.head

    def display(self):
        temp = self.head
        if not temp:
            return
        while True:
            print(temp.data, end=" -> ")
            temp = temp.next
            if temp == self.head:
                break
        print("(Back to Head)")

cll = CircularLinkedList()
cll.append(10)
cll.append(20)
cll.append(30)
cll.display()  # 출력: 10 -> 20 -> 30 -> (Back to Head)

📌 원형 연결 리스트는 반복적인 작업(예: 프로세스 스케줄링)에서 유용하게 사용됩니다.

---

🔹 배열 vs. 연결 리스트

비교 항목	배열(Array)	연결 리스트(Linked List)
크기 조정	고정 크기	동적 크기 가능
접근 속도	O(1) (인덱스 사용)	O(n) (노드 탐색 필요)
삽입/삭제	O(n) (데이터 이동 필요)	O(1) (포인터 변경)
메모리 사용	연속된 메모리 공간 필요	추가적인 포인터 저장 공간 필요

📌 배열은 빠른 접근이 가능하지만, 연결 리스트는 삽입/삭제가 유리합니다.

---

📌 결론

✅ 연결 리스트(Linked List)는 동적 데이터 구조로, 삽입 및 삭제가 용이합니다.
✅ 단일, 이중, 원형 연결 리스트 등 다양한 유형이 존재하며, 사용 목적에 따라 선택해야 합니다.
✅ 배열과 비교하여 특정 상황에서는 메모리 효율성이 뛰어나지만, 임의 접근 속도가 느릴 수 있습니다.
✅ 알고리즘 및 소프트웨어 최적화를 위해 데이터 구조 선택이 매우 중요합니다.