연결 리스트(Linked List): 단일, 이중, 원형 연결 리스트

**연결 리스트(Linked List)**는 각 원소가 데이터와 다음 원소를 가리키는 주소(포인터)를 포함하는 **노드(Node)**들로 구성된 동적 선형 자료구조입니다.

1. 배열(Array) vs 연결 리스트(Linked List) 비교

2. 연결 리스트의 종류

1. 단일 연결 리스트 (Singly Linked List): 각 노드가 다음 노드의 포인터(next)만 갖는 구조.
2. 이중 연결 리스트 (Doubly Linked List): 각 노드가 이전 노드(prev)와 다음 노드(next) 포인터를 모두 갖는 구조. 양방향 탐색 가능.
3. 원형 연결 리스트 (Circular Linked List): 마지막 노드의 next 포인터가 다시 첫 번째 노드(Head)를 가리키는 구조.

3. 단일 연결 리스트 파이썬 구현

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

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

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

    def display(self):
        elements = []
        curr = self.head
        while curr:
            elements.append(str(curr.data))
            curr = curr.next
        print(" -> ".join(elements))

# 실행
ll = SinglyLinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.display()  # 10 -> 20 -> 30

4. 주요 활용 및 장단점

• 장점: 사전 메모리 크기 할당 불필요, 데이터 삽입 및 삭제 시 타 요소 이동 없음.
• 단점: 포인터를 저장을 위한 추가 메모리 필요, 인덱스를 통한 직접 접근 불가.
• 활용 사례: 스택/큐/그래프 등의 자료구조 구현 기반, 이미지 슬라이드쇼, 메모리 관리 파티션 목록.

5. 자주 묻는 질문 (Q&A)

Q. 이중 연결 리스트가 단일 연결 리스트보다 유리한 경우는 언제인가요? A. 특정 노드의 이전 노드로 되돌아가거나 양방향으로 순회해야 할 때 효율적입니다. 단, 포인터 저장 공간이 노드당 2개씩 필요합니다.