1ilsang

Developer who will be a Legend

Data Structure in JavaScript

2019-09-15 1ilsangData-Structure & Algorithm

자바스크립트의 자료구조

cover image

시작하며

 비지니스 로직이 점점더 백단에서 프론트로 이동함에 따라 프론트 엔지니어링 전문지식이 더욱 중요해지게 되었다.
프론트 엔지니어로써, 우리는 리엑트 같은 생산성있는 뷰 라이브러리에 의존한다. 뷰 라이브러리들은 결국 데이터 관리를 위해 리덕스와 같은 상태 라이브러리에 의존한다.

 리엑트와 리덕스는 UI 업데이트가 데이터 변경에 반응하는 반응형 프로그래밍 패러다임에 함께 가입했다. 점점 더, 백엔드는 단순히 API 서버로 작동하여 데이터를 검색하고 업데이트하는 엔드포인트만 제공한다. 사실상, 백엔드는 단지 데이터베이스를 프론트로 “포워딩” 하고, 프론트 엔지니어가 모든 로직을 컨트롤하길 기대한다. 마이크로서비스GraphQL의 인기 상승이 이러한 증가 추세를 증명한다.

 이제 프론트 엔지니어들은 HTML과 CSS에 대한 미적 이해뿐만 아니라, 자바스크립트를 아주 잘 다루어야 한다. 클라이언트의 데이터스토어가 서버의 데이터베이스에 “복제” 되면서, 관용 자료구조에 대한 친밀한 지식이 중심적 역할을 하게 되었다. 실제로 엔지니어의 경험 수준은 특정 자료구조를 언제, 사용해야하는지 구별할 수 있는 능력으로 유추할수있다.

초급 프로그래머는 코드에 대해 걱정하지만 고급 프로그래머는 자료구조와 그들의 관계를 걱정한다.

- Linux, Git 창시자 리누스 토발즈

큰 틀로, 기본적인 3가지 유형의 자료구조가 있다.
  1. Array: StackQueue 는 오직 아이템을 어떻게 삽입/삭제 하는가 만 다른 배열 같은 자료구조들이다.
  2. LinkedList: 링크드 리스트, 트리 그리고 그래프는 다른 노드에 대한 참조를 유지하는 노드로 이루어진 구조체이다.
  3. Hash: 해쉬테이블은 데이터를 저장하고 찾기 위해 해쉬 함수에 의존한다.

 복합성 측면에서, StackQueue는 가장 간단하며 Linked List로 구성할 수 있다. TreeGraph 는 링크드 리스트의 개념을 확장시킨 것이기 때문에 가장 복잡하다. Hash Table 은 이런 자료구조들을 활용하여 안정적으로 돌아가야한다.
 효율성 측면에서, Linked List는 데이터의 기록 및 저장에 가장 최적화되어있으며 Hash Table은 데이터의 탐색과 검색에 가장 효과적이다.

이유를 설명하고 시기를 설명하기 위해, 이 글은 위에서 언급한 의존성의 순서를 따를 것이다. 시작해보자!

Stack

 의심의 여지없이 자바스크립트에서 가장 중요한 Stack은 우리가 실행하는 펑션의 스코프를 푸쉬하는 call stack 일 것이다. 프로그래밍적으로 스택은 단순히 pushpop의 두 가지 정책을 가진 배열이다. Push는 배열의 탑에 원소를 추가한다. 반면 Pop은 같은 위치에서 원소를 제거한다. 즉, Stacks 은 “Last In, First Out” 정책을 따른다(LIFO).

 아래는 Stack 코드의 예다. 우리는 스택의 순서를 뒤집을 수 있다는 점에 유의해야한다. 바텀이 탑으로가고 탑이 바텀에 간다는 뜻이다.(역자 - 저자는 스택의 reverse 도 염두한듯.)

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

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

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

(역자 - 본 글은 ‘자바스크립트 내부에서 쓰이는 자료구조’ 개념을 이해하는 포스터라 API 구현까지는 다루지 않는다.)

 아이템의 숫자가 증가함에 따라, push/popunshift/shift보다 더 성능이 좋아지게 된다. 그 이유는 후자의 경우 모든 아이템이 다시 인덱싱을 해야하기 때문이다.(push/pop 은 최상단 index 만 변하기 때문)

