CcbeanBlog
ccbean
2021-12-18
目录

数据结构与算法-双向链表

# 数据结构与算法-双向链表

# 认识双向链表

单向链表的一些限制：

  • 只能从头遍历到尾或者从尾遍历到头（一般从头到尾）。
  • 链表相连的过程是单向的，实现原理是上一个节点中有指向下一个节点的引用。
  • 单向链表有一个比较明显的缺点：可以轻松到达下一个节点，但回到前一个节点很难，在实际开发中, 经常会遇到需要回到上一个节点的情况。

假设一个文本编辑用链表来存储文本。每一行用一个String对象存储在链表的一个节点中。当编辑器用户向下移动光标时，链表直接操作到下一个节点即可。但是当用于将光标向上移动呢？这个时候为了回到上一个节点，我们可能需要从first开始，依次走到想要的节点上。

双向链表：

  • 既可以从头遍历到尾，也可以从尾遍历到头。
  • 链表相连的过程是双向的。实现原理是一个节点既有向前连接的引用，也有一个向后连接的引用。
  • 双向链表可以有效的解决单向链表存在的问题。
  • 双向链表缺点：
    • 每次在插入或删除某个节点时，都需要处理四个引用，而不是两个，实现起来会困难些。
    • 相对于单向链表，所占内存空间更大一些。
    • 但是，相对于双向链表的便利性而言，这些缺点微不足道。

# 双向链表

双向链表如下图所示：

双向链表01

  • 双向链表不仅有 head 指针指向第一个节点，而且有 tail 指针指向最后一个节点。
  • 每一个节点由三部分组成：item 储存数据、prev 指向前一个节点、next 指向后一个节点。
  • 双向链表的第一个节点的 prev 指向 null。
  • 双向链表的最后一个节点的 next 指向 null。

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

# 常见操作

  • append(element) 向链表尾部追加一个新元素。
  • insert(position, element) 向链表的指定位置插入一个新元素。
  • get(position) 获取指定位置的元素。
  • indexOf(element) 返回元素在链表中的索引。如果链表中没有该元素就返回 -1。
  • update(position, element) 修改指定位置上的元素。
  • removeAt(position) 从链表中的删除指定位置的元素。
  • remove(element) 从链表删除指定的元素。
  • isEmpty() 如果链表中不包含任何元素，返回 trun，如果链表长度大于 0 则返回 false。
  • size() 返回链表包含的元素个数，与数组的 length 属性类似。
  • toString() 由于链表项使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString 方法，让其只输出元素的值。
  • forwardString() 返回正向遍历节点字符串形式。
  • backwordString() 返回反向遍历的节点的字符串形式。

# 封装

创建一个双向链表类，和链表中的节点类。

// 链表节点
class Node {
  constructor (element) {
    this.data = element
    this.next = null
    this.prev = null
  }
}

class DoublyLinkedList {
  constructor () {
    // head指向链表的第一个节点 初始为null
    this.head = null
    // tail指向链表的最后一个节点 初始为null
    this.tail = null
    // 初始链表的长度
    this.length = 0
  }
}

接下来向DoublyLinkedList中扩展相关操作方法

# append

// 向链表尾部追加一个新元素
append (element) {
  const newNode = new Node(element)

  if (this.length === 0) {
    this.head = newNode
    this.tail = newNode
  } else {
    // tail直接获取到原尾部节点
    this.tail.next = newNode
    newNode.prev = this.tail
    this.tail = newNode
  }
	// 链表长度加1
  this.length++
}

分析：

  1. 首先通过元素创建新的节点
  2. 判断链表，链表本身为空，那么直接让head和tail指向这个新的节点即可
    1. 链表不为空，将数据默认追加到尾部。首先tail中的next之前指向的是null， 现在应该指向新的节点newNode，this.tail.next = newNode
    2. 因为是双向链表，newNode的next/tail目前都是null。但是作为最后一个节点，需要有一个指向前一个节点的引用，this.tail这时是前一个节点，所以newNode.prev = this.tail
    3. 因为目前newNod已经变成了最后的节点, 所以this.tail属性的引用应该指向最后: this.tail = newNode即可
    4. 链表长度加1

# insert

向链表指定位置插入一个元素

