javaScript实现单向链表

Javascript 本身提供了十分好用的数据类型，以满足大家的日常使用。单靠 Array 和 Object 也的确足够应付日常的绝大部分需求，这也导致了很多前端er对数据结构这一块不是十分的了解。

数据结构是 CS 的必修科目，前端这个圈子非科班的童鞋比例较高，相信很多人对数据结构的了解并不多。虽然本人大学读的也是 CS，但那时候上课基本都在睡觉，数据结构也是学得一塌糊涂，现在也基本上全忘了。

那下面我们来了解一下，如何用 JavaScript 来实现一个 单向链表 。

维基百科中，对链表的描述如下：

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。

由此可以知道，链表和数据相比，会具有一下优点：

1. 不需要预先分配内存（在静态语言中，数组是需要预先分配内存空间的，空间分配后不能再改变??）
2. 插入和删除元素不需要移动其余元素，效率更高

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);   // 5sList.removeFirst();sList.removeLast();console.log(sList.toString());  // "a -> [1,2] -> 3.14"console.log(sList.length);   // 3

参考资料：

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