Linked List (연결 리스트)

Linked List (연결 리스트)

개념 및 정의

연결 리스트는 데이터 요소가 노드로 이루어져 있고, 각 노드가 다음 노드에 대한 참조를 갖는 선형 데이터 구조입니다. 연결 리스트는 단일 연결 리스트(Singly Linked List)와 이중 연결 리스트(Doubly Linked List), 원형 연결 리스트(Circular Linked List) 등 여러 변형이 있습니다.

장점

1. 동적 크기: 배열과 달리 크기가 동적으로 조정됩니다.
2. 삽입과 삭제가 용이: 중간에 요소를 삽입하거나 삭제하는 경우에도 O(1)의 시간 복잡도를 가질 수 있습니다.
3. 메모리 효율: 필요한 만큼의 메모리를 할당할 수 있으므로 메모리 효율이 좋습니다.

단점

1. 접근 속도: 배열에 비해 임의 접근(random access)이 불가능하거나 느립니다 (O(n)).
2. 추가 메모리 사용: 각 노드가 다음 노드에 대한 참조 정보를 저장해야 하므로 추가 메모리가 필요합니다.
3. 코드 복잡성: 포인터를 사용해 노드를 관리해야 하므로 코드가 복잡해질 수 있습니다.

구현방법 (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 self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def print_list(self):
        cur_node = self.head
        while cur_node:
            print(cur_node.data)
            cur_node = cur_node.next

llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
llist.append(4)
llist.print_list()

연결 리스트는 다양한 형태와 활용 방안을 가지고 있으며, 특히 삽입과 삭제가 빈번한 경우나 데이터의 크기가 동적으로 변하는 경우에 유용하게 사용할 수 있습니다. 데이터 구조와 알고리즘을 공부하는 과정에서 꼭 이해하고 있어야 하는 중요한 개념 중 하나입니다.