数据结构系列——链表

一、单链表

单链表的每个节点都包含值(val),下个节点的引用(next)，通过这种方式将所有节点有序组织起来。如下所示：

有几点共识，在此先提出来

在查找方面，数组比链表快，因为数组可以通过下标快速找到目标，而链表需要通过next字段一个个比较，所以链表在查找时的时间复杂度为O（n），因为链表在内存中是动态分配，有需要增加元素的时候才会去指向下一块内存，所以在内存中是不连续的；而数组再进行数据的随机访问时，理论时间复杂度是O（1），因为数组在内存中是一段连续的存储区域（静态分配，初始化内存地址区域足够大，不需要动态增加内存地址），所以可以通过计算得到目标元素的内存地址

在添加或者删除方面，单链表的时间复杂度是O（1），因为只需要改变对应的引用字段(next)指向就可以了;而数组在增加或者删除时，可能会有0个或者n个元素的位置改变，因为数组内部内存地址是连续的，那么6占据了第一个元素0的索引0之后，6就会占据0所在的内存地址，那么0就会占据后一个元素的内存地址，然后继续递归，直到next指向null,所以最坏情况下会影响到n个元素，时间复杂度为O（n）

单链表的js代码实现：

注意：在代码实现中，我们返回的是头结点，因为我们可能会修改头结点的指向，也就是头结点指向第二个节点之类，所以需要特别注意。另外tem=this.head(或者tem=tem.next)只是改变了变量指向的内存地址，并没有修改链表；只有修改next字段，val字段，才会修改链表的值,另外this.head=this.head.next也是修改了链表，因为我们返回的是头结点，所以这样设置了就是返回第二个节点；除非先用node=this.head,最后返回node,这样返回的就是头结点。

