Javascript之双向链表

上篇文章（链表LinkedList的实现）中实现了普通链表的基本功能，那么本文再来实现一下双向链表。双向链表和普通链表的区别在于，在普通链表中，一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个节点，另一个链向上一个节点。

同样实现和上篇文章中和链表一样的功能，只不过多了一个上一个节点prev的处理。

DoublyLinkedList类包括如下的这些方法：

• append(element)：向列表尾部添加一个新元素。
• removeAt(position)：删除列表中指定位置的元素。
• insert(position, element)：删除列表中指定位置的元素。
• indexOf(element)：返回指定元素在列表中的位置。
• remove(element)：删除指定元素。
• getHead()：获取列表第一个元素。
• getTail()：获取列表最后一个元素。
• isEmpty()：列表是否为空。
• size():列表的大小。

以insert(position, element)方法为例，向链表中添加一个新元素到指定位置。这里需要考虑到三种情况：1.向一个位置添加元素；2.向最后一个位置添加元素;3.向中间位置添加元素。

当向第一个位置添加元素时，需要判断当前链表是否有元素，如果没有，直接添加的就是第一个节点，同时也是最后一个节点。

当链表不为空时，则需要把原来的第一个元素的prev指向新元素，然后再将新元素的next指向原来的第一个元素，再将第一个元素head更新为当前添加的元素。

当向最后一个位置添加元素时，需要将原最后一个元素的next指向新元素，并将新元素的prev指向原最后一个元素，最后再更新最后一个元素tail。

最后一种情况是向中间位置添加元素，从第一个元素head开始向后迭代（当然，也可以根据position相对于链表的长度，选择从第一个或最后一个位置开始迭代，增加迭代效率）。迭代到指定位置后，将该位置元素的prev设置为待添加的元素node，将node的next设置为原该位置的元素。同理，将原迭代位置的上一个元素的next设置的node，在将node的prev也指向上一个元素。

详细查看代码

const DoublyLinkedList = (function () {
    let head = null,
        tail = null,
        length = 0

    const Node = class {
        constructor(element) {
            this.element = element
            this.prev = null
            this.next = null
        }
    }

    class DoublyLinkedList {
        append(element) {
            const node = new Node(element)
            if (length === 0) {
                head = tail = node
            } else {
                node.prev = tail
                tail.next = node
                tail = node
            }
            length++
        }

        insert(position, element) {
            const node = new Node(element)
            let current = head
            if (position > -1 && position < length) {
                if (position === 0) {
                    if (head === null) {
                        head = node
                        tail = node
                    } else {
                        head = node
                        head.next = current
                        current.prev = head
                    }
                } else if (position === length - 1) {
                    tail.next = node
                    node.prev = tail
                    tail = node
                } else {
                    let index = 0,
                        prev = null
                    while (index++ < position) {
                        prev = current
                        current = current.next
                    }
                    prev.next = node
                    node.prev = prev

                    current.prev = node
                    node.next = current
                }
                length++
                return true
            }
            return false
        }

        removeAt(position) {
            if (position > -1 && position < length) {
                let current = head
                if (position === 0) {
                    if (length === 1) {
                        head = tail = null
                    } else {
                        head = head.next
                        head.prev = null
                    }
                } else if (position === length) {
                    current = tail
                    tail = tail.prev
                    tail.next = null
                } else {
                    let index = 0,
                        prev = null
                    while (index++ < position) {
                        prev = current
                        current = current.next
                    }
                    prev.next = current.next
                    current.next.prev = prev
                }
                length--
                return current.element
            }
        }

        indexOf(element) {
            let current = head,
                index = 0
            while (current) {
                if (current.element === element) {
                    return index
                }
                index++
                current = current.next
            }
            return -1
        }

        remove(element) {
            const index = this.indexOf(element)
            return this.removeAt(index)
        }

        isEmpty() {
            return length === 0
        }

        size() {
            return length
        }

        getHead() {
            return head
        }

        getTail() {
            return tail
        }

        toString() {
            let current = head,
                str = ''
            while (current) {
                str += `element: ${current.element}, prev: ${current.prev ? current.prev.element : 'null'}, next: ${current.next ? current.next.element + '\r\n' : 'null'}`
                current = current.next
            }
            return str
        }
    }

    return DoublyLinkedList
}())

const doublyLinkedList = new DoublyLinkedList()
doublyLinkedList.append('a')
doublyLinkedList.append('b')
doublyLinkedList.append('c')
doublyLinkedList.append('d')
doublyLinkedList.insert(1, 'hello world')
console.log(doublyLinkedList.toString());
console.log(doublyLinkedList.indexOf('hello world'));

//输出
// element: a, prev: null, next: hello world
// element: hello world, prev: a, next: b
// element: b, prev: hello world, next: c
// element: c, prev: b, next: d
// element: d, prev: c, next: null
// 1