《链表》——单向链表和双向链表(Java)

完整的代码地址为:github  点击查看

单链表

《链表》——单向链表和双向链表(Java)

单链表包括数据域和指向下一个节点的指针域,其结构如上图所示

首先定义一个数据类:

class DATA{           //定义链表的一个节点
	String key;           //节点的关键字
	String name;
	int age;
}

定义一个单向链表类(包括以下几种方法):

1:在尾部添加节点

2:在头部添加节点

3:查找节点

4:插入节点

5:删除节点

6:计算链表长度

7:显示所有节点对应的代码如下

public class Link {     //定义链表结构
	
	DATA nodeData = new DATA();     //声明一个节点
	Link nextNode;                                //指向下一个节点的指针
	
	
	//添加节点
	Link linkAddEnd(Link head, DATA nodeData)
	{
		Link node, hTemp;
		if( (node = new Link()) ==null)        //如果内存空间分配失败,则返回为空
		{
			System.out.println("内存空间分配失败!");
			return null;
		}
		else
		{
			node.nodeData = nodeData;
			node.nextNode = null;
			if(head == null)      //如果头节点为空,则把当前节点赋给head,并返回
			{
				head = node;
				return head;
			}      
			hTemp = head;       //如果头节点不为空
			while(hTemp.nextNode!=null)        //查找链表的末尾
			{
				hTemp = hTemp.nextNode;
			}
			hTemp.nextNode = node;
			return head;
		}
	}
	
	//插入头节点
	Link linkAddFirst(Link head, DATA nodeData)
	{
		Link node;
		if((node=new Link()) == null ) //如果内存空间分配失败,则返回为空
		{
			System.out.println("内存分配失败");
			return null;
		}
		else
		{
			node.nodeData = nodeData;
			node.nextNode = head;
			head = node;
			return head;
		}
	}
	
	//查找节点
	Link linkFindNode(Link head, String key)
	{
		Link hTemp;
		hTemp = head;
		while(hTemp!=null)       //若节点有效,则进行查找
		{
			if(hTemp.nodeData.key.compareTo(key) == 0) //若节点的关键字与传入的关键字相同
			{
				return hTemp;
			}
			hTemp = hTemp.nextNode;     //处理下一个节点
		}
		return null;	
	}
	
	//插入节点
	Link linkInsertNode(Link head, String findKey,DATA nodeData)
	{
		Link node,hTemp;
		if((node = new Link() ) == null ) //分配内存失败,则返回
		{
			System.out.println("分配内存失败...");
			return null;
		}
		node.nodeData = nodeData;      //保存当前集节点信息
		hTemp = linkFindNode(head, findKey);      //查找要插入的节点
		if(hTemp != null)
		{
			node.nextNode = hTemp.nextNode;
			hTemp.nextNode = node;
		}
		else
		{
			System.out.println("未找到正确的插入位置.........");
		}
		return head;          //返回头引用
	}
	
	//删除节点
	int linkDeleteNode(Link head, String key)
	{
		Link node,hTemp;
		hTemp = head;
		node = head;
		while(hTemp != null )
		{
			if(hTemp.nodeData.key.compareTo(key) == 0)   //若找到关键字,则删除
			{
				node.nextNode = hTemp.nextNode;
				hTemp = null;
				return 1;
			}
			else               //跳到下一个节点
			{
				node = hTemp;
				hTemp = hTemp.nextNode;
			}
		}
		return 0;
	}
	
	//计算链表长度
	int linkLength(Link head)
	{
		Link hTemp;
		hTemp = head;
		int num = 0;
		while(hTemp!=null)
		{
			num ++ ;
			hTemp = hTemp.nextNode;
		}
		return num;	
	}
	
	//显示所有节点
	void linkShow(Link head)
	{
		Link hTemp;
		DATA nodeData;
		hTemp = head;
		System.out.printf("当前链表共有 %d 个节点,链表所有的数据如下:\n" , linkLength(head));
		while(hTemp!=null)
		{
			nodeData = hTemp.nodeData;     //获取当前的节点数据
			System.out.printf("节点(%s %s  %d)\n",nodeData.key,nodeData.name,nodeData.age);
			hTemp = hTemp.nextNode;
		}
	}
	
}


编写测试类:

public class linkTest {

