数据结构之链表

链表是由一组节点组成的集合，每个节点使用一个对象的引用指向它的后继，指向另一个节点的引用就是链。在 JavaScript 中，数组也可以存储元素，但是数组说到底也是一个对象，与其他语言相比效率比较低，因此出现了链表，它可以更方便地代替数组来实现同样的数据存储与移动效果。

定义链表

为了更形象地表示链表，我从网上找了一张表示图，如下

每个链表都有一个头结点，头结点通常作为链表的接入点，它不参与链表的遍历，同样还会有一个尾元素，指向一个 null 结点。在 JavaScript 中，实现一个基于对象的链表，使用两个类，一个类用来表示所有的结点，另一个类用来表示一些链表的基本方法。

Node 类

function Node(element) {
  this.element = element;   // 保存节点上的数据
  this,next = null;      // 保存指向下一个节点的链接
}

LinkedList 类

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

实现插入节点

插入一个节点，首先要明确是在某个节点的前面或后面插入，假设在一个已知节点后面插入元素，则需要先找到该节点“后面”的节点，然后将新节点的 next 属性设置为“后面”节点的 next 属性对应的值，然后设置“后面” 的节点的 next 属性指向新节点。

// 定义一个 find 来找到 “后面” 的节点
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;
  current.next = newNode;
}

现在插入新节点的方法已经完成，我们紧接着定义一个方法用于展示链表中的元素

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

删除节点

删除链表中的一个元素，我们首先要找到该元素所在的节点，然后找到它前面的节点，使其的 next 属性指向待删除节点的下一个节点，这样就可以把节点 remove 掉。

// 定义 findPrevious 方法寻找前面节点
function findPrevious(item){
  var currNode = this,head;
  while(!(currNode.next == null) && (currNode.next.element != item)){
    currNode = currNode.next;
  }  
  return currNode;
}

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

这里的prevNode.next = prevNode.next.next;就是使前面的节点直接指向待删除节点后面的节点。

完整代码

最后放上完整的代码，包含 Node 类、LList 类和测试代码；

function Node(element) {
  this.element = element;   
  this,next = null;      
}
function LList() {
  this.head = new Node("head");
  this.find = find;
  this.insert = insert;
  this.remove = remove;
  this.display = display;
}
function remove(item) {
  var prevNode = this.findPrevious(item);
  if(!(prevNode.next == null)) {
    prevNode.next = prevNode.next.next;
  }
}
function findPrevious(item){
  var currNode = this.head;
  while(!(currNode.next == null) && (currNode.next.element != item)){
    currNode = currNode.next;
  }  
  return currNode;
}
function display() {
  var currNode = this.head;
  while(!(currNode.next ==  null)) {
    console.log(currNode.next.element);
    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;
  current.next = newNode;
}

var city = new LList();
city.insert("Guangzhou","head");
city.insert("Shenzhen","Guangzhou");
city.insert("Shantou","Shenzhen");
city.insert("Zhuhai","Shantou");
city.display();
city.remove("Shenzhen");
city.display();

参考资料：Data Structure and Algorithms Using JavaScript, Michael McMillan 著