今天的目录：1：能说出链表的存储结构和特点2：能说出几种类型的链表及其各自的存储结构3：能说出链表和数组的区别4：完成实操题目5：完成综合案例1、概念和存储结构问题：想想动态数组ArrayList的缺点？1：插入和删除时间复杂度高2：可能造成内存空间的大量浪费3：需要连续的存储空间，对内存要求比较高。比如我们要申请一个1000M的数组，如果内存中没有连续的存储空间足够大，就会申请失败。即使剩余可用内存空间大于1000M，申请依然会失败。结语：能不能申请多少内存就用多少？链表（Linkedlist）是物理存储单元上的一种不连续、无顺序的存储结构。链表中的每个元素称为一个节点（Node），节点之间通过指针（references）连接起来。指向顺序表示节点的逻辑顺序，节点可以在运行时动态生成。每个节点由两部分组成：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。链表能解决数组解决不了的问题吗？1：链表天生具有动态扩展的特点。不需要像动态数组那样申请更大的空间，然后将原空间中的数据复制到新的空间；可以避免内存空间的大量浪费。2：链表不需要一块连续的内存空间，它是用指针??将一组分散的内存块串联起来的，所以如果我们申请一个1000M的链表，只要内存中剩余的可用空间大一些就可以了超过1000M，就不会有问题。但是要注意：存储同样的数据，链表比数组更耗内存！2、链表分类链表按其节点间的连接形式可分为两种：单链表、双链表、循环链表、双向循环链表2.1、单链表链表是最基本的结构在刚才我们提到的链表中，链表通过指针将一组碎片化的内存块连接在一起。.如图所示，我们把记录下一个节点地址的指针称为next后继指针。如果链表中的一个节点是p，p的下一个节点是q，我们可以表示为：p.next=q链表中有两个特殊的节点，它们是第一个节点和最后一个节点。我们习惯上称第一个节点为头节点，最后一个节点为尾节点。其中，头节点用于记录链表的基地址。有了它，我们就可以遍历得到整个链表了。尾节点的特殊之处在于，指针并不指向下一个节点，而是指向一个空地址NULL，也就是说这是链表的最后一个节点。与数组一样，链表也支持数据查找、插入和删除操作。在进行数组插入和删除操作时，为了保持内存数据的连续性，需要移动大量的数据，所以时间复杂度为O(n)。在链表中插入或删除一条数据，我们不需要移动节点来保持内存的连续性，因为链表本身的存储空间是不连续的。因此，在链表中插入和删除一个数据是非常快的。如图所示，对于链表的插入和删除操作，我们只需要考虑相邻节点的指针变化，所以插入和删除的时间复杂度是O(1)。但是，有利也有弊。如果链表要随机访问第k个元素，效率不如数组。因为链表中的数据不是连续存储的，所以不可能像数组一样根据首地址和下标直接通过寻址公式计算出对应的内存地址，而是需要逐个节点依次遍历计算，直到对应的因此，链表的随机访问性能不如数组，查询的时间复杂度为O(n)。2.2.双向链表只有一个方向，结点只有一个后继指针next。双向链表，顾名思义，支持两个方向。每个节点不仅有一个指向后一个节点的后继指针next，还有一个指向前一个节点的前驱指针prev，如图所示，双向链表需要额外增加两个空间来存放后继节点和前驱节点的地址。因此，如果存储相同数量的数据，双向链表比单向链表占用更多的内存空间。两个指针虽然浪费存储空间，但是可以支持双向遍历，这也带来了双向链表操作的灵活性，比如1：O(1)时间可以找到给定节点的前驱节点，而对于单链表list需要O(n)时间2：根据索引查找元素时，可以大大提高查找效率...很多场景下，双向链表比单向链表效率更高，这就是为什么在实际的软件开发中，双向链表虽然占用内存较多，但仍然比单链表使用更广泛。如果你熟悉Java语言，你一定用过LinkedHashMap容器??。如果深入研究LinkedHashMap的实现原理，就会发现使用的是双向链表的数据结构。其实这里一个更重要的思想是用空间换时间的设计思想。在内存空间充足的情况下，如果我们更追求代码的执行速度，可以选择空间复杂度相对较高，时间复杂度相对较低的算法或数据结构。反之，如果内存比较稀缺，比如代码运行在手机等存储容量较小的设备上，这时候就需要将时间换空间的设计思路倒过来.比如最典型的缓存系统就是一种用空间换取时间的思想。2.3.循环链表循环链表是一种特殊的单向链表。其实循环链表也很简单。它和单向链表的唯一区别是尾节点。我们知道，单向链表的尾节点指针指向一个空地址，说明这是最后一个节点。循环链表的尾节点指针指向链表的头节点。从我画的循环链表图中，大家应该可以看出，它像环一样首尾相接，所以叫“循环”链表。与单链表相比，循环链表的优点是从链尾到链头更方便。.当要处理的数据具有环形结构的特点时，特别适合使用循环链表。循环链表的结构如图2.4所示。双向循环链表。一个双向循环链表3.总结&实战3.1．链表数组比较数组和链表是两种完全不同的内存组织方式。正是由于内存存储的不同，它们的插入、删除和随机访问操作的时间复杂度正好相反。下图是链表和数组在插入、删除和随机访问的时间复杂度对比。3.2、206.反向链表词节拍，腾讯、阿里、美团点评近期面试题，206.反向链表高频题双指针迭代类解法{publicListNodereverseList(ListNodehead){ListNodeprev=null;ListNodecurr=head;while(curr!=null){ListNodetemp=curr.next;当前.下一个=上一个；上一个=当前；当前=温度；}返回上一个；快慢指针publicclassSolution{publicbooleanhasCycle(ListNodehead){//特殊判断if(head==null||head.next==null){returnfalse;}ListNodefast=head;ListNodeslow=head;//两个指针分别下降while(true){fast=fast.next.next;慢=慢.next;如果（fast==null||fast.next==null）{returnfalse;}如果（快==慢）{休息；}}返回真；}}4.综合案例4.1.需求在学习数组的时候，我们实现了一个基于数组的List容器，支持对数据进行增、改、删、查等操作。今天学习了链表之后，我们是不是可以实现一个LinkedList容器呢？要求：1：要求与动态数组ArrayList具有相同的功能2：请基于双向链表实现，4.2、实现（1）定义接口，com.iheima.linkedlist.inf.List，接口方法与之前实现ArrayList时相同，只是添加了泛型包com.itheima.linkedlist.inf;/***由传智播客*黑马程序员创建。*/publicinterfaceList{/***返回容器中元素的数量*@return*/intsize();/***判断容器是否为空*@return*/booleanisEmpty();/***查询元素在容器中的索引下标*@paramo元素对象*@returnin如果容器中的下标不存在则返回-1*/intindexOf(Eo);/***判断容器是否包含特定元素*@parame*@return*/booleancontains(Ee);/***添加元素到容器尾部*@parame要添加的元素*@return是否添加成功*/booleanadd(Ee);/***添加元素到指定位置*@paramindex位置下标*@paramelement元素对象*/voidadd(intindex,Eelement);/***用指定元素替换指定位置的数据*@paramindex指定位置索引下标*@paramelementnewelement*@returnoriginalelement*/Eset(intindex,Eelement);/***获取指定位置的元素*@paramindex索引下标*@return该位置的元素*/Eget(intindex);/***移除指定位置的元素*@paramindex索引下标*@return移除的元素*/Eremove(intindex);/***清空容器中的所有元素*/voidclear();}(2)创建接口实现：com.itheima.linkedlist.LinkedList，实现对应的接口(3)容器要基于doubly实现链表，而链表是由一个个节点组成的，所以定义链表节点对象，写一个静态内部类//定义链表节点对象privatestaticclassNode{Eval;节点上一个；下一个节点；//定义结构publicNode(Nodeprev,Eval,Nodenext){this.prev=prev;这个.val=val;这个.下一个=下一个；}}(4)定义相关成员变量//定义容器中元素个数intsize;//定义链表Node的头节点first;//定义链表Node的尾节点last;（5）完成size、isEmpty、indexOf、contains等方法的准备@Overridepublicintsize(){returnsize;}@OverridepublicbooleanisEmpty(){returnsize==0;}@OverridepublicintindexOf(Eo){指数=0;//根据o是否为null的情况，判断是否为null的方式不同。如果为null，则使用==，如果不为null，则使用equalsif(o==null){for(Nodex=first;x!=null;x=x.next){if(x.val==null){返回索引；}索引++；}}else{for(Nodex=first;x!=null;x=x.next){if(o.equals(x.val)){返回索引；}索引++；}}return-1;}@Overridepublicbooleancontains(Ee){returnindexOf(e)!=-1;}(6)完成add方法的编写@Overridepublicbooleanadd(Ee){//Addis将元素值添加到链表的末尾linkLast(e);returntrue;}privatevoidlinkLast(Ee){Nodel=last;节点newNode=newNode(l,e,null);最后一个=新节点；if(l==null){//首先添加=newNode;}else{l.next=newNode;}size++;}@Overridepublicvoidadd(intindex,Eelement){//检查索引checkIndex(index);如果（索引==大小）{linkLast（元素）；}别的{linkBefore（元素，节点（索引））；}}/***在指定节点前添加一个元素*@paramelement*@paramnode*/privatevoidlinkBefore(Eelement,Nodenode){Nodeprev=node.prev;NodenewNode=newNode(prev,element,node);node.prev=newNode;if(prev==null){first=newNode;}else{前一个。下一个=新节点；}size++;}/***找到索引为index*的节点@paramindex*@return*/privateNodenode(intindex){//搜索一半if(index<(size>>1)){//从头开始寻找Nodef=first;for(inti=0;il=last;for(inti=size-1;i>index;i--){//同上l=l.prev;}返回l;}}privatevoidcheckIndex(intindex){if(index<0||index>size){thrownewIndexOutOfBoundsException("index"+index+",size="+size);}}(7)完成set和get方法的编写/***替换指定索引位置元素*@paramindex指定位置索引下标*@paramelementnewelement*@return*/@OverridepublicEset(intindex,E元素){isElementIndex(index);节点oldNode=节点（索引）;EoldVal=oldNode.val;oldNode.val=元素；returnoldVal;}privatevoidisElementIndex(intindex){if(index<0||index>=size){thrownewIndexOutOfBoundsException("index="+index+",size="+size);}}}@OverridepublicEget(intindex){isElementIndex(index);returnnode(index).val;}(8)写完remove方法@OverridepublicEremove(intindex){isElementIndex(index);节点节点=节点（索引）；returnunlink(node);}privateEunlink(Nodenode){Nodeprev=node.prev;节点下一个=节点。下一个;Eval=node.val;节点.val=null；//node是头节点if(prev==null){first=next;}else{prev.next=next;node.prev=null;}//节点是尾节点if(next==null){last=prev;}else{next.prev=prev;节点.下一个=空；}尺寸-;returnval;}(9)完成clear，toString方法写@Overridepublicvoidclear(){for(Nodel=first;l!=null;){Nodenext=l.next;l.val=null;l.prev=null;l.next=null;l=下一个；}第一个=最后一个=空；size=0;}@OverridepublicStringtoString(){//输出1->2->空格式数据StringBuilderstringBuilder=newStringBuilder();for(Nodel=first;l!=null;l=l.next){stringBuilder.append(l.val).append("->");}stringBuilder.append("Null");returnstringBuilder.toString();}(10)编写测试类：com.itheima.linkedlist.LinkedListTestpublicstaticvoidmain(String[]args){Listlist=新链表（）；列表.添加（1）；列表.添加（2）；列表.添加（3）；System.out.println("容器中的元素为："+list);//1->2->3->NullSystem.out.println("容器中元素个数："+list.size()+"容器是否为空："+list.isEmpty());System.out.println("容器是否包含3:"+list.contains(3));list.add(0,4);//4->1->2->3->NullSystem.out.println("容器中的元素为："+list);list.add(3,5);//4->1->2->5->3->NullSystem.out.println("容器中的元素为："+list);list.add(2,6);//4->1->6->2->5->3->NullSystem.out.println("容器中的元素为："+list);System.out.println("获取索引为0的元素："+list.get(0));System.out.println("获取索引为5的元素："+list.get(5));System.out.println("获取索引为2的元素："+list.get(2));list.remove(0);//1->6->2->5->3->NullSystem.out.println("容器中的元素为："+list);list.remove(3);//1->6->2->3->NullSystem.out.println("移除后，容器中的元素为："+list);列表.clear();System.out.println("清除后为："+list);}查看输出！容器中的元素为：1->2->3->Null容器中的元素个数：3容器是否为空：false容器中是否包含3：true容器中的元素为：4->1->2->3->Null容器中的元素为：4->1->2->5->3->Null容器中的元素为：4->1->6->2->5->3->null获取索引索引为0的元素：4获取索引为5的元素：3获取索引为2的元素：6容器中的元素为：1->6->2->5->3->Null去除后，容器中的元素为：1->6->2->3->Null清空后变为：Null如果本文对您有帮助，请点赞关注并喜欢；有什么建议也可以留言或私信。您的支持是我坚持创作的动力
