Hello，大家好！我是老丑，今天给大家分享的是一种数据结构——链表
”链表是什么？有人肯定会说，链表是一种数据结构啊！
说的对！
链表是那么多数据结构中的一种。也是面试常问的一种，当然面试常问的很多，今天我们只讨论这个常问的链表。
链表的定义“链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
”不知道大家吃没吃过糖葫芦，请看：
大家所看到的一串糖葫芦其实就可以被理解为一个非常常见的链表。
生活中，处处有惊喜！！！
糖葫芦被我们的竹签以某种形式进行串起来了，是不是有内味了。
链表的存储方式不再是物理地址开辟一块连续空间存储所有结点的形式，而是通过绳子（指针）将结点链接（串）起来，每个结点在物理空间可以不相邻（物理空间，也就是实际的空间），而逻辑空间上是连续的。
链表的优缺点优点：
可以充分使用碎片化的内存空间插入和删除元素，只需要改变指向，而不用全部迁移。插入和删除时间复杂度角度，适合插入和删除频繁的场景可动态扩增缺点：
不具备随机访问的特性需要额外的空间来记录下一个结点的地址。查询效率低，所以不适合查询频繁的场景必要的概念结点，头结点，尾结点，指针域
链表的最基本操作查找结点插入结点删除结点链表的分类单链表
单链表是链表里面最简单的一种，指的是链表中的结点的指向只能指向链表中的下一个结点或者为空，元素之间不能互相指向。
双链表
每个链表元素既有指向下一个元素的指针，又有指向前一个元素的指针，其中每个结点都有两种指针。即结点类中会存在Prev和Next两个成员变量，其中Prev指向左边的链表结点，Next指向右边的链表结点
循环链表
将单链表的尾结点指向头结点从而实现循环。
双向循环链表
在双链表的基础上，尾结点的Next指针指向头结点，头结点的Prev指针指向尾结点。
图示图中主要显示的是单链表。至于双链表和循环链表和双向循环链表，大家可以自行脑补。
注意：图中的头结点的数据域是null。
很多博文中的图，可能会导致误解，上面的图是确保正确的。
单链表的自实现因为老丑主修的是Java语言，所以单链表的自实现也会采用Java语言来实现
大家可以自行了解双链表和循环链表。
结点类
packagecn.laochou.link;publicclassNode{privateStringdata;privateNodenext;publicStringgetData(){returndata;}publicvoidsetData(Stringdata){this.data=data;}publicNodegetNext(){returnnext;}publicvoidsetNext(Nodenext){this.next=next;}}
链表类
packagecn.laochou.link;/***链表类*/publicclassListNode{//头结点privateNodehead;//大小privateintsize;publicListNode(){head=newNode(null);size=0;}/***添加元素*
paramnode元素*/publicvoidaddNode(Nodenode){Nodecur=head;while(cur.getNext()!=null){cur=cur.getNext();}cur.setNext(node);size++;}/***插入元素*paramindex元素索引*paramnode元素*/publicvoidinsertNode(intindex,Nodenode){if(indexsize){return;}//当索引位置等于链表大小，即是尾结点if(index==size){Nodecur=head;while(cur.getNext()!=null){cur=cur.getNext();}cur.setNext(node);}//当索引位置小于链表大小，说明在中间else{Nodecur=head;//在这里注意，我们如果想在中间插入的话，是必须找到该索引对应结点的前面一个结点。//我们插入的结点的next指针需要指向原来索引所指向的结点。//大家可以想一下，我们需要前一个节点的next指针指向我们要插入的结点。//大家在这里好好理一理哈。for(inti=0;iindex;i++){cur=cur.getNext();}node.setNext(cur.getNext());cur.setNext(node);}}/***删除元素*paramindex元素所对应的索引*/publicvoidremoveNode(intindex){if(index=size){return;}//说明删除的是最后一个结点if(index==size-1){Nodecur=head;while(cur.getNext().getNext()!=null){cur=cur.getNext();}cur.setNext(null);}else{Nodecur=head;for(inti=0;iindex;i++){cur=cur.getNext();}cur.setNext(cur.getNext().getNext());}}/***查找元素*paramdata元素数据*return返回该结点*/publicNodesearch(Stringdata){Nodecur=head;if(data!=null){//在这里注意为什么使用data.equals()，而不是cur.getData().equals()while(cur.getNext()!=null){if(data.equals(cur.getData())){returncur;}else{cur=cur.getNext();}}}returnnull;}/***遍历链表*/publicvoidforEach(){Nodecur=head;while(cur.getNext()!=null){System.out.println(cur.getNext());cur=cur.getNext();}}}主类
importcn.laochou.link.ListNode;importcn.laochou.link.Node;publicclassMain{publicstaticvoidmain(String[]args){ListNodelistNode=newListNode();Nodenode=newNode("laochou");Nodenode2=newNode("yzl");listNode.addNode(node);listNode.addNode(node2);Nodenode3=newNode("bajie");listNode.insertNode(1,node3);listNode.forEach();System.out.println("-----------");System.out.println(listNode.search("lz"));System.out.println(listNode.search("wave"));System.out.println(listNode.search("laochou"));System.out.println("------------");listNode.removeNode(0);listNode.forEach();System.out.println("------------");listNode.removeNode(1);listNode.forEach();}}
最后结果
我希望，大家可以阅读主类，可以先在大脑里面运行下代码。
Node{data=laochou,next=Node{data=bajie,next=Node{data=yzl,next=null}}}Node{data=bajie,next=Node{data=yzl,next=null}}Node{data=yzl,next=null}-----------nullnullNode{data=laochou,next=Node{data=bajie,next=Node{data=yzl,next=null}}}------------Node{data=bajie,next=Node{data=yzl,next=null}}Node{data=yzl,next=null}------------Node{data=bajie,next=null}小试牛刀
大家如果跟着上面把单链表实现了，那么恭喜你，你已经自己完成了一个单链表。
当然对于初步学习链表的小伙伴，可能不太适应，因此我特意找了一个小题目。
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点示例1:输入:head=[4,5,1,9],val=5输出:[4,1,9]解释:给定你链表中值为5的第二个节点，那么在调用了你的函数之后，该链表应变为4-1-9.示例2:输入:head=[4,5,1,9],val=1输出:[4,5,9]解释:给定你链表中值为1的第三个节点，那么在调用了你的函数之后，该链表应变为4-5-9.来源：力扣（LeetCode）
大家可以一试。
链表的应用（扩展）链表的应用还是很多的呀
LRU缓存算法实现跳表的底层也是通过链表实现的...我在这里列举一些数据结构的应用，是想告诉大家，你现在所学习的数据结构都是十分有用的。在你们后面成长的路上也会遇到，并不是让大家立马去学习。大家有个印象就好。
最后推文到这里，就基本结束了。希望小伙伴能从这篇推文中，Get一些知识。
学习路上有FingerDance，不孤单。
我是老丑，一位又老又丑的少年！我们下期见。
觉得推文写得还不错的小伙伴，还请点赞、