자바스크립트로 데이터 구조와 알고리즘 구현하기

13 Oct 2023

javascript

자바스크립트는 유연하고 강력한 프로그래밍 언어로, 데이터 구조와 알고리즘을 구현하는 데에도 매우 적합합니다. 이 글에서는 자바스크립트를 사용하여 몇 가지 일반적인 데이터 구조와 알고리즘을 구현하는 방법에 대해 알아보겠습니다.

배열 (Array)

자바스크립트에서 배열은 가장 기본적인 데이터 구조 중 하나입니다. 배열을 선언하고 값에 접근하는 방법은 아래와 같습니다.

// 배열 선언
let numbers = [1, 2, 3, 4, 5];

// 배열 값에 접근
console.log(numbers[0]);  // 1
console.log(numbers[2]);  // 3

// 배열 값 변경
numbers[3] = 8;
console.log(numbers);  // [1, 2, 3, 8, 5]

// 배열 길이 확인
console.log(numbers.length);  // 5

링크드 리스트 (Linked List)

링크드 리스트는 노드들의 연결로 구성된 데이터 구조입니다. 각각의 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있습니다. 자바스크립트에서 링크드 리스트를 구현하는 예제 코드는 다음과 같습니다.

// 노드 객체 생성
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

// 링크드 리스트 객체 생성
class LinkedList {
  constructor() {
    this.head = null;
  }

  // 노드 추가
  append(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next !== null) {
        current = current.next;
      }
      current.next = newNode;
    }
  }

  // 링크드 리스트 출력
  display() {
    let current = this.head;
    let display = '';

    while (current !== null) {
      display += current.data + ' -> ';
      current = current.next;
    }

    console.log(display + 'null');
  }
}

// 링크드 리스트 생성 및 사용
const linkedList = new LinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);

linkedList.display();  // 1 -> 2 -> 3 -> null

스택 (Stack)

스택은 후입선출(LIFO) 형태의 데이터 구조입니다. 자바스크립트에서 스택을 구현하는 예제 코드는 다음과 같습니다.

// 스택 객체 생성
class Stack {
  constructor() {
    this.stack = [];
  }

  // 스택에 데이터 추가
  push(data) {
    this.stack.push(data);
  }

  // 스택의 가장 위 데이터 추출
  pop() {
    if (this.stack.length === 0) {
      return null;
    }
    return this.stack.pop();
  }

  // 스택이 비어있는지 확인
  isEmpty() {
    return this.stack.length === 0;
  }

  // 스택의 크기 확인
  size() {
    return this.stack.length;
  }
}

// 스택 사용
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);

console.log(stack.pop());  // 3
console.log(stack.isEmpty());  // false
console.log(stack.size());  // 2

큐 (Queue)

큐는 선입선출(FIFO) 형태의 데이터 구조입니다. 자바스크립트에서 큐를 구현하는 예제 코드는 다음과 같습니다.

// 큐 객체 생성
class Queue {
  constructor() {
    this.queue = [];
  }

  // 큐에 데이터 추가
  enqueue(data) {
    this.queue.push(data);
  }

  // 큐의 가장 앞 데이터 추출
  dequeue() {
    if (this.queue.length === 0) {
      return null;
    }
    return this.queue.shift();
  }

  // 큐가 비어있는지 확인
  isEmpty() {
    return this.queue.length === 0;
  }

  // 큐의 크기 확인
  size() {
    return this.queue.length;
  }
}

// 큐 사용
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

console.log(queue.dequeue());  // 1
console.log(queue.isEmpty());  // false
console.log(queue.size());  // 2

해시 테이블 (Hash Table)

해시 테이블은 키와 값으로 이루어진 데이터 구조입니다. 자바스크립트에서 해시 테이블을 구현하는 예제 코드는 다음과 같습니다.

// 해시 테이블 객체 생성
class HashTable {
  constructor() {
    this.table = {};
  }

  // 키-값 쌍 추가
  put(key, value) {
    const hash = this._hash(key);
    this.table[hash] = value;
  }

  // 키로 값 조회
  get(key) {
    const hash = this._hash(key);
    return this.table[hash];
  }

  // 해시 함수
  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash;
  }
}

// 해시 테이블 사용
const hashTable = new HashTable();
hashTable.put('apple', '사과');
hashTable.put('banana', '바나나');

console.log(hashTable.get('apple'));  // 사과
console.log(hashTable.get('banana'));  // 바나나

이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리는 정렬된 이진 트리로, 각 노드의 왼쪽 서브트리는 현재 노드보다 작은 값을, 오른쪽 서브트리는 현재 노드보다 큰 값을 가집니다. 자바스크립트에서 이진 탐색 트리를 구현하는 예제 코드는 다음과 같습니다.

// 이진 탐색 트리 객체 생성
class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  // 노드 추가
  insert(data) {
    const newNode = new Node(data);

    if (this.root === null) {
      this.root = newNode;
    } else {
      this._insertNode(this.root, newNode);
    }
  }

  // 노드 삽입 도우미
  _insertNode(node, newNode) {
    if (newNode.data < node.data) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this._insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this._insertNode(node.right, newNode);
      }
    }
  }
}

// 이진 탐색 트리 사용
const bst = new BinarySearchTree();
bst.insert(4);
bst.insert(2);
bst.insert(6);
bst.insert(1);
bst.insert(3);
bst.insert(5);
bst.insert(7);

정렬 알고리즘 (Sorting Algorithms)

자바스크립트에서도 다양한 정렬 알고리즘을 구현할 수 있습니다. 여기서는 버블 정렬(Bubble Sort)과 퀵 정렬(Quick Sort)을 예제로 소개하겠습니다.

버블 정렬

버블 정렬은 인접한 두 원소를 비교하여 정렬하는 알고리즘입니다. 자바스크립트로 버블 정렬을 구현한 예제 코드는 다음과 같습니다.

// 버블 정렬
function bubbleSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(arr));  // [11, 12, 22, 25, 34, 64, 90]

퀵 정렬

퀵 정렬은 분할정복 알고리즘으로, 하나의 원소를 기준으로 작은 값과 큰 값으로 나누어 정렬합니다. 자바스크립트로 퀵 정렬을 구현한 예제 코드는 다음과 같습니다.

// 퀵 정렬
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const pivot = arr[arr.length - 1];
  const left = [];
  const right = [];

  for (let i = 0; i < arr.length - 1; i++) {
    arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]);
  }

  return [...quickSort(left), pivot, ...quickSort(right)];
}

const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(quickSort(arr));  // [11, 12, 22, 25, 34, 64, 90]

결론

자바스크립트를 사용하여 데이터 구조와 알고리즘을 구현하는 방법을 살펴보았습니다. 이러한 데이터 구조와 알고리즘을 이해하고 활용하면 효율적이고 효과적인 프로그램을 개발할 수 있습니다. 자바스크립트 외에도 다른 언어에서도 비슷한 개념을 활용할 수 있으니 지금부터 연습해보시기 바랍니다.

참고 자료:

목차