读《数据结构与算法 JavaScript描述》——实现一个链表结构

[lizhongzhen11]

什么是链表？

  可以看：https://www.zhihu.com/topic/19649942/intro

  链表（Linked list）是一种常见的基础数据结构，是一种线性表，是一种物理存储单元上非连续、非顺序的存储结构。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括存储数据元素的数据域和存储下一个结点地址的指针域两个部分。 相比于线性表顺序结构，操作复杂。数据元素的逻辑顺序也是通过链表中的指针链接次序实现的。

  链表分为：单（向）链表、循环链表、双向链表。虽然有三种不同的链表，但是其中心思想（存储的逻辑结构）是一样的。

从网上盗三张图来分别展示下

单向链表：

双向链表：

循环链表：

如何实现？

以单向链表为例：

1. 每个节点要有两个属性data和next，data存放数据，next指向下一个节点；
2. 最后一个节点指向null
3. 需要有一个头结点

如此，我可以先实现一个节点类：

function Node (ele)  {
  this.data = ele;
  this.next = null;
}

如何将节点连接起来构成链表呢？
这时候我需要有一个类，用于维护链表的插入、删除等方法。当然，需要先给它一个头节点。

function LinkedList () {
  this.head = new Node('head');
}

头节点有了，接下来如何去插入新节点使其连接呢？
这时候的头节点的next指向的是null，我需要在插入方法中去改变next指向。
我肯定是要插入Node节点对象的，同时头节点的next要指向这个新节点，那么初步实现下：

LinkedList.prototype.insert = function (ele) {
  this.head.next = new Node(ele)
}

但是，问题来了！
我这个insert里面只改变了头节点next指向，如果我想插入第二个甚至更多节点，目前的方法根本不满足！！！所以，我需要记住每个插入的节点。
并且，链表是可以不按顺序插入的，那我必须得知道新节点要插到哪个位置（哪个节点后面），所以我必须找到该节点。
那么插入新节点时，不仅要将新节点数据传入，同时也要将需要插入新节点的前一个节点数据传入才行。

改写下insert：

LinkedList.prototype.insert = function (ele, prev) {
  var curr = this.head
  while (curr.next && curr.data !== prev) {
    curr = curr.next
  }
  if (curr.data !== prev) {
    throw new Error('请在已有节点后插入')
  }
  var newNode = new Node(ele)
  newNode.next = curr.next
  curr.next = newNode
}

// 测试下
var l = new LinkedList()
l // LinkedList{head: {data: 'head', next: null}}
l.insert(1, 1) // Error
l.insert('first', 'head')

接下来，需要实现删除操作。删除的话需要知道被删除节点的前后节点才行，那么首先需要去找前一个节点，附上代码：

LinkedList.prototype.remove = function (item) {
  var curr = this.head
  while (curr.next && curr.next.data !== item) {
    curr = curr.next
  }
  if (!curr.next && curr.data !== item) {
    throw new Error('请删除已有节点')
  }
  var removeNode = curr.next
  curr.next = removeNode.next 
}

// 测试下
var l = new LinkedList()
l // LinkedList{head: {data: 'head', next: null}}
l.insert('first', 'head')
l.remove('first')
l.remove('first') // Error

基本上单向链表算是实现了，最终代码：

function Node (ele)  {
  this.data = ele;
  this.next = null;
}

function LinkedList () {
  this.head = new Node('head');
}

LinkedList.prototype.insert = function (ele, prev) {
  var curr = this.head
  while (curr.next && curr.data !== prev) {
    curr = curr.next
  }
  if (curr.data !== prev) {
    throw new Error('请在已有节点后插入')
  }
  var newNode = new Node(ele)
  newNode.next = curr.next
  curr.next = newNode
}

LinkedList.prototype.remove = function (item) {
  var curr = this.head
  while (curr.next && curr.next.data !== item) {
    curr = curr.next
  }
  if (!curr.next && curr.data !== item) {
    throw new Error('请删除已有节点')
  }
  var removeNode = curr.next
  curr.next = removeNode.next 
}

双向链表其实就是在单向链表基础上加一个指向前节点的链接，直接放书上的代码吧：

function Node (element) {
  this.element = element
  this.next = null
  this.previous = null
}

function LList () {
  this.head = new Node('head')
  this.find = find
  this.insert = insert
  this.display = dispay
  this.remove = remove
  this.findLast = findLast
  this.dispReverse = dispReverse
}

function dispReverse () {
  var cuuNode = this.head
  currNode = this.findLast()
  while (!(currNode.previous === null)) {
    currNode = currNode.previous
  }
}

function findLast () {
  var currNode = this.head
  while (!(currNode.next === null)) {
    currNode = currNode.next
  }
  return currNode
}

function remove () {
  var currNode = this.head
  if (!(currNode.next === null)) {
    currNode.previous.next = currNode.next
    currNode.next.previous = currNode.previous
    currNode.next = null
    currNode.previous = null
  }
}

function display () {
  var currNode = this.head
  while (!(currNode.next === null)) {
    currNode = currNode.next
  }
}

function find (item) {
  var currNode = this.head
  while (currNode.element !== item) {
    currNode = currNode.next
  }
  return currNode
}

function insert (newElement, item) {
  var newNode = new Node(newElement)
  var current = this.find(item)
  newNode.next = current.next
  newNode.previous = current
  current.next = newNode
}

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

head.next = head

这种行为会传导至链表的每个节点，使得每个节点的next属性都指向链表的头节点。换句话说，链表的尾节点指向头节点，形成一个循环链表。

参考

https://zhuanlan.zhihu.com/p/29627391
http://c.biancheng.net/view/3336.html