출처 : https://m.hanbit.co.kr/channel/category/category_view.html?cms_code=CMS8073601837
- 배열 (Array)
정의: 동일한 타입의 고정된 크기의 요소들을 저장하는 자료 구조.
특징: 인덱스를 사용하여 요소에 접근, 크기 변경 불가.
장점:
인덱스를 통해 빠른 데이터 접근(O(1)).
메모리 사용이 효율적.
단점:
크기가 고정되어 변경 불가.
요소의 삽입/삭제가 비효율적(O(n)).
사용 상황:
데이터의 크기가 고정적이고 변하지 않는 경우.
요소 접근이 빈번한 경우.
int[] array = new int[5];
array[0] = 10;
array[1] = 20;- 리스트 (List)
정의: 크기가 가변적인 배열과 유사한 자료 구조.
종류:
ArrayList: 배열 기반, 인덱스 접근이 빠름.
LinkedList: 노드 기반, 요소 추가/삭제가 빠름.
장점:
크기 가변성.
다양한 데이터 타입 저장 가능.
단점:
ArrayList: 요소 삽입/삭제가 비효율적(O(n)).
LinkedList: 인덱스 접근이 느림(O(n)).
사용 상황:
크기가 자주 변하는 데이터 관리.
빈번한 요소 삽입/삭제가 필요한 경우(LinkedList).
List<String> arrayList = new ArrayList<>();
arrayList.add("Hello");
arrayList.add("World");
List<String> linkedList = new LinkedList<>();
linkedList.add("Hello");
linkedList.add("World");- 스택 (Stack)
정의: 후입선출(LIFO) 방식으로 동작.
특징: 요소의 추가(push)와 제거(pop)가 한쪽 끝에서만 발생.
장점:
데이터 관리가 단순하고 직관적.
메모리 사용이 효율적.
단점:
요소 접근이 제한적(오직 맨 위의 요소만 접근 가능).
사용 상황:
함수 호출 스택, 수식 계산, 괄호 검증 등.
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
int top = stack.pop(); // top = 2- 큐 (Queue)
정의: 선입선출(FIFO) 방식으로 동작.
특징: 요소의 추가(enqueue)와 제거(dequeue)가 양쪽 끝에서 발생.
종류:
LinkedList 기반 큐.
ArrayDeque: 더블 엔디드 큐.
PriorityQueue: 우선순위 큐.
장점:
데이터 관리가 단순하고 직관적.
다양한 변형(우선순위 큐 등) 가능.
단점:
요소 접근이 제한적(오직 맨 앞의 요소만 접근 가능).
사용 상황:
작업 스케줄링, 프린터 대기열 등.
Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
int front = queue.poll(); // front = 1
Queue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.add(2);
priorityQueue.add(1);
int priorityFront = priorityQueue.poll(); // priorityFront = 1- 해시 테이블 (Hash Table)
정의: 키-값 쌍으로 데이터를 저장.
특징: 해시 함수를 사용하여 키를 해시값으로 변환 후 저장.
장점:
빠른 데이터 접근, 삽입, 삭제(O(1)).
효율적인 메모리 사용.
단점:
해시 충돌 발생 가능.
메모리 오버헤드 발생 가능.
순서 유지 불가.
사용 상황:
빠른 데이터 검색이 필요한 경우.
키-값 쌍 데이터 관리.
Map<String, Integer> map = new HashMap<>();
map.put("one", 1);
map.put("two", 2);
int value = map.get("one"); // value = 1- 셋 (Set)
정의: 중복되지 않는 요소들의 집합.
특징: 중복 요소를 허용하지 않음, 순서가 중요하지 않음.
종류:
HashSet: 해시 테이블 기반.
TreeSet: 정렬된 순서 유지.
LinkedHashSet: 삽입 순서 유지.
장점:
중복 제거 용이.
빠른 데이터 검색.
단점:
요소의 순서가 중요하지 않은 경우에만 사용 가능.
사용 상황:
중복 데이터를 제거하고 유일한 값을 관리할 때.
집합 연산(합집합, 교집합 등).
Set<String> set = new HashSet<>();
set.add("apple");
set.add("banana");
set.add("apple"); // 중복된 요소는 추가되지 않습니다.- 트리 (Tree)
정의: 계층적인 데이터 구조.
종류:
BinaryTree: 각 노드가 최대 두 개의 자식 노드를 가짐.
BinarySearchTree: 왼쪽 서브트리는 현재 노드보다 작은 값을, 오른쪽 서브트리는 큰 값을 가짐.
AVLTree: 균형을 유지하는 이진 탐색 트리.
Red-Black Tree: 자가 균형 이진 탐색 트리.
장점:
데이터 검색, 삽입, 삭제가 효율적(O(log n)).
계층적 데이터 표현 가능.
단점:
복잡한 구현.
균형 유지 필요.
사용 상황:
데이터 검색, 정렬.
계층적 데이터 관리.
class Node {
int value;
Node left, right;
public Node(int value) {
this.value = value;
left = right = null;
}
}
class BinaryTree {
Node root;
void add(int value) {
root = addRecursive(root, value);
}
Node addRecursive(Node current, int value) {
if (current == null) {
return new Node(value);
}
if (value < current.value) {
current.left = addRecursive(current.left, value);
} else if (value > current.value) {
current.right = addRecursive(current.right, value);
}
return current;
}
}- 그래프 (Graph)
정의: 노드와 노드 간의 연결(간선)로 이루어진 자료 구조.
종류:
방향 그래프(Directed Graph).
무방향 그래프(Undirected Graph).
가중치 그래프(Weighted Graph).
장점:
복잡한 관계 표현 가능.
다양한 알고리즘 적용 가능(최단 경로, 최소 신장 트리 등).
단점:
복잡한 구현.
높은 메모리 사용량.
사용 상황:
네트워크, 소셜 네트워크 분석.
최단 경로 문제, 전자 회로 설계.
class Graph {
private Map<Integer, List<Integer>> adjVertices;
public Graph() {
adjVertices = new HashMap<>();
}
void addVertex(int label) {
adjVertices.putIfAbsent(label, new ArrayList<>());
}
void addEdge(int v1, int v2) {
adjVertices.get(v1).add(v2);
adjVertices.get(v2).add(v1); // 무방향 그래프일 경우
}
List<Integer> getAdjVertices(int label) {
return adjVertices.get(label);
}
}- 덱 (Deque: Double-Ended Queue)
정의: 양쪽 끝에서 요소의 추가 및 제거가 가능한 자료 구조.
특징: 양쪽 끝에서 삽입과 삭제가 가능하여 스택과 큐의 기능을 모두 가짐.
장점:
유연한 데이터 관리.
큐와 스택의 기능을 모두 제공.
단점:
특정 상황에 맞는 사용이 필요.
사용 상황:
양쪽 끝에서 삽입 및 삭제가 필요한 경우.
스택과 큐의 기능을 동시에 필요로 하는 경우.
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeExample {
public static void main(String[] args) {
// Deque 선언 및 초기화
Deque<Integer> deque = new ArrayDeque<>();
// 요소 추가 - 앞쪽과 뒤쪽 모두 가능
deque.addFirst(10); // 앞쪽에 추가
deque.addLast(20); // 뒤쪽에 추가
deque.offerFirst(5); // 앞쪽에 추가
deque.offerLast(25); // 뒤쪽에 추가
// 현재 Deque 상태 출력
System.out.println("Deque: " + deque); // 출력: Deque: [5, 10, 20, 25]
// 요소 제거 - 앞쪽과 뒤쪽 모두 가능
int firstElement = deque.removeFirst(); // 앞쪽 요소 제거
int lastElement = deque.removeLast(); // 뒤쪽 요소 제거
// 제거한 요소 출력
System.out.println("Removed First Element: " + firstElement); // 출력: Removed First Element: 5
System.out.println("Removed Last Element: " + lastElement); // 출력: Removed Last Element: 25
// 현재 Deque 상태 출력
System.out.println("Deque after removals: " + deque); // 출력: Deque after removals: [10, 20]
// 요소 조회 - 제거하지 않고 조회
int peekFirst = deque.peekFirst(); // 앞쪽 요소 조회
int peekLast = deque.peekLast(); // 뒤쪽 요소 조회
// 조회한 요소 출력
System.out.println("Peek First Element: " + peekFirst); // 출력: Peek First Element: 10
System.out.println("Peek Last Element: " + peekLast); // 출력: Peek Last Element: 20
// 요소 삽입 - 예외를 발생시키지 않는 방법
deque.offerFirst(15); // 앞쪽에 추가
deque.offerLast(30); // 뒤쪽에 추가
// 현재 Deque 상태 출력
System.out.println("Deque after offers: " + deque); // 출력: Deque after offers: [15, 10, 20, 30]
// Deque가 비어 있는지 확인
boolean isEmpty = deque.isEmpty();
System.out.println("Is Deque empty? " + isEmpty); // 출력: Is Deque empty? false
}
}
각 자료 구조는 특정한 문제를 해결하기 위해 설계되었으며, 상황에 따라 적절한 자료 구조를 선택하는 것이 중요하다!
강준규