[Python] 자료구조

 

자료구조(Data Structure)란?

자료구조는 데이터를 저장하고 관리하는 구조적 방법을 의미합니다. 이를 통해 효율적인 데이터 처리 및 연산 수행이 가능합니다.

1. 선형 자료구조 (Linear Data Structure)

1.1 배열 (Array)

배열은 같은 타입의 데이터를 연속된 메모리 공간에 저장하는 구조입니다.

Index    0   1   2   3   4
Data     10  20  30  40  50

배열의 특징:

• 탐색: O(1) - 인덱스를 통해 빠르게 접근 가능
• 삽입/삭제: O(n) - 중간 데이터를 추가/삭제할 때 뒤 데이터를 이동해야 함

1.2 연결 리스트 (Linked List)

연결 리스트는 노드(Node)와 포인터(링크)로 연결된 자료구조입니다.

[HEAD] → [10 | O] → [20 | O] → [30 | NULL]

연결 리스트의 특징:

• 탐색: O(n) - 처음부터 하나씩 탐색해야 함
• 삽입/삭제: O(1) - 특정 위치에서 쉽게 추가/삭제 가능

1.3 스택 (Stack)

스택은 후입선출(LIFO, Last In First Out) 구조를 가지는 자료구조입니다.

[TOP] → 30 → 20 → 10

스택의 연산:

• push: 데이터를 맨 위에 추가
• pop: 맨 위 데이터 제거

1.4 큐 (Queue)

큐는 선입선출(FIFO, First In First Out) 구조를 가지는 자료구조입니다.

[Front] 10 → 20 → 30 [Rear]

큐의 연산:

• enqueue: 뒤에서 추가
• dequeue: 앞에서 제거

2. 비선형 자료구조 (Non-Linear Data Structure)

2.1 트리 (Tree)

트리는 계층 구조를 가지는 자료구조입니다.

       (10)
      /    \
    (5)    (15)
   /  \    /  \
 (2)  (7) (12) (20)

이진 탐색 트리 (BST)의 특징:

• 왼쪽 자식 노드 < 부모 < 오른쪽 자식 노드
• 탐색 속도: O(log n)

2.2 그래프 (Graph)

그래프는 노드(Vertex)와 간선(Edge)으로 이루어진 자료구조입니다.

A - B - C
|    |
D - E

그래프 탐색 알고리즘:

• DFS (깊이 우선 탐색)
• BFS (너비 우선 탐색)

자료구조 선택 기준

자료구조	삽입	삭제	탐색
배열(Array)	O(1)	O(n)	O(1)
연결 리스트(Linked List)	O(1)	O(1)	O(n)
스택(Stack)	O(1)	O(1)	O(n)
큐(Queue)	O(1)	O(1)	O(n)
트리(Tree)	O(log n)	O(log n)	O(log n)