一、单向链表1、在我们的数据结构中，单向链表非常重要。其中的数据元素是以节点为单位的，每个节点由该数据元素的数据和下一个节点的地址组成。在java集合框架中，最底层的LinkedList、HashMap（数组加链表）等都是用链表实现的。2.以下是单链表的一些特点：数据元素存放在内存中的地址是不连续的：在单链表的节点中定义了一个节点，它存放的是下一个节点的内存地址，在example在转换对象的时候，jvm会开辟不同的内存空间，而且是不连续的。添加效率高：添加元素时，先找到插入位置的前一个，只需要断开1和2元素之间的连接，将插入节点的next指向第一个元素的next(1)，然后设置一个元素的next指向插入节点（2），后面的元素不需要移动。删除效率高：删除一个元素时，先找到删除位置，将上一个的下一个指向删除位置的下一个，不需要移动后面的元素。查询效率低：查询时必须从头开始依次遍历，而数组可以直接通过索引查找，因为它的内存是连续的。3.下面的代码用于实现单链表结构：packagecom.tlinkedList;/***User:zhang*Date:2020/10/26**/publicclassTLinkedList{privateNodehead;//链表头privateintsize;//链表元素个数publicTLinkedList(){head=null;size=0;}//将节点作为内部类。也可以新建一个Node类作为一个节点.t=t;}}//在链表头部添加一个节点publicvoidaddFirst(Tt){Nodenode=newNode(t);node.next=head;head=node;size++;}//在中间链表的添加一个节点publicvoidaddMid(Tt,intindex){Nodenode=newNode(t);Nodemid=head;for(inti=0;ilinkedList=newTLinkedList<>();linkedList.addFirst("hello1");linkedList.addFirst("hello2");linkedList.addFirst("hello3");for(inti=0;i{privateNodehead;//该栈的头节点stackprivateintsize;//栈中元素个数classNode{privateNodenext;//下一个节点privateTt;//该节点的数据(Tt){tthis.t=t;}}publicTest_Stack(){head=null;size=0;}publicstaticvoidmain(String[]args){Test_StackTStack=newTest_Stack<>();TStack.push("hello1");TStack.push("hello2");TStack.push("hello3");for(inti=0;i<3;i++){System.out.println(TStack.pop());}}//推送publicvoidpush(Tt){Nodenode=newNode(t);if(size==0){node.next=head;head=node;size++;return;}if(size==1){head.next=node;node.next=null;size++;return;}NodelastNode=head;while(lastNode.next!=null){lastNodelastNode=lastNode.next;}lastNode.next=node;node.next=null;size++;}//poppublicTpop(){if(size==0){System.out.println("没有值i在堆栈中");returnnull;}if(size==1){Tt=head.getT();head=null;size--;返回；}点头elastNode=head;NodeqNode=head;while(lastNode.next!=null){qNode=lastNode;lastNodelastNode=lastNode.next;}Tt=lastNode.getT();qNode.next=null;size--;return;}//获取栈中元素个数publicintgetSize(){returnsize;}//返回栈顶元素publicTpeek(){if(size==0){System.out.println("栈中无值");返回空;}if(size==1){returnhead.getT();}NodelastNode=head;while(lastNode.next!=null){lastNodelastNode=lastNode.next;}returnlastNode.getT();}}结果：3.队列(队列)1、队列的特点也可以用“先进先出”这几个字来概括，即先进去的元素先输出。2、我们常见的消息队列就是通过队列结构实现的。3、队列的常用操作如下：put(enqueue)：向尾部插入一个结点。pop（出队）：以头节点的下一个节点为头，然后删除原来的头节点。4.通过链表结构实现队列：packagecom.tQueue;/***User:zhang*Date:2020/10/26**/publicclassTQueue{privateNodefront;//头节点privateNodetail;//尾节点privateintsize;//队列中的元素个数classNode{privateNodenext;//下一个节点privateTt;//节点数据publicNode(Tt){tthis.t=t;}publicTgetT(){returnt;}publicvoidsetT(Tt){tthis.t=t;}}publicintgetSize(){returnsize;}publicvoidsetSize(intsize){this.size=size;}publicTQueue(){front=tail=null;}//入队publicvoidput(Tt){Nodenode=newNode(t);if(size==0){front=tail=node;size++;return;}NodelastNode=front;while(lastNode.next!=null){lastNodelastNode=lastNode.next;}lastNode.next=node;tail=node;size++;}//queuepublicTpop(){if(size==0){System.out.println("队列中没有值");returnnull;}Tt=front.getT();frontfront=front.next;size--;returnt;}publicstaticvoidmain(String[]args){TQueuetQueue=newTQueue<>();tQueue.put("Hello1");tQueue.put("Hello2");tQueue.put("Hello3");for(inti=0;i<3;i++){System.out.println(tQueue.pop());}}}结果：
