ArrayList
ArrayList는 Array(배열) 과는 다르게 동적으로 데이터를 저장할 수 있는 자료구조입니다.
특징으로는 다음과 같습니다.
- 연속적인 데이터(중간에 빈공간 x)의 리스트이다.
- 배열을 이용하기 때문에 인덱스를 이용해 요소에 빠르게 접근할 수 있다.
- 크기가 고정되어 있는 배열과 달리 공간을 늘리거나 줄입니다.
- 배열 공간이 꽉찰 때마다 배열을 복사하는 방식으로 늘리는데, 이때마다 지연이 된다.
- 데이터를 리스트 중간에 삽입/삭제하는 경우에 중간에 빈 공간이 생기지 않도록 요소들의 위치를 앞뒤로 이동시키기때문에 삽입/삭제 동작은 느리다.
핵심은 '배열을 이용하여 구현한다' 와 크기가 꽉찰 때 리사이즈가 발생되어 기존 용량 2배로 확장된다는 점입니다. (이 때 기존 데이터도 복사함)
코드를 통해 알아봅시다.
class ArrayList {
constructor() {
this.capacity = 2; // 초기 용량
this.length = 0;
this.data = new Array(this.capacity);
}
_resize() {
this.capacity *= 2;
const newData = new Array(this.capacity);
for (let i = 0; i < this.length; i++) {
newData[i] = this.data[i];
}
this.data = newData;
}
add(value) {
if (this.length >= this.capacity) {
this._resize();
}
this.data[this.length] = value;
this.length++;
}
get(index) {
if (index < 0 || index >= this.length) {
throw new Error("Index out of bounds");
}
return this.data[index];
}
remove(index) {
if (index < 0 || index >= this.length) {
throw new Error("Index out of bounds");
}
for (let i = index; i < this.length - 1; i++) {
this.data[i] = this.data[i + 1];
}
this.length--;
this.data[this.length] = undefined; // 메모리 누수 방지
}
size() {
return this.length;
}
toString() {
return "[" + this.data.slice(0, this.length).join(", ") + "]";
}
}
const list = new ArrayList();
- add 함수 → 현재 저장된 데이터의 개수가 capacity(용량)을 초과할 경우 resize(리사이즈)가 발생합니다.
- resize 함수 → 기존 용량의 2배 크기를 갖는 새로운 배열을 생성하고, 기존 데이터를 새로운 배열에 복사하여 저장 공간을 확장합니다.
- remove 함수 → 중간 인덱스의 요소가 삭제될 경우, 해당 인덱스 뒤에 있는 요소들을 한 칸씩 앞으로 이동(shifting)시켜 연속된 데이터 구조를 유지합니다.
이러한 이유로 ArrayList 조회 속도는 O(1)이고 삭제, 삽입 속도는 O(N)이 되게 됩니다.
LinkedList
LinkedList는 비연속적으로 저장하는 자료구조입니다.
LinkedList 특징은 다음과 같습니다.
- 실행 중에도 데이터 크기를 유연하게 조정할 수 있어, 미리 데이터 크기를 알 필요가 없습니다.
- 중간에 있는 요소를 삽입하거나 삭제할 때, 연결 리스트는 포인터만 조정하면 되므로 상대적으로 간편합니다.
- 불필요한 메모리를 미리 할당하지 않아 메모리 사용 효율이 높습니다.
- prev, next 포인터도 저장해야 하므로 메모리 사용이 비효율적입니다.
핵심은 ArrayList처럼 연속적인 메모리 공간(배열)을 사용하지 않고, prev, next라는 포인터를 이용한다는 점입니다.
코드를 통해 알아봅시다.
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
add(value) {
const newNode = new Node(value);
if (!this.head) {
this.head = this.tail = newNode;
} else {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
}
this.size++;
}
get(index) {
if (index < 0 || index >= this.size) {
throw new Error("Index out of bounds");
}
let current;
// 양방향이므로 앞/뒤에서 효율적으로 탐색
if (index < this.size / 2) {
current = this.head;
for (let i = 0; i < index; i++) {
current = current.next;
}
} else {
current = this.tail;
for (let i = this.size - 1; i > index; i--) {
current = current.prev;
}
}
return current.value;
}
remove(index) {
if (index < 0 || index >= this.size) {
throw new Error("Index out of bounds");
}
let current;
// head 제거
if (index === 0) {
current = this.head;
this.head = this.head.next;
if (this.head) this.head.prev = null;
else this.tail = null;
}
// tail 제거
else if (index === this.size - 1) {
current = this.tail;
this.tail = this.tail.prev;
this.tail.next = null;
}
// 중간 제거
else {
current = this.head;
for (let i = 0; i < index; i++) {
current = current.next;
}
current.prev.next = current.next;
current.next.prev = current.prev;
}
this.size--;
}
toArray() {
const result = [];
let current = this.head;
while (current) {
result.push(current.value);
current = current.next;
}
return result;
}
}
- Node 클래스 → Node 클래스는 prev, next, value까지 저장할 객체입니다. 여기서 ArrayList보다 추가적인 메모리 사용이 발생한다는 단점이 발생합니다.
- add 함수 → 노드를 추가할 때는 리스트가 비어 있는 경우와 기존에 데이터가 있는 경우로 나누어 처리합니다.
- 리스트가 비어 있는 경우 → head와 tail 모두 새로 생성한 노드를 가리키면 됩니다.
- 기존에 데이터가 있는 경우 → 기존 tail의 next를 새 노드로 지정하고, 노드의 prev를 기존 tail로 연결한 뒤, tail을 새 노드로 갱신합니다.
- remove 함수 → 노드를 삭제할 때는, head인 경우, tail인 경우, 중간인 경우로 나누어서 처리합니다.
- head인 경우 → head를 삭제한 head의 next 노드를 가리키면 됩니다.
- tail인 경우 → tail을 삭제한 tail의 prev노드를 가리키면 됩니다.
- 중간인 경우 → 삭제하려는 노드의 이전 노드(prev)와 다음 노드(next)를 서로 연결해주면 됩니다.
- get 함수 → 인덱스를 바로 접근할 수 없기 때문에, 처음부터 순차적으로 탐색합니다. ( 앞에서부터 탐색할지, 뒤에서부터 탐색할지 최적화 )
이러한 이유로 LinkedList는 삭제 삽입 시 O(1)이라는 시간복잡도를 같습니다. 반면 조회 시 O(N)이라는 시간복잡도를 같습니다.
HashTable
해시 테이블은 (key, value)형식으로 데이터를 저장하는 자료구조입니다.
HashTable 시간복잡도는 O(1)이고 충돌이 발생하는 정의만 알고 있었을 뿐, 왜 그런지 생각해 본 적은 없습니다.
이번 기회에 알아 봤습니다.
해시 테이블은 다음과 같은 특징을 가지고 있습니다.
- 해시 함수를 이용해 키를 해시값으로 변환합니다.
- 이 해시값을 인덱스로 사용해 배열 특정 위치에 값을 저장합니다.
- 다른 key에서 동일한 해시 코드가 나올 경우 충돌이 발생합니다.
- 충돌 해결을 위해 연결 리스트를 사용하여 관리합니다.
- O(1) 이라는 검색, 삭제, 삽입 속도를 가지고 있습니다.
- 해시 함수가 비효율적인 경우 충돌이 발생하여 O(n) 시간 복잡도가 걸릴 수 있습니다.
코드를 통해 알아봅시다.
class HashTable {
constructor(size = 53) {
this.size = size;
this.table = new Array(size);
}
// 해시 함수: 단순 문자열 -> 숫자 변환
hash(key) {
let total = 0;
const PRIME = 31; // 충돌 줄이기 위한 소수 사용
for (let i = 0; i < Math.min(key.length, 100); i++) {
const char = key[i];
const value = char.charCodeAt(0) - 96; // 'a' => 1
total = (total * PRIME + value) % this.size;
}
return total;
}
set(key, value) {
const index = this.hash(key);
if (!this.table[index]) {
this.table[index] = [];
}
// 이미 존재하는 키일 경우 덮어쓰기
for (let pair of this.table[index]) {
if (pair[0] === key) {
pair[1] = value;
return;
}
}
// 새로운 키라면 추가
this.table[index].push([key, value]);
}
get(key) {
const index = this.hash(key);
const bucket = this.table[index];
if (bucket) {
for (let pair of bucket) {
if (pair[0] === key) {
return pair[1];
}
}
}
return undefined;
}
remove(key) {
const index = this.hash(key);
const bucket = this.table[index];
if (bucket) {
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
bucket.splice(i, 1);
return true;
}
}
}
return false;
}
}
const ht = new HashTable();
- hash 함수 → 문자열로 들어온 key를 숫자로 변환하여 해시값을 생성하는 함수입니다. 이 함수는 'ab', 'ba'처럼 문자 구성은 같지만 순서가 다른 경우에도 서로 다른 해시값을 생성합니다. 최종적으로는 모듈러 연산을 통해 배열의 크기(this.size) 범위 내에서 인덱스를 반환합니다.
- set 함수 → hash 함수를 사용해 key에 대한 인덱스를 계산한 뒤, 해당 인덱스에 값을 저장합니다. 일반적으로는 해시 충돌 처리를 위해 연결 리스트(Linked List) 등의 구조를 사용하지만, 여기서는 간단히 배열을 이용해 값을 저장합니다. 또한, 일반적인 해시 테이블은 저장 용량이 일정 수준(capacity)을 넘으면 resize를 호출해 배열 크기를 동적으로 늘려주지만, 이번 구현에서는 해당 기능을 포함하지 않았습니다.
- remove 함수 → hash 함수를 사용해 인덱스를 가져오고 배열(원래는 링크드 리스트) 값을 가져옵니다. 그리고 배열을 순회하여 해당 값을 없애주는 함수입니다.
- get 함수 → hash 함수를 사용해 key에 대한 인덱스를 계산한 뒤, 해당 인덱스의 배열(버킷)에서 값을 조회합니다.
이러한 이유로 충돌이 발생하지 않는 이상 삽입 삭제 조회는 O(1) 이라는 시간 복잡도를 가지게 됩니다. 반면 충돌이 발생할 경우 연결 리스트(또는 배열)를 순회해야 하며, 이 경우 최악의 시간 복잡도는 O(n)까지 늘어날 수 있습니다.
Heap
힙은 완전 이진 트리의 일종으로 가장 큰 특징은 부모노드와 자식 노드간 대소 관계를 만족해야 합니다.
그래서 항상 루트 노드는 최대 또는 최소값이 되는 그러한 자료구조를 의미합니다.
특징에 대해 알아 봅시다.
- 우선순위 큐를 위해 고안된 자료구조 입니다.
- 힙 정렬에도 사용됩니다.
- 이진 탐색 트리와 달리 중복을 허용합니다.
- 삽입, 삭제 시 logN이 소요 됩니다.
- Heap은 배열로 구현됩니다.
여기서 중요한 점은 Heap은 배열로 구현할 수 있습니다. 그리고 배열이라는 특징 속에서 규칙이 존재합니다.
- 부모 노드 → Math.floor(현재 index / 2)
- 왼쪽 자식 노드 → 현재 index * 2
- 오른쪽 자식 노드 → 현재 index * 2 + 1
- 부모노드 >= 자식 노드
이러한 특징으로 삽입 로직 핵심을 알아봅시다.
- 삽입은 값을 힙의 마지막 위치에 추가한 뒤, 부모 노드와 자식 노드를 비교하여 조건을 만족할 때까지 위로 올라가며 swap하는 과정 입니다.
마찬가지로 삭제 수도 코드를 작성해 봅시다.
- 삭제는 힙의 루트 노드(가장 큰 값)를 제거한 후, 마지막 값을 루트로 옮기고, 자식 노드들과 비교하여 조건을 만족할 때까지 아래로 내려가며 swap하는 과정입니다.
코드를 통해 알아 봅시다.
class MaxHeap {
constructor() {
this.heap = [];
}
// 부모 인덱스를 반환
getParentIndex(index) {
return Math.floor((index - 1) / 2);
}
// 왼쪽 자식 인덱스를 반환
getLeftChildIndex(index) {
return 2 * index;
}
// 오른쪽 자식 인덱스를 반환
getRightChildIndex(index) {
return 2 * index + 1;
}
// 힙에서 요소 추가
insert(value) {
this.heap.push(value);
this.heapifyUp(this.heap.length - 1);
}
// 힙의 마지막 요소가 올바른 위치로 가도록 정렬
heapifyUp(index) {
let parentIndex = this.getParentIndex(index);
// 부모가 자식보다 작으면, 부모와 자식을 swap
while (index > 0 && this.heap[parentIndex] < this.heap[index]) {
this.swap(parentIndex, index);
index = parentIndex;
parentIndex = this.getParentIndex(index);
}
}
// 힙에서 가장 큰 요소(루트)를 제거하고, 마지막 요소를 루트로 이동 후 힙화
extractMax() {
if (this.heap.length === 0) return null;
if (this.heap.length === 1) return this.heap.pop();
const max = this.heap[0];
this.heap[0] = this.heap.pop(); // 마지막 요소를 루트로 이동
this.heapifyDown(0); // 루트에서부터 힙을 재정렬
return max;
}
// 힙을 아래로 내려가며 올바른 위치를 찾아줌
heapifyDown(index) {
let leftIndex = this.getLeftChildIndex(index);
let rightIndex = this.getRightChildIndex(index);
let largest = index;
// 왼쪽 자식이 더 크면 largest를 왼쪽 자식으로 변경
if (leftIndex < this.heap.length && this.heap[leftIndex] > this.heap[largest]) {
largest = leftIndex;
}
// 오른쪽 자식이 더 크면 largest를 오른쪽 자식으로 변경
if (rightIndex < this.heap.length && this.heap[rightIndex] > this.heap[largest]) {
largest = rightIndex;
}
// 만약 largest가 바뀌었으면, 부모와 largest를 swap 후 heapifyDown
if (largest !== index) {
this.swap(index, largest);
this.heapifyDown(largest);
}
}
// 두 인덱스의 값을 스왑
swap(i, j) {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
// 힙의 상태를 출력
printHeap() {
console.log(this.heap);
}
}
heap을 배열로 구현한 모습입니다.
- insert → 마지막 위치에 값을 추가한 뒤, 힙의 특징인 부모 노드를 쉽게 알 수 있다는 점을 활용하여 부모 노드와 값을 비교하고, 조건을 만족할 때까지 swap을 반복하는 과정입니다.
- delete → 마지막 노드를 루트로 이동시킨 후, 왼쪽과 오른쪽 자식을 비교하여 더 큰 자식과 swap하며 아래로 내려가는 과정을 반복합니다.
이러한 이유로 힙은 삽입과 삭제 시 트리의 높이에 비례하는 시간, 즉 O(log N)의 시간 복잡도를 가집니다. 또한 힙을 이용해 정렬을 수행할 수 있으며, 이 경우 전체 정렬에 걸리는 시간은 O(N log N)입니다.
Stack
스택은 가장 마지막에 삽입된 데이터가 먼저 삭제되는 구조를 가지고 있습니다.
특징으로는 다음과 같습니다.
- push를 하게 되면 새로운 데이터를 top 위치에 삽입합니다.
- pop을 하게 되면 top 위치에 데이터를 제거할 수 있습니다.
코드를 통해 알아봅시다.
class Stack {
constructor() {
this.stack = [];
}
// 스택에 값 추가 (push)
push(value) {
this.stack.push(value);
}
// 스택에서 값 제거 (pop)
pop() {
if (this.isEmpty()) return null;
return this.stack.pop();
}
// 스택의 최상단 값 확인 (peek)
peek() {
if (this.isEmpty()) return null;
return this.stack[this.stack.length - 1];
}
// 스택이 비어있는지 확인
isEmpty() {
return this.stack.length === 0;
}
// 스택 크기 반환
size() {
return this.stack.length;
}
// 스택 출력
print() {
console.log(this.stack);
}
}
자바스크립트에서 배열의 핵심동작은 스택과 비슷합니다.
자바스크립트 이 외에 언어에서 동적 배열이라던지, 연결 리스트로 스택을 구현합니다.
활용 사례는 다음과 같습니다.
- 브라우저 히스토리
- undo 기능
문제) 스택으로 정렬하는 함수를 만드시오, 하나의 스택을 추가로 사용할 수 있고, Array 등을 사용할 수 없다.
Queue
큐는 먼저 들어온 데이터가 먼저 나가는 방식의 선형 자료구조입니다.
큐는 일반적으로 링크드 리스트 및 스택 2개로 구현할 수 있습니다.
// 노드 클래스 정의
class Node {
constructor(value) {
this.value = value;
this.next = null; // 기본적으로 next는 null로 초기화
}
}
// 큐 클래스 정의
class Queue {
constructor() {
this.front = null; // 큐의 앞
this.rear = null; // 큐의 뒤
this.size = 0; // 큐의 크기
}
// 큐에 요소 추가 (enqueue)
enqueue(value) {
const newNode = new Node(value); // 새로운 노드 생성
if (this.rear === null) {
// 큐가 비어있다면, front와 rear 모두 새로운 노드를 가리킴
this.front = this.rear = newNode;
} else {
// 큐가 비어있지 않으면, rear의 next를 새로운 노드로 연결
this.rear.next = newNode;
this.rear = newNode; // rear는 새로운 노드를 가리킴
}
this.size++; // 큐 크기 증가
}
// 큐에서 요소 제거 (dequeue)
dequeue() {
if (this.isEmpty()) {
return 'Queue is empty';
}
const removedNode = this.front; // front 노드를 제거
this.front = this.front.next; // front를 다음 노드로 이동
// 큐가 비었으면 rear도 null로 설정
if (this.front === null) {
this.rear = null;
}
this.size--; // 큐 크기 감소
return removedNode.value; // 제거한 노드의 값 반환
}
// 큐의 첫 번째 요소 확인 (peek)
peek() {
if (this.isEmpty()) {
return 'Queue is empty';
}
return this.front.value; // front 노드의 값 반환
}
// 큐가 비어있는지 확인
isEmpty() {
return this.size === 0;
}
}
싱글 링크드 리스트로 구현했습니다.
반면 두 개의 스택으로도 충분히 구현 가능합니다.
class QueueWithTwoStacks {
constructor() {
this.stack1 = []; // 삽입 스택
this.stack2 = []; // 삭제 스택
}
// 큐에 요소 추가
enqueue(value) {
this.stack1.push(value); // stack1에 값을 추가
}
// 큐에서 요소 제거
dequeue() {
if (this.isEmpty()) {
return 'Queue is empty';
}
if (this.stack2.length === 0) {
// stack2가 비었으면 stack1의 요소를 stack2로 옮깁니다.
while (this.stack1.length > 0) {
this.stack2.push(this.stack1.pop());
}
}
return this.stack2.pop(); // stack2에서 값을 제거하여 반환
}
// 큐가 비어있는지 확인
isEmpty() {
return this.stack1.length === 0 && this.stack2.length === 0;
}
// 큐의 크기 반환
size() {
return this.stack1.length + this.stack2.length;
}
}
dequeue 또는 peek 함수가 호출될 때마다 stack1에 있는 데이터를 stack2로 옮깁니다. 그리고 stack2에 마지막 데이터를 pop해주면 됩니다. 그리고 다시 stack1으로 옮겨주면 됩니다.
'개인 학습' 카테고리의 다른 글
| React의 Suspense 동작 원리 (0) | 2025.04.09 |
|---|---|
| 전역 상태 관리 파헤치기 (0) | 2025.04.06 |
| 서버 사이드 렌더링 (0) | 2025.04.04 |
| Debounce과 Throttle (0) | 2025.04.04 |
| 리액트 코드 분석하기 (0) | 2025.04.02 |
