链表
链表是一种物理存储单元上非线性、非连续性的数据结构（它在数据逻辑上是线性的），它的每个节点由两个域组成：数据域和指针域。数据域中存储实际数据，指针域则存储着指针信息，指向链表中的下一个元素或者上一个元素。正是由于指针的存在，链表的存储在物理单元是非连续性的。
链表的优点和缺点同样明显。和线性表相比，链表在添加和删除节点上的效率更高，因为其只需要修改指针信息即可完成操作，而不像线性表（数组）那样需要移动元素。同样的，链表的长度在理论上也是无限的（在存储器容量范围内），并可以动态变化长度，相比线性表优势很大。 相应的，由于线性表无法随机访问节点，只能通过指针顺着链表进行遍历查询来访问，故其访问数据元素的效率比较低。
JS实现单链表
function LinkedList() { let Node = function (ele) { this.ele = ele; this.next = null; } let length = 0, head = null; //头指针 //向尾部追加元素 this.append = function (ele) { let node = new Node(ele), temp; //临时指针 if (!head) { head = node; } else { temp = head; while (temp.next) { temp = temp.next } temp.next = node; } length++; return true; } //插入到指定位置 this.insert = function (position, ele) { if (position >= 0 && position < length) { let node = new Node(ele), temp = head, index = 0, previous; if (position == 0) { node.next = temp; head = node; } else { while (index++ < position) { previous = temp; temp = temp.next; } node.next = temp; previous.next = node; } length++; return true; } else { return false; } } //删除指定位置元素 this.removeAt = function (position) { if (position > -1 && position < length) { let temp = head, previous, index = 0; if (position == 0) { head = head.next; } else { while (index++ < position) { previous = temp; temp = temp.next; } previous.next = temp.next; } length--; return temp.ele; } else { return null; } } //删除所有值为ele的元素 this.removeEle = function (ele) { let temp = head, previous, num = 0; if (ele == temp.ele) { head = head.next; length--; num++; } while (temp.next) { previous = temp; temp = temp.next; if (temp.ele == ele) { previous.next = temp.next; length--; num++; } } return num; } //删除最后一个元素 this.pop = function () { let temp = head, previous = temp; if (length < 1) { return false; } if (length == 1) { head = null; length--; return temp.ele; } while (temp.next) { previous = temp; temp = temp.next; } previous.next = null; length--; return temp.ele; } this.indexOf = function (ele) { let temp = head, index = 0; while (temp) { if (temp.ele == ele) { return index; } temp = temp.next; index++; } return -1; } this.toString = function () { let temp = head, string = ''; while (temp) { string += temp.ele + ' '; temp = temp.next; } return string; } this.length = function () { return length; } this.isEmpty = function () { return length === 0; }; this.getHead = function () { return head.ele; } } let mylist = new LinkedList(); mylist.append('A'); mylist.append('B'); mylist.append('C'); mylist.append('D'); mylist.append('C'); mylist.append('B'); mylist.append('A'); console.log(mylist.toString()); console.log(mylist.pop()); console.log(mylist.toString()); console.log('移除%d个C', mylist.removeEle('C')); console.log(mylist.toString()); console.log(mylist.length()); console.log(mylist.getHead()); console.log(mylist.indexOf('C'))
JS实现单循环链表：
在单链表的基础上，将尾节点的指针指向头结点，就构成了一个循环链表。环形链表从任意一个节点开始，都可以遍历整个链表。
function CircularLinkedList(){ var Node = function(element){ this.element = element; this.next = null; } var length = 0, head = null; this.append = function(element){ var node = new Node(element), current; if (!head) { head = node; node.next = head; }else{ current = head; while(current.next !== head){ current = current.next; } current.next = node; node.next = head; }; length++; return true; }; this.insert = function(position, element){ if(position > -1 && position < length){ var node = new Node(element), index = 0, current = head, previous; if (position === 0) { node.next = head; head = node; }else{ while(index++ < position){ previous = current; current = current.next; } previous.next = node; node.next = current; }; length++; return true; }else{ return false; } }; //移除指定位置元素 this.removeAt = function(position){ if(position > -1 && position < length){ var current = head, previous, index = 0; if (position === 0) { head = current.next; }else{ while (index++ < position){ previous = current; current = current.next; } previous.next = current.next; }; length--; return current.element; }else{ return null; } }; //移除指定元素 this.remove = function (element){ var current = head, previous, indexCheck = 0; while(current && indexCheck < length){ if(current.element === element){ if(indexCheck == 0){ head = current.next; length--; return true; }else{ previous.next = current.next; length--; return true; } }else{ previous = current; current = current.next; indexCheck++; } } return false; }; //移除最后一个元素 this.remove = function(){ if(length === 0){ return false; } var current = head, previous, indexCheck = 0; if(length === 1){ head = null; length--; return current.element; } while(indexCheck++ < length){ previous = current; current = current.next; } previous.next = head; length--; return previous.element; //返回移除的元素 }; this.indexOf = function(element){ var current = head, index = 0; while(current && index < length){ if(current.element === element){ return index; }else{ index++; current = current.next; } } return false; }; this.isEmpty = function(){ return length === 0; }; this.size = function(){ return length; }; this.toString = function(){ var current = head, string = '', indexCheck = 0; while(current && indexCheck < length){ string += current.element; current = current.next; indexCheck++; } return string; }; }
let mylist=new CircularLinkedList();
mylist.append('A');
mylist.append('B');
mylist.append('C');
mylist.append('D');
console.log(mylist.toString());
console.log(mylist.remove()); //D
console.log(mylist.toString());