[자료구조] 스택, 큐, 링크드 리스트 구현 개념 정리

스택, 큐, 링크드 리스트

자료구조는 데이터를 어떤 방식으로 저장하고 꺼낼지 정하는 구조이다.

 

같은 데이터라도 저장 방식에 따라 삽입, 삭제, 탐색의 효율이 달라진다.

이번 글에서는 기본 자료구조인 스택, 큐, 링크드 리스트를 정리해보고자 한다.

 

스택

스택은 나중에 들어온 데이터가 먼저 나가는 자료구조이다.

이를 LIFO(Last In First Out) 구조라고 한다.

 

쉽게 생각하면 접시를 쌓는 모습을 떠올리면 된다.

접시를 하나씩 위에 올리고, 꺼낼 때는 가장 위에 있는 접시부터 꺼낸다.

 

먼저 들어온 데이터는 아래에 쌓인다.
나중에 들어온 데이터는 위에 쌓인다.
꺼낼 때는 가장 위의 데이터부터 꺼낸다.

 

스택에서 자주 사용하는 연산은 다음과 같다.

push
데이터를 스택에 넣는다.

pop
가장 마지막에 들어온 데이터를 꺼낸다.

peek
가장 위에 있는 데이터를 확인만 한다.

is_empty
스택이 비어 있는지 확인한다.

 

스택 구현

파이썬에서는 리스트를 이용해 스택을 쉽게 구현할 수 있다.

stack = []

stack.append(1)
stack.append(2)
stack.append(3)

print(stack)

 

출력은 다음과 같다.

[1, 2, 3]

 

여기서 가장 마지막에 들어온 값은 3이다.

print(stack.pop())
print(stack)

 

출력은 다음과 같다.

3
[1, 2]

 

pop()은 리스트의 마지막 값을 꺼낸다.

스택의 LIFO 구조와 잘 맞는다.

 

간단한 스택 클래스를 만들면 다음과 같다.

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if self.is_empty():
            return None
        return self.items.pop()

    def peek(self):
        if self.is_empty():
            return None
        return self.items[-1]

    def is_empty(self):
        return len(self.items) == 0

 

사용 예시는 다음과 같다.

 

stack = Stack()

stack.push(10)
stack.push(20)
stack.push(30)

print(stack.peek())
print(stack.pop())
print(stack.pop())

 

출력은 다음과 같다.

30
30
20

 

스택은 가장 최근에 저장한 데이터를 먼저 처리해야 할 때 사용된다.

 

예를 들어 함수 호출, 괄호 검사, 뒤로 가기 기능, 깊이 우선 탐색 DFS 등에 활용된다.

 

큐

큐는 먼저 들어온 데이터가 먼저 나가는 자료구조이다.

이를 FIFO(First In First Out) 구조라고 한다.

 

줄을 서는 상황을 생각하면 쉽다.

먼저 줄을 선 사람이 먼저 서비스를 받는다.

먼저 들어온 데이터가 앞에 있다.
나중에 들어온 데이터는 뒤에 붙는다.
꺼낼 때는 가장 앞의 데이터부터 꺼낸다.

 

큐에서 자주 사용하는 연산은 다음과 같다.

enqueue
데이터를 큐의 뒤쪽에 넣는다.

dequeue
큐의 앞쪽 데이터를 꺼낸다.

front
가장 앞에 있는 데이터를 확인한다.

is_empty
큐가 비어 있는지 확인한다.

 

큐 구현

파이썬 리스트로도 큐를 만들 수 있다.

queue = []

queue.append(1)
queue.append(2)
queue.append(3)

print(queue)

 

출력은 다음과 같다.

[1, 2, 3]

 

가장 먼저 들어온 값은 1이다.

print(queue.pop(0))
print(queue)

 

출력은 다음과 같다.

1
[2, 3]

 

다만 리스트에서 pop(0)을 사용하면 앞의 값을 꺼낸 뒤 나머지 원소들을 한 칸씩 앞으로 옮겨야 한다.

 

데이터가 많아질수록 비효율적이다.

 

그래서 파이썬에서는 큐를 구현할 때 collections.deque를 자주 사용한다.

from collections import deque

queue = deque()

queue.append(1)
queue.append(2)
queue.append(3)

print(queue.popleft())
print(queue)

 

출력은 다음과 같다.

1
deque([2, 3])

 

deque는 양쪽 끝에서 삽입과 삭제가 빠르다.

간단한 큐 클래스를 만들면 다음과 같다.

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if self.is_empty():
            return None
        return self.items.popleft()

    def front(self):
        if self.is_empty():
            return None
        return self.items[0]

    def is_empty(self):
        return len(self.items) == 0

 

사용 예시는 다음과 같다.

