一. 认识双向链表

双向链表介绍

  • 单向链表:
    • 只能从头遍历到尾或者从尾遍历到头(一般从头到尾)
    • 也就是链表相连的过程是单向的. 实现的原理是上一个链表中有一个指向下一个的引用.
    • 单向链表有一个比较明显的缺点:
      • 我们可以轻松的到达下一个节点, 但是回到钱一个节点是很难的. 但是, 在实际开发中, 经常会遇到需要回到上一个节点的情况
      • 举个例子: 假设一个文本编辑用链表来存储文本. 每一行用一个String对象存储在链表的一个节点中. 当编辑器用户向下移动光标时, 链表直接操作到下一个节点即可. 但是当用于将光标向上移动呢? 这个时候为了回到上一个节点, 我们可能需要从first开始, 依次走到想要的节点上.
  • 双向链表
    • 既可以从头遍历到尾, 又可以从尾遍历到头
    • 也就是链表相连的过程是双向的. 那么它的实现原理, 你能猜到吗?
    • 一个节点既有向前连接的引用, 也有一个向后连接的引用.
    • 双向链表可以有效的解决单向链表中提到的问题.
    • 双向链表有什么缺点呢?
      • 每次在插入或删除某个节点时, 需要处理四个节点的引用, 而不是两个. 也就是实现起来要困难一些
      • 并且相当于单向链表, 必然占用内存空间更大一些.
      • 但是这些缺点和我们使用起来的方便程度相比, 是微不足道的.

  • 双向连接的图解:
    双向链表 - 图1
    img

    双向链表的创建

  • 我们来创建一个双向链表的类

    1. // 创建双向链表的构造函数
    2. function DoublyLinkedList() {
    3.   // 创建节点构造函数
    4.   function Node(element) {
    5.       this.element = element
    6.       this.next = null
    7.       this.prev = null // 新添加的
    8.   }
    9.   // 定义属性
    10.   this.length = 0
    11.   this.head = null
    12.   this.tail = null // 新添加的
    13.   // 定义相关操作方法
    14. }

  • 代码解析:

    • 基本思路和单向链表比较相似, 都是创建节点结构函数以及定义一些属性和方法.
    • 只是Node中添加了一个this.prev属性, 该属性用于指向上一个节点.
    • 另外属性中添加了一个this.tail属性, 该属性指向末尾的节点

      二. 操作双向链表

      双向链表的操作和单向链表的方法都是类似的. 只是在实现的过程中, 需要考虑更多节点之间的关系, 所以变得比单向链表复杂了一些.

