一、什么是链表
链表是一种链式存储的线性表，是由一组节点组成的集合，每一个节点都存储了下一个节点的地址；指向另一个节点的引用叫链；和数组中的元素内存地址是连续的相比，链表中的所有元素的内存地址不一定是连续的。结构模拟如图：
一般来说，说到链表，就要提下数组，一般链表都是和数组进行对比。
在很多编程语言中，数组的长度时固定的，所以数组中的增加和删除比较麻烦，需要频繁的移动数组中的其他元素。
然而，JavaScript中的数组并不存在上述问题，JS中的数组相对其他语言使用上更方便，因为JS中的数组本质是一个类似数组的对象，这就使得JS的数组虽然使用更方便，但比其他语言(C++、Java、C#)的数组效率要低。
所以，在实际应用中如果发现数组很慢，就可以考虑使用链表来替代它。除了对数据的随机访问，链表几乎可以用在任何可以使用一维数组的情况中。如果需要随机访问，数组仍然是更好的选择。
二、链表的设计
为了对链表更好的使用，我们设计了类LinkedList, 对链表中节点的增删改查方法进行了封装。结构如图：
其中size和head为LinkedList构造函数私有属性，size记录链表中有多少个节点，head指向链表的头结点。
根据需要对外暴露了以下方法（可以根据需要自定义其他方法）：
单向LinkedList完整设计代码：
/** * 自定义链表：对外公开的方法有 * append(element) 在链表最后追加节点 * insert(index, element) 根据索引index, 在索引位置插入节点 * remove(element) 删除节点 * removeAt(index) 删除指定索引节点 * removeAll(element) 删除所有匹配的节点 * set(index, element) 根据索引，修改对应索引的节点值 * get(index) 根据索引获取节点信息 * indexOf(element) 获取某个节点的索引位置 * clear() 清空所有节点 * length() 返回节点长度 * print() 打印所有节点信息 * toString() 打印所有节点信息，同print * */ const LinkedList = function(){ let head = null; let size = 0; //记录链表元素个数 //Node模型 function LinkNode(element, next){ this.element = element; this.next = next; } //元素越界检查, 越界抛出异常 function outOfBounds(index){ if (index < 0 || index >= size){ throw("抱歉，目标位置不存在！"); } } //根据索引，获取目标对象 function node(index){ outOfBounds(index); let obj = head; for (let i = 0; i < index; i++){ obj = obj.next; } return obj; } //新增一个元素 function append(element){ if (size == 0){ head = new LinkNode(element, null); } else{ let obj = node(size-1); obj.next = new LinkNode(element, null); } size++; } //插入一个元素 function insert(index, element){ if (index == 0){ head = new LinkNode(element, head); } else{ let obj = node(index-1); obj.next = new LinkNode(element, obj.next); } size++; } //修改元素 function set(index, element){ let obj = node(index); obj.element = element; } //根据值移除节点元素 function remove(element){ if (size < 1) return null; if (head.element == element){ head = head.next; size--; return element; } else{ let temp = head; while(temp.next){ if (temp.next.element == element){ temp.next = temp.next.next; size--; return element; } else{ temp = temp.next; } } } return null; } //根据索引移除节点 function removeAt(index){ outOfBounds(index); let element = null; if (index == 0){ element = head.element; head = head.next; } else{ let prev = node(index-1); element = prev.next.element; prev.next = prev.next.next; } size--; return element; } //移除链表里面的所有匹配值element的元素 function removeAll(element){ let virHead = new LinkNode(null, head); //创建一个虚拟头结点，head为次节点 let tempNode = virHead, ele = null; while(tempNode.next){ if (tempNode.next.element == element){ tempNode.next = tempNode.next.next; size--; ele = element; } else{ tempNode = tempNode.next; } } //重新赋值 head = virHead.next; return ele; } //获取某个元素 function get(index){ return node(index).element; } //获取元素索引 function indexOf(element){ let obj = head, index = -1; for (let i = 0; i < size; i++){ if (obj.element == element){ index = i; break; } obj = obj.next; } return index; } //清除所有元素 function clear(){ head = null; size = 0; } //属性转字符串 function getObjString(obj){ let str = ""; if (obj instanceof Array){ str += "["; for (let i = 0; i < obj.length; i++){ str += getObjString(obj[i]); } str = str.substring(0, str.length - 2); str += "], " } else if (obj instanceof Object){ str += "{"; for (var key in obj){ let item = obj[key]; str += "\"" + key + "\": " + getObjString(item); } str = str.substring(0, str.length-2); str += "}, " } else if (typeof obj == "string"){ str += "\"" + obj + "\"" + ", "; } else{ str += obj + ", "; } return str; } function toString(){ let str = "", obj = head; for (let i = 0; i < size; i++){ str += getObjString(obj.element); obj = obj.next; } if (str.length > 0) str = str.substring(0, str.length -2); return str; } //打印所有元素 function print(){ console.log(this.toString()) } //对外公开方法 this.append = append; this.insert = insert; this.remove = remove; this.removeAt = removeAt; this.removeAll = removeAll; this.set = set; this.get = get; this.indexOf = indexOf; this.length = function(){ return size; } this.clear = clear; this.print = print; this.toString = toString; } ////测试 // let obj = new LinkedList(); // let obj1 = { title: "全明星比赛", stores: [{name: "张飞vs岳飞", store: "2:3"}, { name: "关羽vs秦琼", store: "5:5"}]}; // // obj.append(99); // obj.append("hello") // obj.append(true) // obj.insert(3, obj1); // obj.insert(0, [12, false, "Good", 81]); // obj.print(); // console.log("obj1.index: ", obj.indexOf(obj1)); // obj.remove(0); // obj.removeAll(obj1); // obj.print(); ////测试2 console.log("\n\n......test2.....") var obj2 = new LinkedList(); obj2.append(8); obj2.insert(1,99); obj2.append('abc'); obj2.append(8); obj2.append(false); obj2.append(12); obj2.append(8); obj2.append('123'); obj2.append(8); obj2.print(); obj2.removeAll(8); //删除所有8 obj2.print();