queue = Queue()

queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)

print(queue.front())
print(queue.dequeue())
print(queue.dequeue())

 

출력은 다음과 같다.

10
10
20

 

큐는 먼저 들어온 작업을 먼저 처리해야 할 때 사용된다.

 

예를 들어 프린터 대기열, 작업 스케줄링, 너비 우선 탐색 BFS, 메시지 큐 등에 활용된다.

 

스택과 큐 비교

스택과 큐는 데이터를 넣고 꺼내는 순서가 다르다.

구분	스택	큐
구조	LIFO	FIFO
의미	나중에 들어온 데이터가 먼저 나감	먼저 들어온 데이터가 먼저 나감
삽입	push	enqueue
삭제	pop	dequeue
예시	접시 쌓기	줄 서기
활용	DFS, 뒤로 가기, 괄호 검사	BFS, 대기열, 작업 처리

짧게 정리하면 다음과 같다.

스택
마지막에 들어온 것을 먼저 꺼낸다.

큐
처음에 들어온 것을 먼저 꺼낸다.

 

링크드 리스트

링크드 리스트는 데이터를 노드 단위로 저장하고, 각 노드가 다음 노드를 가리키는 자료구조이다.

 

배열이나 리스트는 데이터가 메모리상에서 연속적으로 저장되는 구조에 가깝다.
반면 링크드 리스트는 각 데이터가 흩어져 있어도, 다음 노드의 위치를 알고 있으면 연결된 구조를 만들 수 있다.

 

링크드 리스트의 기본 단위는 노드이다.

노드 = 데이터 + 다음 노드 주소

 

예를 들어 다음과 같은 데이터가 있다고 하자.

10, 20, 30

 

링크드 리스트에서는 다음처럼 연결된다.

[10 | 다음] [20 | 다음] [30 | None]

 

각 노드는 자신의 데이터와 다음 노드를 가리키는 정보를 가진다.

 

마지막 노드는 더 이상 다음 노드가 없으므로 None을 가리킨다.

노드 구현

파이썬으로 노드를 만들면 다음과 같다.

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

 

data에는 실제 값이 들어간다.

next에는 다음 노드가 들어간다.

 

노드 3개를 직접 연결해보면 다음과 같다.

node1 = Node(10)
node2 = Node(20)
node3 = Node(30)

node1.next = node2
node2.next = node3

 

이렇게 하면 node1에서 출발해 node2, node3으로 이동할 수 있다.

current = node1

while current is not None:
    print(current.data)
    current = current.next

 

출력은 다음과 같다.

10
20
30

 

링크드 리스트 구현

링크드 리스트는 보통 첫 번째 노드를 가리키는 head를 가진다.

head
첫 번째 노드를 가리키는 변수

 

간단한 단일 연결 리스트를 구현하면 다음과 같다.

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 self.head is None:
            self.head = new_node
            return

        current = self.head

        while current.next is not None:
            current = current.next

        current.next = new_node

    def print_all(self):
        current = self.head

        while current is not None:
            print(current.data)
            current = current.next

 

사용 예시는 다음과 같다.

linked_list = LinkedList()

linked_list.append(10)
linked_list.append(20)
linked_list.append(30)

linked_list.print_all()

 

출력은 다음과 같다.

10
20
30

 

append()는 리스트의 끝에 새 노드를 추가한다.

 

처음 노드가 없다면 새 노드가 head가 된다.

이미 노드가 있다면 마지막 노드까지 이동한 뒤, 마지막 노드의 next가 새 노드를 가리키게 한다.

 

링크드 리스트의 삽입

링크드 리스트의 장점은 중간 삽입과 삭제가 비교적 유연하다는 점이다.

 

예를 들어 10과 30 사이에 20을 넣고 싶다고 하자.

배열이라면 뒤의 원소들을 한 칸씩 밀어야 할 수 있다.

 

링크드 리스트에서는 연결만 바꾸면 된다.

기존
10이 30을 가리킴

삽입 후
10이 20을 가리킴
20이 30을 가리킴

 

연결 정보만 바꾸면 되기 때문에 중간 삽입이 효율적일 수 있다.

 

다만 삽입할 위치를 찾기 위해 처음부터 노드를 따라가야 한다.

특정 위치에 바로 접근하는 것은 배열보다 느리다.

링크드 리스트의 삭제

링크드 리스트에서 노드를 삭제할 때도 연결을 바꾼다.

 

예를 들어 10, 20, 30에서 20을 삭제한다고 하자.

기존
10이 20을 가리킴
20이 30을 가리킴

삭제 후
10이 30을 가리킴

 

20을 직접 없앤다기보다, 이전 노드인 10이 20을 건너뛰고 30을 가리키게 만든다.

