[JS] js의 data structure

안녕하세요, Einere입니다.

오늘은 javascript에서 data structure에 대해 간단하게 정리하고자 합니다.

stack

stack은 pop과 push를 사용하는 array입니다.

class Stack {
    constructor(...items) {
        this.reverse = false;
        this.stack = [...items];
    }

    push(...items) {
        return this.reverse
            ? this.stack.unshift(...items)
            : this.stack.push(...items);
    }

    pop() {
        return this.reverse ? this.stack.shift() : this.stack.pop();
    }
}

위의 코드를 보시면 특이하게 reverse라는 bool형 property가 존재하는데요, 

해당 property의 값에 따라 push과 pop메소드를 unshift와 shift메소드로 대체할 수 있습니다.

queue

queue는 unshift와 pop(혹은 shift와 push)를 사용하는 array입니다.

class Queue {
    constructor(...items) {
        this.reverse = false;
        this.queue = [...items];
    }

    enqueue(...items) {
        return this.reverse
            ? this.queue.push(...items)
            : this.queue.unshift(...items);
    }

    dequeue() {
        return this.reverse ? this.queue.shift() : this.queue.pop();
    }
}

stack의 경우와 마찬가지로 reverse property의 값에 따라 unshift와 pop메소드를 push와 shift로 대체할 수 있습니다.

linked list

linked list는 node간의 pointer를 통해 연결된 자료구조입니다.

single linked list는 앞쪽 node가 뒷쪽 node를 가리킬 수 있으며,

double linked list는 앞쪽과 뒷쪽 node가 서로를 가리킬 수 있습니다.

class Node {
    constructor(value, next, prev) {
        this.value = value;
        this.next = next;
        this.prev = prev;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
    }

    addToHead(value) {
        const node = new Node(value, null, this.head);
        if (this.head) this.head.next = node;
        else this.tail = node;
        this.head = node;
    }

    addToTail(value) {
        const node = new Node(value, this.tail, null);
        if (this.tail) this.tail.prev = node;
        else this.head = node;
        this.tail = node;
    }

    removeHead() {
        if (!this.head) return null;
        const value = this.head.value;
        this.head = this.head.prev;
        if (this.head) this.head.next = null;
        else this.tail = null;
        return value;
    }

    removeTail() {
        if (!this.tail) return null;
        const value = this.tail.value;
        this.tail = this.tail.next;
        if (this.tail) this.tail.prev = null;
        else this.head = null;
        return value;
    }

    search(value) {
        let current = this.head;
        while (current) {
            if (current.value === value) return value;
            current = current.prev;
        }
        return null;
    }

    indexOf(value) {
        const indexes = [];
        let current = this.tail;
        let index = 0;
        while (current) {
            if (current.value === value) indexes.push(index);
            current = current.next;
            index++;
        }
        return indexes;
    }
}

linked list는 array와 유사하게, stack과 queue를 구현할 수 있습니다.

stack의 경우, single linked list를 사용하여 head에서만 insertion과 removal이 실행되면 되고, (single이므로 tail에서는 불가능합니다.)

queue의 경우, double linked list를 사용하여 head에서 insertion이 실행되고 tail에서 removal이 실행되면 됩니다. (혹은 반대로)

tree

tree는 많은 자식들에 대한 pointer를 가지는 linked list입니다.

즉 부모 node는 자식 node를 여러개 가리킬 수 있으며, 자식 node는 유일한 부모 node를 가집니다.

특히 binary search tree는 최대 2개의 node(left child, right child)만을 가질 수 있는 tree입니다. (즉, complete binary tree입니다.)

그리고 각 node의 값은 left child node <= parent node < right child node의 관계를 가져야 합니다.

이러한 특성 덕분에, BST에서 특정 값을 가지는 node를 찾는 데에는 O(log n)의 시간복잡도를 가집니다.

그러나 linked list로 구현된 tree는 O(n)의 시간복잡도를 가집니다. (complete binary tree는 array로 구현할 수 있습니다.)

그외에, 최솟값(left leaf)과 최댓값(right leaf)을 찾기 용이합니다.

tree를 탐색하는 방법에는 Depth First Traversal와 Breadth First Traversal가 있습니다.

DFT는 우선 leaf node까지 찍고 다시 올라오는 방식이며, BFT는 depth가 얕은 node들부터 우선 탐색하는 방식입니다.

DFT는 recursion이 더 적합하며, BFT는 iteration이 더 적합합니다.

DFT방식에서, tree를 탐색하는 순서를 결정하는 방식에는 pre-order, in-order, post-order로 총 3가지 방식이 존재합니다.

특히 in-order방식은 node를 순서대로 탐색하기 때문에, sorting에 적합한 특성입니다.

class Tree {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    insert(value) {
        if (value <= this.value) {
            if (!this.left) this.left = new Tree(value);
            else this.left.insert(value);
        } else {
            if (!this.right) this.right = new Tree(value);
            else this.right.insert(value);
        }
    }

    contains(value) {
        if (value === this.value) return true;
        if (value < this.value) {
            if (!this.left) return false;
            else return this.left.contains(value);
        } else {
            if (!this.right) return false;
            else return this.right.contains(value);
        }
    }

    depthFirstTraverse(order, callback) {
        order === "pre" && callback(this.value);
        this.left && this.left.depthFirstTraverse(order, callback);
        order === "in" && callback(this.value);
        this.right && this.right.depthFirstTraverse(order, callback);
        order === "post" && callback(this.value);
    }

    breadthFirstTraverse(callback) {
        const queue = [this];
        while (queue.length) {
            const root = queue.shift();
            callback(root.value);
            root.left && queue.push(root.left);
            root.right && queue.push(root.right);
        }
    }

    getMinValue() {
        if (this.left) return this.left.getMinValue();
        return this.value;
    }

    getMaxValue() {
        if (this.right) return this.right.getMaxValue();
        return this.value;
    }
}

참고 : Data Structure In JavaScript