链表和数组js中的数组大家都用过。数组实际上是一个线性表的顺序存储结构。其特点是用一组地址连续的存储单元顺序存储数据元素。而它的缺点也是由它的特性造成的。例如，删除或插入数组时，可能需要移动大量元素。下面粗略模拟一下数组的插入操作：functioninsert(arr,index,data){for(leti=arr.length;i>index;i--){arr[i]=arr[i-1];}arr[索引]=数据；}从上面的代码可以看出，数组的插入和删除可能是一个O(n)的操作。这就引出了链表的数据结构。链表不需要逻辑上相邻的元素在物理上也相邻，因此不存在顺序存储结构的缺点。当然，它也失去了数组在连续空间中的随机性。访问的优势。单向链表的特点：使用一组任意的内存空间来存储数据元素（这里的内存空间可以是连续的，也可以是不连续的）。每个节点（node）由数据本身和一个指向后续节点的指针构成整个链表。访问必须从头指针开始。头指针指向第一个节点。最后一个节点的指针指向一个空(NULL)列表。链表中的几个主要操作创建节点插入节点搜索/遍历节点删除节点合并将节点指针初始化为空存储数据类Node{constructor(key){this.next=null;this.key=键；}}初始化单向链表每个链表都有一个头指针，指向第一个节点，没有节点则指向NULLclassList{constructor(){this.head=null;}}创建节点staticcreateNode(key){returnnewcreateNode(key);创建一个节点而不是直接封装到插入操作中，因为我感觉这样逻辑会更正确。创建链表->创建节点->将节点插入链表。可能你会遇到一些文章，用一个数据作为参数，直接调用insert操作，在insert里面创建一个节点。插入节点（在头节点之后插入）插入操作只需要调整节点的指针即可。两种情况：head没有指向任何节点，说明当前插入的节点是指向新节点的第一个head。新节点的指针指向NULLhead。指向的节点head指向新节点新节点的指针指向原head指向的节点insert(node){//如果head有指向节点if(this.head){node.next=这个头；}else{node.next=null;}this.head=节点；}从head开始查找节点当发现节点中的key等于你要查找的key时，返回该节点find(key){letnode=this.head;while(node!==null&&node.key!==key){node=node.next;}返回节点；}删除节点有三种情况：被删除的节点恰好是第一个，head指向的节点head指向被删除节点的下一个节点（node.next）。待删除节点是找到待删除节点的前一个节点（prevNode）的最后一个节点。将prevNode中的指针指向NULL删除链表中间的一个节点找到待删除节点的上一个节点（prevNode），将prevNode中的指针指向待删除节点的下一个节点delete(node){//第一种情况if(node===this.head){this.head=node.next;返回;}//找到要删除的节点的前一个节点letprevNode=this.head;while(prevNode.next!==node){prevNode=prevNode.next;}//第二种情况if(node.next===null){prevNode.next=null;}//第三种情况if(node.next){prevNode.next=node.next;}}单链表整体代码classListNode{constructor(key){this.next=null;this.key=键；}}classList{constructor(){this.head=null;这个.length=0;}staticcreateNode(key){returnnewListNode(key);}//向头部插入数据insert(node){//如果头部后面有一个指向的节点if(this.head){node.next=this.head;}else{node.next=null;}this.head=节点；这个。长度++；}find(key){letnode=this.head;while(node!==null&&node.key!==key){node=node.next;}返回节点；}delete(node){if(this.length===0){throw'nodeisundefined';}if(node===this.head){this.head=node.next;这个.length--;返回;}让prevNode=this.head;while(prevNode.next!==node){prevNode=prevNode.next;}if(node.next===null){prevNode.next=null;}if(node.next){prevNode.next=node.next;}this.length--;}}双向链表如果你理解了上面介绍的单向链表，那么这里介绍的双向链表其实和上图差不多。你可以清楚地看到双向链表和单向链表的区别。双向链表有一个指向前一个节点的额外指针。初始化指向上一个节点和指向下一个节点的指针NodedataclassListNode{this.prev=null;这个.下一个=空；this.key=键；}将双链表头指针初始化为NULLclassList{constructor(){this.head=null;}}创建节点staticcreateNode(key){returnnewListNode(key);}插入节点（（在head节点后插入）见上图中head后面的第一个节点，该节点的prev指向NULL，该节点的next指针指向下一个节点，也就是该节点由当前head指针指向，如果head后面有结点，那么原head之后结点的prev指向新插入的结点（因为是双向的。）最后把head指向新结点insert(node){node.prev=null;node.next=this.head;if(this.head){this.head.prev=node;}this.head=node;}这里的搜索节点和one-node的方式，直接贴代码就可以了删除节点和之前的单向链表一样，可以分三种情况来看：第一个节点head指向待删除节点的下一个节点，下一个节点的prev指针指向要删除的节点的前一个节点删除的是中间的一个节点。要删除的前一个节点。next指向下一个要删除的节点。下一个要删除的节点的prev指向上一个要删除的节点。最后一个要删除的节点是最后一个要删除的节点。nextofanode指向null（即被删除节点的next指向的地址地址）删除（节点）{常量{上一个，下一个}=节点；删除节点.prev；删除node.next；if(node===this.head){this.head=next;}如果（下一个）{下一个.prev=上一个；}if(prev){prev.next=next;}}双向链表整体代码classListNode{constructor(key){//指向上一个节点this.prev=null;//指向下一个节点this.next=null;//节点数据（或查找键）this.key=key;}}/***双向链表*/classList{constructor(){this.head=null;}staticcreateNode(key){returnnewListNode(key);}插入（节点）{node.prev=null;node.next=this.head;如果(this.head){this.head.prev=node;}this.head=节点；}search(key){letnode=this.head;while(node!==null&&node.key!==key){node=node.next;}返回节点；}delete(node){const{prev,next}=node;删除节点.prev；删除node.next；如果（节点===this.head){this.head=next;}if(prev){prev.next=next;}if(next){next.prev=prev;}}}总结这里做一个小总结，可能有些人看完后不是很理解。我的建议是理解上面的单向链表。其实只要了解链表的基本概念，就是有个头，然后就是很多结点（Node），然后用一个指针把它们串起来就行了。至于里面的插入和删除操作，其实就是调整节点中的指针。后续可能有数据结构，可能会讲二叉堆，也可能回过头来讲一下队列和栈的一些思想在程序中的应用。欢迎大家指出文章中的错误，有什么写作建议也可以提出。我会继续写一些关于前端的技术文章。喜欢的话可以关注一下。