간단한 삭제 메서드는 다음과 같다.

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

    def append(self, data):
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
            return

        current = self.head

        while current.next is not None:
            current = current.next

        current.next = new_node

    def delete(self, data):
        if self.head is None:
            return

        if self.head.data == data:
            self.head = self.head.next
            return

        current = self.head

        while current.next is not None:
            if current.next.data == data:
                current.next = current.next.next
                return
            current = current.next

    def print_all(self):
        current = self.head

        while current is not None:
            print(current.data)
            current = current.next

 

사용 예시는 다음과 같다.

linked_list = LinkedList()

linked_list.append(10)
linked_list.append(20)
linked_list.append(30)

linked_list.delete(20)

linked_list.print_all()

 

출력은 다음과 같다.

10
30

 

링크드 리스트의 특징

링크드 리스트는 배열과 다르게 인덱스로 바로 접근하기 어렵다.

 

예를 들어 세 번째 값을 찾으려면 head부터 시작해서 다음 노드를 따라가야 한다.

head에서 시작
다음 노드로 이동
다음 노드로 이동
원하는 노드 도착

 

그래서 탐색은 느릴 수 있다.

하지만 노드의 연결만 바꾸면 삽입과 삭제를 처리할 수 있기 때문에, 중간 삽입과 삭제가 자주 일어나는 구조에서는 유용할 수 있다.

구분	배열 또는 리스트	링크드리스트
저장 방식	연속된 공간에 저장	노드들이 연결됨
인덱스 접근	빠름	느림
중간 삽입	상대적으로 비효율적	연결만 바꾸면 됨
중간 삭제	상대적으로 비효율적	연결만 바꾸면 됨
메모리	데이터 중심	데이터와 다음 노드 정보 필요

 

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

가장 기본적인 링크드 리스트는 단일 연결 리스트이다.

 

단일 연결 리스트는 각 노드가 다음 노드만 가리킨다.

10 -> 20 -> 30

 

이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 모두 가리킨다.

10 <-> 20 <-> 30

 

이중 연결 리스트는 앞뒤로 이동할 수 있어서 더 유연하다.

하지만 각 노드가 이전 노드 정보까지 저장해야 하므로 메모리를 더 사용한다.

 

스택, 큐와 링크드 리스트의 관계

스택과 큐는 추상 자료형에 가깝다.

어떤 순서로 데이터를 넣고 꺼낼지에 대한 규칙이 중요하다.

스택
나중에 들어온 데이터를 먼저 꺼낸다.

큐
먼저 들어온 데이터를 먼저 꺼낸다.

 

반면 링크드 리스트는 데이터를 실제로 어떻게 저장할지에 대한 구현 방식에 가깝다.

스택과 큐는 배열로도 구현할 수 있고, 링크드 리스트로도 구현할 수 있다.

스택 구현
리스트로 구현 가능
링크드 리스트로 구현 가능

큐 구현
deque로 구현 가능
링크드 리스트로 구현 가능

 

링크드 리스트를 이용하면 스택의 push, pop을 노드 연결로 처리할 수 있다.

큐도 head와 tail을 잘 관리하면 enqueue, dequeue를 효율적으로 처리할 수 있다.

정리

스택, 큐, 링크드 리스트는 자료구조의 기본 개념이다.

 

스택은 나중에 들어온 데이터가 먼저 나가는 LIFO 구조이다.

데이터를 넣는 연산은 push, 데이터를 꺼내는 연산은 pop이라고 한다.
함수 호출, 뒤로 가기, 괄호 검사, DFS 등에 활용된다.

 

큐는 먼저 들어온 데이터가 먼저 나가는 FIFO 구조이다.

데이터를 넣는 연산은 enqueue, 데이터를 꺼내는 연산은 dequeue라고 한다.
작업 대기열, 프린터 큐, BFS, 메시지 처리 등에 활용된다.

 

링크드 리스트는 노드들이 연결된 자료구조이다.

각 노드는 데이터와 다음 노드를 가리키는 정보를 가진다.
첫 번째 노드는 head가 가리키고, 마지막 노드는 None을 가리킨다.

 

링크드 리스트는 인덱스로 바로 접근하기는 어렵지만, 연결만 바꾸면 삽입과 삭제를 처리할 수 있다.

 

스택과 큐는 데이터를 넣고 꺼내는 규칙이고, 링크드 리스트는 데이터를 저장하는 구현 방식이다.

 

간단히 정리하면 다음과 같다.

스택
마지막에 들어온 데이터가 먼저 나간다.

큐
처음에 들어온 데이터가 먼저 나간다.

링크드 리스트
노드들이 다음 노드를 가리키며 연결된 구조이다.