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

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

什么是双向链表

双向链表和普通链表的区别在于，在链表中，
一个节点只有链向下一个节点的链接；而在双向链表中，链接是双向的：一个链向下一个元素，
另一个链向前一个元素。如下图所示：

那么接下来我们就开始实现DoublyLinkedList类：

function DoublyLinkedList () {
    let Node = function (element) {
        this.element = element
        this.next = null
        this.prev = null
    }
    // 列表头部
    let head = null
    let length = 0
    // 列表尾部
    let tail = null
}
复制代码

在上述代码中，我们可看出相对于普通链表的实现来说，多了prev和tail。因为双向链表支持反向迭代，所以需要tail用来标识尾部。

在任意位置插入一个新元素

function DoublyLinkedList () {
    let Node = function (element) {
        this.element = element
        this.next = null
        this.prev = null
    }
    // 列表头部
    let head = null
    let length = 0
    // 列表尾部
    let tail = null
    
    this.insert = function (position, element) {
        // 检查越界
        if(position >= 0 && position <= length) {
            let node = new Node(element)
            let current = head
            let previous = null
            let index = 0
            // 在第一个位置添加
            if(position === 0) {
                // head不存在则说明此时是空列表，那么添加到第一位需要将新元素node赋值给head，并且将node赋值给尾部tail
                if(!head) {
                    head = node
                    tail = node
                } else {
                    // head存在则说明此时列表中已有元素，那么添加到第一位就需要将新元素的next属性指向current，并且将current的prev属性指向新元素node，并且将head设为node
                    node.next = current
                    head = node
                    current.prev = node
                }
            } else if(position === length){ 
                // 添加到最后一项
                current = tail
                current.next = node
                node.prev = current
                tail = node
            } else {
                // 循环迭代
                while (index++ < position) {
                    previous = current
                    current = current.next
                }
                // 跳出循环时说明找到了要插入的位置，此时的previous和current就是将要插入的新元素node的前一个元素和后一个元素。
                node.next = current
                node.prev = previous
                
                previous.next = node
                current.prev = node
                
            }
            // 切记插入之后更新列表长度
            length++
            return true
        } else {
            // 插入失败
            return false
        }
    }
}
复制代码