1. 배열 (Array)
정의
- 크기가 고정된 연속적인 메모리 공간에 데이터를 저장하는 자료구조.
- 인덱스를 사용해 요소에 빠르게 접근 가능.
특징
- 장점: 인덱스를 통한 빠른 조회(O(1)).
- 단점: 크기 변경이 불가능하며 삽입/삭제가 느림(O(n)).
// 배열 선언 및 기본 연산 let arr = [1, 2, 3, 4, 5]; // 삽입 arr.push(6); // 끝에 삽입 arr.unshift(0); // 앞에 삽입 // 삭제 arr.pop(); // 끝에서 삭제 arr.shift(); // 앞에서 삭제 // 접근 console.log(arr[2]); // 인덱스 2의 값 (3) // 탐색 console.log(arr.indexOf(3)); // 값 3의 인덱스 (2) // 출력 console.log(arr); // [0, 1, 2, 3, 4, 5]
사용 예시
- 데이터를 순서대로 저장해야 할 때.
- 2D 배열(행렬)과 같이 데이터를 구조화해서 저장.
- 예: 게임 보드, 표 데이터.
2. 연결 리스트 (Linked List)
정의
- 데이터와 포인터(다음 노드의 주소)를 포함하는 노드들의 연속적인 구조.
종류
- 단일 연결 리스트 (Singly Linked List): 각 노드가 다음 노드만 가리킴.
- 이중 연결 리스트 (Doubly Linked List): 각 노드가 이전 노드와 다음 노드를 가리킴.
- 원형 연결 리스트 (Circular Linked List): 마지막 노드가 첫 번째 노드를 가리킴.
특징
- 장점: 크기가 동적으로 증가/감소 가능. 중간 삽입/삭제가 빠름(O(1)).
- 단점: 인덱스로 직접 접근이 불가능(O(n)).
class Node { constructor(value) { this.value = value; this.next = null; } } class LinkedList { constructor() { this.head = null; this.tail = null; this.size = 0; } // 추가 append(value) { const newNode = new Node(value); if (!this.head) { this.head = this.tail = newNode; } else { this.tail.next = newNode; this.tail = newNode; } this.size++; } // 삭제 remove(value) { if (!this.head) return; if (this.head.value === value) { this.head = this.head.next; this.size--; return; } let current = this.head; while (current.next && current.next.value !== value) { current = current.next; } if (current.next) { current.next = current.next.next; if (!current.next) this.tail = current; this.size--; } } // 출력 print() { let current = this.head; const result = []; while (current) { result.push(current.value); current = current.next; } console.log(result.join(" -> ")); } } // 사용 예시 const list = new LinkedList(); list.append(1); list.append(2); list.append(3); list.print(); // 1 -> 2 -> 3 list.remove(2); list.print(); // 1 -> 3
사용 예시
- 큐와 스택의 구현.
- 메모리 효율이 중요하거나 크기가 동적으로 변하는 데이터 구조.
3. 스택 (Stack)
정의
- LIFO(Last In First Out) 구조. 마지막에 삽입된 데이터가 먼저 제거됨.
특징
- 삽입/삭제 연산이 한쪽 끝에서만 이루어짐.
- 주요 연산:
push(삽입),pop(삭제),peek(맨 위 데이터 확인).
class Stack { constructor() { this.stack = []; } push(value) { this.stack.push(value); } pop() { return this.stack.pop(); } peek() { return this.stack[this.stack.length - 1]; } isEmpty() { return this.stack.length === 0; } } // 사용 예시 const stack = new Stack(); stack.push(10); stack.push(20); console.log(stack.peek()); // 20 console.log(stack.pop()); // 20 console.log(stack.isEmpty()); // false
사용 예시
- 재귀 호출의 처리 (스택 프레임).
- 괄호 유효성 검사.
- 브라우저 방문 기록의 뒤로 가기/앞으로 가기.
4. 큐 (Queue)
정의
- FIFO(First In First Out) 구조. 먼저 삽입된 데이터가 먼저 제거됨.
특징
- 주요 연산:
enqueue(삽입),dequeue(삭제),peek(맨 앞 데이터 확인).
- 변형:
- 우선순위 큐: 데이터의 우선순위에 따라 처리 순서 결정.
- 원형 큐: 크기를 제한해 메모리 재활용.
배열을 사용한 큐 구현
class Queue { constructor() { this.queue = []; } enqueue(value) { this.queue.push(value); } dequeue() { return this.queue.shift(); } peek() { return this.queue[0]; } isEmpty() { return this.queue.length === 0; } } // 사용 예시 const queue = new Queue(); queue.enqueue(1); queue.enqueue(2); console.log(queue.peek()); // 1 console.log(queue.dequeue()); // 1 console.log(queue.isEmpty()); // false
링크드 리스트를 사용한 큐 구현
class Node { constructor(value) { this.value = value; this.next = null; } } class LinkedListQueue { constructor() { this.front = null; this.rear = null; this.length = 0; } enqueue(value) { const newNode = new Node(value); if (this.isEmpty()) { this.front = newNode; this.rear = newNode; } else { this.rear.next = newNode; // 현재 끝의 다음 노드로 추가 this.rear = newNode; // 끝을 새 노드로 갱신 } this.length++; } dequeue() { if (this.isEmpty()) return "Queue is empty!"; const value = this.front.value; this.front = this.front.next; this.length--; if (this.isEmpty()) this.rear = null; // 비었을 경우 rear도 초기화 return value; } peek() { return this.isEmpty() ? "Queue is empty!" : this.front.value; } isEmpty() { return this.length === 0; } size() { return this.length; } } // 사용 예시 const linkedListQueue = new LinkedListQueue(); linkedListQueue.enqueue(1); linkedListQueue.enqueue(2); console.log(linkedListQueue.dequeue()); // 1 console.log(linkedListQueue.peek()); // 2
2개의 스택을 사용한 큐 구현
class TwoStackQueue { constructor() { this.stack1 = []; // 입력 스택 this.stack2 = []; // 출력 스택 } enqueue(value) { this.stack1.push(value); } dequeue() { if (this.isEmpty()) return "Queue is empty!"; if (this.stack2.length === 0) { while (this.stack1.length > 0) { this.stack2.push(this.stack1.pop()); // 역순으로 stack2에 삽입 } } return this.stack2.pop(); } peek() { if (this.isEmpty()) return "Queue is empty!"; if (this.stack2.length === 0) { while (this.stack1.length > 0) { this.stack2.push(this.stack1.pop()); } } return this.stack2[this.stack2.length - 1]; } isEmpty() { return this.stack1.length === 0 && this.stack2.length === 0; } size() { return this.stack1.length + this.stack2.length; } } // 사용 예시 const twoStackQueue = new TwoStackQueue(); twoStackQueue.enqueue(1); twoStackQueue.enqueue(2); console.log(twoStackQueue.dequeue()); // 1 console.log(twoStackQueue.peek()); // 2
Circular 큐 구현
class CircularQueue { constructor(capacity) { this.queue = new Array(capacity); this.head = 0; this.tail = 0; this.size = 0; this.capacity = capacity; } enqueue(value) { if (this.isFull()) return "Queue is full!"; this.queue[this.tail] = value; this.tail = (this.tail + 1) % this.capacity; // 원형으로 이동 this.size++; } dequeue() { if (this.isEmpty()) return "Queue is empty!"; const value = this.queue[this.head]; this.queue[this.head] = undefined; // 비운 자리를 초기화 this.head = (this.head + 1) % this.capacity; // 원형으로 이동 this.size--; return value; } peek() { return this.isEmpty() ? "Queue is empty!" : this.queue[this.head]; } isEmpty() { return this.size === 0; } isFull() { return this.size === this.capacity; } currentSize() { return this.size; } } // 사용 예시 const circularQueue = new CircularQueue(3); circularQueue.enqueue(1); circularQueue.enqueue(2); circularQueue.enqueue(3); console.log(circularQueue.enqueue(4)); // "Queue is full!" console.log(circularQueue.dequeue()); // 1 console.log(circularQueue.peek()); // 2
사용 예시
- 너비 우선 탐색(BFS) 구현.
- 프로세스 스케줄링.
- 데이터 스트림 처리.
5. 해시 테이블 (Hash Table)
정의
- 데이터를 키-값 쌍으로 저장하며, 키를 해싱(Hashing)하여 값에 빠르게 접근.
특징
- 장점: 평균적으로 검색, 삽입, 삭제 연산이 O(1).
- 단점: 충돌(해시 충돌)이 발생할 수 있으며, 이를 처리하기 위한 추가 기법 필요.
- 충돌 처리 방법: 체이닝(Chaining), 오픈 어드레싱(Open Addressing).
class HashTable { constructor(size = 50) { this.table = new Array(size); } hash(key) { let hash = 0; for (let char of key) { hash += char.charCodeAt(0); } return hash % this.table.length; } set(key, value) { const index = this.hash(key); if (!this.table[index]) { this.table[index] = []; } this.table[index].push([key, value]); } get(key) { const index = this.hash(key); if (!this.table[index]) return undefined; for (let [k, v] of this.table[index]) { if (k === key) return v; } } remove(key) { const index = this.hash(key); if (!this.table[index]) return; this.table[index] = this.table[index].filter(([k]) => k !== key); } } // 사용 예시 const hashTable = new HashTable(); hashTable.set("name", "John"); console.log(hashTable.get("name")); // John hashTable.remove("name"); console.log(hashTable.get("name")); // undefined
사용 예시
- 데이터베이스 인덱스.
- 중복 데이터 확인 (예: 두 배열의 교집합 찾기).
- 캐시(Cache) 구현.
6. 트리 (Tree)
정의
- 계층적 구조를 가지며, 루트 노드에서 시작해 자식 노드로 확장됨.
종류
- 이진 트리 (Binary Tree): 각 노드가 최대 두 개의 자식을 가짐.
- 이진 탐색 트리 (BST): 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼.
- 힙 (Heap):
- 최소 힙: 부모 노드 ≤ 자식 노드.
- 최대 힙: 부모 노드 ≥ 자식 노드.
- AVL 트리: 스스로 균형을 유지하는 이진 탐색 트리.
- B-트리: 데이터베이스나 파일 시스템에서 사용되는 다진 트리.
- Trie: 문자열을 저장하고 검색하는데 최적화된 트리 기반의 데이터 구조
특징
- 노드 간의 연결로 구현.
- 검색, 삽입, 삭제는 일반적으로 O(log n).
이진트리
class BinaryTreeNode { constructor(value) { this.value = value; this.left = null; this.right = null; } } class BinaryTree { constructor() { this.root = null; } insert(value) { const newNode = new BinaryTreeNode(value); if (!this.root) { this.root = newNode; return; } const queue = [this.root]; while (queue.length > 0) { const current = queue.shift(); if (!current.left) { current.left = newNode; return; } else if (!current.right) { current.right = newNode; return; } else { queue.push(current.left, current.right); } } } // 트리 순회 예제: 중위 순회 inOrderTraversal(node = this.root, result = []) { if (node) { this.inOrderTraversal(node.left, result); result.push(node.value); this.inOrderTraversal(node.right, result); } return result; } } // 사용 예시 const binaryTree = new BinaryTree(); binaryTree.insert(1); binaryTree.insert(2); binaryTree.insert(3); binaryTree.insert(4); binaryTree.insert(5); console.log(binaryTree.inOrderTraversal()); // [4, 2, 5, 1, 3]
이진탐색트리
class BSTNode { constructor(value) { this.value = value; this.left = null; this.right = null; } } class BinarySearchTree { constructor() { this.root = null; } insert(value) { const newNode = new BSTNode(value); if (!this.root) { this.root = newNode; return; } let current = this.root; while (true) { if (value < current.value) { if (!current.left) { current.left = newNode; return; } current = current.left; } else { if (!current.right) { current.right = newNode; return; } current = current.right; } } } search(value) { let current = this.root; while (current) { if (value === current.value) return true; current = value < current.value ? current.left : current.right; } return false; } inOrderTraversal(node = this.root, result = []) { if (node) { this.inOrderTraversal(node.left, result); result.push(node.value); this.inOrderTraversal(node.right, result); } return result; } } // 사용 예시 const bst = new BinarySearchTree(); bst.insert(10); bst.insert(5); bst.insert(15); bst.insert(7); console.log(bst.search(7)); // true console.log(bst.search(3)); // false console.log(bst.inOrderTraversal()); // [5, 7, 10, 15]
힙
class Heap { constructor(compare) { this.data = []; this.compare = compare; // 비교 함수: Min Heap 또는 Max Heap 결정 } // 부모 인덱스 가져오기 parentIndex(index) { return Math.floor((index - 1) / 2); } // 왼쪽 자식 인덱스 가져오기 leftChildIndex(index) { return index * 2 + 1; } // 오른쪽 자식 인덱스 가져오기 rightChildIndex(index) { return index * 2 + 2; } // 힙에 값 삽입 push(value) { this.data.push(value); this.bubbleUp(); } // 최상위 값 제거 (루트 값) pop() { if (this.size() === 0) return null; if (this.size() === 1) return this.data.pop(); const root = this.data[0]; this.data[0] = this.data.pop(); this.bubbleDown(); return root; } // 루트 값 가져오기 peek() { return this.size() > 0 ? this.data[0] : null; } // 힙 크기 size() { return this.data.length; } // 삽입 시 힙 재구성 bubbleUp() { let index = this.size() - 1; while (index > 0) { const parent = this.parentIndex(index); if (this.compare(this.data[index], this.data[parent]) < 0) { [this.data[index], this.data[parent]] = [this.data[parent], this.data[index]]; index = parent; } else { break; } } } // 제거 시 힙 재구성 bubbleDown() { let index = 0; while (this.leftChildIndex(index) < this.size()) { let smallerChild = this.leftChildIndex(index); const rightChild = this.rightChildIndex(index); if (rightChild < this.size() && this.compare(this.data[rightChild], this.data[smallerChild]) < 0) { smallerChild = rightChild; } if (this.compare(this.data[smallerChild], this.data[index]) < 0) { [this.data[index], this.data[smallerChild]] = [this.data[smallerChild], this.data[index]]; index = smallerChild; } else { break; } } } } const minHeap = new Heap((a, b) => a - b); minHeap.push(10); minHeap.push(5); minHeap.push(20); minHeap.push(3); console.log(minHeap.peek()); // 3 (최소값) console.log(minHeap.pop()); // 3 console.log(minHeap.pop()); // 5 console.log(minHeap.pop()); // 10 const maxHeap = new Heap((a, b) => b - a); maxHeap.push(10); maxHeap.push(5); maxHeap.push(20); maxHeap.push(3); console.log(maxHeap.peek()); // 20 (최대값) console.log(maxHeap.pop()); // 20 console.log(maxHeap.pop()); // 10 console.log(maxHeap.pop()); // 5
AVL 트리
class AVLNode { constructor(value) { this.value = value; this.left = null; this.right = null; this.height = 1; } } class AVLTree { constructor() { this.root = null; } getHeight(node) { return node ? node.height : 0; } getBalance(node) { return node ? this.getHeight(node.left) - this.getHeight(node.right) : 0; } rotateRight(y) { const x = y.left; const T2 = x.right; x.right = y; y.left = T2; y.height = Math.max(this.getHeight(y.left), this.getHeight(y.right)) + 1; x.height = Math.max(this.getHeight(x.left), this.getHeight(x.right)) + 1; return x; } rotateLeft(x) { const y = x.right; const T2 = y.left; y.left = x; x.right = T2; x.height = Math.max(this.getHeight(x.left), this.getHeight(x.right)) + 1; y.height = Math.max(this.getHeight(y.left), this.getHeight(y.right)) + 1; return y; } insert(node, value) { if (!node) return new AVLNode(value); if (value < node.value) { node.left = this.insert(node.left, value); } else if (value > node.value) { node.right = this.insert(node.right, value); } else { return node; // 중복 값 무시 } node.height = Math.max(this.getHeight(node.left), this.getHeight(node.right)) + 1; const balance = this.getBalance(node); // Left Heavy if (balance > 1 && value < node.left.value) return this.rotateRight(node); // Right Heavy if (balance < -1 && value > node.right.value) return this.rotateLeft(node); // Left-Right if (balance > 1 && value > node.left.value) { node.left = this.rotateLeft(node.left); return this.rotateRight(node); } // Right-Left if (balance < -1 && value < node.right.value) { node.right = this.rotateRight(node.right); return this.rotateLeft(node); } return node; } add(value) { this.root = this.insert(this.root, value); } inOrderTraversal(node = this.root, result = []) { if (node) { this.inOrderTraversal(node.left, result); result.push(node.value); this.inOrderTraversal(node.right, result); } return result; } } // 사용 예시 const avl = new AVLTree(); avl.add(10); avl.add(20); avl.add(30); avl.add(40); console.log(avl.inOrderTraversal()); // [10, 20, 30, 40]
Red-Black 트리
class Node { constructor(value, color = "RED") { this.value = value; this.color = color; // RED or BLACK this.left = null; this.right = null; this.parent = null; } } class RedBlackTree { constructor() { this.NIL = new Node(null, "BLACK"); // NIL 노드 this.root = this.NIL; } // 왼쪽 회전 rotateLeft(x) { const y = x.right; x.right = y.left; if (y.left !== this.NIL) { y.left.parent = x; } y.parent = x.parent; if (x.parent === null) { this.root = y; } else if (x === x.parent.left) { x.parent.left = y; } else { x.parent.right = y; } y.left = x; x.parent = y; } // 오른쪽 회전 rotateRight(y) { const x = y.left; y.left = x.right; if (x.right !== this.NIL) { x.right.parent = y; } x.parent = y.parent; if (y.parent === null) { this.root = x; } else if (y === y.parent.right) { y.parent.right = x; } else { y.parent.left = x; } x.right = y; y.parent = x; } // 삽입 insert(value) { const newNode = new Node(value); newNode.left = this.NIL; newNode.right = this.NIL; let parent = null; let current = this.root; while (current !== this.NIL) { parent = current; if (value < current.value) { current = current.left; } else { current = current.right; } } newNode.parent = parent; if (parent === null) { this.root = newNode; } else if (value < parent.value) { parent.left = newNode; } else { parent.right = newNode; } newNode.color = "RED"; this.fixInsert(newNode); } // 삽입 후 색상 및 균형 조정 fixInsert(node) { while (node.parent && node.parent.color === "RED") { if (node.parent === node.parent.parent.left) { const uncle = node.parent.parent.right; if (uncle.color === "RED") { node.parent.color = "BLACK"; uncle.color = "BLACK"; node.parent.parent.color = "RED"; node = node.parent.parent; } else { if (node === node.parent.right) { node = node.parent; this.rotateLeft(node); } node.parent.color = "BLACK"; node.parent.parent.color = "RED"; this.rotateRight(node.parent.parent); } } else { const uncle = node.parent.parent.left; if (uncle.color === "RED") { node.parent.color = "BLACK"; uncle.color = "BLACK"; node.parent.parent.color = "RED"; node = node.parent.parent; } else { if (node === node.parent.left) { node = node.parent; this.rotateRight(node); } node.parent.color = "BLACK"; node.parent.parent.color = "RED"; this.rotateLeft(node.parent.parent); } } } this.root.color = "BLACK"; } // 중위 순회 inOrderTraversal(node = this.root, result = []) { if (node !== this.NIL) { this.inOrderTraversal(node.left, result); result.push(node.value); this.inOrderTraversal(node.right, result); } return result; } } // 사용 예시 const rbTree = new RedBlackTree(); rbTree.insert(10); rbTree.insert(20); rbTree.insert(15); rbTree.insert(30); rbTree.insert(25); console.log(rbTree.inOrderTraversal()); // [10, 15, 20, 25, 30]
Trie
class TrieNode { constructor() { this.children = {}; this.isEndOfWord = false; } } class Trie { constructor() { this.root = new TrieNode(); } insert(word) { let current = this.root; for (const char of word) { if (!current.children[char]) { current.children[char] = new TrieNode(); } current = current.children[char]; } current.isEndOfWord = true; } search(word) { let current = this.root; for (const char of word) { if (!current.children[char]) return false; current = current.children[char]; } return current.isEndOfWord; } startsWith(prefix) { let current = this.root; for (const char of prefix) { if (!current.children[char]) return false; current = current.children[char]; } return true; } } // 사용 예시 const trie = new Trie(); trie.insert("apple"); console.log(trie.search("apple")); // true console.log(trie.startsWith("app")); // true console.log(trie.search("app")); // false
사용 예시
- 데이터 검색(예: 트라이 Trie).
- 최소/최대 값 관리(힙).
- 계층적 데이터 표현(예: 파일 시스템).
7. 그래프 (Graph)
정의
- 노드(정점)와 간선으로 구성된 구조. 방향성과 가중치 여부에 따라 유형이 나뉨.
표현 방법
- 인접 행렬 (Adjacency Matrix): 2D 배열로 간선 표현.
- 인접 리스트 (Adjacency List): 각 노드가 연결된 노드들의 리스트를 가짐.
특징
- 방향 그래프(Directed)와 무방향 그래프(Undirected).
- 가중치 그래프(Weighted): 간선에 가중치가 있음.
class Graph { constructor() { this.adjacencyList = {}; } addVertex(vertex) { if (!this.adjacencyList[vertex]) { this.adjacencyList[vertex] = []; } } addEdge(v1, v2) { this.adjacencyList[v1].push(v2); this.adjacencyList[v2].push(v1); } removeEdge(v1, v2) { this.adjacencyList[v1] = this.adjacencyList[v1].filter(v => v !== v2); this.adjacencyList[v2] = this.adjacencyList[v2].filter(v => v !== v1); } removeVertex(vertex) { while (this.adjacencyList[vertex].length) { const adjacentVertex = this.adjacencyList[vertex].pop(); this.removeEdge(vertex, adjacentVertex); } delete this.adjacencyList[vertex]; } } // 사용 예시 const graph = new Graph(); graph.addVertex("A"); graph.addVertex("B"); graph.addEdge("A", "B"); console.log(graph.adjacencyList); // { A: ['B'], B: ['A'] } graph.removeEdge("A", "B"); console.log(graph.adjacencyList); // { A: [], B: [] }
사용 예시
- 네트워크, 소셜 미디어 그래프.
- 최단 경로 문제(다익스트라, 플로이드-워셜).
자료구조 비교 요약
자료구조 | 접근 시간 | 삽입/삭제 시간 | 특징 |
배열 | O(1) | O(n) | 고정 크기, 빠른 조회 |
연결 리스트 | O(n) | O(1) | 동적 크기, 빠른 삽입/삭제 |
스택 | O(n) | O(1) | LIFO, 재귀적 구조 처리 |
큐 | O(n) | O(1) | FIFO, 순차적 처리 |
해시 테이블 | O(1) | O(1) | 평균적으로 빠른 검색/삽입/삭제 |
트리 | O(log n) | O(log n) | 계층적 데이터 관리, 탐색 및 정렬에 유용 |
그래프 | O(V+E) | O(V+E) | 네트워크, 경로 탐색 문제 해결 |