// 向链表中插入节点
insert (position, element) {
  // 越界处理
  if (position < 0 || position > this.length) return false

  const newNode = new Node(element)

  if (position === 0) {
    // 首位插入
    if (this.head === null) {
      this.head = newNode
      this.tail = newNode
    } else {
      this.head.prev = newNode
      newNode.next = this.head
      this.head = newNode
    }
  } else if (position === this.length) {
    // 尾部插入
    this.tail.next = newNode
    newNode.prev = this.tail
    this.tail = newNode
  } else {
    // 中间插入
    let currentNode = this.head
    let previousNode = null
    let index = 0

    while (position > index++) {
      previousNode = currentNode // 原position -1位置节点
      currentNode = currentNode.next // 原position位置节点
    }

    // 改变节点的指向
    newNode.next = currentNode
    newNode.prev = previousNode
    previousNode.next = newNode
    currentNode.prev = newNode
  }

  // 链表长度加1
  this.length++
  return true
}

分析：

  1. 越界处理

  2. position === 0元素在头部插入，分两种情况：

    1. 链表为空，那么直接让head/tail指向newNode即可

    2. 链表不为空，这时需要修改原来head的prev指向新节点；新节点的next指向原来的head；并且head现在要指向newNode

      双向链表02

  3. position === length元素在尾部插入，和append()处理逻辑相同，不过这里不需要处理position为0的情况，已经处理过了。

    双向链表03

  4. 元素在中间插入，通过while循环找到正确的插入位置。

    1. newNode的next/prev必然要指向前后的节点，分别指向previousNode和currentNode

    2. 而currentNode.prev需要指向newNode，而previousNode.next需要指向newNode

      双向链表04

如果我们position大于length/2，从尾部开始迭代性能更高一些。所以可以再对上面代码进行优化。下面的方法也是如此，可以优化。

# removeAt

// 从链表中的删除指定位置的元素
removeAt (position) {
  if (position < 0 || position >= this.length) return null

  let currentNode = this.head

  if (position === 0) {
    // 移除首位
    if (this.length === 1) {
      this.head = null
      this.tail = null
    } else {
      this.head = this.head.next
      this.head.prev = null
    }
  } else if (position === this.length - 1) {
    // 移除末尾
    currentNode = this.tail
    this.tail = this.tail.prev
    this.tail.next = null
  } else {
    // 移除中间
    let previousNode = null
    let index = 0
    while (position > index++) {
      previousNode = currentNode
      currentNode = currentNode.next
    }

    // 改变节点指向
    previousNode.next = currentNode.next
    currentNode.next.prev = previousNode
  }

  this.length--

  return currentNode.element
}

分析：

  1. 越界处理。

  2. 删除头部元素，分两种情况：

    1. 链表中只有一个元素，那么将head/tail直接设置为null即可

    2. 链表有多个元素，这个时候删除头部的元素，将头部元素指向第二个元素，第二个元素的prev指向null

      双向链表05

  3. 删除尾部元素，将tail设置为倒数第二个元素，倒数第二个元素的next设置成null即可。

    双向链表06

  4. 删除中间元素，while循环找到正确位置的元素，将previousNode.next直接设置成currentNode.next，将currentNode.next.prev设置成previousNode即可。

    双向链表07

其它方法实现，大都同单向链表或是比较简单，不再分析。

# 完整实现

// 链表节点
class Node {
  constructor (data) {
    this.element = data
    this.next = null
    this.prev = null
  }
}