	public static void main(String[] args) {
		Link node = null , head=null;
		Link link = new Link();
		String key, findKey;
		Scanner input = new Scanner(System.in);
		
		System.out.printf("链表测试开始,先输出链表中的数据,格式为:关键字	姓名	年龄\n");
		do
		{                        //循环插入节点,知道输入的key 为0 结束
			DATA nodeData = new DATA();
			nodeData.key = input.next();
			if(nodeData.key.equals("0"))
			{
				break;
			}
			else
			{
				nodeData.name = input.next();
				nodeData.age = input.nextInt();
				head = link.linkAddEnd(head, nodeData);  //在链表尾部添加节点
			}
		}while(true);
		link.linkShow(head);     //显示所有节点
		
		System.out.printf("\n演示插入节点,输入插入位置的关键字:");
		findKey = input.next();                //输入插入的关键字
		System.out.println("输入插入节点的数据(关键字 姓名 年龄)");
		DATA nodeData = new DATA();              //输入节点的元素值
		nodeData.key = input.next();
		nodeData.name = input.next();
		nodeData.age = input.nextInt();
		head = link.linkInsertNode(head, findKey, nodeData);           //调用插入函数
		link.linkShow(head);    //显示所有节点
		
		System.out.println("演示删除节点,输入要删除的关键字:");
		key = input.next();
		link.linkDeleteNode(head, key);         //调用删除节点的函数
		link.linkShow(head);                     //显示所有节点
		
		System.out.println("演示在链表中差找,输入要查找的关键字:");
		key = input.next();
		node = link.linkFindNode(head, key);  //调用查找函数,返回节点引用
		if(node!=null)
		{
			nodeData = node.nodeData;         //获取节点的数据
			System.out.printf("关键字 %s 对应的节点数据为 (%s %s %s)\n", key,nodeData.key,nodeData.name,nodeData.age);
		}
		else
		{
			System.out.printf("在链表中为查找的为%s 的关键字 \n" , key);
		}
		
		
	}
	
}


双向链表

链结点的结构:

┌────┬────┬────────┐

│data│next│previous│

└────┴────┴────────┘

结构图如下:

《链表》——单向链表和双向链表(Java)


package Link;

import java.util.Scanner;

class Data{           //定义链表的一个节点
	String key;           //节点的关键字,唯一
	String name;
	int age;
}

public class DoubleLink {

	
	int flag; //输入选择值
	Scanner scan = new Scanner(System.in);
	Data data = new Data();
	DoubleLink nextNode;  //后继节点
	DoubleLink priorNode;    //前驱节点
	
	//链表添加节点
	DoubleLink addNode(DoubleLink head, String priorKey, String nextKey, Data nodeData){
		
		DoubleLink node=null, htemp=null;
		if((node = new DoubleLink()) == null)
			System.out.println("内存空间分配失败");
		if(head== null)        //如果head为空
		{
			System.out.println("当前链表为空,是否将当前节点当作头节点?\n0:否\t1:是");
			
			node.data=nodeData;
			node.nextNode=null;
			node.priorNode=null;
			flag = scan.nextInt();
			switch(flag)
			{
			case 0:
				break;
			case 1:
				head=node;
				break;
			default:
					System.out.println("你输入的数据不合法");;
			}
		}       //如果head不为空
		else{
			if(linkFindNode(head, priorKey,nextKey,nodeData))
				System.out.println("插入成功");
			else
				System.out.println("插入失败(原因可能是你输入的前驱和后继即诶但均不存在)");
		}
					
		return head;
	}

	//查找并插入节点
	boolean linkFindNode(DoubleLink head, String priorKey, String nextKey,Data nodeData) {
		// TODO Auto-generated method stub
		DoubleLink htemp=null,node=null;
		
		if( (node = new DoubleLink()) == null )
		{
			System.out.println("内存分配失败");
			return false;
		}
		//将传进来的值赋值给node
		node.data = nodeData;
		node.nextNode = null;
		node.priorNode=null;
		//两大类情况
		htemp = head;
		while(htemp != null)
		{
			if(htemp.data.key.equals(priorKey)) //前驱节点存在
			{
				if(htemp.nextNode == null)     //该节点的后继节点为空,说明该节点为头节点
				{
					System.out.println("你输入的后继节点不存在,前驱节点为头节点,是否插入在其后面?\n 1:是 \t 0 :否 ");
					flag = scan.nextInt();
					if(flag == 0)
						break;
					else if(flag==1)
					{
						htemp.nextNode = node;       //将查找到的节点的后继节点指向node
						node.nextNode = null;
						node.priorNode = htemp;
						
						return true;
					}
					else
						System.out.println("你输入的数字不合法!!!");
				}
				else             //后继节点不为空
				{
					if(htemp.nextNode.data.key.equals(nextKey))            //存在的后继节点与nextKey相同。相同执行if
					{
						node.nextNode = htemp.nextNode;
						htemp.nextNode.priorNode = node;
						
						htemp.nextNode = node;
						node.priorNode = htemp;
						return true;
					
					}
					else         //不同执行else
					{
						htemp = htemp.nextNode; //若当前节点没找到,遍历下一个节点
					}
				}
			}
			else //前驱节点不存在,后驱节点存在
			{
				if(htemp.data.key.equals(nextKey))      //如果当前节点与nextKey相同
				{
					if(htemp.nextNode==null)  //如果后继节点为空,即当前节点为尾节点
					{
						System.out.println("你输入的前驱节点不存在,后继节点为头节点,是否插入在其前面?\n 1:是 \t 0 :否 ");
						flag = scan.nextInt();
						if(flag == 0)
							break;
						else if(flag==1)
						{
							htemp.priorNode = node;
							node.nextNode = htemp;
							
							node.priorNode=null;
							return true;
						}
						else
							System.out.println("你输入的数字不合法!!!");
					}
					else //如果当前节点的后继节点不为空,则执行下一个节点
					{
						htemp = htemp.nextNode; //若当前节点没找到,遍历下一个节点
					}
				}
				else
					htemp = htemp.nextNode; //若当前节点没找到,遍历下一个节点
			}
		}
		return false;
	}
	
