首先，链表有以下特点：
1. 存储空间不固定，可灵活扩充
2.方便多次的插入和删除，效率较高
单链表
单链表是最常用的链表，其对数据的操作均为单项的，向后查找的。
/*
链表（基于对象） 此处为单链表
*/
function Node (ele) {
this.element = ele;
this.next = null;
} function LinkedList () {
this.head = new Node("head"); // 头结点
this.find = find; // 根据element值查找节点
this.findPrevious = findPrevious;
this.insert = insert;
this.remove = remove;
this.display = display;
} function find (item) {
var currNode = this.head;
while(currNode.element !== item) {
if(currNode.next === null) {
return false;
}
currNode = currNode.next;
}
return currNode;
} function findPrevious (item) {
var currNode = this.head;
while(currNode.next!==null&& currNode.next.element!=item){
currNode = currNode.next;
}
return currNode;
} function insert (newEleContent, item) {
var newNode = new Node(newEleContent);
var currNode = this.find(item);
newNode.next = currNode.next;
currNode.next = newNode;
} function display () {
var currNode = this.head;
while(currNode.next !== null){
console.log(currNode.next.element)
currNode = currNode.next;
}
} function remove (item) {
var currNode = this.find(item);
var previousNode = this.findPrevious(currNode.element);
previousNode.next = currNode.next;
currNode = null;
}
双向链表
双向链表可以方便地对数据进行向前和向后查找（操作），如播放器正向播放音乐时用户存在上一曲和下一曲的操作需要，此时就用到了双向链表。
function Node (ele) {
this.element = ele;
this.next = null;
this.previous = null;
}
function DuplexLinkedList () {
this.head = new Node("head");
this.find = find;
this.findLast = findLast;
this.remove = remove;
this.insert = insert;
this.display = display;
this.displayReverse = displayReverse;
}
function find (item) {
var currNode = this.head;
while (currNode.element!==item) {
currNode = currNode.next;
}
return currNode;
}
function remove (item) {
var currNode = this.find(item);
currNode.previous.next = currNode.next;
if(currNode.next){
currNode.next.previous = currNode.previous;
}
currNode = null;
}
function insert (eleContent, item) {
var newNode = new Node(eleContent);
var currNode = this.find(item);
// 先操作新节点，否则会进死循环
newNode.previous = currNode;
newNode.next = currNode.next;
currNode.next = newNode;
if(currNode.next.previoue){
currNode.next.previous = newNode;
}
console.log(newNode);
}
function findLast () {
var currNode = this.head;
while(currNode.next!==null){
currNode = currNode.next;
}
return currNode;
}
function display () {
var currNode = this.head;
while (currNode.next!==null){
console.log(currNode.next.element);
currNode = currNode.next;
}
}
function displayReverse () {
var currNode = this.findLast();
console.log(currNode);
while(currNode.previous!==null){
console.log(currNode.element);
currNode = currNode.previous;
}
}
循环链表
同理，循环链表是单向的，但是可以循环地查找。例如解决约瑟夫环问题
function Node (ele) {
this.element = ele;
this.next = null;
}
//循环链表需要将this.head.next指向this.head
function CirLinkedList () {
this.head = new Node("head");
this.head.next = this.head;
this.find = find;
this.findPrevious = findPrevious;
this.insert = insert;
this.remove = remove;
this.display = display;
}
function find (item) {
var currNode = this.head;
while(currNode.element !== item) {
if(currNode.next === null) {
return false;
}
currNode = currNode.next;
}
return currNode;
}
function findPrevious (item) {
var currNode = this.head;
while(currNode.next!==null&& currNode.next.element!==item){
currNode = currNode.next;
}
return currNode;
}
function insert (newEleContent, item) {
var newNode = new Node(newEleContent);
var currNode = this.find(item);
newNode.next = currNode.next;
currNode.next = newNode;
console.log(newNode);
}
function display () {
var currNode = this.head;
// 循环输出判断需要增加next是不是头节点
while(currNode.next.element != "head" && currNode.next.element!=="head" ){
console.log(currNode.next.element);
currNode = currNode.next;
}
}
function remove (item) {
var currNode = this.find(item);
var previousNode = this.findPrevious(currNode.element);
previousNode.next = currNode.next;
currNode = null;
}