파이썬에서 stack, queue, linked list 구현하기

728x90

파이썬에서 주요 자료구조 사용 및 구현

자료구조는 데이터를 효율적으로 저장하고 처리하기 위한 체계이다.

이 글에서는 스택, 큐, 연결 리스트와 같은 주요 자료구조를 파이썬에서 구현하는 방법을 알아보자

1. 스택(Stack)

스택은 후입선출(LIFO, Last In First Out) 방식으로 동작하는 자료구조이다.

파이썬에서는 리스트를 사용하여 스택을 구현하거나,

collections 모듈의 deque를 사용할 수 있다.

1.1 리스트를 사용한 스택 구현

stack = []

# 스택에 요소 추가 (push)
stack.append(10)
stack.append(20)
stack.append(30)

# 스택에서 요소 제거 (pop)
element = stack.pop()
print("제거된 요소:", element)  # 30

# 현재 스택 상태
print("스택 상태:", stack)  # [10, 20]

시간 복잡도:
- append(): O(1)
- pop(): O(1)

1.2 `deque`를 사용한 스택 구현

deque는 리스트보다 효율적인 스택 연산을 제공한다.

from collections import deque

stack = deque()

# 요소 추가
stack.append(10)
stack.append(20)

# 요소 제거
element = stack.pop()
print("제거된 요소:", element)  # 20

시간 복잡도:
- append(): O(1)
- pop(): O(1)

2. 큐(Queue)

큐는 선입선출(FIFO, First In First Out) 방식으로 동작하는 자료구조이다.

파이썬에서는 deque를 사용하여 큐를 구현할 수 있다.

2.1 `deque`를 사용한 큐 구현

from collections import deque

queue = deque()

# 큐에 요소 추가 (enqueue)
queue.append(10)
queue.append(20)
queue.append(30)

# 큐에서 요소 제거 (dequeue)
element = queue.popleft()
print("제거된 요소:", element)  # 10

# 현재 큐 상태
print("큐 상태:", queue)  # [20, 30]

시간 복잡도:
- append(): O(1)
- popleft(): O(1)

2.2 리스트를 사용한 큐 구현

리스트를 사용하여 큐를 구현할 수도 있지만, 효율성이 떨어진다.

queue = []

# 요소 추가
queue.append(10)
queue.append(20)

# 요소 제거
element = queue.pop(0)
print("제거된 요소:", element)  # 10

시간 복잡도:
- append(): O(1)
- pop(0): O(n) (앞 요소를 제거하면 모든 요소를 이동시켜야 한다.)

3. 연결 리스트(Linked List)

연결 리스트는 노드(Node)들이 순차적으로 연결된 형태의 자료구조이다.

각 노드는 데이터를 저장하는 필드와 다음 노드에 대한 참조를 포함한다.

3.1 단일 연결 리스트 구현

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

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

# 사용 예시
ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.display()  # 10 -> 20 -> 30 -> None

시간 복잡도:
- 추가(append): O(n) (리스트의 끝까지 탐색)
- 탐색(search): O(n)

3.2 연결 리스트의 요소 삭제

def delete(self, key):
    current = self.head

    # 첫 번째 노드를 삭제하는 경우
    if current and current.data == key:
        self.head = current.next
        current = None
        return

    # 나머지 노드를 탐색하며 삭제
    prev = None
    while current and current.data != key:
        prev = current
        current = current.next

    if current is None:
        return

    prev.next = current.next
    current = None

시간 복잡도:
- 삭제(delete): O(n)

4. 정리

자료구조	주요 연산	리스트 기반 시간 복잡도	deque 기반 시간 복잡도	연결 리스트 시간 복잡도
스택	push, pop	O(1)	O(1)	-
큐	enqueue, dequeue	O(n), O(1)	O(1), O(1)	-
연결 리스트	append, delete	O(n), O(n)	-	O(n), O(n)

파이썬은 기본적으로 리스트와 deque를 제공하므로, 간단한 구현은 이들을 활용하면 된다.

연결 리스트와 같은 자료구조는 직접 구현하며 자료구조의 원리를 이해하는 데 도움이 된다.