[자료구조]파이썬 연결 리스트 자료구조 완벽 가이드: 기초부터 활용까지

파이썬에서 배열은 자주 사용되지만, 더 복잡한 데이터 구조를 필요로 할 때 연결 리스트가 중요합니다. 연결 리스트는 데이터의 순서를 유지하면서 삽입과 삭제가 용이한 자료구조입니다. 이 포스팅에서는 파이썬으로 연결 리스트를 구현하는 방법을 단계별로 설명하고, 그 활용법을 소개합니다.

≣ 목차

• 연결 리스트 기본 개념📘
• 연결 리스트의 노드 구현🛠️
• 단일 연결 리스트 구현💡
• 이중 연결 리스트 구현🔄
• 원형 연결 리스트 구현🔁
• 연결 리스트의 활용 예제🌐
• 연결 리스트와 관련된 문제 해결🔍
• 핵심 내용👀

---

01. 연결 리스트 기본 개념📘

연결 리스트는 각 노드가 데이터와 다음 노드에 대한 참조를 포함하는 구조입니다. 배열과 달리 연결 리스트는 메모리 공간을 연속적으로 사용할 필요가 없어 효율적입니다.

연결 리스트의 주요 특징

1. 동적 크기: 배열은 고정 크기지만, 연결 리스트는 요소를 추가하거나 삭제할 때마다 크기가 동적으로 변할 수 있습니다.
2. 메모리 사용의 효율성: 필요한 만큼의 메모리를 사용하므로 메모리 낭비가 적습니다.
3. 삽입 및 삭제가 용이: 특정 위치에 요소를 삽입하거나 삭제하는 작업이 배열보다 효율적입니다. 배열에서는 삽입 또는 삭제 후 요소들을 이동시켜야 하지만, 연결 리스트에서는 참조를 변경하는 것으로 충분합니다.

연결 리스트의 구성 요소

1. 노드(Node): 연결 리스트의 기본 단위로, 데이터와 다음 노드에 대한 참조를 포함합니다.
   - 데이터: 노드가 저장하는 실제 값.
   - 포인터: 다음 노드를 가리키는 참조.
2. 헤드 포인터(Head Pointer): 리스트의 시작점을 가리키는 포인터로, 첫 번째 노드를 참조합니다.

연결 리스트의 종류

1. 단일 연결 리스트(Singly Linked List): 각 노드가 하나의 다음 노드를 가리키는 포인터를 가지는 구조입니다.
   구성: 노드(Node)와 포인터(Next)로 구성.
2. 이중 연결 리스트(Doubly Linked List): 각 노드가 두 개의 포인터(하나는 다음 노드, 하나는 이전 노드)를 가지는 구조입니다.
   구성: 노드(Node), 다음 노드 포인터(Next), 이전 노드 포인터(Prev).
3. 환형 연결 리스트(Circular Linked List): 마지막 노드가 첫 번째 노드를 가리켜 원형으로 연결된 구조입니다.
   - 단일 환형 연결 리스트: 단일 연결 리스트의 변형으로 마지막 노드의 다음 포인터가 첫 번째 노드를 가리킵니다.
   - 이중 환형 연결 리스트: 이중 연결 리스트의 변형으로 마지막 노드의 다음 포인터가 첫 번째 노드를 가리키고, 첫 번째 노드의 이전 포인터가 마지막 노드를 가리킵니다.

연결 리스트의 기본 연산

1. 삽입(Insertion): 새로운 노드를 리스트의 특정 위치에 추가합니다.
2. 삭제(Deletion): 리스트에서 특정 노드를 제거합니다.
3. 탐색(Search): 리스트에서 특정 값을 찾습니다.
4. 순회(Traversal): 리스트의 모든 노드를 순서대로 방문합니다.

---

02. 연결 리스트의 노드 구현🛠️

연결 리스트의 노드는 데이터 구조의 기본 단위로, 다음 노드에 대한 참조(포인터)와 함께 데이터를 포함합니다. Python에서는 클래스를 사용하여 연결 리스트의 노드를 구현할 수 있습니다. 다음은 단일 연결 리스트와 이중 연결 리스트의 노드 구현 예제입니다.

