Java的线性表的链式存储--单链表我们都知道线性表的存储结构分为两种，顺序存储结构和链式存储结构，lineartable的分类可以参考下图来学习和记忆。今天我们主要学习链式存储结构。1.链式存储介绍“链式存储结构，地址可以是连续或不连续的存储单元存储数据元素”——来自定义。其实你可以想象这样一个场景，你想找一个人（他叫小谭），所以你先问A，A说他不知道，但是他说B可能知道，并告诉你B在哪里是，所以你去找B，B说他不知道，但是他说C可能知道，并且告诉你C的地址，你就去找C，C才真正知道小檀在哪里。上面的场景其实可以帮助我们理解链表。实际上，每个链表都包含多个节点，节点又包含两部分。一个是数据字段（存储节点包含的信息），另一个是指针字段（存储下一个节点或前一个节点）。一个节点的地址），而这个指针域就相当于问B，B知道C的地址，这个指针域就是C存储的地址。链表其实又分为三种：单链表，双链表链表和循环链表。今天先说说单链表。2.单向链表简介什么是单向链表？单向链表是一种链表，其中每个节点只有一个指针字段。如下图所示，是一个带前导节点的单向链表。接下来我们要知道什么是头指针，头节点，头节点。头指针：指向链表节点首节点的指针头节点：指附加在链表首节点之前的节点头节点：指存储链表中第一个实际数据元素的节点（如上图a1节点）3.单向链表的创建单向链表的创建有两种方式，分别是头插入法和尾插入法。1、头部插入法头部插入法，顾名思义，就是在头部位置插入一个新的元素，每一个新加入的元素作为链表的首节点。那么如何在Java中实现header插入的方法。首先我们需要定义一个节点，如下publicclassListNode{publicintval;//datafieldpublicListNodenext;//pointerfield}然后我们创建一个头指针（没有头节点）//numberofelementsintn=5;//创建一个头指针ListNodeheadNode=newListNode();//头部插入方式headNode=createHead(headNode,n);然后创建一个私有方法实现head插入方法，这里我们插入5个新元素，head插入的核心是先断开head节点和head指针的连接，也就是需要存储原来的地址新节点的指针域中的head节点，即newNode.next=headNode.next，然后让head指针指向新节点headNode.next=newNode，这两步是head插入的核心，必须明白。/***头部插值法*新节点放在头节点后面，之前的节点放在新节点后面*@paramheadNode头指针*@return*/privatestaticListNodecreateHead(ListNodeheadNode,intn){//插入5个新节点for(inti=1;i<=n;i++){ListNodenewNode=newListNode();新节点.val=i;//将之前所有节点指向新节点（即新节点指向之前所有节点）newNode.next=headNode.next;//将头指针指向新节点headNode.next=newNode;}returnheadNode;}最后打印出链表（其实也是单链表遍历），判断条件是指针字段为空时才为最后一个节点。privatestaticvoidprintLinkedList(ListNodeheadNode){intcountNode=0;while(headNode.next!=null){countNode++;System.out.println(headNode.next.val);headNode=headNode.next;系统输出。println("单向链表的总节点数："+countNode);}最后的输出显然是倒序的，因为没有从头部插入新的元素，自然是第一个就是最后一个，最后一个就是第一种：2.尾部插入法尾部插入法，顾名思义，就是在尾部位置（也就是最后一个位置）插入一个新的元素，每一个新加入的元素作为最后一个节点链表。那么在Java中如何实现插入尾的方法呢，这里还是不带头节点的实现，头节点和头指针的实现方式和头插入一样，这里我就直接实现：/***tail插入方法*找到链表的尾节点，将新增的数据作为尾节点的后续节点*@paramheadNode*/privatestaticListNodecreateByTail(ListNodeheadNode,intn){//使尾指针也指向头指针ListNodetailNode=headNode;for(inti=1;i<=n;i++){ListNodenewNode=newListNode();新节点.val=i;newNode.next=null;//在链表尾部插入tailNode.next=newNode;//指向新的tail节点，tailer总是保存最后一个节点的地址tailNode=newNode;}returnheadNode;}和head插入的区别在于我们需要声明一个tail指针来辅助我们实现。起初，尾指针指向头指针，每插入一个元素，尾指针就会向后移动。这里讲一下原理：每在末尾增加一个新的节点，我们就需要断开原来的连接。如何断开连接？首先，我们需要让tail指针指向一个新节点，即tailNode.next=newNode;然后将尾指针向后移动一个位置，使尾指针指向最后一个节点。即尾指针一直指向最后一个节点，最后返回头指针，输出最后的结果：4.单链表的删除单链表创建好了，如何删除链表中的元素？对于单链表的删除，我分为两种情况第一种是删除，分别是删除第i个节点和删除指定元素的节点。1、要删除第i个节点，我们可以先这样想：在单向链表中，节点之间是通过指针域链接起来的，所以如果我们要删除节点，其实需要改变它。对应的指针字段对应地址。当我们要删除第i个元素时，比如我们要删除上图中的第三个元素（也就是3），其实我们需要做的就是让2号元素指向4号元素（其实我们需要修改第2个元素的指针字段，让第2个元素的指针字段存放第4个元素）。那么可以做些什么来实现这一步呢？很明显，要实现这一步，我们必须找到4号元素和2号元素，但是仔细想想，其实我们只需要找到2号元素，因为4号的地址元素是存放在第2个指针字段里面的一个元素。所以根据上面的分析，我们可以得到删除的两个核心步骤：1、要删除第i个节点，需要先找到第i-1个节点，也就是第i个节点的前一个节点；2.然后让第i-1个节点指向第i-1个节点的下一个节点。下面的代码具体实现了如何删除第i个元素。/***删除第i个节点*1,24,4,5*删除后应该是1,2,4,5*@paramheadNode*@paramindex*@return*/publicstaticListNodedeleteNodeByIndex(ListNodeheadNode,intindex){intcount=1;//给它一个ListNode的引用preNode=headNode;//检查计数器是否达到i-1，如果达到i-1，找到第i-1个节点while(preNode.next!=null&&count<=index-1){//寻找前一个节点count++of当前要删除的节点；preNode=preNode.next;}if(preNode!=null){preNode.next=preNode.next.next;}returnheadNode;}2.删除指定元素的节点。有两种方法可以删除指定元素的节点。一个节点的idea可以删除。实现方法如下图所示：/***删除链表中具有指定值的节点*@paramheadNode*@paramval*@return*/privatestaticListNodedeleteNodeByNum(ListNodeheadNode,intval){ListNodedeleteOne=headNode;intcountByDeleteOne=1;while(deleteOne.next!=null){if(deleteOne.next.val==val){deleteOne=deleteOne.next;休息;}countByDeleteOne++;deleteOne=deleteOne.next;}returndeleteNodeByIndex(headNode,countByDeleteOne);}第二种方法的实现很精妙（前提是这个节点不是尾节点）publicvoiddeleteNode(ListNodenode){//通过给节点，然后改变节点的指针指向下一个节点就是node.val=node.next.val;node.next=node.next.next;}5.单向链表查询（及修改）单向链表查询的实现很简单，就是遍历当前的单向链表，然后用一个计数器添加到当前下标，那么当前节点就是要查询的节点，然后返回。当然，还要判断传递的下标是否合法。当然，如果需要修改，则需要将当前找到的节点的data字段重新赋值为需要修改的值，这里不再赘述代码。具体实现如下：privatestaticListNodesearchLinkedList(ListNodeheadNode,intindex){//如果下标是非法下标，则表示找不到if(index<1||index>getLinkedListLength(headNode)){返回空值；}for(inti=0;i
