Java教程

数据结构学习Java版-链表的基本知识

本文主要是介绍数据结构学习Java版-链表的基本知识，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、单链表介绍

  • 链表是有序的列表；
  • 以节点的方式来存储；
  • 每个节点包含data域，next域：指向下一个节点；
  • 链表的各个节点不一定是连续存放；
  • 链表分为带头节点的和不带头节点的链表；

package 数据结构;

public class SingleLinkedListDemo {
	public static void main(String[] args) {
		//创建节点进行测试
		HeroNode hero1=new HeroNode(1, "宋江", "及时雨");
		HeroNode hero2=new HeroNode(2, "吴用", "智多星");
		HeroNode hero3=new HeroNode(3, "鲁智深", "花和尚");
		HeroNode hero4=new HeroNode(4, "林冲", "豹子头");
		//创建链表
		SingleLinkedList singleLinkedList=new SingleLinkedList();
		//添加节点
//		singleLinkedList.add(hero1);
//		singleLinkedList.add(hero3);
//		singleLinkedList.add(hero2);
//		
//		singleLinkedList.add(hero4);
		//按顺序添加节点
		singleLinkedList.addByOrder(hero4);
		singleLinkedList.addByOrder(hero1);
		singleLinkedList.addByOrder(hero3);
		singleLinkedList.addByOrder(hero2);
		//测试修改节点
		HeroNode newHeroNode=new HeroNode(1, "zhangsan", "法外狂徒");
		singleLinkedList.update(newHeroNode);
		//删除节点
		singleLinkedList.del(1);
		singleLinkedList.del(3);
		//显示节点
		singleLinkedList.list();
	}
}
class SingleLinkedList{
	//定义一个头节点，不存放具体数据
	private HeroNode head=new HeroNode(0, "", "");
	/*
	 * 添加节点到单链表
	 * 当不考虑编号顺序时，找到当前链表的最后节点，然后将最后节点的next指向新的节点
	 */
	public void add(HeroNode heroNode) {
		HeroNode temp=head;//头节点不能动
		while(true) {
			//找到链表的最后
			if(temp.next==null) {
				break;
			}
			//没有找到则将temp后移
			temp=temp.next;
		}
		//将最后节点的next指向新的节点
		temp.next=heroNode;
	}
	//显示链表
	public void list() {
		//先判断是否为空
		if(head.next==null) {
			System.out.println("empty");
			return;
		}
		HeroNode temp=head.next;
		while(true) {
			//退出循环条件
			if(temp.next==null) {
				break;
			}
			System.out.println(temp);
			temp=temp.next;
		}
	}
	public void addByOrder(HeroNode heroNode) {
		HeroNode temp=head;
		boolean flag=false;
		while(true) {
			if(temp.next==null) {
				break;//已到链表的最后
			}
			if(temp.next.no>heroNode.no) {
				break;//位置找到，在temp后面插入
				
			}else if(temp.next.no==heroNode.no) {
				flag=true;//说明编号已经存在
				break;
			}
			temp=temp.next;
		}
		if(flag) {
			System.out.println("编号已存在");
		}else {
			//可以插入到链表中temp的后面
			heroNode.next=temp.next;
			temp.next=heroNode;
		}
	}
	public void update(HeroNode newHeroNode) {
		if(head.next==null) {
			System.out.println("empty");
			return;
		}
		boolean flag=false;
		HeroNode temp=head.next;
		while(true) {
			if(temp.next==null) {
				break;
			}else if(temp.no==newHeroNode.no) {
				flag=true;//找到了要修改的节点
				break;
			}
			temp=temp.next;
		}
		if(flag) {
			temp.name=newHeroNode.name;
			temp.nickname=newHeroNode.nickname;
		}else {
			System.out.println("未找到");
		}
	}
	public void del(int no) {
		HeroNode temp=head;
		boolean flag=false;
		while(true) {
			if(temp.next==null) {
				break;
			}else if(temp.next.no==no) {
				flag=true;//找到待删除节点的前一个节点temp
				break;
			}
			temp=temp.next;
		}
		if(flag) {
			temp.next=temp.next.next;
		}else {
			System.out.println("未找到");
		}
	}
}
//每一个HeroNode对象就是一个节点
class HeroNode{
	public int no;
	public String name;
	public String nickname;
	public  HeroNode next;//指向下一个节点
	//创建构造器
	public HeroNode(int no,String name,String nickname) {
		this.name=name;
		this.no=no;
		this.nickname=nickname;
	}
	//重写toString
	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
	}
	
}

