正文
JavaScript实现单向链表
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
JavaScript 本身提供了十分好用的数据类型，以满足大家的日常使用。单靠 Array 和 Object 也的确足够应付日常的绝大部分需求，这也导致了很多前端er对数据结构这一块不是十分的了解。
数据结构是 CS 的必修科目，前端这个圈子非科班的童鞋比例较高，相信很多人对数据结构的了解并不多。虽然本人大学读的也是 CS，但那时候上课基本都在睡觉，数据结构也是学得一塌糊涂，现在也基本上全忘了。
那下面我们来了解一下，如何用 JavaScript 来实现一个 单向链表 。
维基百科中，对链表的描述如下：
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。
由此可以知道，链表和数据相比，会具有一下优点：
- 不需要预先分配内存（在静态语言中，数组是需要预先分配内存空间的，空间分配后不能再改变）
- 插入和删除元素不需要移动其余元素，效率更高
JavaScript 作为一门动态语言，其中的数组也是动态数组，不需要预先分配内存的。在使用过程中还可以动态增减数组长度，这直接让 Array 类型的适用范围扩大了不少。
数组在进行插入和删除元素时，是十分麻烦的事情，而这方面却是链表的优势。在查找元素的效率方面，链表就比不上数组那么方便快捷了。
单向链表，是链表中最简单的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。
下面我们看看 单向链表 的图示：
可以看到，链表中每一个 item（元素） 都有两个部分组成：data 和 next。其中 data 用于存储数据，是真正的存储区。而 next 用于存放地址，用于指向下一个 item。
下面我们看看怎么设计一个单向列表。
一般的单向列表，都具有以下的属性和方法：
- first：指向第一个 item
- last：指向最后一个 item
- length：链表的 item 数量
- get()：获取指定位置的 item
- set()：修改指定位置的 item
- add()：插入一个新的 item 到指定位置
- remove()：移除指定位置的 item
- clear()：清空所有 item
为了方便实用，还提供了部分语法糖：
- addFirst()：插入一个新的 item 到链表头部
- addLast()：插入一个新的 item 到链表尾部
- removeFirst()：移除第一个 item
- removeLast()：移除最后一个 item
- toString()：列表以 "10 -> a -> [1,2] -> 3.14" 方式输出
下面是 SinglyLinkedList 的类：
var SinglyLinkedList = function () {
function SinglyLinkedList() {
this.length = 0;
this.first = null;
this.last = null;
}
/**
* 根据索引获取 item
* @param {Number} index 链表索引
* @returns {*}
*/
SinglyLinkedList.prototype.get = function (index) {
if (typeof index !== 'number' || index < 0 || index >= this.length) {
return undefined;
}
var item = this.first;
for (var i = 0; i < index; i++) {
item = item.next;
}
return item;
};
/**
* 根据索引设置 item 的内容
* @param {Number} index 链表索引
* @param {*} value 需要设置的值
* @returns {*}
*/
SinglyLinkedList.prototype.set = function (index, value) {
if (typeof index !== 'number' || index < 0 || index >= this.length) {
return false;
}
var item = this.get(index);
item.data = value;
return item;
};
/**
* 根据索引位置插入新的 item
* @param {Number} index 链表索引
* @param {*} value 需要设置的值
* @returns {*}
*/
SinglyLinkedList.prototype.add = function (index, value) {
if (typeof index !== 'number' || index < 0 || index > this.length || index === undefined) {
return false;
}
var item = {
data: value,
next: null
};
if (this.length > 0) {
if (index === 0) {
item.next = this.first;
this.first = item;
} else if (index === this.length) {
this.last.next = item;
this.last = item;
} else {
var prevItem = this.get(index - 1),
nextItem = this.get(index);
item.next = nextItem;
prevItem.next = item;
}
} else {
this.first = item;
this.last = item;
}
this.length++;
return item;
};
/**
* 根据索引删除 item
* @param {Number} index 链表索引
* @returns {boolean}
*/
SinglyLinkedList.prototype.remove = function (index) {
if (typeof index !== 'number' || index < 0 || index >= this.length) {
return false;
}
var item = this.get(index);
if (this.length > 1) {
if (index === 0) {
this.first = item.next;
} else if (index === this.length - 1) {
this.last = this.get(this.length - 2);
this.last.next = null;
} else {
this.get(index - 1).next = item.next;
}
} else {
this.first = null;
this.last = null;
}
item = null;
this.length--;
return true;
};
/**
* 清空整个单链表
* @returns {boolean}
*/
SinglyLinkedList.prototype.clear = function () {
this.first = null;
this.last = null;
this.length = 0;
return true;
};
SinglyLinkedList.prototype.addFirst = function (value) {
return this.add(0, value);
};
SinglyLinkedList.prototype.addLast = function (value) {
return this.add(this.length, value);
};
SinglyLinkedList.prototype.removeFirst = function () {
return this.remove(0);
};
SinglyLinkedList.prototype.removeLast = function () {
return this.remove(this.length - 1);
};
SinglyLinkedList.prototype.toString = function () {
var arr = [],
item = {};
if (this.length) {
do {
item = item.next || this.get(0);
arr.push(typeof item.data === 'object' ? JSON.stringify(item.data).replace(/\"/g, '') : item.data);
} while (item.next);
}
return arr.join(' -> ');
};
return SinglyLinkedList;
}();
使用方法很简单：
var sList = new SinglyLinkedList();
sList.addLast('a');
sList.addFirst(10);
sList.addLast(3.14);
sList.add(2, [1, 2]);
sList.addLast({a: 1, b: 2});
console.log(sList.toString()); // "10 -> a -> [1,2] -> 3.14 -> {a:1,b:2}"
console.log(sList.length); //
sList.removeFirst();
sList.removeLast();
console.log(sList.toString()); // "a -> [1,2] -> 3.14"
console.log(sList.length); //
参考资料：
http://zh.wikipedia.org/wiki/%E9%93%BE%E8%A1%A8
http://www.cnblogs.com/skywang12345/p/3561803.html#a33
本文作者：Maple Jan
本文链接：http://www.cnblogs.com/maplejan/p/3903749.html
