JS实现双向链表

  链表有多种不同的类型，我们讨论下双向链表。双向链表与单链表的区别在于，在单链表中，一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素。
  双向链表提供了两种迭代列表的方法：从头到尾，或则反过来。在单链表中，如果我们在迭代列表中错过了要找的元素，就需要回到列表的起点，重新开始迭代，这是双向列表的优点。
  双向链表与单向链表的实现类似，需要同时控制next、prev两个指针，同时需要增加尾引用tail，我们对上一节单链表的JS代码进行改造。

 function DoubleLinkedList() {

        // Node辅助类，表示要加入列表的项，element是即将添加到列表的值，next是指向列表中下一个节点项的指针
        let Node = function (element) {
            this.element = element
            this.prev = null // 新增一个向前的指针
            this.next = null 
        }

        let length = 0
        let head = null
        let tail = null // 新增一个尾引用

        // 向链表尾部追加元素
        this.append = function (element) {
            let node = new Node(element)

            let current
            if (head === null) { // 列表中第一个节点
                head = node // head与tail是同一个元素
                tail = node
            } else {
                current = head
                while (current.next) {
                    current = current.next // 找到最后一项，是null
                }
                current.next = node // 给最后一项赋值
                node.prev = current
                tail = node // 修改尾引用
            }
            length++ // 更新列表的长度
        }

        // 从链表中移除指定位置元素
        this.removeAt = function (position) {
            if (position > -1 && position < length) { // 值没有越界
                let current = head
                let previous,
                    index = 0
                if (position === 0) { //  移除第一项
                    head = current.next
                    if (length === 1) { // 只有一项
                        tail = null
                    } else {
                        head.prev = null
                    }
                } else if (position === length - 1) { // 移除最后一项
                    current = tail
                    tail = current.prev
                    tail.next = null
                }
                else {
                    while (index++ < position) {
                        previous = current
                        current = current.next
                    }
                    previous.next = current.next // 将previous与current的下一项连接起来，跳过current，从而移除
                    current.next.prev = previous
                }
                length-- // 更新列表的长度
                return current.element
            } else {
                return null
            }
        }

        // 在链表任意位置插入一个元素
        this.insert = function (position, element) {
            if (position >= 0 && position <= length) { // 检查越界值
                let node = new Node(element),
                    current = head,
                    previous,
                    index = 0
                if (position === 0) { // 在第一个位置添加
                    if (!head) {
                        head = node
                        tail = node
                    }else {
                        node.next = current
                        current.prev = node
                        head = node
                    }
                    node.next = current
                    head = node
                } else if (position === length) {
                    current = tail
                    current.next = node
                    node.prev = current
                    tail = node
                } else {
                    while (index++ < position) {
                        previous = current
                        current = current.next
                    }
                    node.next = current // 在previous与current的下一项之间插入node
                    previous.next = node

                    current.prev = node
                    node.prev = previous
                }
                length++
                return true
            } else {
                return false
            }
        }

        // 把链表内的值转换成一个字符串
        this.toString = function () {
            let current = head,
                string = ''
            while (current) {
                string += current.element + ' '
                current = current.next
            }
            return string
        }

        // 在链表中查找元素并返回索引值
        this.indexOf = function (element) {
            let current = head,
                index = 0
            while (current) {
                if (element === current.element) {
                    return index
                }
                index++
                current = current.next
            }
            return -1
        }

        // 从链表中移除指定元素
        this.remove = function (element) {
            let index = this.indexOf(element)
            return this.removeAt(index)
        }

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

        this.size = function () {
            return length
        }

        this.getHead = function () {
            return head
        }
    }
    let list = new DoubleLinkedList()
    list.append(1)
    list.append(2)
    console.log(list.toString()) // 1 2
    list.insert(0, 'hello')
    list.insert(1, 'world')
    console.log(list.toString()) // hello world 1 2
    list.remove(1)
    list.remove(2)
    console.log(list.toString()) // hello world