데이터를 노드로 연결해 구성하는 연결 리스트(Linked List)

연결 리스트(Linked List)는 데이터 요소들이 노드(Node)라는 단위로 구성되어 서로 연결된 구조를 갖는 자료구조입니다.

각 노드는 데이터와 다음 노드를 가리키는 포인터(Pointer)로 이루어져 있습니다.

연결 리스트는 다음과 같은 구조와 특성을 갖습니다.

연결 리스트의 기본 단위입니다.

각 노드는 데이터와 하나 또는 두 개의 포인터를 포함하며, 포인터는 다음 노드(또는 경우에 따라 이전 노드)를 가리킵니다.

연결 리스트의 첫 번째 노드를 가리키는 포인터입니다.

연결 리스트의 시작점을 나타냅니다.

연결 리스트의 마지막 노드를 가리키는 포인터입니다.

테일 노드의 포인터는 일반적으로 None을 가리킵니다.

아래 코드는 파이썬으로 단순 연결 리스트(Singly Linked List)를 구현한 예제입니다.

복사
class Node:
    def __init__(self, data):
        # 노드의 데이터
        self.data = data
        # 다음 노드를 가리키는 포인터
        self.next = None

class LinkedList:
    def __init__(self, data):
        # 첫 번째 노드 생성
        self.head = Node(data)
        # 초기에는 헤드와 테일이 동일
        self.tail = self.head

    def append(self, data):
        # 새 노드 생성 및 연결
        node = Node(data)
        # 테일 노드의 다음 노드로 새 노드를 연결
        self.tail.next = node
        # 새 노드를 테일로 지정
        self.tail = node

    def print_all(self):
        # 연결 리스트 출력
        node = self.head

        # 노드를 순회하며 데이터 출력
        while node:
            print(node.data, end=" ")
            node = node.next
        print()

# 연결 리스트 생성
linked_list = LinkedList(5)

# 노드 추가
linked_list.append(12)
linked_list.append(7)

# 연결 리스트 출력
linked_list.print_all()
# 출력: 5 12 7

연결 리스트는 노드가 연결되는 방식에 따라 다음과 같이 나뉩니다.

각 노드가 다음 노드만을 가리키는 가장 단순한 형태의 연결 리스트입니다.

각 노드가 이전 노드와 다음 노드를 모두 가리킵니다.

양방향 탐색이 가능하며, 삽입과 삭제가 더욱 효율적입니다.

마지막 노드가 첫 번째 노드를 가리키는 구조로, 리스트가 순환됩니다.

순환적 작업에 유용합니다.

연결 리스트는 메모리 관리와 삽입/삭제 연산이 중요한 경우 유리한 반면, 배열은 임의 접근과 데이터 처리 속도가 중요한 경우 적합합니다.