리스트: Singly Linked List와 Doubly Linked List

5.1 리스트의 정의와 종류

리스트란 요소(노드)들로 이루어진 동적 데이터 구조로, 각 노드는 데이터와 다른 노드에 대한 링크를 가지고 있어. 배열과는 달리, 리스트는 프로그램 실행 중에 크기를 변경할 수 있어.

중요해! 여기서는 Python의 list 클래스가 아니라, 알고리즘 이론에서의 데이터 구조를 이야기하고 있어.

리스트의 종류:

• Singly Linked List: 각 노드는 데이터와 다음 노드에 대한 링크를 포함해.
• Doubly Linked List: 각 노드는 데이터, 다음 노드에 대한 링크, 이전 노드에 대한 링크를 포함해.

5.2 Singly Linked List의 작동 원리

Singly Linked List의 구조:

• 노드 (Node): 데이터와 다음 노드에 대한 링크, 두 부분으로 구성됨.
• 헤드 (Head): 리스트의 첫 번째 노드를 가리키는 포인터.

작동 원리:

• 노드 추가: 새로운 노드를 생성하고, 마지막 노드의 링크를 새로운 노드로 업데이트하는 방식.
• 노드 삭제: 삭제할 노드의 이전 노드가 다음 노드를 가리키도록 링크를 업데이트해야 해.

구현 예시:

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
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

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

# 사용 예시:
sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.display()  # 출력: 1 -> 2 -> 3 -> None

5.3 Doubly Linked List의 작동 원리

Doubly Linked List의 구조:

• 노드 (Node): 데이터, 다음 노드에 대한 링크, 이전 노드에 대한 링크, 세 부분으로 구성됨.
• 헤드 (Head): 리스트의 첫 번째 노드를 가리키는 포인터.
• 테일(Tail): 리스트의 마지막 노드를 가리키는 포인터 (꼭 필요한 건 아니지만 자주 사용됨).

작동 원리:

• 노드 추가: 새로운 노드를 생성하고, 마지막 노드와 새로운 노드의 링크를 업데이트하는 방식.
• 노드 삭제: 삭제할 노드의 이전 노드와 다음 노드의 링크를 업데이트해야 해.

구현 예시:

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

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

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

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

# 사용 예시:
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.display()  # 출력: 1 <-> 2 <-> 3 <-> None

5.4 주요 연산

주요 연산: 삽입, 삭제, 검색

삽입:

• Singly Linked List: 리스트의 끝에 새 노드를 삽입 하려면 마지막 노드까지 모든 노드를 통과해야 해 그리고 마지막 노드의 링크를 업데이트해야 해.
• Doubly Linked List: 리스트의 끝에 새 노드를 삽입하는 것은 Singly Linked List와 동일하지만, 이전 노드에 대한 링크 prev도 업데이트해야 해.

삭제:

• Singly Linked List: 노드를 삭제하려면 삭제할 노드까지 리스트를 통과해야 해 그리고 삭제할 노드의 이전 노드가 다음 노드를 가리키도록 링크를 업데이트해야 해.
• Doubly Linked List: 노드를 삭제하려면 삭제할 노드의 이웃 노드의 next와 prev 링크를 업데이트해야 해.

검색: 헤드부터 테일까지 리스트를 통과하며 각 노드의 데이터를 찾고자 하는 값과 비교해. 시간 복잡도는 O(n)이야.

5.5 리스트 사용 예시

Singly Linked List 기반으로 스택을 구현해 보자.

스택은 push와 pop 메서드를 사용하여 쉽게 Singly Linked List로 구현할 수 있어. 두 가지 메서드가 필요해:

• push — 새 요소를 리스트의 끝에 추가하는 것
• pop — 리스트의 끝에서 마지막 요소를 추출하는 것

구현 예시:

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

class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if not self.top:
            return None
        data = self.top.data
        self.top = self.top.next
        return data

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

# 사용 예시:
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.display()  # 출력: 3 -> 2 -> 1 -> None
print(stack.pop())  # 출력: 3
stack.display()  # 출력: 2 -> 1 -> None