프로그래머가 알아야 할 필수 자료구조 8가지

나홀로 알고리즘 스터디도 어느 덧 3주차가 되었다. 그런데 2주차 문제를 풀다보니
"아직 내 머릿 속에 자료구조가 제대로 정리되지 않았구나" 를 깨닫고 정리해보는 오늘의 포스팅.

"자료 구조(Data Structure)"가 무엇이길래?

출처: https://www.codetree.ai

오늘은 컴퓨터 과학의 기본이자 모든 개발자가 반드시 알아야 할 자료구조(Data Structure)에 대해 이야기해 보려 합니다. 자료구조는 데이터를 효율적으로 저장하고 관리하는 방법을 의미하는데요. 마치 물건을 정리할 때 옷장, 서랍, 상자 등 목적에 맞는 도구를 사용하는 것과 같습니다. 이 글을 통해 가장 기본이 되는 8가지 자료구조를 쉽게 이해하고, 실제 코딩에 어떻게 적용되는지 감을 잡을 수 있기를 바랍니다.

1. 배열 (Array) ≒ 파이썬의 List

출처: https://takeuforward.org

배열은 가장 기본적인 자료구조로, 동일한 타입의 데이터를 메모리에 연속적으로 나열하여 저장합니다. 덕분에 인덱스(index)를 사용해 원하는 데이터에 빠르게 접근할 수 있다는 장점이 있습니다. 다만, 크기를 한 번 정하면 변경하기 어렵고, 중간에 데이터를 삽입하거나 삭제할 때 많은 데이터를 옮겨야 하므로 비효율적입니다.

• 장점: 빠른 접근 속도 (O(1))
• 단점: 크기 변경의 어려움, 비효율적인 삽입/삭제 (O(n))
• 예시: 전화번호부, 게임의 맵 데이터, 행렬 계산

2. 연결 리스트 (Linked List)

출처: https://velog.io/@717lumos

연결 리스트에는 단일 연결 리스트와 이중 연결 리스트가 있으며, 메모리에 비연속적으로 흩어져 있는 데이터를 노드(node)라는 단위로 연결한 구조입니다. 각 노드는 데이터와 다음 노드의 주소를 가리키는 포인터를 가집니다. 덕분에 데이터의 삽입과 삭제가 매우 빠르다는 장점이 있지만, 원하는 데이터에 접근하려면 처음부터 순차적으로 따라가야 하므로 접근 속도가 느립니다.

• 장점: 빠른 삽입/삭제 (O(1))
• 단점: 느린 접근 속도 (O(n))
• 예시: 웹 브라우저의 '뒤로 가기' 기능, 음악 재생 목록
  
  

1) 단일 연결 리스트 (Singly Linked List)

단일 연결 리스트는 가장 기본적인 연결 리스트 형태로, 각 노드가 다음 노드의 주소만 가지고 있습니다. 이는 노드를 한 방향으로만 탐색할 수 있다는 의미입니다. 새로운 노드를 추가하거나 기존 노드를 삭제하는 데 효율적이지만, 이전 노드로 돌아가려면 리스트의 시작부터 다시 탐색해야 한다는 단점이 있습니다.

# 연결 리스트 구현 코드

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
        
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node
        
    def print_list(self):
        current_node = self.head
        while current_node:
            print(current_node.data, end=" -> ")
            current_node = current_node.next
        print("None")
        
        
my_list = LinkedList()
my_list.append("A")
my_list.append("B")
my_list.append("C")

my_list.print_list()  # A -> B -> C -> None

이렇게 파이썬에는 내장된 연결 리스트 자료구조가 없기에 위의 예시처럼 Node 클래스와 LinkedList 클래스를 만들어 연결 리스트를 구현해야 합니다.

2) 이중 연결 리스트 (Doubly Linked List)

이중 연결 리스트는 단일 연결 리스트의 단점을 보완한 형태로, 각 노드가 이전 노드의 주소와 다음 노드의 주소를 모두 가지고 있습니다. 이 덕분에 양방향으로 탐색이 가능해져 특정 노드의 앞뒤로 쉽게 이동할 수 있습니다. 단일 연결 리스트보다 더 유연하지만, 각 노드에 포인터가 하나 더 추가되어 메모리 사용량이 늘어나는 오버헤드가 발생합니다.

3. 스택 (Stack)

출처: https://www.programiz.com

쌓는다는 의미를 가진 스택은 접시를 쌓아 올리거나 빼는 것처럼, LIFO(Last-In, First-Out) 원칙에 따라 동작하는 자료구조입니다. 가장 마지막에 들어온 데이터가 가장 먼저 나갑니다. 데이터를 넣는 연산을 '푸시(push)', 데이터를 빼는 연산을 '팝(pop)'이라고 합니다.