Queue

 자바스크립트는 non-blocking을 지원하는 event-driven 방식의 프로그래밍 언어이다. 내부적으로, 브라우저는 하나의 쓰레드만 관리하기 때문에 브라우저는 자바스크립트 코드 전체를 실행하기 위해 오직 하나의 쓰레드만 관리하며, event queue를 사용하여 listener등록(enqueue) 하고 event loop로 등록된 event들을 listen 한다.
 싱글 쓰레드 환경에서 비동기를 지원하기 위해(CPU 자원과 웹 경험의 향상을 위해서), listener function들은 call stack이 비어있을 때만 제거(dequeue) 되며 실행된다. Promise 들은 이 event-driven architecture에 의존하여 다른 작업을 차단하지 않는 비동기 코드의 “동기식” 실행을 허락한다.

 프로그래밍적으로, Queue는 두개의 단순한 작업(unshift and pop)이 있는 배열에 불과하다. Unshift는 아이템들을 배열의 등록(enqueue) 하는 반면, Pop은 배열의 시작 에서 제거(dequeue)한다. 즉, Queue는 “First In, First Out”(FIFO) 정책을 따른다. 만약 방향이 뒤집어지면, 우리는 unshiftpop을 각각 pushshift로 대치할 수 있다.

아래는 Queue 코드의 예이다.

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();
    }
}

Linked List

Linked List 는 배열같이 데이터들을 순차적으로 저장한다. 링크드 리스트는 인덱스를 유지하는 대신 다른 원소를 가리키는 포인터 를 가지고 있다. 첫 번째 노드head라고 불리는 반면 마지막 노드tail이라 불린다. singly-linked list 에서 각 노드는 다음노드를 가리키는 오직 하나의 포인터만 가지고 있다. 여기서 head는 우리가 리스트의 나머지들로 걸어가기 위한 시작점이다. doubly-linked list의 경우 이전(previous) 노드로 가는 포인트도 가지고 있다. 그러므로 우리는 tail에서 시작해 “뒤에서” 앞으로 갈 수 있다.

 링크드 리스트는 삽입삭제상수시간 O(1)을 가진다 왜냐하면 단순히 포인터들만 바꾸면 되기 때문이다. 배열에서 같은 작동을 하기 위해선 선형 시간 O(N)이 필요하다 왜냐면 이후의 아이템들이 한 칸씩 밀려나야 하기 때문이다. 또한, 링크드리스트는 공간(메모리)이 있는 한 넓힐 수 있다. 그러나, 자동으로 리사이징을 하는 “동적” 배열도 생각외로 비싼 값을 치뤄야 할 수 있다. 물론, 이것들은 항상 등가교환이다. 링크드 리스트의 원소를 변경하거나 찾아보자. 우리는 아마도 선형 시간으로 전체 길이를 탐색해야 할 수도 있다. 반면 인덱스 배열에서는 바로 찾아갈 수 있다.

 배열처럼, 링크드 리스트도 stack 같이 조작할 수 있다. head 를 삽입, 삭제하는 공간이 하나이므로 쉽게 구현할 수 있다. 또한 링크드리스트는 queue와 같이 작동 할 수 있다. 이는 doubly-linked list 로 이루어 질 수 있는데, tail에서 삽입이 일어나거나 head에서 삭제가 일어날 때 혹은 반대일 때 가능하다. 많은 숫자들이 존재하는 원소에서 이 구현 방법은 배열을 사용해 큐를 구현하는 것보다 더 좋은 성능을 보인다. 이유는 배열에서 shiftunshift 작동이 일어날 때 인덱스를 재배열 하기 위해 선형 시간이 필요하기 때문이다.

 링크드리스트는 클라이언트와 서버에서 모두 쓸모있다. 클라이언트에서 Redux 같은 상태관리 라이브러리들은 미들웨어 로직을 링크드 리스트 방식으로 구현한다. action이 디스패치 될 때, 모두 reducer에 도달할 때까지 하나의 미들웨어에서 다음 미들웨어로 연결된다. 서버의 경우 Express 같은 웹 프레임워크도 비슷한 미들웨어 로직을 가지고 있다. request 를 받았을 때, 이것들은 reponse 받을 때 까지 미들웨어를 타고다닌다.

아래는 Doubly-Linked List 의 코드 예이다.

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;
    }
}

Tree

Tree많은 child nodes을 유지하고 있는 계층적 구조라는 것을 제외하곤 linked list같다. 즉, 각 노드는 한 명 이상의 부모를 가질 수 없다. Document Object Model(DOM)이 이 구조이다. root 는 html 노드이며 자식들로 headbody노드가 있다. 이들은 친숙한 모든 html 태그 로 더욱 세분화된다. 실제로 리엑트 컴포넌트 또한 prototype 상속구성 의 트리 구조를 생성한다. 물론 DOM의 인메모리 표현인 리엑트의 가상DOM 또한 트리 구조이다.