단일 연결 리스트의 노드 구현

단일 연결 리스트의 노드는 다음 노드를 가리키는 포인터(next)와 데이터를 포함합니다.

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

# 노드 생성 예시
node1 = Node(1)
node2 = Node(2)
node1.next = node2  # node1이 node2를 가리키도록 설정

print(node1.data)  # Output: 1
print(node1.next.data)  # Output: 2

이중 연결 리스트의 노드 구현

이중 연결 리스트의 노드는 이전 노드를 가리키는 포인터(prev)와 다음 노드를 가리키는 포인터(next), 그리고 데이터를 포함합니다.

class DoublyNode:
    def __init__(self, data):
        self.data = data  # 노드가 저장할 데이터
        self.prev = None  # 이전 노드를 가리키는 포인터
        self.next = None  # 다음 노드를 가리키는 포인터

# 노드 생성 예시
dnode1 = DoublyNode(1)
dnode2 = DoublyNode(2)
dnode1.next = dnode2  # dnode1이 dnode2를 가리키도록 설정
dnode2.prev = dnode1  # dnode2가 dnode1을 가리키도록 설정

print(dnode1.data)  # Output: 1
print(dnode1.next.data)  # Output: 2
print(dnode2.prev.data)  # Output: 1

단일 연결 리스트와 이중 연결 리스트 비교

• 단일 연결 리스트: 각 노드가 하나의 다음 노드에 대한 포인터만 가지고 있습니다. 삽입과 삭제 연산이 간단하지만, 단방향으로만 탐색할 수 있습니다.
• 이중 연결 리스트: 각 노드가 이전 노드와 다음 노드에 대한 두 개의 포인터를 가지고 있습니다. 양방향으로 탐색이 가능하며, 삽입과 삭제 연산이 더 유연하지만, 추가적인 메모리 공간이 필요합니다.

---

03. 단일 연결 리스트 구현💡

단일 연결 리스트(Singly Linked List)는 각 노드가 하나의 다음 노드에 대한 포인터를 가지고 있는 데이터 구조입니다. 이 구조를 Python 클래스로 구현해보겠습니다. 이 구현에는 삽입, 삭제, 탐색, 순회 등의 기본 연산을 포함합니다.

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

class SinglyLinkedList:
    def __init__(self):
        self.head = None  # 리스트의 시작을 가리키는 포인터

    def insert(self, data):
        """리스트의 맨 앞에 새로운 노드를 삽입합니다."""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def delete(self, key):
        """리스트에서 주어진 값을 가진 첫 번째 노드를 삭제합니다."""
        temp = self.head

        if temp is not None:
            if temp.data == key:
                self.head = temp.next
                temp = None
                return

        while temp is not None:
            if temp.data == key:
                break
            prev = temp
            temp = temp.next

        if temp == None:
            return

        prev.next = temp.next
        temp = None

    def search(self, key):
        """리스트에서 주어진 값을 가진 노드를 찾습니다."""
        current = self.head
        while current is not None:
            if current.data == key:
                return True
            current = current.next
        return False

    def traverse(self):
        """리스트의 모든 노드를 순서대로 방문합니다."""
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 사용 예시
sll = SinglyLinkedList()
sll.insert(1)
sll.insert(2)
sll.insert(3)
sll.traverse()  # Output: 3 -> 2 -> 1 -> None
sll.delete(2)
sll.traverse()  # Output: 3 -> 1 -> None
print(sll.search(1))  # Output: True
print(sll.search(4))  # Output: False

코드 설명

Node 클래스:

• __init__ 메서드는 노드가 저장할 데이터(data)와 다음 노드를 가리키는 포인터(next)를 초기화합니다.

SinglyLinkedList 클래스:

• __init__ 메서드는 리스트의 시작을 가리키는 포인터(head)를 초기화합니다.
• insert 메서드는 리스트의 맨 앞에 새로운 노드를 삽입합니다. 새로운 노드의 next 포인터는 현재의 head를 가리키며, head는 새 노드를 가리키도록 업데이트됩니다.
• delete 메서드는 리스트에서 주어진 값을 가진 첫 번째 노드를 삭제합니다. head가 삭제될 노드인지 확인한 후, 그렇지 않으면 리스트를 순회하며 삭제할 노드를 찾고, 이전 노드의 next 포인터를 업데이트합니다.
• search 메서드는 리스트를 순회하며 주어진 값을 가진 노드를 찾습니다. 값을 찾으면 True를 반환하고, 그렇지 않으면 False를 반환합니다.
• traverse 메서드는 리스트의 모든 노드를 순서대로 방문하여 데이터를 출력합니다. 노드가 끝나면 None을 출력합니다.

---

04. 이중 연결 리스트 구현🔄

이중 연결 리스트(Doubly Linked List)는 각 노드가 이전 노드와 다음 노드를 가리키는 두 개의 포인터를 가지고 있는 데이터 구조입니다. 이 구조를 Python 클래스로 구현해보겠습니다. 구현에는 삽입, 삭제, 탐색, 순회 등의 기본 연산을 포함합니다.

class DoublyNode:
    def __init__(self, data):
        self.data = data  # 노드가 저장할 데이터
        self.prev = None  # 이전 노드를 가리키는 포인터
        self.next = None  # 다음 노드를 가리키는 포인터

class DoublyLinkedList:
    def __init__(self):
        self.head = None  # 리스트의 시작을 가리키는 포인터

    def insert_front(self, data):
        """리스트의 맨 앞에 새로운 노드를 삽입합니다."""
        new_node = DoublyNode(data)
        new_node.next = self.head
        if self.head is not None:
            self.head.prev = new_node
        self.head = new_node

    def insert_end(self, data):
        """리스트의 맨 끝에 새로운 노드를 삽입합니다."""
        new_node = DoublyNode(data)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def delete_node(self, node):
        """주어진 노드를 삭제합니다."""
        if self.head is None or node is None:
            return

        if self.head == node:
            self.head = node.next

        if node.next is not None:
            node.next.prev = node.prev

        if node.prev is not None:
            node.prev.next = node.next

        node = None

    def search(self, key):
        """리스트에서 주어진 값을 가진 노드를 찾습니다."""
        current = self.head
        while current is not None:
            if current.data == key:
                return True
            current = current.next
        return False

    def traverse_forward(self):
        """리스트의 모든 노드를 순서대로 방문합니다 (정방향)."""
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

    def traverse_backward(self):
        """리스트의 모든 노드를 순서대로 방문합니다 (역방향)."""
        current = self.head
        last = None
        while current:
            last = current
            current = current.next

        while last:
            print(last.data, end=" <-> ")
            last = last.prev
        print("None")

# 사용 예시
dll = DoublyLinkedList()
dll.insert_front(1)
dll.insert_front(2)
dll.insert_end(3)
dll.traverse_forward()  # Output: 2 <-> 1 <-> 3 <-> None
dll.traverse_backward() # Output: 3 <-> 1 <-> 2 <-> None
dll.delete_node(dll.head.next)  # 노드 1을 삭제
dll.traverse_forward()  # Output: 2 <-> 3 <-> None
print(dll.search(2))  # Output: True
print(dll.search(4))  # Output: False

코드 설명

DoublyNode 클래스:

• __init__ 메서드는 노드가 저장할 데이터(data), 이전 노드를 가리키는 포인터(prev), 다음 노드를 가리키는 포인터(next)를 초기화합니다.

DoublyLinkedList 클래스:

• __init__ 메서드는 리스트의 시작을 가리키는 포인터(head)를 초기화합니다.
• insert_front 메서드는 리스트의 맨 앞에 새로운 노드를 삽입합니다. 새로운 노드의 next 포인터는 현재의 head를 가리키며, head가 가리키는 노드의 prev 포인터는 새로운 노드를 가리킵니다. 그리고 head는 새 노드를 가리키도록 업데이트됩니다.
• insert_end 메서드는 리스트의 맨 끝에 새로운 노드를 삽입합니다. 리스트가 비어 있으면 head가 새로운 노드를 가리키도록 하고, 그렇지 않으면 리스트의 끝까지 이동하여 새 노드를 추가합니다.
• delete_node 메서드는 리스트에서 주어진 노드를 삭제합니다. 삭제할 노드가 head인지, 중간에 있는지, 끝에 있는지에 따라 포인터를 적절히 업데이트합니다.
• search 메서드는 리스트를 순회하며 주어진 값을 가진 노드를 찾습니다. 값을 찾으면 True를 반환하고, 그렇지 않으면 False를 반환합니다.
• traverse_forward 메서드는 리스트의 모든 노드를 정방향으로 순서대로 방문하여 데이터를 출력합니다. 노드가 끝나면 None을 출력합니다.
• traverse_backward 메서드는 리스트의 모든 노드를 역방향으로 순서대로 방문하여 데이터를 출력합니다. 노드가 끝나면 None을 출력합니다.

---

05. 원형 연결 리스트 구현🔁

원형 연결 리스트(Circular Linked List)는 마지막 노드가 첫 번째 노드를 가리키는 구조를 가지고 있습니다. 이 구조는 단일 또는 이중 연결 리스트로 구현할 수 있습니다. 여기서는 단일 원형 연결 리스트를 구현해보겠습니다. 이 구현에는 삽입, 삭제, 탐색, 순회 등의 기본 연산을 포함합니다.

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

class CircularLinkedList:
    def __init__(self):
        self.head = None  # 리스트의 시작을 가리키는 포인터

    def insert_front(self, data):
        """리스트의 맨 앞에 새로운 노드를 삽입합니다."""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.head.next = self.head
        else:
            temp = self.head
            while temp.next != self.head:
                temp = temp.next
            new_node.next = self.head
            temp.next = new_node
            self.head = new_node

    def insert_end(self, data):
        """리스트의 맨 끝에 새로운 노드를 삽입합니다."""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.head.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 delete_node(self, key):
        """리스트에서 주어진 값을 가진 첫 번째 노드를 삭제합니다."""
        if self.head is None:
            return
        
        temp = self.head
        prev = None

        # 리스트에 노드가 하나인 경우
        if temp.data == key and temp.next == self.head:
            self.head = None
            return

        # 리스트의 첫 번째 노드를 삭제하는 경우
        if temp.data == key:
            while temp.next != self.head:
                temp = temp.next
            temp.next = self.head.next
            self.head = self.head.next
            return

        # 리스트의 중간 또는 마지막 노드를 삭제하는 경우
        while temp.next != self.head:
            prev = temp
            temp = temp.next
            if temp.data == key:
                prev.next = temp.next
                return

    def search(self, key):
        """리스트에서 주어진 값을 가진 노드를 찾습니다."""
        if self.head is None:
            return False
        
        temp = self.head
        while True:
            if temp.data == key:
                return True
            temp = temp.next
            if temp == self.head:
                break
        return False

    def traverse(self):
        """리스트의 모든 노드를 순서대로 방문합니다."""
        if self.head is None:
            print("List is empty")
            return
        
        temp = self.head
        while True:
            print(temp.data, end=" -> ")
            temp = temp.next
            if temp == self.head:
                break
        print("HEAD")

# 사용 예시
cll = CircularLinkedList()
cll.insert_front(1)
cll.insert_front(2)
cll.insert_end(3)
cll.traverse()  # Output: 2 -> 1 -> 3 -> HEAD
cll.delete_node(1)
cll.traverse()  # Output: 2 -> 3 -> HEAD
print(cll.search(2))  # Output: True
print(cll.search(4))  # Output: False

코드 설명

Node 클래스:

• __init__ 메서드는 노드가 저장할 데이터(data)와 다음 노드를 가리키는 포인터(next)를 초기화합니다.

CircularLinkedList 클래스:

• __init__ 메서드는 리스트의 시작을 가리키는 포인터(head)를 초기화합니다.
• insert_front 메서드는 리스트의 맨 앞에 새로운 노드를 삽입합니다. 리스트가 비어 있으면 새 노드의 next 포인터는 자기 자신을 가리키도록 설정합니다. 그렇지 않으면 리스트를 순회하여 마지막 노드를 찾고, 새 노드를 head로 설정하며, 마지막 노드의 next 포인터를 새 노드로 설정합니다.
• insert_end 메서드는 리스트의 맨 끝에 새로운 노드를 삽입합니다. 리스트가 비어 있으면 새 노드의 next 포인터는 자기 자신을 가리키도록 설정합니다. 그렇지 않으면 리스트를 순회하여 마지막 노드를 찾고, 새 노드를 마지막 노드의 next 포인터에 연결합니다.
• delete_node 메서드는 리스트에서 주어진 값을 가진 첫 번째 노드를 삭제합니다. 삭제할 노드가 head인지, 중간에 있는지, 끝에 있는지에 따라 포인터를 적절히 업데이트합니다.
• search 메서드는 리스트를 순회하며 주어진 값을 가진 노드를 찾습니다. 값을 찾으면 True를 반환하고, 그렇지 않으면 False를 반환합니다.
• traverse 메서드는 리스트의 모든 노드를 순서대로 방문하여 데이터를 출력합니다. 마지막에는 HEAD를 출력하여 원형 리스트의 끝을 나타냅니다.

---

06. 연결 리스트와 관련된 문제 해결🔍

연결 리스트에서 중복 제거 해결 방법:

• 방법 1: set을 사용하여 O(n) 시간 복잡도로 중복을 제거할 수 있습니다. 각 노드를 순회하면서 이미 등장한 값을 set에 저장하고, 다음에 동일한 값이 등장하면 삭제합니다.
• 방법 2: 두 개의 포인터를 사용하여 모든 노드를 비교하며 중복을 제거합니다. 이 방법은 추가적인 메모리 없이 해결할 수 있습니다.

Python 코드 (방법 1, set 사용):

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

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

    def insert_end(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def remove_duplicates(self):
        seen = set()
        current = self.head
        prev = None
        while current:
            if current.data in seen:
                prev.next = current.next
            else:
                seen.add(current.data)
                prev = current
            current = current.next

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

# 사용 예시
sll = SinglyLinkedList()
sll.insert_end(1)
sll.insert_end(2)
sll.insert_end(2)
sll.insert_end(3)
sll.insert_end(3)
sll.traverse()  # Output: 1 -> 2 -> 2 -> 3 -> 3 -> None
sll.remove_duplicates()
sll.traverse()  # Output: 1 -> 2 -> 3 -> None

Python 코드 (방법 2, 두 포인터 사용):

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

    def insert_end(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def remove_duplicates(self):
        current = self.head
        while current:
            runner = current
            while runner.next:
                if runner.next.data == current.data:
                    runner.next = runner.next.next
                else:
                    runner = runner.next
            current = current.next

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

# 사용 예시
sll = SinglyLinkedList()
sll.insert_end(1)
sll.insert_end(2)
sll.insert_end(2)
sll.insert_end(3)
sll.insert_end(3)
sll.traverse()  # Output: 1 -> 2 -> 2 -> 3 -> 3 -> None
sll.remove_duplicates()
sll.traverse()  # Output: 1 -> 2 -> 3 -> None

---

연결 리스트 길이 구하기:

 

문제: 연결 리스트의 길이를 구합니다.

해결 방법: 리스트를 순회하며 노드의 개수를 카운트합니다.

Python 코드:

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

    def insert_end(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def length(self):
        count = 0
        current = self.head
        while current:
            count += 1
            current = current.next
        return count

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

# 사용 예시
sll = SinglyLinkedList()
sll.insert_end(1)
sll.insert_end(2)
sll.insert_end(3)
print(sll.length())  # Output: 3

---

연결 리스트에서 특정 값 찾기:

 

문제: 연결 리스트에서 특정 값을 가진 노드를 찾습니다.

해결 방법: 리스트를 순회하면서 각 노드의 값을 확인합니다.

Python 코드:

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

    def insert_end(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def search(self, key):
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

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

# 사용 예시
sll = SinglyLinkedList()
sll.insert_end(1)
sll.insert_end(2)
sll.insert_end(3)
print(sll.search(2))  # Output: True
print(sll.search(4))  # Output: False