• 특징: LIFO (Last In First Out, 후입선출)
• 장점: 단순하고 직관적인 구조
• 단점: 중간 데이터 접근 불가
• 예시: 웹 브라우저의 '뒤로 가기', 함수 호출 스택, 실행 취소(Undo)

4. 큐 (Queue)

출처: https://www.saralcode.com

큐는 줄을 서는 것처럼, FIFO(First-In, First-Out) 원칙에 따라 동작하는 자료구조입니다. 현실 세계에서 우리가 가장 앞에 줄을 선 사람이 가장 먼저 계산을 하고 나가는 것 처럼, 큐를 사용하면 가장 먼저 들어온 데이터가 가장 먼저 나갑니다. 데이터를 넣는 연산을 '인큐(enqueue)', 데이터를 빼는 연산을 '디큐(dequeue)'라고 합니다.

• 특징: FIFO (First In First Out, 선입선출)
• 장점: 공정한 데이터 처리 순서 보장
• 단점: 중간 데이터 접근 불가
• 예시: 프린터 인쇄 대기열, 운영체제의 작업 스케줄링

5. 해시 테이블 (Hash Table)

출처: https://velog.io/@kimhyeongi

해시 테이블은 키(key)와 값(value)을 한 쌍으로 저장하는 자료구조입니다. 해시 함수를 이용해 키를 특정 주소에 매핑함으로써, 원하는 데이터를 거의 즉시 찾아낼 수 있다는 강력한 장점을 가집니다. 파이썬의 dictionary가 바로 해시 테이블로 구현되어 있습니다.

• 장점: 매우 빠른 탐색, 삽입, 삭제 (O(1))
• 단점: 해시 충돌(collision) 가능성, 비연속적인 메모리 저장
• 예시: 전화번호부, 로그인 시스템, 캐시

여기서 해시 충돌(Hash Collision)이란 서로 다른 키(key)가 해시 함수를 거쳐 동일한 인덱스(index)로 변환되는 현상을 말합니다.

해시 테이블은 키를 해시 함수에 넣어 얻은 인덱스에 데이터를 저장하는데, 이 해시 함수가 완벽하지 않아 여러 키가 같은 인덱스를 가리키게 되는 거죠. 예를 들어, 'apple'과 'orange'라는 두 단어가 있다고 가정해 볼게요. 이상적인 해시 함수는 이 둘을 서로 다른 인덱스로 매핑해야 하지만, 만약 둘 다 인덱스 5로 변환된다면 해시 충돌이 발생한 겁니다.

이런 충돌이 발생하면 데이터를 어디에 저장해야 할지, 또는 어떻게 찾아야 할지 문제가 생기기 때문에, 이를 해결하는 여러 방법(예: 개별 체이닝, 개방 주소법)이 존재합니다.

1) 개별 체이닝 (Separate Chaining)

출처: https://you88.tistory.com/36

해시 충돌이 발생한 인덱스에 연결 리스트를 사용하여 여러 데이터를 저장하는 방법입니다. 각 버킷(bucket)이 하나의 연결 리스트를 가리키고, 충돌이 발생하면 해당 연결 리스트의 끝에 새로운 노드를 추가합니다.

동작 방식:

• 해시 함수를 통해 인덱스를 계산합니다.
• 해당 인덱스에 이미 다른 데이터가 있다면, 그 자리에 있는 연결 리스트에 새로운 노드를 연결합니다.
• 데이터를 찾을 때는, 인덱스로 이동한 후 연결 리스트를 순회하며 원하는 키를 찾습니다.
  
  

2) 개방 주소법 (Open Addressing)

출처: https://you88.tistory.com/36

해시 충돌이 발생하면, 비어 있는 다른 버킷을 찾아 데이터를 저장하는 방법입니다. 데이터를 저장할 다른 "열린 주소"를 찾는다고 해서 개방 주소법이라고 부릅니다.

동작 방식:

• 해시 함수를 통해 인덱스를 계산합니다.
• 해당 인덱스가 이미 차 있으면, 미리 정해진 규칙(탐사법)에 따라 다음 빈 버킷을 찾습니다.
• 데이터를 찾을 때는, 동일한 탐사 순서를 따라가며 원하는 키를 찾거나 빈 버킷을 만날 때까지 탐색합니다.

6. 트리 (Tree)

출처: https://sites.ualberta.ca

트리는 나무를 거꾸로 뒤집어 놓은 듯한 계층적인 비선형 자료구조입니다. 데이터들이 부모-자식 관계를 가지며, 계층적 데이터를 표현하는 데 매우 효과적입니다. 특히 이진 탐색 트리(Binary Search Tree)는 효율적인 탐색을 가능하게 합니다.

