【前端数据结构基础】链表

摘要：前言数组是我们非常熟悉且常用的一种数据结构。但我们发现，数组不总是组织数据的最佳数据结构。参考资料数据结构与算法描述第章链表由于书上的源代码出现了错误，因此代码根据实际运行结果做了相应修改。

数组是我们非常熟悉且常用的一种数据结构。但我们发现，数组不总是组织数据的最佳数据结构。因为在很多编程语言中，数组的长度是固定的，所以当数组已经被数据填满时，再加入新的元素就会非常困难。同时，在数组中添加或删除元素也很麻烦，因为需要将数组中的其他元素向前或向后平移，以反映数组进行了添加或删除的操作。
虽然说在JavaScript中的数组不存在上述问题，我们使用splice()方法不需要再访问数组中的其他元素。但是在JavaScript中，数组被实现成了对象，因此与其他语言中的数组相比，效率很低。
在很多情况下，当我们发现数组在实际使用时很慢，就可以考虑使用链表来代替它。除了对数据的随机访问，链表几乎可以用在任何可以使用一维数组的情况中。如果需要随机访问，数组仍然是最好的选择。

链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一个节点的引用叫做链。如下图所示

数组元素依靠它们的位置进行引用，而链表元素依靠相互关系进行引用。如我们可以说Item2在Item1后面，而不能说Item2是链表中的第二个元素。
我们所说的遍历链表，就是跟着链接，从链表的首元素一直走到尾元素（不包括链表的头节点）。
我们可以发现，链表的尾元素指向一个null节点。

要标识出链表的起始节点有些麻烦，因此我们经常会在链表最前面有一个特殊节点，叫做头节点。

链表中插入一个节点的效率很高，我们只需要修改其前面的节点，使其指向新加入的节点，同时将新加入的节点指向原来前驱指向的节点即可。

链表中删除一个节点也非常容易。将待删元素的前驱节点指向待删元素的后继节点，再讲待删元素指向null即可。

我们将用JavaScript构造一个基于对象的链表结构，各部分功能使用注释说明。

/**
 * Node类 表示节点，我们使用构造函数来创建节点
 * element 用来保存节点上的数据
 * next 用来保存指向下一个节点的链接
 * @param {*} element
 */
function Node (element) {
  this.element = element
  this.next = null
}

/**
 * LList类 提供对链表操作的方法
 * find 用于查找元素
 * insert 用于插入新节点
 * display 用于遍历显示链表结构
 * findPrev 用于遍历查找待删除数据的前一个节点
 * remove 用于删除节点
 */
function LList () {
  this.head = new Node("head")
  this.find = find
  this.insert = insert
  this.display = display
  this.findPrev = findPrev
  this.remove = remove
}

/**
 * find() 方法用于通过遍历链表，查找给定数据
 * 返回保存该数据的节点
 * @param {*} item
 */
function find (item) {
  // 初始化当前位置为链表头部
  let currNode = this.head
  // 循环遍历寻找当前位置并返回
  while ((currNode != null) && (currNode.element != null) && (currNode.next != null)) {
    currNode = currNode.next
  }
  return currNode
}

/**
 * insert() 方法用于插入新节点
 * @param {*} newEle
 * @param {*} item
 */
function insert (newEle, item) {
  // 创建新节点
  let newNode = new Node(newEle)
  // 查找要插入的节点位置
  let current = this.find(item)
  // 将新节点的后继指向要插入位置的后继
  if (current != null) {
    newNode.next = current.next
    // 将要插入位置的后继指向新节点
    current.next = newNode
  } else {
    // current 为null时
    newNode.next = null
    this.head.next = newNode
  }
}

/**
 * findPrev() 方法用于遍历查找待删除数据的前一个节点
 * @param {*} item
 */
function findPrev (item) {
  // 初始化当前节点为头节点
  let currNode = this.head
  // 当前节点的后继为item时停止遍历并返回，即返回待查找节点的前驱节点
  while (!(currNode.next == null) && (currNode.next.element != item)) {
    currNode = currNode.next
  }
  return currNode
}

/**
 * remove() 方法用于删除一个节点
 * @param {*} item
 */
function remove (item) {
  // 找到item数据节点的前驱节点
  let prevNode = this.findPrev(item)
  if (!(prevNode.next == null)) {
    // 将前驱节点的后继节点赋值为其后继节点的后继节点，即跳过了待删节点
    prevNode.next = prevNode.next.next
  }
}

/**
 * display() 方法用于遍历链表
 */
function display () {
  // 初始化当前节点为头节点
  let currNode = this.head
  while (!(currNode.next == null)) {
    // 遍历输出节点，并指向下一节点
    console.log(currNode.next.element)
    currNode = currNode.next
  }
}

// 测试代码
let students = new LList()
students.insert("Miyang", "head")
students.insert("Tom", "Miyang")
students.insert("Jerry", "Tom")
students.remove("Tom")
students.display()