尾部追加数据

  • 我们还是先来实现尾部追加数据的方法

    1. // 在尾部追加数据
    2. DoublyLinkedList.prototype.append = function (element) {
    3.   // 1.根据元素创建节点
    4.   var newNode = new Node(element)
    5.   // 2.判断列表是否为空列表
    6.   if (this.head == null) {
    7.       this.head = newNode
    8.       this.tail = newNode
    9.   } else {
    10.       this.tail.next = newNode
    11.       newNode.prev = this.tail
    12.       this.tail = newNode
    13.   }
    15.   // 3.length+1
    16.   this.length++
    17. }

  • 代码解析:

    • 代码1部分不用多讲, 还是通过元素创建新的节点.
    • 代码2部分相比之前有一些复杂, 但是还是两种情况.
    • 情况一: 链表原来为空
      • 链表中原来如果没有数据, 那么直接让head和tail指向这个新的节点即可.
    • 情况二: 链表中已经存在数据
      • 因为我们是要将数据默认追加到尾部, 所以这个变得也很简单.
      • 首先tail中的next之前指向的是null. 现在应该指向新的节点newNode: this.tail.next = newNode
      • 因为是双向链表, 新节点的next/tail目前都是null. 但是作为最后一个节点, 需要有一个指向前一个节点的引用. 所以这里我们需要newNode.prev = this.tail
      • 因为目前newNod已经变成了最后的节点, 所以this.tail属性的引用应该指向最后: this.tail = newNode即可
    • 代码3部分不用多做解析, length需要+1

      正向反向遍历

  • 链表的遍历

    • 之前我们在单向链表中实现了一个toString方法, 它是一种正向的遍历.
    • 现在, 为了用户使用方便, 我们实现三个方法
      • forwardString: 正向遍历转成字符串的方法
      • reverseString: 反向遍历转成字符串的方法
      • toString: 正向遍历转成字符串的方法

  • 方法的相关实现:

    1. // 正向遍历的方法
    2. DoublyLinkedList.prototype.forwardString = function () {
    3.   var current = this.head
    4.   var forwardStr = ""
    6.   while (current) {
    7.       forwardStr += "," + current.element
    8.       current = current.next
    9.   }
    11.   return forwardStr.slice(1)
    12. }
    13. // 反向遍历的方法
    14. DoublyLinkedList.prototype.reverseString = function () {
    15.   var current = this.tail
    16.   var reverseStr = ""
    18.   while (current) {
    19.       reverseStr += "," + current.element
    20.       current = current.prev
    21.   }
    23.   return reverseStr.slice(1)
    24. }
    25. // 实现toString方法
    26. DoublyLinkedList.prototype.toString = function () {
    27.   return this.forwardString()
    28. }

  • 完成上面的代码后, 测试append方法

    1. // 1.创建双向链表对象
    2. var list = new DoublyLinkedList()
    3. // 2.追加元素
    4. list.append("abc")
    5. list.append("cba")
    6. list.append("nba")
    7. list.append("mba")
    8. // 3.获取所有的遍历结果
    9. alert(list.forwardString()) // abc,cba,nba,mba
    10. alert(list.reverseString()) // mba,nba,cba,abc
    11. alert(list) // abc,cba,nba,mba

    任意位置插入

  • 向双向链表的任意位置插入数据会有一些复杂, 考虑的情况也会有一些多.

    1. // 在任意位置插入数据
    2. DoublyLinkedList.prototype.insert = function (position, element) {
    3.   // 1.判断越界的问题
    4.   if (position < 0 || position > this.length) return false
    5.   // 2.创建新的节点
    6.   var newNode = new Node(element)
    7.   // 3.判断插入的位置
    8.   if (position === 0) { // 在第一个位置插入数据
    9.       // 判断链表是否为空
    10.       if (this.head == null) {
    11.           this.head = newNode
    12.           this.tail = newNode
    13.       } else {
    14.           this.head.prev = newNode
    15.           newNode.next = this.head
    16.           this.head = newNode
    17.       }
    18.   } else if (position === this.length) { // 插入到最后的情况
    19.       // 思考: 这种情况是否需要判断链表为空的情况呢? 答案是不需要, 为什么?
    20.       this.tail.next = newNode
    21.       newNode.prev = this.tail
    22.       this.tail = newNode
    23.   } else { // 在中间位置插入数据
    24.       // 定义属性
    25.       var index = 0
    26.       var current = this.head
    27.       var previous = null
    29.       // 查找正确的位置
    30.       while (index++ < position) {
    31.           previous = current
    32.           current = current.next
    33.       }
    35.       // 交换节点的指向顺序
    36.       newNode.next = current
    37.       newNode.prev = previous
    38.       current.prev = newNode
    39.       previous.next = newNode
    40.   }
    42.   // 4.length+1
    43.   this.length++
    45.   return true
    46. }

  • 代码深度解析, 代码比较复杂, 我们分成三种情况:

    • 情况一: 将元素插入到头部(position === 0)
      • 事实上, 将元素插入到头部是比较简单. 只是它有分成了两种情况.
      • 情况一: 列表为空. 那么直接让head/tail指向newNode即可
      • 情况二: 列表不为空, 这个时候需要修改原来head的prev指向新节点. 新节点的next指向原来的head. 并且head现在要指向newNode
    • 双向链表 - 图2
      img
    • 情况二: 将元素插入到尾部(position === length)
      • 这种情况比较简答了, 因为我们在append方法中已经处理过了.
      • 注意: 这里不需要判断元素为空的情况, 因为在position === 0的时候, 我们已经处理过了. 所以到这里的时候, 肯定不为空.
    • 双向链表 - 图3
      img
    • 情况三: 将元素插入到中间位置
      • 情况三是比较复杂一些的, 但是我们理清楚它的逻辑关系也就比较简单了.
      • 首先, 我们需要找到正确的插入位置. 通过while循环, 这个并不难, 因为我们在单向链表的时候已经找过了.
      • 查找正确的位置后, 需要进行插入操作.
      • 首先, 你的newNode的next/prev必然要指向前后的节点, 也就是current和previous
      • 其次, 而current的prev需要指向newNode, 而previous的next需要指向newNode.
      • 逻辑搞定, 并没有想象中的复杂, 详细看图解.
    • 双向链表 - 图4
      img

  • 测试一下该方法

    1. // 4.insert方法测试
    2. list.insert(0, "100")
    3. list.insert(2, "200")
    4. list.insert(6, "300")
    5. alert(list) // 100,abc,200,cba,nba,mba,300

  • 课下思考: 代码性能能否改进一点呢?

    • 如果我们position大于length/2, 是否从尾部开始迭代性能更高一些呢?
    • 对于初学者来说, 可以作为思考. 但是先搞定上面的内容吧.

      位置移除数据

  • 我们继续来做下一个功能: 通过下标值删除某个元素

    1. // 根据位置删除对应的元素
    2. DoublyLinkedList.prototype.removeAt = function (position) {
    3.   // 1.判断越界的问题
    4.   if (position < 0 || position >= this.length) return null
    5.   // 2.判断移除的位置
    6.   var current = this.head
    7.   if (position === 0) {
    8.       if (this.length == 1) {
    9.           this.head = null
    10.           this.tail = null
    11.       } else {
    12.           this.head = this.head.next
    13.           this.head.prev = null
    14.       }
    15.   } else if (position === this.length -1) {
    16.       current = this.tail
    17.       this.tail = this.tail.prev
    18.       this.tail.next = null
    19.   } else {
    20.       var index = 0
    21.       var previous = null
    22.       while (index++ < position) {
    23.           previous = current
    24.           current = current.next
    25.       }
    26.       previous.next = current.next
    27.       current.next.prev = previous
    28.   }
    29.   // 3.length-1
    30.   this.length--
    31.   return current.element
    32. }

  • 代码深度解析, 和插入一样, 可以分成三种情况:

    • 情况一: 删除头部的元素
      • 删除头部的元素也分成两种情况.
      • 情况一: 链表只有一个元素, 那么将head/tail直接设置为null即可
      • 情况二: 链表有多个元素, 这个时候删除头部的元素. head = head.next. head.prev = null
    • 双向链表 - 图5
      img
    • 情况二: 删除尾部的元素
      • 删除尾部的元素和删除头部有多个元素的情况比较相似. (也不需要考虑个数为1的情况, 因为上一种情况已经考虑了)
      • 将tail设置为tail的prev. tail的next设置为null即可.
    • 双向链表 - 图6
      img
    • 情况三: 删除中间位置的元素
      • 这种情况就需要先找到正确的位置, 还是使用while循环.
      • 将previous的next直接设置成current的next, 将current.next的prev设置成previous即可
    • 双向链表 - 图7
      img

  • 测试removeAt方法

    1. // 5.removeAt方法测试
    2. alert(list.removeAt(0)) // 100
    3. alert(list.removeAt(1)) // 200
    4. alert(list.removeAt(4)) // 300
    5. alert(list) // abc,cba,nba,mba

    获取元素位置

  • 下面完成下一个功能: 根据元素获取再链表中的位置

    1. // 根据元素获取在链表中的位置
    2. DoublyLinkedList.prototype.indexOf = function (element) {
    3.   // 1.定义变量保存信息
    4.   var current = this.head
    5.   var index = 0
    6.   // 2.查找正确的信息
    7.   while (current) {
    8.       if (current.element === element) {
    9.           return index
    10.       }
    11.       index++
    12.       current = current.next
    13.   }
    14.   // 3.来到这个位置, 说明没有找到, 则返回-1
    15.   return -1
    16. }

  • 代码解析:

    • 这个代码的实现和单向链表一样, 不再解释.

  • 代码测试:

    1. // 6.indexOf方法测试
    2. alert(list.indexOf("abc")) // 0
    3. alert(list.indexOf("cba")) // 1
    4. alert(list.indexOf("nba")) // 2
    5. alert(list.indexOf("mba")) // 3

    根据元素删除

  • 有了上面的indexOf方法, 我们可以非常方便实现根据元素来删除信息

    1. // 根据元素删除
    2. DoublyLinkedList.prototype.remove = function (element) {
    3.   var index = this.indexOf(element)
    4.   return this.removeAt(index)
    5. }

  • 代码解析:

    • 和单向链表一样, 不再解释.

  • 测试代码:

    1. // 7.remove方法测试
    2. alert(list.remove("abc")) // abc
    3. alert(list) // cba,nba,mba

    其他方法实现

  • 其他四个方法, 放在一起了

    1. // 判断是否为空
    2. DoublyLinkedList.prototype.isEmpty = function () {
    3.   return this.length === 0
    4. }
    5. // 获取链表长度
    6. DoublyLinkedList.prototype.size = function () {
    7.   return this.length
    8. }
    9. // 获取第一个元素
    10. DoublyLinkedList.prototype.getHead = function () {
    11.   return this.head.element
    12. }
    13. // 获取最后一个元素
    14. DoublyLinkedList.prototype.getTail = function () {
    15.   return this.tail.element
    16. }

  • 代码解析:

    • 比较简单, 不再给出解释了.

  • 代码测试:

    1. // 8.测试最后四个方法
    2. alert(list.getHead())
    3. alert(list.getTail())
    4. alert(list.isEmpty())
    5. alert(list.size())

    三. 完整代码

  • 给出双向链表的完整代码:

    1. // 创建双向链表的构造函数
    2. function DoublyLinkedList() {
    3.   // 创建节点构造函数
    4.   function Node(element) {
    5.       this.element = element
    6.       this.next = null
    7.       this.prev = null // 新添加的
    8.   }
    9.   // 定义属性
    10.   this.length = 0
    11.   this.head = null
    12.   this.tail = null // 新添加的
    13.   // 定义相关操作方法
    14.   // 在尾部追加数据
    15.   DoublyLinkedList.prototype.append = function (element) {
    16.       // 1.根据元素创建节点
    17.       var newNode = new Node(element)
    18.       // 2.判断列表是否为空列表
    19.       if (this.head == null) {
    20.           this.head = newNode
    21.           this.tail = newNode
    22.       } else {
    23.           this.tail.next = newNode
    24.           newNode.prev = this.tail
    25.           this.tail = newNode
    26.       }
    27.       // 3.length+1
    28.       this.length++
    29.   }
    30.   // 在任意位置插入数据
    31.   DoublyLinkedList.prototype.insert = function (position, element) {
    32.       // 1.判断越界的问题
    33.       if (position < 0 || position > this.length) return false
    34.       // 2.创建新的节点
    35.       var newNode = new Node(element)
    36.       // 3.判断插入的位置
    37.       if (position === 0) { // 在第一个位置插入数据
    38.           // 判断链表是否为空
    39.           if (this.head == null) {
    40.               this.head = newNode
    41.               this.tail = newNode
    42.           } else {
    43.               this.head.prev = newNode
    44.               newNode.next = this.head
    45.               this.head = newNode
    46.           }
    47.       } else if (position === this.length) { // 插入到最后的情况
    48.           // 思考: 这种情况是否需要判断链表为空的情况呢? 答案是不需要, 为什么?
    49.           this.tail.next = newNode
    50.           newNode.prev = this.tail
    51.           this.tail = newNode
    52.       } else { // 在中间位置插入数据
    53.           // 定义属性
    54.           var index = 0
    55.           var current = this.head
    56.           var previous = null
    57.           // 查找正确的位置
    58.           while (index++ < position) {
    59.               previous = current
    60.               current = current.next
    61.           }
    62.           // 交换节点的指向顺序
    63.           newNode.next = current
    64.           newNode.prev = previous
    65.           current.prev = newNode
    66.           previous.next = newNode
    67.       }
    68.       // 4.length+1
    69.       this.length++
    70.       return true
    71.   }
    72.   // 根据位置删除对应的元素
    73.   DoublyLinkedList.prototype.removeAt = function (position) {
    74.       // 1.判断越界的问题
    75.       if (position < 0 || position >= this.length) return null
    76.       // 2.判断移除的位置
    77.       var current = this.head
    78.       if (position === 0) {
    79.           if (this.length == 1) {
    80.               this.head = null
    81.               this.tail = null
    82.           } else {
    83.               this.head = this.head.next
    84.               this.head.prev = null
    85.           }
    86.       } else if (position === this.length -1) {
    87.           current = this.tail
    88.           this.tail = this.tail.prev
    89.           this.tail.next = null
    90.       } else {
    91.           var index = 0
    92.           var previous = null
    93.           while (index++ < position) {
    94.               previous = current
    95.               current = current.next
    96.           }
    97.           previous.next = current.next
    98.           current.next.prev = previous
    99.       }
    100.       // 3.length-1
    101.       this.length--
    102.       return current.element
    103.   }
    104.   // 根据元素获取在链表中的位置
    105.   DoublyLinkedList.prototype.indexOf = function (element) {
    106.       // 1.定义变量保存信息
    107.       var current = this.head
    108.       var index = 0
    109.       // 2.查找正确的信息
    110.       while (current) {
    111.           if (current.element === element) {
    112.               return index
    113.           }
    114.           index++
    115.           current = current.next
    116.       }
    117.       // 3.来到这个位置, 说明没有找到, 则返回-1
    118.       return -1
    119.   }
    120.   // 根据元素删除
    121.   DoublyLinkedList.prototype.remove = function (element) {
    122.       var index = this.indexOf(element)
    123.       return this.removeAt(index)
    124.   }
    125.   // 判断是否为空
    126.   DoublyLinkedList.prototype.isEmpty = function () {
    127.       return this.length === 0
    128.   }
    129.   // 获取链表长度
    130.   DoublyLinkedList.prototype.size = function () {
    131.       return this.length
    132.   }
    133.   // 获取第一个元素
    134.   DoublyLinkedList.prototype.getHead = function () {
    135.       return this.head.element
    136.   }
    137.   // 获取最后一个元素
    138.   DoublyLinkedList.prototype.getTail = function () {
    139.       return this.tail.element
    140.   }
    141.   // 遍历方法的实现
    142.   // 正向遍历的方法
    143.   DoublyLinkedList.prototype.forwardString = function () {
    144.       var current = this.head
    145.       var forwardStr = ""
    146.       while (current) {
    147.           forwardStr += "," + current.element
    148.           current = current.next
    149.       }
    150.       return forwardStr.slice(1)
    151.   }
    152.   // 反向遍历的方法
    153.   DoublyLinkedList.prototype.reverseString = function () {
    154.       var current = this.tail
    155.       var reverseStr = ""
    156.       while (current) {
    157.           reverseStr += "," + current.element
    158.           current = current.prev
    159.       }
    160.       return reverseStr.slice(1)
    161.   }
    162.   // 实现toString方法
    163.   DoublyLinkedList.prototype.toString = function () {
    164.       return this.forwardString()
    165.   }
    166. }