function List () { // 节点 let Node = function (element) { this.val = element this.next = null } // 初始头节点为 null this.head = null // 链表长度 let length = 0

// 操作 // 1.追加节点 this.append=function (element) { let node = new Node(element),p = this.head // 如果不存在头结点，那么设置头结点为新创建的该节点 if (!this.head){ this.head = node } else { while (p.next) { p = p.next } p.next = node;// 把节点的指针指向下一个节点 } length += 1 } this.getList = function() {return head} // 1.查找操作的时间复杂度是O(n),因为需要遍历元素 this.search = function(element) { let p=this.head; while(p){ if(p.val==element) return true p=p.next; } return false; } // 2. 插入操作活动删除操作的时间复杂度是O(1),因为找到元素(查找才需要O(n)!)之后，只需要更改指针就可以了！ this.insert = function(position, element) { let p=this.head; let node=new Node(element); let len=0; if(position==0){ node.next=p; this.head=node; return this.head; }else if(position>0){ let pre=this.head;// head的前部分 while(len pre=p; p=p.next; len++; } pre.next=node;// 修改了链表head的某个节点的next指针 node.next=p;// 修改了node节点的指针指向p,p表示的是head后部分 return this.head; }else if(position return null } } // 2.2也就是删除操作不包含查找操作！先查找，再删除/插入... this.remove = function(element){ let p=this.head,pre=this.head; if(p.val==element){ p=p.next;// 相当于删除了第一个节点 this.head=p; return this.head; } while(p){ if(p.val==element){ pre.next=p.next; p.next=null; break; } pre=p; // pre节点为p节点 p=p.next; } // 由于pre节点不一定是头节点，所以不一定=this.head return this.head;} }

// 测试 let list = new List() console.log(list); for(let i = 0; i < 5; i+=1) { list.append(i) } console.log(list.head); console.log(list.search(1)) console.log(list.search(8)) // console.log(list.insert(0,9)) console.log(list.insert(2,9)) console.log(list.remove(0)) // console.log(list.remove(9))

二、双链表

双链表与单链表的区别在于除了val字段和next字段之外还有一个prev字段，用于指向前一个节点，头结点到的prev指向null,尾节点的next指向null

查找，增加和删除操作其实和单链表差不多，双链表结构如下图所示:

function List(){ // 创建一个节点 let Node=function(element){ this.prev=null; this.element=element; this.next=null; } // 初始化头结点为null this.head=null; // 初始化尾节点为null this.tail=null; // 操作函数 this.insert=function (position,element){ // 如果索引为0 let node=new Node(element) if(position==0){ node.next=this.head; this.head=node; return this.head; }else if(position return null; }else{ // 遍历 let len=0; let tem=this.head; while(true){ // 插入 if(len==position-1){ // 如果到了链表的末尾 if(tem.next==null){ tem.next=node; node.prev=tem; return this.head; }else{ tem.next.prev=node; let a=tem.next; // 保存下一个节点 tem.next=node; node.prev=tem; node.next=a; return this.head; } } tem=tem.next; len++; // 超出长度范围 if(tem==null){ return null; } } } }

this.delete=function (position){ let tem=this.head; if(position==0){ // 如果只有一个节点 if(tem.next==null){ this.head=null; }else{ tem.next.prev=null; this.head=tem.next; } return this.head; }else{ let len=0; while(true){ // 超出范围 if(tem.next==null&&len return null; }else if(len==position){ // 存在节点 let a=tem.prev; // 如果不是最后一个节点 if(a.next.next){ a.next=a.next.next; a.next.prev=a; }else{ a.next.prev=null; a.next=null; } return this.head; }else if(tem.next){ tem=tem.next; len++; } } } }

this.search=function(element){ let tem=this.head; while(true){ if(tem==null){ return false; }

if(tem.element==element){ return true; } tem=tem.next; } } } let list=new List(); // 1. 插入O(1) console.log(list.insert(0,0)) console.log(list.insert(1,1)) console.log(list.insert(1,2)) console.log(list.insert(10,2));// null; console.log(list.insert(3,3));// 0 2 1 3 // 2. 删除O(1) // console.log(list.delete(0));// 2 1 3 // console.log(list.delete(1));// 0 1 3 // console.log(list.delete(2));// 0 2 3 console.log(list.delete(3));// 0 2 1 // 3. 查找O(n) console.log(list.search(22));//false

三、循环单链表

就是单链表是循环的，尾节点指向头结点，循环单链表需要注意到达末尾节点的判断条件是当前node.next=this.head,也就是下一个节点就指向头结点

function CircleList(){ let Node=function(element){ this.element=element; this.next=null; } this.head=null; // 1.插入 this.insert=function (position,element){ if(position let tem=this.head; let node=new Node(element); if(position==0){ node.next=tem; this.head=node; tem=this.head; // 改变尾节点指向 while(true){ //如果还没有循环 if(tem.next==null){ tem.next=this.head; return this.head } tem=tem.next; // 在插入0之前，之前的循环在当前的索引1 if(tem.next===this.head.next){ tem.next=this.head; return this.head } } }else{ let len=0; while(true){ // 此时position至少为1 if(len==position-1){ // 如果是最后一个 if(tem.next==this.head){ tem.next=node; node.next=this.head;// 循环指向头结点 }else{ node.next=tem.next; tem.next=node; } return this.head; } if(tem.next===this.head) return null; tem=tem.next; len++; } } } // 2. 删除 this.delete=function(element){ let tem=this.head; if(tem==null) return false // 为了不搞混节点顺序，需要针对头节点 if(tem.element==element){ while(true){ if(tem.next===this.head){ tem.next=this.head.next; this.head=this.head.next; return this.head; } tem=tem.next; } } tem=tem.next; while(tem!==this.head){ if(tem.next.element==element){ let a=tem.next;//3 tem.next=tem.next.next;// 88->9 a.next=null; return this.head; } tem=tem.next; } return false } // 3.查找 this.search=function (element){ let tem=this.head; if(tem===null) return false; while(true){ tem=tem.next; if(tem.element==element) return true; if(tem===this.head) return false; } } } let list=new CircleList(); console.log(list.insert(0,1)) console.log(list.insert(0,2)) console.log(list.insert(0,3)) console.log(list.insert(1,9)) console.log(list.insert(4,88));// 3,9,2,1,88 // console.log(list.insert(14,88));//null // 删除 // console.log(list.delete(1));//3 9 2 88 // console.log(list.delete(88));//3 9 2 1 console.log(list.delete(3));//9 2 1 88 // 查找 console.log(list.search(3));//false console.log(list.search(9));//true

本节只介绍单链表、双链表、循环单链表的结构和查找增加删除函数的设计，还有一个循环双链表以后再实现。下一节将会介绍关于链表的十道经典练习题