5.双向链表

双向链表优点

• 即可以从头遍历到尾，也可以从尾遍历到头

• 一个节点既有向前连接的引用，也有一个向后连接的引用

双向链表缺点

• 每次插入或删除某个节点时，需要处理四个引用

• 相对于单向链表，所占内存空间更大

5.1双向链表的特点

• 使用一个head指向头部，一个tail指向尾部

• 每个节点都由三部分组成：前一个节点指针（prev）/保存的元素（item）/后一个节点的指针（next）

• 双向链表第一个节点的prev为null，最后的节点next为null

5.2双向链表常见操作

与单向链表相比多了forwardString()和backwardString()操作

• forwardString()：返回正向遍历的节点字符串形式

• backwardString()：返回反向遍历的节点字符串形式

5.3双向链表操作实践

5.3.1链表整体实现预览

function DoublyLinkedList () {
    function Node (data, next) {
       this.prev = null
       this.data = data
     this.next = next
    }
    this.head = null
    this.tail = null
    this.length = 0//记录当前数组的长度
    //append
    DoublyLinkedList.prototype.append = function (element) {}
    DoublyLinkedList.prototype.insert = function (position,element) {}
    DoublyLinkedList.prototype.get = function (position){}
    DoublyLinkedList.prototype.indexOf = function (element){}
    DoublyLinkedList.prototype.update = function (positon,element){}
    DoublyLinkedList.prototype.removeAt = function (position){}
    DoublyLinkedList.prototype.remove = function (element){}
    DoublyLinkedList.prototype.isEmpty = function (){}
    DoublyLinkedList.prototype.size = function (){}
    DoublyLinkedList.prototype.toString = function (){}
    DoublyLinkedList.prototype.forwardString = function (){}
    DoublyLinkedList.prototype.backwardString = function (){}
}
​

5.3.2append（data）方法

向链表尾部追加数据有两种可能

• 链表本身为空，新添加的数据为唯一节点

• 链表不为空，需要向其他节点后追加节点

DoublyLinkedList.prototype.append = function (data) {
        var newNode = new Node(data)
        if (this.length == 0)//第一个节点
        {
            this.head = newNode
            this.tail = newNode
​
        }
        else {
            newNode.prev = this.tail
            this.tail.next = newNode
            this.tail = newNode
        }
        this.length += 1
    }
​

5.3.3forwardString()方法

DoublyLinkedList.prototype.forwardString = function () {
        currentNode = this.head
        let elements = ''
        while (currentNode != null) {
            elements += currentNode.data + ' '
            currentNode = currentNode.next
        }
        return elements
    }

5.3.4toString（）方法

DoublyLinkedList.prototype.toString = function () {
        return this.forwardString()
    }

5.3.5backwardString（）方法

DoublyLinkedList.prototype.backwardString = function () {
        currentNode = this.tail
        let elements = ''
        while (currentNode != null) {
            elements += currentNode.data + ' '
            currentNode = currentNode.prev
        }
        return elements
    }

5.3.6insert(position, data)方法

DoublyLinkedList.prototype.insert = function (position, data) {
        var currentNode = this.head
        var index = 0
        var newNode = new Node(data)
        //越界判断
        if (position < 0 || position > this.length)
            return false
        //当在头部插入元素的情况
        if (position == 0) {
            this.head = newNode
            newNode.next = currentNode
            currentNode.prev = newNode
        }
        //当在尾部插入元素的情况下
        else if (position == this.length) {
            this.tail.next = newNode
            newNode.prev = this.tail
            this.tail = newNode
        }
        else {
            while (currentNode != null) {
                if (index++ == position - 1)
                    break
                else {
                    currentNode = currentNode.next
                }
            }
​
            var q = currentNode.next
            currentNode.next = newNode
            newNode.prev = currentNode
            newNode.next = q
            q.prev = newNode
        }
        this.length += 1
        return true
​
    }

5.3.7get(position)方法

// 方法一：用于数据少时
 DoublyLinkedList.prototype.get = function (position) {
        var currentNode = this.head
        var index = 0
        if (position < 0 || position >= this.length)
            return false
        else {
            while (index++ < position) {
                currentNode = currentNode.next
            }
            return currentNode.data
        }
    }
//方法二：用于数据多时
DoublyLinkedList.prototype.get = function (position) {
        var num = position > (this.length / 2)
        if (position < 0 || position >= this.length)
            return false
        if (!num) {
            var index = 0
            var currentNode = this.head
            while (index++ < position) {
                currentNode = currentNode.next
            }
        }
        else {
            var index = this.length - 1
            var currentNode = this.tail
            while (index-- > position) {
                currentNode = currentNode.prev
            }
        }
        return currentNode.data
    }

5.3.8indexOf(element)方法

DoublyLinkedList.prototype.indexOf = function (element) {
        var currentNode = this.head
        var index = 0
        while (currentNode != null) {
            if (currentNode.data == element)
                return index
            else currentNode = currentNode.next
            index += 1
        }
        return -1
    }

5.3.9update(position,element)方法

DoublyLinkedList.prototype.update = function (position, element) {
        var num = position > (this.length / 2)
        if (position < 0 || position >= this.length) return false
        if (!num) {
            var currentNode = this.head
            var index = 0
            while (index++ < position) {
                currentNode = currentNode.next
            }
        }
        else {
            var currentNode = this.tail
            var index = this.length - 1
            while (index-- > position) {
                currentNode = currentNode.prev
            }
        }
​
        currentNode.data = element
        return true
    }
}

5.3.10removeAt(position)方法

DoublyLinkedList.prototype.removeAt = function (position) {
    var num = position > (this.length / 2)
    if (position < 0 || position >= this.length) return false
    if (this.length == 1) {
        this.head = null
        this.tail = null
    }
    else if (position == 0) {
        this.head.next.prev = null
        this.head = this.head.next
    }
    else if (position == this.length - 1) {
        this.tail = this.tail.prev
        this.tail.next.prev = null
        this.tail.next = null
    }
    else {
        if (!num) {
            var index = 0
            var currentNode = this.head
            while (index++ < position) {
                currentNode = currentNode.next
            }
        }
        else {
            var index = this.length - 1
            var currentNode = this.tail
            while (index-- > position) {
                currentNode = currentNode.prev
            }
        }
        currentNode.prev.next = currentNode.next
        currentNode.next.prev = currentNode.prev
    }
    this.length -= 1
    return true
}

5.3.11remove(element)方法

DoublyLinkedList.prototype.remove = function (element) {
    var index = this.indexOf(element)
    return this.removeAt(index)
​
}

5.3.12size()方法

DoublyLinkedList.prototype.size = function () {
    return this.length
}

5.3.13isEmpty()方法

DoublyLinkedList.prototype.isEmpty = function () {
    if (this.length == 0) return true
    else return false
}