单链表注意事项：

  1. 头节点不能改动，因此引入临时节点temp;
  2. 判断链表是否为空：head.next==null;
  3. 判断是否到达链表尾部：temp.next==null;
  4. 删除节点：要找到待删除节点的前一个节点。

二、双向链表介绍

  1. 单向链表的查找方向只能是一个方向，而双向链表可以向前或则向后查找；
  2. 单链表需要依靠辅助节点来删除节点，而双向链表可以自我删除。
  3. 双向链表与单向链表的最大不同操作是：删除节点。
package 数据结构;

public class DoubleLinkedListDemo {

	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		//创建节点进行测试
				HeroNode2 hero1=new HeroNode2(1, "宋江", "及时雨");
				HeroNode2 hero2=new HeroNode2(2, "吴用", "智多星");
				HeroNode2 hero3=new HeroNode2(3, "鲁智深", "花和尚");
				HeroNode2 hero4=new HeroNode2(4, "林冲", "豹子头");
		//创建链表
				DoubleLinkedList doubleLinkedList=new DoubleLinkedList();
				//添加节点
				doubleLinkedList.add(hero4);
				doubleLinkedList.add(hero1);
				doubleLinkedList.add(hero2);
				doubleLinkedList.add(hero3);
				//显示链表
				doubleLinkedList.list();
				//删除节点
				doubleLinkedList.del(4);
				doubleLinkedList.list();
				
	}

}
//创建一个双向链表
class DoubleLinkedList{
	//定义一个头节点，不存放具体数据
		private HeroNode2 head=new HeroNode2(0, "", "");
		//得到头节点
		public HeroNode2 getHead() {
			return head;
		}
		//添加节点
		public void add(HeroNode2 heroNode) {
			HeroNode2 temp=head;//头节点不能动
			while(true) {
				//找到链表的最后
				if(temp.next==null) {
					break;
				}
				//没有找到则将temp后移
				temp=temp.next;
			}
			//两步：将最后节点的next指向新的节点,新节点的pre指向temp.
			temp.next=heroNode;
			heroNode.pre=temp;
		}
		//修改节点
		public void update(HeroNode2 newHeroNode) {
			if(head.next==null) {
				System.out.println("empty");
				return;
			}
			boolean flag=false;
			HeroNode2 temp=head.next;
			while(true) {
				if(temp.next==null) {
					break;
				}else if(temp.no==newHeroNode.no) {
					flag=true;//找到了要修改的节点
					break;
				}
				temp=temp.next;
			}
			if(flag) {
				temp.name=newHeroNode.name;
				temp.nickname=newHeroNode.nickname;
			}else {
				System.out.println("未找到");
			}
		}
		//删除节点
		public void del(int no) {
			HeroNode2 temp=head.next;//temp是第一个节点
			boolean flag=false;
			while(true) {
				if(temp==null) {
					break;
				}else if(temp.no==no) {
					flag=true;//找到待删除节点
					break;
				}
				temp=temp.next;
			}
			if(flag) {
				temp.pre.next=temp.next;
				//如果是最后一个节点则不需要执行第二句
				if(temp.next!=null) {
					temp.next.pre=temp.pre;
				}
				
			}else {
				System.out.println("未找到");
			}
		}
		//显示链表
		public void list() {
			//先判断是否为空
			if(head.next==null) {
				System.out.println("empty");
				return;
			}
			HeroNode2 temp=head.next;
			while(true) {
				//退出循环条件
				if(temp.next==null) {
					break;
				}
				System.out.println(temp);
				temp=temp.next;
			}
		}
}
//每一个HeroNode对象就是一个节点
class HeroNode2{
	public int no;
	public String name;
	public String nickname;
	public  HeroNode2 next;//指向下一个节点
	public HeroNode2 pre;//指向前一个节点
	//创建构造器
	public HeroNode2(int no,String name,String nickname) {
		this.name=name;
		this.no=no;
		this.nickname=nickname;
	}
	//重写toString
	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
	}
	
}

 

这篇关于数据结构学习Java版-链表的基本知识的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航