用JavaScript实现基于对象的单项链表

用 JavaScript 实现基于对象的单项链表

单向链表介绍

何为单向链表

与数组的 索引: 值（可以直接在数组层面对值进行修改）不同，链表各个值的关系偏向去中心化。

见上图，每个节点可分为两部分：1. 节点的值；2. 下一个节点的指向，即下一个节点是谁。例如：上图链表中的第一个节点，它的值是 milk，它的下一个节点是 值为 Bread的节点。

单向链表优点

当我们需要组织数据时，数组不总是最佳的数据结构（对于大多数编程语言而言），缘于它有两个显著的缺点：1. 数组的长度是固定的，当数组已被数据填满时，加入新数据会显得很麻烦；2. 当我们插入、或删除数组中的某个值时，需要把数组中的其它值向后、或向前移动，以反映数组被进行了增删操作。

所以当我们需要频繁的对数据进行增删操作时，选择数组不是那么地明智，这时我们可以使用链表来实现对数据的增删功能。链表的增删会方便很多，当增加数据时，只需要更改它的节点指向和上一级节点的节点指向；当删除数据时，只需把待删除节点的节点指向赋给上一级节点即可，此时待删除节点便在链表中消失了（因为无法通过节点与节点的关系再找到它，便可视为消失了）。

例如：如果我们在 milk 和 bread 中增加 sandwich 数据，只需把 milk 的节点指向改为 sandwich，把指向 bread 的节点指向赋给 sandwich 即可；当需要删除 sandwich 时，只需把指向 bread 的节点指向赋给 milk 即可，此时 sandwich 便自动消失了。

构建链表

当我们需要组织某一类的数据时，只需先建一个相应的构造器（构造函数）即可，这个构造器应包含以下的属性和方法：头节点；增，删，查等。

节点构造器

我们可以先做头节点的构造器；

// 我们可以把一个节点视为一个盒子，这个盒子被分为两部分，一部分盛放的是该节点的值，另一部分盛放的则是指向下一个节点的节点指向。function Node(element) {
  this.element = element;
  this.next = null;
}

链表构造器

某类数据的链表构造器

function LList() { //LList: linkedList 链表
  // 新建值为 head 的节点（表头），便可一生二二生三三生万物了，下面的操作都要基于表头。this.head = new Node("head");
  
  // 查找方法，给 find 一个值，便可查到相应的节点
  this.find = find;
  
  // 插入方法，可以实现在哪插入、插入什么数据的功能
  this.insert = insert;
  
  // 展示打印功能，传入想要查询的节点的元素，该节点便能被打印出来，包括的指向的下一节点
  this.display = display;

  // 如果要删除某一节点，则需要找到它的前一节点，修改它的节点指向
  this.findPrevious = findPrevious;
 
  // 删除方法，传入想要删除的元素，即可实现删除功能
  this.remove = remove; 
}

find()方法

find()方法展示了如何在链表上进行移动。首先，新创一个节点，并将表头赋给这个新创的节点。然后在链表上进行循环，如果如果当前节点的 element 属性和我们要查找的值不一样，就从当前节点移到下一节点，如果查找成功，返回包含该数据的节点，失败，返回null。

function find(item) {
  
  // 将表头赋给新创的节点
  var currNode = this.head;
  
  // 循环，如果当前节点的值与我们想要查找的值不一样，移动到下一节点。知道找到目标或移到 null
  while (currNode.element !== item) {currNode = currNode.next;}
  
  // 返回相应节点或 null
  return currNode;
}

insert()方法

insert()实现插入功能，传入新节点的值 newElement 和待插位置item，并修改新节点和待插位置的节点指向，完成插入。

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

display()

display()显示链表中的元素

function display() {
  var currNOde = this.head;
  while (currNode !== item) {console.log(currNode.element);
    currNode = currNode.next;
  }
}

findPrevious()

findPrevious()查找到待删除的前一节点

function findPrevious(item) {
  var currNode = this.head;
  while ((currNode.next !== null) && (currNode.next.element !== item)) {currNode = currNode;}
  return currNode;
}

remove()方法

function remove(item) {var preNode = this.findPrevious(item);
  if(preNode.next !== null) {preNode.next = preNode.next.next;}
}

完整代码

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

function LList() {this.head = new Node("head");
  this.find = find;
  this.insert = insert;
  this.display = display;
  this.findPrevious = findPrevious;
  this.remove = remove;
}

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 currNode = this.find(item);
  newNode.next = currNode.next;
  currNode.next = newNode;
}

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

function findPrevious(item) {
  var currNode = this.head;
  while ((currNode.next.element !== item) && (currNode.next !== null)) {currNode = currNode.next;}
  return currNode;
}

function remove(item) {var preNode = this.findPrevious(item);
  if(preNode.next !== null) {preNode.next = preNode.next.next;}
}

测试

向链表中写入数据

var cities = new LList();
cities.insert("beijing", "head");
cities.insert("shanghai", "beijing");
cities.insert("guangzhou", "shanghai");
cities.insert("shenzhen", "guangzhou");

展示链表

cities.display();

删除 "shanghai" 后，再次展示

cities.remove("shanghai");
cities.display();

删除成功！

Reference

Michael McMillan, (2014). Data Structures & Algorithms with JavaScript. Beijing: O’Reilly Media, Inc. and Posts & Telecom Press.