[250211] 자료구조 정리~

자료구조 (Data Structure)란? 🧬

1. 자료구조 정의

자료구조(Data Structure)란 데이터를 효율적으로 저장하고 관리하는 방법을 의미한다. 프로그램에서 데이터를 효과적으로

조작할 수 있도록 다양한 방식으로 구조화되며, 알고리즘의 성능과 직결된다.

---

2. 자료구조의 종류

자료구조는 크게 선형 구조와 비선형 구조로 나뉜다.

1️⃣ 선형 구조 (Linear Data Structure)

데이터가 순차적으로 배치되는 구조로, 한 번에 하나의 데이터만 직접 접근할 수 있다.

(1) 배열 (Array)

• 특징: 동일한 데이터 타입의 요소들이 연속적인 메모리 공간에 저장됨
• 장점: 인덱스를 사용한 빠른 조회 (O(1))
• 단점: 크기가 고정적이며, 삽입/삭제가 어려움 (O(n))

(2) 연결 리스트 (Linked List)

• 특징: 각 노드(Node)가 데이터와 다음 노드를 가리키는 포인터를 가짐
• 장점: 동적 메모리 할당 가능, 삽입/삭제가 용이 (O(1))
• 단점: 검색이 느림 (O(n)), 추가적인 메모리(포인터) 필요

(3) 스택 (Stack)

• 특징: LIFO(Last In, First Out) 방식으로 동작하는 자료구조
• 연산:
  • `push()`: 데이터 삽입
  • `pop()`: 데이터 제거
  • `peek()`: 최상위 요소 확인
• 사용 예시: 함수 호출 스택, 웹 브라우저의 뒤로 가기

(4) 큐 (Queue)

• 특징: FIFO(First In, First Out) 방식으로 동작하는 자료구조
• 연산:
  • `enqueue()`: 데이터 삽입
  • `dequeue()`: 데이터 제거
• 사용 예시: 프로세스 스케줄링, 프린터 대기열

(5) 덱 (Deque, Double-ended Queue)

• 특징: 양쪽 끝에서 삽입/삭제가 가능한 큐
• 사용 예시: 캐시(Cache), 우선순위 큐

 

2️⃣ 비선형 구조 (Non-Linear Data Structure)

데이터가 계층적 또는 복잡한 관계를 가지며, 순차적으로 배치되지 않는 구조이다.

(1) 트리 (Tree)

• 특징: 계층적 구조를 가지며, 부모-자식 관계가 존재함
• 종류:
  • 이진 트리 (Binary Tree)
  • 이진 탐색 트리 (BST, Binary Search Tree)
  • AVL 트리, 레드-블랙 트리
• 사용 예시: 파일 시스템, 데이터베이스 인덱스(B+ 트리)

(2) 그래프 (Graph)

• 특징: 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조
• 종류:
  • 방향 그래프(Directed Graph)
  • 무방향 그래프(Undirected Graph)
• 탐색 알고리즘:
  • DFS(깊이 우선 탐색)
  • BFS(너비 우선 탐색)
• 사용 예시: 네트워크, SNS 친구 추천

---

3. 자료구조 선택 기준

자료구조를 선택할 때는 삽입, 삭제, 검색 성능을 고려해야 한다.

자료구조	삽입	삭제	검색
배열(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)
해시 테이블(Hash Table)	O(1)	O(1)	O(1)

---

자료구조 정리:
✅ 자료구조는 데이터를 효율적으로 저장하고 관리하는 방법이다~
✅ 선형 자료구조에는 배열, 연결 리스트, 스택, 큐가 있다~
✅ 비선형 자료구조에는 트리와 그래프가 있다~
✅ 자료구조 선택 시 삽입, 삭제, 검색 성능을 고려해야 한다~
✅ 효율적인 알고리즘을 위해 적절한 자료구조를 선택하는 것이 중요하다~