	//输出节点
	public void OutputLinkNode(DoubleLink head)
	{
		if(head == null)
			System.out.println("当前链表为空");
		else{
			System.out.println("输入的链表数据如下:");
			DoubleLink htemp;
			htemp = head;
			while(htemp!=null)
			{
				System.out.println(htemp.data.key + "\t" + htemp.data.name + "\t" + htemp.data.age);
				htemp= htemp.nextNode;
			}
		}
		System.out.println();
	}
	
	//输出链表的深度
	int LinkDepth(DoubleLink head)
	{
		int sum = 0;
		DoubleLink htemp = head;
		while(htemp!=null)
		{
			sum ++;
			htemp = htemp.nextNode;
		}
		return sum;
	}
	
	//查找节点
	DoubleLink FindLink(DoubleLink head, String findKey)
	{
		DoubleLink htemp=head;
		while(htemp!=null)
		{
			if(htemp.data.key.equals(findKey))
				return htemp;
			htemp = htemp.nextNode;
		}
		return null;
	}
	
	//删除节点
	DoubleLink DeleteNode(DoubleLink head, String deleteKey)
	{
		DoubleLink htemp = head;
		while(htemp!=null)
		{
			if(htemp.data.key.equals(deleteKey))
			{
				if(htemp.priorNode==null)  //如果是头节点
				{
					return htemp.nextNode;
				}
				else if (htemp.nextNode==null)     //如果是尾节点
				{
					htemp.priorNode.nextNode=null;
					htemp.priorNode=null;
					return head;
				}
				else //如果是中间
				{
					htemp.priorNode.nextNode=htemp.nextNode;
					htemp.nextNode.priorNode = htemp.priorNode;
					return head;
				}
			}
			else
				htemp = htemp.nextNode;
		}	
		System.out.println("你要删除的节点不存在!");
		return head;
	}
	
}

测试实现:

package Link;

import java.util.Scanner;

public class DoubleLinkTest {

	public static void main(String[] args) {
		
		DoubleLink node=null, head=null;
		DoubleLink dlink = new DoubleLink(); //声明一个双向链表对象
		Scanner scan  = new Scanner(System.in);
		
		System.out.println("双向链表测试开始....");
		do{
			System.out.println("请输入插入节点的关键字,姓名和年龄,格式为:关键字	姓名	年龄");
			Data data = new Data();
			data.key = scan.next();
			data.name = scan.next();
			data.age = scan.nextInt();

			if(data.key.contains("0"))  //循环插入节点,直到插入的为0时结束
				break;
			else
			{
				System.out.println("请输入插入节点的前驱节点和后继节点,格式为 前驱节点  后继节点");
				String priorKey = scan.next();
				String nextKey = scan.next();
				
				head = dlink.addNode(head, priorKey, nextKey, data);   //添加节点 
				dlink.OutputLinkNode(head);   //输出链表
			}
		}while(true);
		
		//输出链表的深度
		System.out.println("该链表的深度为:" + dlink.LinkDepth(head));
		
		//查找链表中的某个节点
		System.out.println("请输入要查找的节点的关键字...");
		String findKey = scan.next();
		node = dlink.FindLink(head, findKey);
		 if(node==null)
			 System.out.println("你所查找的节点不存在!");
		 else
			 System.out.println("该节点的值为:" + node.data.key + "\t" + node.data.name + "\t" + node.data.age);
		
		 //删除节点值
		 System.out.println("请输入要删除的节点的关键字...");
		 String deleteKey = scan.next();
		 node =  dlink.DeleteNode(head, deleteKey);
		 if(node == null)
			 System.out.println("删除节点后的链表为空,其深度为:" + 0);
		 else
		 	{
				 System.out.println("删除后的链表为:");
				 dlink.OutputLinkNode(head);
				 System.out.println("删除节点后链表的深度为:" + dlink.LinkDepth(head));
		 	}
	}
}

结果展示

《链表》——单向链表和双向链表(Java)《链表》——单向链表和双向链表(Java)


上一篇:2011年全国软件大赛模拟题及参考答案(Java本科组)


下一篇:阿里云Centos7.6上面部署基于redis的分布式爬虫scrapy-redis将任务队列push进redis