一、单链表
单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。
在开头插入。在链接列表中插入新节点的最简单位置是开始。
从头开始删除。删除链表中的第一个节点也很容易
在末尾插入。要在链接列表的末尾插入一个节点,我们维护一个指向列表中最后一个节点的链接。
/**
* 单链表
*/classSingleLinked{
Node HeadNode=newNode(0,"","");//创建链表时头结点便已经创建完成在//增加节点publicvoidadd(Node node){
Node temp= HeadNode;while(temp.next!= null) temp= temp.next;
temp.next= node;}/**
* 按no的顺序添加节点
*/publicvoidaddNodeByOrder(Node node){
Node temp= HeadNode;while(temp.next!= null){//如果没有大小匹配的,就放在末尾if(temp.no< node.no&& temp.next.no> node.no)break;}if(temp.next== null){
temp.next= node;}else{
node.next= temp.next;
temp.next= node;}}/**
* 根据no修改信息
*/publicvoidupdateNodeByNo(Node newNode){
Node temp= HeadNode;while(true){if(temp.no== newNode.no){
temp.name= newNode.name;
temp.nickName= newNode.nickName;break;}//最后一个节点if(temp.next== null)thrownewRuntimeException("no错误");
temp= temp.next;}}/**
* 删除节点
*/publicvoiddeletNodeByNo(int no){
Node temp= HeadNode;if(temp.next== null){
System.out.println("链表为空");return;}
Node pre= temp;//前驱指针
temp= temp.next;while(true){if(temp.no== no){
pre.next= temp.next;break;}if(temp.next== null)break;
pre= temp;
temp= temp.next;}}/**
* 遍历当前链表
*/publicvoidshowLinked(){if(HeadNode.next== null){
System.out.println("链表为空");return;}
Node temp= HeadNode.next;while(true){
System.out.println(temp);if(temp.next== null)break;
temp= temp.next;}}}
节点类
/**
* 节点类
*/classNode{publicint no;//编号public String name;public String nickName;public Node next;//指向下一个节点//节点的构造方法publicNode(int no, String name, String nickName){this.no= no;this.name= name;this.nickName= nickName;this.next= null;}@Overridepublic StringtoString(){returnnewStringJoiner(", ", Node.class.getSimpleName()+"[","]").add("no="+ no).add("name='"+ name+"'").add("nickName='"+ nickName+"'").toString();}}
二、双向链表
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
/**
* 链表类
*/classDoublyLinked{private DoubleNode FirstNode=newDoubleNode(0,"");//创建链表时先初始化一个头结点/**
* 最后一个节点后
*
* @param node
*/publicvoidadd(DoubleNode node){
DoubleNode temp= FirstNode;while(temp.getNext()!= null){
temp= temp.getNext();}
temp.setNext(node);
node.setPre(temp);}/**
* 按顺序添加节点
*/publicvoidaddByOrder(DoubleNode node){
DoubleNode temp= FirstNode;while(true){if(temp.getNo()== node.getNo()){
System.out.println("节点已经存在");return;}if(temp.getNo()> node.getNo()){//中间插入
temp.getPre().setNext(node);
node.setPre(temp.getPre());
node.setNext(temp);
temp.setPre(node);break;}if(temp.getNext()== null){//最后一个节点
temp.setNext(node);
node.setPre(temp);break;}
temp= temp.getNext();}}/**
* 遍历链表
*/publicvoidshowLinked(){if(FirstNode.getNext()== null){
System.out.println("链表为空");return;}
DoubleNode temp= FirstNode.getNext();while(true){
System.out.println(temp);if(temp.getNext()== null)break;
temp= temp.getNext();}}/**
* 删除节点
*/publicvoiddeleteNode(int no){if(FirstNode.getNext()== null){
System.out.println("链表为空");return;}
DoubleNode temp= FirstNode.getNext();while(true){if(temp.getNo()== no){
temp.getPre().setNext(temp.getNext());
temp.getNext().setPre(temp.getPre());}if(temp.getNext()== null)break;
temp= temp.getNext();}}/**
* 修改节点信息
*/publicvoidupdateNode(DoubleNode newNode){if(FirstNode.getNext()== null){
System.out.println("链表为空");return;}
DoubleNode temp= FirstNode.getNext();while(true){if(temp.getNo()== newNode.getNo()){
temp.setName(newNode.getName());break;}if(temp.getNext()== null){
System.out.println("没有相关节点");break;}
temp= temp.getNext();}}}
节点类
/**
* 节点类
*/classDoubleNode{privateint no;private String name;private DoubleNode next;//指向后一个节点private DoubleNode pre;//指向前一个节点publicDoubleNode(int no, String name){this.no= no;this.name= name;}publicintgetNo(){return no;}publicvoidsetNo(int no){this.no= no;}public StringgetName(){return name;}publicvoidsetName(String name){this.name= name;}public DoubleNodegetNext(){return next;}publicvoidsetNext(DoubleNode next){this.next= next;}public DoubleNodegetPre(){return pre;}publicvoidsetPre(DoubleNode pre){this.pre= pre;}@Overridepublic StringtoString(){returnnewStringJoiner(", ", DoubleNode.class.getSimpleName()+"[","]").add("no="+ no).add("name='"+ name+"'").toString();}}