자료구조 종류 (파이썬 예시)

01 자료구조

1.  자료구조란

• 자료구조는 데이터를 효율적으로 저장하고 관리하는 방법을 제공하는 개념
• 다양한 자료구조가 있으며, 용도에 따라 적절한 자료구조를 선택해야 함

02 자료구조 종류

1. 배열 (Array)

1) 특징

• 같은 타입의 데이터를 연속된 메모리 공간에 저장
• 인덱스 (Index)를 사용하여 요소에 빠르게 접근 가능 (시간복잡도: O(1))
• 크기가 고정되어 있어 삽입/삭제가 비효율적 (시간복잡도: O(n))

2) 예시

arr = [10, 20, 30, 40, 50]
print(arr[2]) # 30

 

3) 활용 예시

• 리스트 기반의 순차적 데이터 저장
• 고정된 크기의 데이터 저장

 

2. 연결 리스트 (Linked List)

1) 특징

• 노드(Node) 단위로 구성, 각 노드는 데이터 + 다음 노드의 주소를 저장
• 동적 크기 조절 가능 (배열보다 유연함)
• 임의 접근이 불가능 (O(n))
• 삽입/삭제가 빠름 (O(1)) (배열과 비교 시)

2) 예시

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class LinkedList:
    def __init__(self):
        self.head = None
    
    def append(self, data):
        if not self.head:
            self.head = Node(data)
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = Node(data)

ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)

3) 활용 예시

• 데이터 삽입/삭제가 빈번한 경우
• 메모리 활용을 최적화해야 하는 경우

 

3. 스택 (Stack)

1) 특징

• LIFO (Last-In, First-Out) 구조, 즉 나중에 들어온 데이터가 먼저 나감
• push()로 삽입, pop()으로 삭제
• 재귀 함수 호출 및 뒤집기 연산에서 유용

2) 예시

stack = []
stack.append(1)  # push
stack.append(2)
stack.append(3)
print(stack)        #  [1, 2, 3]
print(stack.pop())  # 3 (LIFO 구조)

3) 활용 예시

• DFS (깊이 우선 탐색) 알고리즘
• 웹 브라우저 뒤로 가기

 

4. 큐 (Queue)

1) 특징

• FIFO (First-In, First-Out) 구조, 즉 먼저 들어온 데이터가 먼저 나감
• enqueue()로 삽입, dequeue()로 삭제

2) 예시

from collections import deque

queue = deque()
queue.append(1)  # enqueue
queue.append(2)
queue.append(3)
print(queue.popleft()) # 1 (FIFO 구조)

3) 활용 예시

• BFS (너비 우선 탐색) 알고리즘
• 프린터 대기열, 프로세스 스케줄링

 

5. 우선순위 큐 (Priority Queue)

1) 특징

• 우선순위가 높은 요소가 먼저 처리됨
• 힙(Heap)을 사용하여 구현 (heapq 라이브러리 활용)
  •  

2) 예시

import heapq

pq = []
heapq.heappush(pq, (1, "A"))
heapq.heappush(pq, (3, "C"))
heapq.heappush(pq, (2, "B"))

print(heapq.heappop(pq))  # (1, "A") - 우선순위 낮은 값 먼저 처리

3) 활용 예시

• 다익스트라 (최단 경로 탐색) 알고리즘
• 우선순위가 중요한 작업 (예: CPU 스케줄링, 운영체제 스케줄링, 네트워크 패킷 처리)
• 실시간 순위 데이터 관리 (예: 게임 점수, 뉴스 트렌드 분석)

 

6. 해시 테이블 (Hash Table)

1) 특징

• Key-Value 저장 방식
• 해시 함수를 이용해 빠른 검색 (O(1))
• 충졸 해결 기법 (chaining, 개방 주소법 등) 필요

2) 예시

hash_map = {}
hash_map["apple"] = 5
hash_map["banana"] = 3

print(hash_map) # {"apple": 5, "banana": 3}
print(hash_map["apple"])  # 5

3) 활용 예시

• 빠른 데이터 검색
• 캐싱(Cache) 구현

 

7. 그래프 (Graph)

1) 특징

• 정점(Node)과 간선(Edge)으로 구성
• 방향 그래프 / 무방향 그래프
• 인접 행렬, 인접 리스트로 표현 가능

2) 예시

# 인접 리스트
graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"]
}

3) 활용 예시

• SNS 친구 추천 알고리즘
• 최단 경로 탐색 (다익스트라, BFS, DFS)

 

정리

자료구조	특징	시간 복잡도
배열 (Array)	인덱스를 통한 빠른 접근	조회: O(1), 삽입/삭제: O(n)
연결 리스트 (Linked List)	동적 메모리 할당 가능	조회: O(n), 삽입/삭제: O(1)
스택 (Stack)	LIFO (후입선출) 구조	push: O(1), pop: O(1)
큐 (Queue)	FIFO (선입선출) 구조	enqueue: O(1), dequeue: O(1)
우선순위 큐 (Priority Queue)	우선순위 기반 정렬	삽입/삭제: O(log n)
해시 테이블 (Hash Table)	Key-Value 매핑	검색: O(1), 충돌 발생 시 O(n)
그래프 (Graph)	노드 간 관계 표현	탐색: O(V + E)