Binary Search Tree는 각 노드가 두 개의 자식 이상을 가질 수 없기 때문에 특별하다. left child의 값은 반드시 부모의 값보다 작거나 같아야한다 반면 right child는 반드시 부모의 값보다 커야한다. 이와같이 구조화되고 균형이 맞춰졌다면, 우리는 어떠한 값이든 search로그 시간만에 찾을 수 있다. 이유는 각 브랜치를 순회시 작업의 반을 무시할 수 있기 때문이다. 삽입삭제 또한 로그시간에 가능하다. 게다가, 가장 왼쪽, 가장 오른쪽 노드가 각각 최소 혹은 최대 값이므로 값을 쉽게 찾을 수 있다.

 트리의 순회는 수직 또는 수평의 절차로 발생할 수 있다. 세로 방향의 Depth-First Traversal(DFT: DFS) 에서 재귀 알고리즘은 반복문보다 더 우아하다. 노드들은 pre-order, in-order, post-order 으로 순회된다. 만약 리프노드를 검사하기 전에 루트노드를 탐색해야 한다면, 우리는 pre-order 를 선택할 것이다. 그러나 만약 루트전에 리프노드부터 탐색해야 한다면 post-order를 선택해야 한다. in-order 는 이름이 암시하듯, 노드들을 순차적으로 순회할 수 있다. 이 속성들은 이진탐색트리를 정렬에 최적화 되게 만든다.

 수평 방향의 Breadth-First Traversal(BFT: BFS)에서 반복문은 재귀보다 더 우아하다. 이것은 각 순회에 모든 자식 노드들을 트래킹하기 위해서 queue의 사용을 요구한다. 이 큐에 필요한 메모리는 사소하지 않을 수 있다. 하지만 트리의 모양이 깊이보다 넓다면, BFT가 DFT 보다 더 나은 선택이다. 또한, BFT 가 두 노드 사이를 이동하는 경로는 가능한 가장 짧은 거리이다.

아래는 Binary Search Tree의 코드 예이다.

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;
    }
}

mocha.setup("bdd");
const { assert } = chai;

const tree = new Tree(5);
for (const value of [3, 6, 1, 7, 8, 4, 10, 2, 9]) tree.insert(value);

/*
  5
 3 6
1 4 7
 2   8
          10
         9  
*/

describe("Binary Search Tree", () => {
    it("Should implement insert", () => {
        assert.equal(tree.value, 5);
        assert.equal(tree.left.value, 3);
        assert.equal(tree.right.value, 6);
        assert.equal(tree.left.left.value, 1);
        assert.equal(tree.right.right.value, 7);
        assert.equal(tree.right.right.right.value, 8);
        assert.equal(tree.left.right.value, 4);
        assert.equal(tree.right.right.right.right.value, 10);
        assert.equal(tree.left.left.right.value, 2);
        assert.equal(tree.right.right.right.right.left.value, 9);
    });

    it("Should implement contains", () => {
        assert.equal(tree.contains(2), true);
        assert.equal(tree.contains(9), true);
        assert.equal(tree.contains(0), false);
        assert.equal(tree.contains(11), false);
    });

    it("Should implement depthFirstTraverse", () => {
        const _pre = [];
        const _in = [];
        const _post = [];
        tree.depthFirstTraverse("pre", value => _pre.push(value));
        tree.depthFirstTraverse("in", value => _in.push(value));
        tree.depthFirstTraverse("post", value => _post.push(value));
        assert.deepEqual(_pre, [5, 3, 1, 2, 4, 6, 7, 8, 10, 9]);
        assert.deepEqual(_in, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
        assert.deepEqual(_post, [2, 1, 4, 3, 9, 10, 8, 7, 6, 5]);
    });

    it("Should implement breadthDepthTraverse", () => {
        const result = [];
        tree.breadthFirstTraverse(value => result.push(value));
        assert.deepEqual(result, [5, 3, 6, 1, 4, 7, 2, 8, 10, 9]);
    });

    it("Should implement getMinValue", () => {
        assert.equal(tree.getMinValue(), 1);
    });

    it("Should implement getMaxValue", () => {
        assert.equal(tree.getMaxValue(), 10);
    });
});

Graph

 만약 트리의 부모가 하나보다 더 많이 가질 수 있다면, 이것이 바로 Graph 이다. 그래프에서 노드들을 이어주는 Edge는 노드들이 방향, 무방향, 가중치, 비가중치 를 가지게 한다. Edge 들은 vector와 유사한 방향과 가중치를 가진다.

추가 예정

감사합니다.