从上一节可以，顺序存储结构的弱点就是在插入或删除操作时，需要移动大量元素。所以这里需要介绍一下链式存储结构，由于它不要求逻辑上相邻的元素在物理位置上也相邻，所以它没有顺序存储结构的弱点，但是也没有顺序表可随机存取的优点。
下面介绍一下什么是链表。
线性表的链式存储结构用一组任意的存储单元存储线性表的数据元素。所以，每一个数据元素除了存储自身的信息之外，还需要存储一个指向其后继的存储位置的信息。这两部分信息组成了元素的存储映像，称为结点。
结点包括两个域：数据域和指针域。
数据域是元素中存储数据元素的信息。
指针域是元素中存储的后继存储位置的信息。
n个结点链接成为链表，就是线性表的链式存储结构，又由于此链表的每个结点中只包含一个指针域，所有又称为线性链表或单链表。
举一个例子
上图表示的线性表为
ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG
这样应该就好理解多了吧。
下面我们通过js代码来实现链表的插入和删除还有查找操作
<!DOCTYPE html> <html> <head> <meta charset="UTF-8"/> <script type = "text/javascript"> var Node = function(newData){//创建节点对象 this.next = null; this.data = null; this.Init = function(){ this.data = newData; }; this.Init(); } //定义链表类 var List = function(){ this.head = null; this.size = 0; this.Init = function(){ this.head = null; this.size = 0; } this.Init(); this.Insert = function(newData){//初始批量插入操作 this.size += 1; var newNode = new Node(newData); if(this.head == null){ this.head = newNode; return; } var tempNode = this.head; while(tempNode.next != null) tempNode = tempNode.next;//找到链表尾部 tempNode.next = newNode;//将新元素插入到链表尾部 }; this.GetData = function(pos){//查找操作 if(pos >= this.size || pos < 0) return null; else{ tempNode = this.head; for(i = 0;i < pos;i++) tempNode = tempNode.next; //找到所处位置 return tempNode.data; } }; this.Remove = function(pos){//移除某一位置节点 if(pos >= this.size || pos < 0) return null; this.size -= 1; tempNode = this.head; if(pos == 0){ this.head = this.head.next; return this.head; } for(i = 0;i < pos - 1;i++){ tempNode = tempNode.next; } tempNode.next = tempNode.next.next; return tempNode.next; }; this.InsertBefore=function(data,pos){//从某一位置前插入节点 if(pos>=this.size||pos<0) return null; this.size+=1; tempNode=this.head; var newNode = new Node(data);//将数据创造节点 if(pos==0){ newNode.next=tempNode; return newNode.next; } for(i=0;i<pos-1;i++){ tempNode=tempNode.next;//找到插入的位置 } newNode.next=tempNode.next;//插入操作 tempNode.next=newNode; return newNode.next; }; this.Print = function(){//输出 document.write("链表中元素: <br>"); tempNode = this.head; while(tempNode != null){ document.write(tempNode.data + " "); tempNode = tempNode.next; } document.write("<br>"); }; }; //运行测试: var list = new List(); var array = new Array(1,2,3,4,5,6); for(i = 0;i < array.length;i++){ list.Insert(array[i]); } list.Print(); document.write("查找操作下标为4的元素: <br>"); var data= list.GetData(4); document.write(data+"<br>"); document.write("删除操作: <br>"); list.Remove(5); list.Print(); document.write("插入操作: <br>"); list.InsertBefore(8,3); list.Print(); document.write("链表大小: " + list.size); </script> </head> <body> </body> </html>
运行得到结果为
先分析一下插入和删除的代码。
this.InsertBefore=function(data,pos){//从某一位置前插入节点 if(pos>=this.size||pos<0) return null; this.size+=1; tempNode=this.head; var newNode = new Node(data);//将数据创造节点 if(pos==0){ newNode.next=tempNode; return newNode.next; } for(i=0;i<pos-1;i++){ tempNode=tempNode.next;//找到插入的位置 } newNode.next=tempNode.next;//插入操作 tempNode.next=newNode; return newNode.next; }; this.Remove = function(pos){//移除某一位置节点 if(pos >= this.size || pos < 0) return null; this.size -= 1; tempNode = this.head; if(pos == 0){ this.head = this.head.next; return this.head; } for(i = 0;i < pos - 1;i++){ tempNode = tempNode.next; } tempNode.next = tempNode.next.next; return tempNode.next; };
可以看出，插入和删除的世界复杂度都为o(n)。因为在第i个结点前插入或删除都得找到第i-1个元素。
再来看看初始化方法Insert，