• 특징: 계층적 구조
• 장점: 효율적인 탐색, 삽입, 삭제
• 단점: 균형이 깨지면 비효율적 (트리 불균형)
• 예시: 파일 시스템, 데이터베이스 인덱스

7. 힙 (Heap)

출처: https://medium.com/@ishta.pal

힙은 최댓값 또는 최솟값을 빠르게 찾기 위한 특별한 종류의 트리입니다. 부모 노드는 항상 자식 노드보다 크거나(최대 힙) 작아야(최소 힙) 한다는 규칙을 가집니다. 이를 통해 최댓값/최솟값을 $O(1)$의 시간 복잡도로 쉽게 찾을 수 있습니다.

• 특징: 최대/최소값을 빠르게 찾기 위한 트리
• 장점: 최대/최소값 탐색이 매우 빠름 (O(1))
• 단점: 중간 값 탐색이 어려움
• 예시: 우선순위 큐(Priority Queue), 힙 정렬(Heap Sort)

8. 그래프 (Graph)

출처: https://smartxbrains.in

그래프는 현실 세계의 복잡한 연결 관계를 표현하는 데 사용되는 자료구조입니다. 데이터(노드 또는 정점)와 그 데이터 간의 연결(간선)로 이루어집니다. 소셜 네트워크 관계, 도로망, 회로도 등을 표현하는 데 유용합니다.

• 특징: 비선형 구조, 복잡한 관계 표현
• 장점: 현실의 복잡한 연결 관계 모델링에 적합
• 단점: 구현 및 알고리즘이 복잡함
• 예시: 내비게이션 길 찾기, 소셜 네트워크의 친구 관계, 추천 시스템

배열과 파이썬의 리스트, 연결 리스트는 무엇이 다를까?

배열, 리스트, 연결 리스트는 메모리 할당 방식과 그에 따른 성능이 다릅니다. 배열은 고정된 크기로 메모리에 연속적으로 데이터를 저장해 접근이 빠르지만, 삽입/삭제가 비효율적입니다. 리스트(동적 배열)는 배열의 확장형으로, 연속된 메모리를 사용하며 크기가 자동으로 조절되지만, 삽입/삭제의 비효율성은 같습니다. 반면, 연결 리스트는 비연속적인 메모리에 노드들이 포인터로 연결되어 있어 삽입/삭제가 빠르지만, 특정 데이터에 접근하려면 순차적으로 탐색해야 해 느립니다.

세 가지 자료구조 비교 요약

특징	배열(Array)	리스트(Python List)	연결 리스트(Linked List)
메모리 할당	연속적	연속적	비연속적
크기	고정	동적(자동 확장)	동적
접근 속도	O(1) (빠름)	O(1) (빠름)	O(n) (느림)
삽입/삭제 속도	O(n) (느림)	O(n) (느림)	O(1) (빠름)
대표적인 사용처	행렬, 정적 데이터	대부분의 일반적인 리스트 작업	잦은 삽입/삭제가 필요한 스택, 큐

배열 vs 연결 리스트: 파고들기

그리고 위 세가지 중 배열과 연결 리스트는 특히 자주 비교되곤 합니다.
아래에 이해를 돕기 위한 사진을 한 장 가져왔습니다.

출처: https://www.sahinarslan.tech

각각의 저장 공간을 나타내고 있는 위 사진을 통해 짐작할 수 있듯, 연결 리스트는 노드가 포인터로 연결되어 있어 메모리의 빈 공간 아무데나 저장이 가능하지만 데이터 접근이 느리다는 장단점이, 배열은 함께 저장되어야 하기 때문에 반대로 데이터 접근은 빠르지만 삽입/삭제시 데이터를 통째로 저장할 공간을 찾아야 하기 때문에 비효율적이라는 장단점이 있습니다.

마무리

이렇게 오늘은 컴퓨터 과학의 핵심인 자료구조에 대해 알아보았다.
각 자료구조는 데이터를 저장하고 관리하는 고유한 방식과 장단점을 가지고 있으며 이에 대한 이해는 문제 해결 능력을 향상시키는 데 매우 중요하니 꼭 알아두자구요!

참고자료

[yes_dohyun]님의 블로그: https://yesdohyun.tistory.com/21
[코딩하는체대생]님의 블로그: https://mini-min-dev.tistory.com/137
[옹벨 일기]님의 블로그: https://ongveloper.tistory.com/403
[코딩알려주는누나]님의 YouTube: https://www.youtube.com/watch?v=Q2Up3PN0-nM