module.exports = class DoublyLinkedList {
  constructor () {
    // head指向链表的第一个节点 初始为null
    this.head = null
    // tail指向链表的最后一个节点 初始为null
    this.tail = null
    // 初始链表的长度
    this.length = 0
  }

  // 向链表尾部追加一个新元素
  append (element) {
    const newNode = new Node(element)

    if (this.length === 0) {
      this.head = newNode
      this.tail = newNode
    } else {
      // tail直接获取到原尾部节点
      this.tail.next = newNode
      newNode.prev = this.tail
      this.tail = newNode
    }
    // 链表长度加1
    this.length++
  }

  // 向链表中插入节点
  insert (position, element) {
    // 越界处理
    if (position < 0 || position > this.length) return false

    const newNode = new Node(element)

    if (position === 0) {
      // 首位插入
      if (this.head === null) {
        this.head = newNode
        this.tail = newNode
      } else {
        this.head.prev = newNode
        newNode.next = this.head
        this.head = newNode
      }
    } else if (position === this.length) {
      // 尾部插入
      this.tail.next = newNode
      newNode.prev = this.tail
      this.tail = newNode
    } else {
      // 中间插入
      let currentNode = this.head
      let previousNode = null
      let index = 0

      while (position > index++) {
        previousNode = currentNode // 原position -1位置节点
        currentNode = currentNode.next // 原position位置节点
      }

      // 改变节点的指向
      newNode.next = currentNode
      newNode.prev = previousNode
      previousNode.next = newNode
      currentNode.prev = newNode
    }

    // 链表长度加1
    this.length++
    return true
  }

  // 从链表中的删除指定位置的元素
  removeAt (position) {
    if (position < 0 || position >= this.length) return null

    let currentNode = this.head

    if (position === 0) {
      // 移除首位
      if (this.length === 1) {
        this.head = null
        this.tail = null
      } else {
        this.head = this.head.next
        this.head.prev = null
      }
    } else if (position === this.length - 1) {
      // 移除末尾
      currentNode = this.tail
      this.tail = this.tail.prev
      this.tail.next = null
    } else {
      // 移除中间
      let previousNode = null
      let index = 0
      while (position > index++) {
        previousNode = currentNode
        currentNode = currentNode.next
      }

      // 改变节点指向
      previousNode.next = currentNode.next
      currentNode.next.prev = previousNode
    }

    this.length--

    return currentNode.element
  }

  // 返回元素在链表中的索引。如果链表中没有该元素就返回 -1。
  indexOf (element) {
    let currentNode = this.head
    let index = 0
    while (currentNode) {
      if (currentNode.element === element) {
        // 返回匹配索引
        return index
      }

      currentNode = currentNode.next
      index++
    }

    // 未找到
    return -1
  }

  // 移除指定元素
  remove (element) {
    return this.removeAt(this.indexOf(element))
  }

  // 获取指定位置元素
  get (position) {
    // 越界处理
    if (position < 0 || position >= this.length) return null

    let currentNode = this.head
    let index = 0
    while (position > index++) {
      currentNode = currentNode.next
    }

    return currentNode.element
  }

  // 更新节点 并返回更新后的节点
  update (position, element) {
    // 越界处理
    if (position < 0 || position >= this.length) return false

    let currentNode = this.head

    let index = 0
    while (position > index++) {
      currentNode = currentNode.next
    }
    // 更新position位置的element
    currentNode.element = element

    return currentNode
  }

  // 判断链表是否为空
  isEmpty () {
    return this.length === 0
  }

  size () {
    return this.length
  }

  getHead () {
    return this.head
  }

  getTail () {
    return this.tail
  }

  forwardString () {
    let currentNode = this.head

    let res = ''
    while (currentNode) {
      res += `${currentNode.element} `
      currentNode = currentNode.next
    }

    return res
  }

  reverseString () {
    let currentNode = this.tail

    let res = ''
    while (currentNode) {
      res += `${currentNode.element} `
      currentNode = currentNode.prev
    }

    return res
  }
}

测试：

const DoublyLinkedList = require('../../lib/DoublyLinkedList')

const doublyLinkedList = new DoublyLinkedList()

// append
doublyLinkedList.append('B')
doublyLinkedList.append('C')
doublyLinkedList.append('D')
console.log('doublyLinkedList', doublyLinkedList)

// insert
console.log('insert', doublyLinkedList.insert(0, 'A'))
console.log('insert', doublyLinkedList.insert(4, 'E'))
console.log('insert', doublyLinkedList.insert(3, 'd'))
console.log('insert', doublyLinkedList.insert(-1, '-A'))
console.log('forwardString', doublyLinkedList.forwardString())
console.log('reverseString', doublyLinkedList.reverseString())

// indexOf
console.log('indexOf', doublyLinkedList.indexOf('5'))
console.log('indexOf', doublyLinkedList.indexOf('100'))

// get
console.log('get', doublyLinkedList.get(0))
console.log('get', doublyLinkedList.get(1))

// // 测试 update 方法
console.log('update', doublyLinkedList.update(3, 'D'))
console.log('forwardString', doublyLinkedList.forwardString())

// removeAt
console.log('removeAt', doublyLinkedList.removeAt(0))
console.log('removeAt', doublyLinkedList.removeAt(1))
console.log('removeAt', doublyLinkedList.removeAt(3))
console.log('forwardString', doublyLinkedList.forwardString())

// remove
console.log('remove', doublyLinkedList.remove('D'))

// 测试 isEmpty 方法
console.log('isEmpty', doublyLinkedList.isEmpty())

// 测试 size 方法
console.log('size', doublyLinkedList.size())
编辑 (opens new window)
上次更新: 2021/12/21, 17:36:40
数据结构与算法-链表
数据结构与算法-集合

← 数据结构与算法-集合→

最近更新
01
阅读精通正则表达式总结
09-29
02
项目搭建规范的配置
07-15
03
Vite的使用
07-03
更多文章>
Theme by Vdoing | Copyright © 2018-2023 Ccbeango