자료구조
자료구조 개요
자료구조(Data Structures)는 데이터를 효율적으로 저장하고 관리하는 방법을 정의하는 논리적, 수학적 개념입니다. 자료구조는 프로그램의 성능과 효율성에 큰 영향을 미치며, 다양한 유형의 자료구조가 존재합니다. 이 문서에서는 주요 자료구조의 개념과 특징을 설명합니다.
1. 배열 (Array)
- 설명: 동일한 타입의 요소들을 연속적인 메모리 공간에 저장하는 자료구조입니다.
- 특징:
- 고정된 크기
- 인덱스를 통해 빠른 접근이 가능
- 삽입 및 삭제가 비효율적
- 예시:
1 2
arr = [1, 2, 3, 4, 5] print(arr[2]) # 출력: 3
2. 연결 리스트 (Linked List)
- 설명: 각 요소가 데이터와 다음 요소를 가리키는 포인터를 포함하는 노드로 구성된 자료구조입니다.
- 특징:
- 크기가 동적
- 삽입 및 삭제가 효율적
- 인덱스를 통한 접근이 비효율적
- 종류:
- 단일 연결 리스트 (Singly Linked List)
- 이중 연결 리스트 (Doubly Linked List)
- 원형 연결 리스트 (Circular Linked List)
- 예시:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
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 else: current = self.head while current.next: current = current.next current.next = new_node
3. 스택 (Stack)
- 설명: 후입선출(LIFO, Last In First Out) 방식으로 동작하는 자료구조입니다.
- 특징:
- 요소의 삽입과 삭제가 한쪽 끝에서만 발생
- 주요 연산: 푸시(Push), 팝(Pop), 피크(Peek)
- 예시:
1 2 3 4
stack = [] stack.append(1) # 푸시 stack.append(2) print(stack.pop()) # 팝, 출력: 2
4. 큐 (Queue)
- 설명: 선입선출(FIFO, First In First Out) 방식으로 동작하는 자료구조입니다.
- 특징:
- 요소의 삽입은 뒤에서, 삭제는 앞에서 발생
- 주요 연산: 인큐(Enqueue), 디큐(Dequeue)
- 종류:
- 일반 큐
- 원형 큐 (Circular Queue)
- 우선순위 큐 (Priority Queue)
- 예시:
1 2 3 4 5
from collections import deque queue = deque() queue.append(1) # 인큐 queue.append(2) print(queue.popleft()) # 디큐, 출력: 1
5. 트리 (Tree)
- 설명: 계층적인 구조를 가지며, 노드와 에지로 구성된 자료구조입니다.
- 특징:
- 루트 노드에서 시작하여 자식 노드로 확장
- 이진 트리, AVL 트리, 힙 등 다양한 종류가 있음
- 종류:
- 이진 트리 (Binary Tree)
- 이진 탐색 트리 (Binary Search Tree)
- AVL 트리 (AVL Tree)
- 힙 (Heap)
- 예시:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
class TreeNode: def __init__(self, value): self.value = value self.left = None self.right = None def insert(root, value): if root is None: return TreeNode(value) if value < root.value: root.left = insert(root.left, value) else: root.right = insert(root.right, value) return root
6. 그래프 (Graph)
- 설명: 노드(정점)와 에지(간선)로 구성된 자료구조로, 복잡한 관계를 나타내는 데 사용됩니다.
- 특징:
- 방향 그래프와 무방향 그래프가 있음
- 순환 그래프와 비순환 그래프가 있음
- 종류:
- 인접 행렬 (Adjacency Matrix)
- 인접 리스트 (Adjacency List)
- 예시:
1 2 3 4 5 6 7 8
graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] }
결론
자료구조는 데이터의 효율적인 저장과 관리를 위한 기본적인 개념입니다. 배열, 연결 리스트, 스택, 큐, 트리, 그래프 등 다양한 자료구조가 있으며, 각각의 특성과 용도에 맞게 선택하여 사용해야 합니다. 올바른 자료구조의 선택은 프로그램의 성능과 효율성에 큰 영향을 미칩니다.
This post is licensed under CC BY 4.0 by the author.
