数据结构04 链表/循环链表/双向链表

链表/循环链表/双向链表"/>

数据结构04 链表/循环链表/双向链表

链表

简介

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

实现 增加/获取下一个节点/是否是最后的节点/获取节点数据

package jklove;public class node {
//链表就是火车 ，每个节点需要装载自己的货物，和连接物
int data;
node next;
//构造方法初始化数据
node(int data) {
this.data=data;
}//增加节点
public  node add(node node) {
//将当前节点给 变量 currentnode
node currentnode= this;
//循环查找 下一个节点的next是否为null
while(true) {
node next=currentnode.next;
//退出条件
if(next==null) {
break;
}
currentnode=next;
}
currentnode.next=node;return this;
}
//获取当前节点的下一个节点
public node getnext() {
return this.next;
}public int getdata() {
return this.data;
}public boolean isLast() {
return this.next==null;
}}

测试

package jklove;public class test {
public static void main(String[] args) {
node node =new node(1);
node.add(new node(3)).add(new node(78));System.out.println( node.getnext().isLast());
}}

节点的删除/展示 /插入

我删除当前节点，获取不到前面的节点所以删除当前节点只能通过上一个节点指向 下下节点

删除思路图

插入思路图

 //删除节点public void delete(){node newNode=next.next;this.next=newNode;}//展示所以节点public void nodeShow(){node node =this;while (true){//这里写错了 this.next 一直不为null 导致死循环// if (this.next==null){break;}  这里应该更新当前节点的下一个为null 结束if (node==null){break;}System.out.print(node.data+"  ");node=node.next;}}//插入一个节点public void insert(node inode){node getnext = this.getnext();this.next=inode;inode.next=getnext;}

循环链表

思路图

package suanfa01;public class loopnode {//链表就是火车 ，每个节点需要装载自己的货物，和连接物int data;loopnode next=this;//构造方法初始化数据public loopnode(int data) {this.data=data;}//增加节点//获取当前节点的下一个节点public loopnode getnext() {return this.next;}public int getdata() {return this.data;}public boolean isLast() {return this.next==null;}//删除节点public void delete(){loopnode newNode=next.next;this.next=newNode;}//插入一个节点public void insert(loopnode inode){loopnode next = this.next;this.next=inode;inode.next=next;//这样写导致了 除了第一次意外所有都是最后两个节点互指
//        this.next=inode;
//        inode.next=next;}}

测试

package test;import suanfa01.node;import static org.junit.jupiter.api.Assertions.*;class test {public static void main(String[] args) {node node =new node(1);node.add(new node(3)).add(new node(78));node.nodeShow();node.getnext().delete();node.nodeShow();System.out.println();node.insert(new node(7777));node.nodeShow();System.out.println( node.getnext().isLast());}
}

双向链表

双向链表就是记录上一个节点和下一个节点地址， 这里是循环的双向链表

思路图

package suanfa01;public class doubleNode {doubleNode pre =this;doubleNode after=this;int data;public doubleNode(int data){this.data=data;}public void insert(doubleNode node){//获取原本链表的下一个节点doubleNode after = this.after;//修个本节点的next为node ，node 的前一个为本节点this.after=node;node.pre=this;//修改插入节点的下一个为原链表节点的下一个节点， 原本链表的下一个节点的上一个节点指向插入节点node.after=after;after.pre=node;}public int getData(){return this.data;}public doubleNode getAfter(){return this.after;}public doubleNode getPre(){return this.pre;}}

测试

package test;import suanfa01.doubleNode;import static org.junit.jupiter.api.Assertions.*;class doubleNodeTest {public static void main(String[] args) {doubleNode d =new doubleNode(1);doubleNode d2 =new doubleNode(2);doubleNode d3 =new doubleNode(3);System.out.println(d.getPre().getData());System.out.println(d.getData());System.out.println(d.getAfter().getData());d.insert(d2);System.out.println(d.getPre().getData());System.out.println(d.getData());System.out.println(d.getAfter().getData());d2.insert(d3);System.out.println(d.getPre().getData());System.out.println(d.getData());System.out.println(d.getAfter().getData());}}