class Node {

    constructor(element) {

        this.element = element;

        this.prev = null;

        this.next = null;

    }

}

class DoubledLinskLIst {

    constructor() {

        this.length = 0;

        this.head = null;

        this.tail = null;

    }

    append(element) {

        let node = new Node(element);

        if (this.getHead() === null) {  //空链表的情况

            this.head = node;

            this.tail = node;   //如果是空链表，插入一个元素，它的head和tail都指向node

        }

        else {

            let current = this.getTail();

            current.next = node;

            node.prev = current;

            this.tail = node;

        }

        this.length++;

    }

    insert(position, element) {

        if (position >= 0 && position <= this.size()) {

            let current = this.getHead(),

                previous,

                index = 0,

                node = new Node(element);

            if (position === 0) {

                if (!this.getHead()) {    //空链表

                    this.head = node;

                    this.tail = node;

                }

                else {

                    this.head = node;

                    node.next = current;

                    current.prev = node;

                }

            }

            else if (position === this.size()) {

                current = this.getTail();

                this.tail = node;

                node.prev = current;

                current.next = node;

            }

            else {

                while (index++ < position) {

                    previous = current;

                    current = current.next;

                }

                previous.next = node;

                node.prev = previous;

                node.next = current;

                current.prev = node;

            }

            this.length++;

            return true;

        }

        else {

            return false;

        }

    }

    removeAt(position) {

        if (position >= 0 && position < this.size()) {

            let current = this.getHead(), index = 0, previous;

            if (position === 0) {

                this.head = current.next;

                if (this.size() === 1) {    //链表只有一个数据

                    this.tail = null;

                }

                else {

                    current.next.prev = null;

                }

            }

            else if (position === this.size() - 1) {

                current = this.getTail();

                this.tail = current.prev;

                current.prev.next = null;

            }

            else {

                while (index++ < position) {

                    previous = current;

                    current = current.next;

                }

                previous.next = current.next;

                current.next.prev = previous;

            }

            this.length--;

            return current.element;

        }

        else {

            return null;

        }

    }

    indexOf(element) {

        let current = this.getHead(), index = 0;

        while (current) {

            if (current.element === element) {

                return index;

            }

            index++;

            current = current.next;

        }

        return -1;

    }

    remove(element) {

        let position = this.indexOf(element);

        return this.removeAt(position);

    }

    getHead() {

        return this.head;

    }

    getTail() {

        return this.tail;

    }

    size() {

        return this.length;

    }

    isEmpty() {

        return this.length === 0;

    }

    toString() {

        let current = this.getHead(),

            string = '';

        while (current) {

            string += current.element + (current.next ? ', ' : '');

            current = current.next;

        }

        return string;

    }

    print() {

        console.log(this.toString());

    }

}