链表简介
链表是一种常见的数据结构，也属于线性表，但不会按线性的顺序来储存数据。而是在每一个节点中，储存了下一个节点的指针。可以看图理解。(有c语言基础的可能比较好理解)。
使用链表结构可以克服数组需要预先知道数据大小的缺点(c语言的数组需要预先定义长度)，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。
接下来就是介绍两种常见的链表: 单向链表，双向链表在javascript中的实现。
单向链表
链表中最简单的形式就是单向链表，链表中的节点都包含两个部分，第一部分储存着自身信息，第二部分则储存有指向下一节点的指针。最后一个节点则指向null:
javascipt中单向链表的实现
首先，创建一个构造函数。
/** * 单向链表构造函数 */function linkedlist() { /** * 单向链表中节点的构造函数 * @param {any} element 要传入链表的节点 */ var node = function(element) { this.element = element; //下个节点的地址 this.next = null; } //单向链表的长度 var length = 0; //单向链表的头结点，初始化为null var head = null;}
不难看出，单向链表构造函数比栈与队列要复杂许多。
单向链表需要有如下的方法:
append(element): 添加元素到链表尾部 insert(position,element): 向单向链表中某个位置插入元素 indexof(element): 寻找某个元素在单向链表中的位置 remove(element): 移除给定的元素 removeat(position): 移除单向链表中某个位置的元素 gethead(): 获取单向链表的头部 isampty(): 检查单向链表是否为空，为空则返回true tostring(): 将链表所有内容以字符串输出 size(): 返回单向链表长度
append方法:
说明: 向单向链表尾部添加元素。
实现:
/** * 向单向链表尾部添加元素 * @param {any} element 要加入链表的节点 */this.append = function(element) { var node = new node(element); var current; if (head == null) { head = node; } else { // 当前项等于链表头部元素. // while循环到最后一个，从而将该节点加入链表尾部。 current = head; // 当next为null时，判定为false。退出循环。 while (current.next) { current = current.next; } current.next = node; } length++;};
insert方法:
说明: 向单向链表中某个位置插入元素。
实现:
/** * 向单向链表中插入某个元素 * @param {number} position 要插入的位置 * @param {any} element 要插入的元素 * @return {boolean} 插入成功返回true，失败返回false */this.insert = function(position, element) { if (position >= 0 && position =0表示移除成功 */this.remove = function(element) { var index = this.indexof(element); return this.removeat(index);};
removeat方法:
说明:移除单向链表中某个位置的元素。
实现:
/** * 移除单向链表中某一个元素 * @param {number} position 要移除元素的位置 * @return {any} 移除成功返回被移除的元素，不成功则返回null */this.removeat = function(position) { if (position > -1 && position < length) { var current = head; var previous; var index = 0; if (position == 0) { // 因为之前head指向第一个元素，现在把head修改为指向第二个元素。 // 核心概念在于链表前后全靠指针链接，而非数组一般。 // 所以只需要改变head的元素。 head = current.next; } else { while (index++ = 0 && position <= length) { var node = new node(element); var index = 0; var previous; var current = head; if (position === 0) { if (head === null) { head = node; tail = node; } else { current.prev = node; node.next = current; head = node; } } else if (position === length) { current = tail; current.next = node; node.prev = current; tail = node; } else { while (index++ -1 && position < length) { var current = head; var index = 0; var previous; if (position === 0) { head = current.next; if (length === 1) { tail = null; head.prev = null; } } else if (position === length - 1) { current = tail; tail = current.prev; tail.next = null; } else { while (index++ < position) { previous = current.prev; current = current.next; } previous.next = current.next; current.next.prev = previous; } length--; return current.element; } else { return false; }};
showhead、showlength、showtail方法
实现:
/** * 获取链表的头部 * @return {any} 链表的头部 */this.showhead = function() { return head;};/** * 获取链表长度 * @return {number} 链表长度 */this.showlength = function() { return length;};/** * 获取链表尾部 * @return {any} 链表尾部 */this.showtail = function() { return tail;};
感想
链表这一节，基本全部都是先按需求写代码，写完后再和书上对比。发现简直被瞬间秒成渣。自己写的很多暗坑，逻辑也很混乱。看来还是太年轻了。