// 输出结果
Miyang
Tom
Jerry

关于双向链表的实现，我们只需要在单向链表的基础上，增加一个指向前驱节点的链接。
实现代码如下：

/**
 * Node类 表示节点，我们使用构造函数来创建节点
 * element 用来保存节点上的数据
 * next 用来保存指向下一个节点的链接
 * @param {*} element
 */
function Node (element) {
  this.element = element
  this.next = null
  this.previous = null
}

/**
 * LList类 提供对链表操作的方法
 * find 用于查找元素
 * insert 用于插入新节点
 * display 用于遍历显示链表结构
 * findPrev 用于遍历查找待删除数据的前一个节点
 * remove 用于删除节点
 */
function LList () {
  this.head = new Node("head")
  this.find = find
  this.insert = insert
  this.display = display
  this.findPrev = findPrev
  this.remove = remove
  this.findLast = findLast
  this.dispReverse = dispReverse
}

/**
 * find() 方法用于通过遍历链表，查找给定数据
 * 返回保存该数据的节点
 * @param {*} item
 */
function find (item) {
  // 初始化当前位置为链表头部
  let currNode = this.head
  // 循环遍历寻找当前位置并返回
  while ((currNode != null) && (currNode.element != null) && (currNode.next != null)) {
    currNode = currNode.next
  }
  return currNode
}

/**
 * insert() 方法用于插入新节点
 * @param {*} newEle
 * @param {*} item
 */
function insert (newEle, item) {
  // 创建新节点
  let newNode = new Node(newEle)
  // 查找要插入的节点位置
  let current = this.find(item)
  // 将新节点的后继指向要插入位置的后继
  if (current != null) {
    newNode.next = current.next
    newNode.previous = current
    // 将要插入位置的后继指向新节点
    current.next = newNode
  } else {
    // current 为null时
    newNode.next = null
    newNode.previous = null
    this.head.next = newNode
  }
}

/**
 * findPrev() 方法用于遍历查找待删除数据的前一个节点
 * @param {*} item
 */
function findPrev (item) {
  // 初始化当前节点为头节点
  let currNode = this.head
  // 当前节点的后继为item时停止遍历并返回，即返回待查找节点的前驱节点
  while (!(currNode.next == null) && (currNode.next.element != item)) {
    currNode = currNode.next
  }
  return currNode
}

/**
 * remove() 方法用于删除一个节点
 * @param {*} item
 */
function remove (item) {
  // 找到item数据节点的前驱节点
  let currNode = this.find(item)
  if (!(currNode.next == null)) {
    currNode.previous.next = currNode.next
    currNode.next.previous = currNode.previous
    currNode.next = null
    currNode.previous = null
  }
}

/**
 * display() 方法用于遍历链表
 */
function display () {
  // 初始化当前节点为头节点
  let currNode = this.head
  while (!(currNode.next == null)) {
    // 遍历输出节点，并指向下一节点
    console.log(currNode.next.element)
    currNode = currNode.next
  }
}

/**
 * findLast() 方法用于找到链表中最后一个节点
 */
function findLast () {
  let currNode = this.head
  while (!(currNode.next == null)) {
    currNode = currNode.next
  }
  return currNode
}

/**
 * dispReverse() 方法用于反向遍历链表
 */
function dispReverse () {
  let currNode = this.head
  currNode = this.findLast()
  while (!(currNode.previous == null)) {
    console.log(currNode.element)
    currNode = currNode.previous
  }
}

// 测试代码
let students = new LList()
students.insert("Miyang", "head")
students.insert("Tom", "Miyang")
students.insert("Jerry", "Tom")
students.remove("Tom")
students.display()
console.log()
students.dispReverse()

// 输出结果
Miyang
Tom
Jerry

Jerry
Tom
Miyang

循环链表和单向链表相似，唯一的区别是，在创建循环链表时，让其头节点的next属性指向它本身，即：

head.next = head

修改LList类的构造函数：

function LList () {
  this.head = new Node("head")
  this.head.next = this.head
  this.find = find
  this.insert = insert
  this.display = display
  this.findPrev = findPrev
  this.remove = remove
  this.findLast = findLast
  this.dispReverse = dispReverse
}

同时，其他地方也需要修改，如display()方法，否则会造成死循环

function display () {
  // 初始化当前节点为头节点
  let currNode = this.head
  while (!(currNode.next == null) && !(currNode.next.element == "head")) {
    // 遍历输出节点，并指向下一节点
    console.log(currNode.next.element)
    currNode = currNode.next
  }
}

同样的，其他方法也需要做类似修改，在此就不一一举例了。

上面对JavaScript实现链表做了基本介绍，大家也可以尝试去定义一些其他方法，如在链表中向前移动n个节点advance(n)、在双向链表中向后移动n个节点back(n)等。

参考资料：数据结构与算法JavaScript描述 第6章 链表
由于书上的源代码出现了错误，因此代码根据实际运行结果做了相应修改。