SOURCE

class LinkedList {
    length = 0

    head = null

    Node = class {
        data
        next = null
        constructor(data) {
            this.data = data
        }
    }

    append(data) {
        const newNode = new this.Node(data)

        if (this.length === 0) {
            this.head = newNode
        } else {
            let currentNode = this.head

            while (currentNode.next !== null) {
                currentNode = currentNode.next
            }

            currentNode.next = newNode
        }

        this.length++
    }

    toString() {
        let currentNode = this.head
        let result = ''

        while (currentNode) {
            result += currentNode.data + ''
            currentNode = currentNode.next
        }

        return result
    }

    insert(position, data) {

        if (position < 0 || position > this.length) return false

        const newNode = new this.Node(data)

        if (position === 0) {
            newNode.next = this.head

            this.head = newNode
        } else {
            let currentNode = this.head
            let previousNode = null
            let index = 0
            while (index++ < position) {
                previousNode = currentNode
                currentNode = currentNode.next
            }

            newNode.next = currentNode
            previousNode.next = newNode
        }

        this.length++
        return newNode
    }

    getData(position) {
        if (position < 0 || position >= this.length) return false

        let currentNode = this.head
        let index = 0
        while (index++ < position) {
            currentNode = currentNode.next
        }

        return currentNode.data
    }

    indexOf(data) {
        let currentNode = this.head
        let index = 0
        while (currentNode) {
            if (currentNode.data === data) {
                return index
            }
            currentNode = currentNode.next
            index++
        }

        return -1
    }

    update(position, data) {
        if (position < 0 || position >= this.length) return false

        let currentNode = this.head
        let index = 0

        while (index++ < position) {
            currentNode = currentNode.next
        }

        currentNode.data = data

        return currentNode
    }

    removeAt(position) {
        if (position < 0 || position >= this.length) return false

        let currentNode = this.head
        if (position === 0) {
            this.head = this.head.next
        } else {
            let previousNode = null
            let index = 0

            while (index++ < position) {
                previousNode = currentNode
                currentNode = currentNode.next
            }

            previousNode.next = currentNode.next
        }

        this.length--

        return currentNode
    }

    remove(data) {
        this.removeAt(this.indexOf(data))
    }

    isEmpty() {
        return this.length === 0
    }

    size() {
        return this.length
    }
}

class DoublyLinkedList extends LinkedList {
    DoublyNode = class {
        data
        next = null
        prev = null
        constructor(data) {
            this.data = data
        }
    }
    constructor(data) {
        super(data)
        this.tail = null
    }

    append(data) {
        const newNode = new this.DoublyNode(data)

        if (this.head === null) {
            this.head = newNode
            this.tail = newNode
        } else {
            this.tail.next = newNode
            newNode.prev = this.tail
            this.tail = newNode
        }

        this.length++
    }

    insert(position, data) {
        if (position < 0 || position > this.length) return false

        const newNode = new this.DoublyNode(data)

        if (position === 0) {
            if (this.head === null) {
                this.head = newNode
                this.tail = newNode
            } else {
                newNode.next = this.head
                this.head.prev = newNode
                this.head = newNode
            }
        } else if (position === this.length) {
            this.tail.next = newNode
            newNode.prev = this.tail
            this.tail = newNode
        } else {
            let targetIndex = 0
            let currentNode = this.head
            let previousNode = null

            while (targetIndex++ < position) {
                previousNode = currentNode
                currentNode = currentNode.next
            }

            previousNode.next = newNode
            newNode.prev = previousNode

            newNode.next = currentNode
            currentNode.prev = newNode
        }

        this.length++

        return true
    }
    // getData() 继承单向链表
    getData(position) {
        return super.getData(position);
    }

    // indexOf() 继承单向链表
    indexOf(data) {
        return super.indexOf(data);
    }
    removeAt(position) {
        if (position < 0 || position > this.length - 1) return null

        let currentNode = this.head
        if (position === 0) {

            if (this.length === 1) {
                this.head = null
                this.tail = null
            } else {
                this.head = this.head.next
                this.head.prev = null
            }
        } else if (position === this.length - 1) {

            currentNode = this.tail
            this.tail.prev.next = null
            this.tail = this.tail.prev
        } else {
            let targetIndex = 0
            let previousNode = null
            while (targetIndex++ < position) {
                previousNode = currentNode
                currentNode = currentNode.next
            }

            previousNode.next = currentNode.next
            currentNode.next.prev = previousNode
        }

        this.length--
        return currentNode.data
    }

    update(position, data) {
        const result = this.removeAt(position)

        this.insert(position, data)

        return result
    }

    forwardToString() {
        let currentNode = this.head;
        let result = '';

        // 遍历所有的节点，拼接为字符串，直到节点为 null
        while (currentNode) {
            result += currentNode.data + '--';
            currentNode = currentNode.next;
        }

        return result;
    }

    backwardString() {
        let currentNode = this.tail;
        let result = '';

        // 遍历所有的节点，拼接为字符串，直到节点为 null
        while (currentNode) {
            result += currentNode.data + '--';
            currentNode = currentNode.prev;
        }

        return result;
    }
}

const doublyLinkedList = new DoublyLinkedList();

// append() 测试
doublyLinkedList.append('ZZ');
doublyLinkedList.append('XX');
doublyLinkedList.append('CC');
console.log(doublyLinkedList);

// insert() 测试
doublyLinkedList.insert(0, '00');
doublyLinkedList.insert(2, '22');
console.log(doublyLinkedList);

// getData() 测试
console.log(doublyLinkedList.getData(1)); //--> ZZ

// indexOf() 测试
console.log(doublyLinkedList.indexOf('XX')); //--> 3
console.log(doublyLinkedList);

// removeAt() 测试
doublyLinkedList.removeAt(0);
doublyLinkedList.removeAt(1);
console.log(doublyLinkedList);

// update() 测试
doublyLinkedList.update(0, '111111');
console.log(doublyLinkedList);

// remove() 测试
console.log(doublyLinkedList.remove('111111'));
console.log(doublyLinkedList.remove('22222'));
console.log(doublyLinkedList);

// forwardToString() 测试
console.log(doublyLinkedList.forwardToString());

// backwardString() 测试
console.log(doublyLinkedList.backwardString());