본문으로 건너뛰기
실습하기

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

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

각 노드는 데이터와 포인터(Pointer)로 구성되어 있으며, 포인터는 다음 노드를 가리킵니다.


연결 리스트의 구조와 특성​

  • 노드(Node): 연결 리스트의 각 요소를 노드라고 합니다. 각 노드는 데이터와 하나 또는 두 개의 '포인터'(Pointer)를 포함합니다. 포인터는 다음 노드(때로는 이전 노드)를 가리킵니다.

  • 헤드(Head): 연결 리스트의 첫 번째 노드를 가리키는 포인터입니다.

  • 테일(Tail): 연결 리스트의 마지막 노드를 가리키는 포인터입니다.

파이썬 연결 리스트 구현 예시
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 is not None:
            print(node.data)
            node = node.next

linked_list = LinkedList(5)
linked_list.append(12)
linked_list.print_all() # 5 12

연결 리스트 종류​

  • 단일 연결 리스트(Singly Linked List): 각 노드가 다음 노드만을 가리키는 가장 단순한 형태의 연결 리스트입니다.

  • 이중 연결 리스트(Doubly Linked List): 각 노드가 이전 노드와 다음 노드를 모두 가리키는 구조로, 양방향 탐색이 가능합니다.

  • 원형 연결 리스트(Circular Linked List): 마지막 노드가 첫 번째 노드를 가리키는 형태로, 순환 구조를 갖습니다.


연결 리스트와 배열의 비교​

  • 메모리 할당: 배열은 고정 크기의 연속적인 메모리 공간을 사용하는 반면, 연결 리스트는 필요에 따라 동적으로 메모리를 할당합니다.

  • 삽입/삭제 연산: 배열에서는 삽입과 삭제가 비효율적일 수 있으나, 연결 리스트에서는 상대적으로 간단하고 빠릅니다.

  • 임의 접근: 배열은 인덱스를 통한 임의 접근이 가능하지만, 연결 리스트는 순차적 접근만 가능합니다.

다음 내용이 궁금하다면?

코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!