LinkedList(연결 리스트) with JavaScript

* node 에서는 기본적으로 class를 사용하지 못하므로 babel을 사용해야 한다. 적용법은 최하단 링크에 있다. 귀찮으면 아래 링크의 git을 clone을 하시면 된다. 

단일 LInked List (출처 : https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8)

이중 Linked List (출처 : https://upload.wikimedia.org/wikipedia/commons/thumb/c/ca/Doubly_linked_list.png/400px-Doubly_linked_list.png)

Linked List (연결리스트) : 하나의 데이터 노드가 다음 노드의 참조값을 가지는 리스트.

데이터 추가 삭제는 빠르지만, 데이터를 찾는데 오래 걸린다. 그래서 별로 써본 기억이 없다.

class Node {
    data;
    previous;
    next;

    constructor(data, previous, next) {
        this.next = next;
        this.data = data;
        this.previous = previous;
    }
}

class LinkedList {

    first;
    last;
    size;

    constructor(firstNodeData) {
        this.first = new Node(firstNodeData);
        this.last = this.first;
        this.size = 1;
    }

    insertLast = (data) => {
        const newNode = new Node(data, this.last);
        this.last.next = newNode;
        this.last = newNode;
    }

    getSize = () => this.size;

    isEmpty = () => {
        const status = (this.size === 0) ? true : false;
        return status;
    };

    printInOrder = (node) => {
        if (node === undefined || node === null) {
            return;
        }
        process.stdout.write(node.data + ', ');
        this.printInOrder(node.next);
    };

    printReverseOrder = (node) => {
        if (node === undefined || node === null) {
            return;
        }
        process.stdout.write(node.data + ', ');
        this.printReverseOrder(node.previous);
    };

    searchNode = (data, order) => {
        const startNode = (order === 'asc') ? this.first : this.last;
        return this.roundNode(startNode, data, order);
    };

    roundNode = (node, data, order) => {
        if (node === null | node === undefined) return null;
        if (node.data === data) return node;
        const foundNode = (order === 'asc') ? this.roundNode(node.next, data, order) : this.roundNode(node.previous, data, order);
        return foundNode;
    };

    insertNode = (data, nodeToFind) => {
        const foundNode = this.searchNode(nodeToFind);
        const newNode = new Node(data, foundNode, foundNode.next);
        foundNode.next.previous = newNode;
        foundNode.next = newNode;

        if (foundNode.next === null | foundNode.next === undefined){
            this.last = newNode
        }
        this.size++;
    };

    deleteNode = (data, searchOrder) => {
        const foundNode = this.searchNode(data, searchOrder);
        foundNode.previous.next = foundNode.next;
        foundNode.next.previous = foundNode.previous;
        this.size--;
    };
}

const linkedList = new LinkedList('firstNode');
for (let i = 0; i < 10; i++) {
    linkedList.insertLast(`Node ${i}`);
}

//////// print 
// linkedList.printInOrder(linkedList.first);
// linkedList.printReverseOrder(linkedList.last);

//////// find node inorder
// const foundNode = linkedList.searchNode('Node 3', 'asc');
// const foundNode = linkedList.searchNode('Node 5', 'desc');
// console.log(foundNode);

//////// find and insert node
// linkedList.insertNode('added Node', 'Node 5');
// linkedList.insertNode('added Node2', 'Node 7');

//////// delete node
// linkedList.deleteNode('added Node2', 'asc');

//////// print result
// console.log();
// linkedList.printInOrder(linkedList.first);
// linkedList.printReverseOrder(linkedList.last);
// console.log();

 

---

아래의 내 깃허브에서 소스를 볼 수 있다.

https://github.com/iamdap91/basic-data-structure

iamdap91/basic-data-structure

http://jeonghwan-kim.github.io/2016/07/19/babel.html

Babel로 ES6 코드 사용하기