이중 연결 리스트

	class Node {
    constructor(val) {
        this.val = val;
        this.next = null;
        this.prev = null;
    }
}

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }

    push(val) {
        var newNode = new Node(val);

        if(this.length === 0) {
            this.head = newNode;
            this.tail = newNode;
        }else {
            newNode.prev = this.tail;
            this.tail.next = newNode;
            this.tail = newNode;            
        }

        this.length++;
        return this;
    }

    pop() {
        if(!this.head) return undifined;
        var removed = this.tail;
        if(this.length === 1) {
            this.head = null;
            this.tail = null;
        }else {
            this.tail = removed.tail;
            this.tail = null;
            removed.tail = null;
        }
        this.length--;
        return removed;
    }

    shift() {
        if(this.length === 0) return undifined;
        var oldHead = this.head;
        if(this.length === 1) {
            this.head = null;
            this.tail = null;
        }else {
            this.head = this.head.next;
            this.head.prev = null;
            oldHead.next = null;
        }
        this.length--;
        return oldHead;
    }

    unshift(val) {
        var newNode = new Node(val);
        if(this.length === 0) {
            this.head = newNode;
            this.tail = newNode;
        }else {
            this.head.prev = newNode;
            newNode.next = this.head;
            this.head = newNode;
        }

        this.length++;
        return this;
    }
    
    get(index) {
        if(index < 0 || index >= this.length) return null;
    
        if(index <= this.length / 2) {
            var count = 0;
            var current = this.head;
            while(count !== index) {
                current = current.next;
                count++;
            }
            return current;
        }else {
            var count = this.length - 1;
            var current = this.tail;
            while(count !== index) {
                current = current.prev;
                count--;
            }
            return current;
        }
    }

    set(index, val) {
        var currentNode = this.get(index);
        if(!currentNode) return false;
        currentNode.val = val;

        return true
    }

    insert(index, val) {
        if(index < 0 || index > this.length) return false;
        if(index === 0) {
            this.unshift(val);
        }else if(index === this.length - 1) {
            this.push(val);
        }else {
            var prevNode = this.get(index - 1);
            var newNode = new Node(val);
            newNode.prev = prevNode;
            newNode.next = prevNode.next;
            prevNode.next.prev = newNode;
            prevNode.next = newNode;
        }
        this.length++;
        return true;
    }

    remove(index) {
        if(index < 0 || index >= this.length) return false;
        var currentNode = this.get(index);
        if(index === 0) {
            this.shift();
            currentNode.next = null;
        }else if(index === this.length - 1) {
            this.pop();
            currentNode.prev = null;
        }else {
            var prevNode = currentNode.prev;
            var afterNode = currentNode.next;
            prevNode.next = afterNode;
            afterNode.prev = prevNode;
            currentNode.next = null;
            currentNode.prev = null;
        }

        this.length--;
        return currentNode;
    }
}

var list = new DoublyLinkedList();