JavaScript数据结构与算法(二)：链表

一： 什么是链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一 个节点的引用叫做链。链表有两个关键词：【非连续，非顺序】，【指针链接】

1.【非连续，非顺序】

准确来说，链表的存储单元是非必须连续的，就是说可以是连续的，也可以是非连续的。 这一特性决定了链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表在插入的时候可以达到O(1)的复杂度。结点可以在运行时动态生成。

2. 【指针链接】

链表除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。它的每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 同时链表由于增加了结点的指针域，空间开销比较大。该特性带来的一个缺点就是要找一个数，必须要从头开始找起。查找一个节点或者访问特定编号的节点需要O(n)的时间。

二： 链表 VS 数组

1.数组的缺点

数组不总是组织数据的最佳数据结构，在很多编程语言中，数组的长度是固定的，所以当数组已被数据填满时，再要加入新的元素就会非常困难。在数组中，添加和删除元素也很麻烦，因为需要将数组中的其他元素向前或向后平移，以反映数组刚刚进行了添加或删除操作。然而，JavaScript的数组并不存在上述问题，因为使用 split() 方法不需要再访问数组中的其他元素了。JavaScript 中数组的主要问题是，它们被实现成了对象，与其他语言(比如 C++ 和 Java) 的数组相比，效率很低。

2.什么时候使用链表？

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。如果你发现数组在实际使用时很慢，就可以考虑使用链表来替代它。除了对数据的随机访问，链表几乎可以用在任何可以使用一维数组的情况中。但是如果需要随机访问，数组仍然是更好的选择。

三： 设计一个基于对象的链表

这里设计的链表包含两个类。Node 类用来表示节点，LinkedList 类提供了插入节点、删除 节点、显示列表元素的方法，以及其他一些辅助方法。

1. Node类

element 用来保存节点上的数据，next 用来保存指向下一个节点的链接

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

2.LinkedList类

LinkedList 类提供了对链表进行操作的方法。该类的功能包括插入删除节点、在列表中查找给定的值。该类也有一个构造函数，那就是使用一个 Node 对象来保存该链表的头节点。

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

2.1【显】—— 显示链表中所有的元素

先将列表的头节点赋给一个变量，然后循环遍历链表，当前节点的 next 属性为 null 时循环结束。为了只显示包含数据的节点(换句话说，不显示头节点)，程序只访问当前节点的下一个节点中保存的数据:

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

2.2【查】—— 查找某一节点

首先，创建一个新节点，并将链表的头节点赋给这个新创建的节点。然后在链表上进行循环，如果当前节点的 element 属性和我们要找的信息不符，就从当前节点移动到下一个节点。如果查找成功，该方法返回包含该数据的节点;否则返回 null。

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

2.3【增】—— 增加节点

向链表中插入新节点时，需要明确指出要在哪个节点前面或后面插入。所以我们先利用上面的find方法查需要插入在何处。一旦找到“后面”的节点，就可以将新节点插入链表了。首先，将新节点的 next 属性设 置为“后面”节点的 next 属性对应的值。然后设置“后面”节点的 next 属性指向新节点。

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

2.3【删】—— 删除节点

从链表中删除节点时，需要先找到待删除节点前面的节点。找到这个节点后，修改它的 next 属性，使其不再指向待删除节点，而是指向待删除节点的下一个节点。所以我们先定义一个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;
	}
}

接下来我们来测试一下，实现一个根据时间排序的周杰伦专辑

var album = new LinkedList(); 
album.insert("Jay", "head"); 
album.insert("范特西", "Jay"); 
album.insert("七里香", "范特西"); 
album.insert("十一月的肖邦", "七里香"); 
album.display();
console.log('------------');
album.remove("七里香"); 
album.display();


result:
	Jay
	范特西
	七里香
	十一月的肖邦
	------------
	Jay
	范特西
	十一月的肖邦

四: 拓展

链表有很多种不同的类型：单向链表，双向链表，循环链表。上面我们实现的是一个单向链表。

双向链表

尽管从链表的头节点遍历到尾节点很简单，但反过来，从后向前遍历则没那么简单。通过给 Node 对象增加一个属性，该属性存储指向前驱节点的链接，这样就容易多了。这就是双向链表。双向链表插入一个节点需要更多的工作，我们需要指出该节点正确的前驱和后继。

function Node(element) { 
	this.element = element; 
	this.next = null; 
	this.previous = null;
}
// insert方法中也需要设置新节点的previous属性
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 属性，使其指向待删除节点的后继;设置该节点后继的 previous 属性，使其指向待删除节点的前驱。

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

为了完成以反序显示链表中元素这类任务，需要给双向链表增加一个工具方法，用来查找最后的节点。findLast() 方法找出了链表中的最后一个节点，同时免除了从前往后遍历链表之苦:

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

有了这个工具方法，就可以写一个方法，反序显示双向链表中的元素。

function dispReverse() {
	var currNode = this.head;
	currNode = this.findLast();
	while (!(currNode.previous == null)) {
		console.log(currNode.element);
		currNode = currNode.previous; 
	}
}

最后将这些新方法加入双向链表的构造函数。

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

循环链表

循环链表和单向链表相似，节点类型都是一样的。唯一的区别是，在创建循环链表时，让其头节点的 next 属性指向它本身，即: head.next = head。这种行为会传导至链表中的每个节点，使得每个节点的 next 属性都指向链表的头节点。换句话说，链表的尾节点指向头节点，形成了一个循环链表。

如果你希望可以从后向前遍历链表，但是又不想付出额外代价来创建一个双向链表，那么就需要使用循环链表。从循环链表的尾节点向后移动，就等于从后向前遍历链表。

五：总结

1. 链表采用动态分配内存的形式实现。需要时可以用new分配内存空间，不需要时用delete将已分配的空间释放，不会造成内存空间的浪费。数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。
2. 数组中的数据在内存中的按顺序存储的，而链表是随机存储的！
3. (静态)数组从栈中分配空间，对于程序员方便快速,但是自由度小。链表从堆中分配空间，自由度大但是申请管理比较麻烦。
4. 链表在插入，删除的时候可以达到O(1)的复杂度,查找一个节点或者访问特定编号的节点需要O(n)的时间。数组在插入，删除的时候需要O(n)的复杂度,查找一个节点或者访问特定编号的节点的复杂度为O(1)。