数据结构之双向链表（二）-一一网

这是我参与更文挑战的第18天，活动详情查看：更文挑战

从任意位置移除元素

接下来，我们来实现removeAt方法

function DoublyLinkedList () {
    let Node = function (element) {
        this.element = element
        this.next = null
        this.prev = null
    }
    // 列表头部
    let head = null
    let length = 0
    // 列表尾部
    let tail = null
    
    // 首先我们知道removeAt方法接收一个参数position即要移除的元素的位置
    this.removeAt = function (position) {
        // 按照惯例，检查越界
        if(position > -1 && position < length) {
            let current = head
            let previous = null
            let index = 0
            // 移除第一项
            if (position === 0) {
                head = current.next
                // 如果只有一项，则更新tail
                if (length === 1) {
                    tail = null
                } eles {
                    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与current的下一项连接一起来 跳过current
                previous.next = current.next
                current.next.prev = previous
            }
            length--
            return current.element
        } else {
            return null
        }
    }
}
复制代码

上述代码中：

我们首先判断了边界值，如果越界直接返回null，表示没有移除任何元素。
没有越界的话，就是我们要处理的情况，首先定义current变量其初始值为head，然后定义previous初始值为null，定义index初始值为0
移除第一项即position为0时：因为current初始化值为head，所以current.next为第二项，那么移除第一项就是将列表头部的head元素的值设置为第二个元素，即head = current.next。而双向链表还需要处理prev的指向，此时，如果列表只有一个元素，那么列表的尾部元素tail为null，否则需要将head.prev设为null
移除最后一项即position值为length-1时：因为tail是对最后一个元素的引用，那么将tail赋值给current即我们要移除的元素，同时将tail指向列表的倒数第二项即此时的current.prev，并且将tail.next设为null
移除列表中间的元素就需要迭代列表，直到找到元素所在的位置。current的变量所引用的就是要移除的元素，在循环体内更新迭代previous和current的值，找到位置之后，将previous.next指向current.next，将current.next.prev指向previous
移除完元素之后将列表的长度length属性进行更新
返回移除的元素current.elemnt