java实现单链表、双链表、循环链表 （数据结构）

单向链表

代码中有注释方便理解

概述

1. 单向的，只能从头到尾
2. 每一个节点知道下一个节点的，却不知道上一个节点

实现代码

 package customLinkedList;

public class LinkedList
{
	// ***************************单链表************************************//
 	
	public static class GenericNode{
		Object value ; // 数据
		GenericNode next; // 下一个位置
	}
	
	// 有头链表
	GenericNode head = new GenericNode();
	
	// 添加
	public void add( Object value)
	{
		GenericNode tail = head ; // 尾巴位置
		while(tail.next != null)
			tail = tail.next; // 找到尾巴位置
		
		// 插入数据
		GenericNode node = new GenericNode();
		node.value = value; // 绑定数据
		tail.next = node;
	}
	
	// 查找节点并删除 如果有多个相同的节点也删除
	public void remove(Object value)
	{
		GenericNode node = head;
		while(node.next!= null)
		{
			if(node.next.value.equals(value))
				node.next = node.next.next; // 覆盖前面那个 
			else
				node= node.next;  // 否则就下一个
		}
	}
	// 得到个数
	public int size()
	{
		int count = 0;
		GenericNode node = head;
		while(node.next!=null)
		{
			count ++ ;
			node = node.next;
		}
		return count;
	}
}

双向链表

概述

1. 双向链表 就是指向上一个节点，也指向下一个节点。
2. 可以从后面开始往前面查找
3. 也可以从前面开始往后面查找

双向链表的实现代码

 package customLinkedList;

public class DoublyLinkedList
{
	// *************** 双向链表的实现 ***************************//
	 
	public static class GenericNode{
		Object value ;
		GenericNode prve;
		GenericNode next;
		@Override
		public String toString()
		{
			return (value==null)?"NULL":value.toString();
		}

	}
		
	public GenericNode tail = new GenericNode(); // 固定头尾节点
	public GenericNode head = new GenericNode(); 
	
	public DoublyLinkedList()
	{
		tail.prve = head; // 连接两个点
		head.next = tail;
	}
	
	public void add(Object value)
	{
		// 一个新的节点
		GenericNode node =new  GenericNode();   
		node.value = value;
		
		tail.prve.next = node; // 最后一个节点 的上一个节点的下一个等于 新节点
		node.next = tail; // 新节点的下一个 等于尾巴节点 
		node.prve = tail.prve; // 新节点的上一个等于 尾巴的上一个节点 
		tail.prve = node; // 尾巴的上一个节点等 新节点
	}
	
	
	// 删除
	public void remove(Object value)
	{
		GenericNode node = head.next;
		while(node.next!=null)
		{
			if(node.value.equals(value))
			{
				node.prve.next =node.next; // 重新定义新的节点信息 当前节点的上一个节点 的下一个 等于 当前节点下一个
				node.next.prve =node.prve; // 当前节点的下一个的上一个节点 等当前节点的上一个  因为要链接上
			}
			node = node.next;
		}
	}
	
}

循环链表

概述

1. 就是将链表中的头节点 与 尾结点连接起来 ， 形成一个循环的链子

2. 循环链表可以是单链表，也可以是双链表

应用示例！

问题：有N个同学围成一个圈，循环报数1.2.3.
报数报到3的同学退出，下一个接着从1开始报数…
求：最后剩下的同学是哪位 ？
（实现代码在底部 ）

循环链表的实现代码（本次实现 采用双链表 ）

package customLinkedList;

public class LoopLinkedList 
{
	// ********************* 循环链表的实现 *******************************// 
	
		public static class GenericNode{
			Object value ;
			GenericNode prve;
			GenericNode next;
		}
		
		// 采用无头链表
		public GenericNode head =null; // 头部
		public GenericNode tail =null; // 尾巴
		
		public void add(Object value)
		{
			// 一个新的节点
			GenericNode node =new  GenericNode();   
			node.value = value;
			
			// 如果是第一个插入的数据
			if(head == null)
			{
				head = node;
				tail = node;
				head.next = tail.prve = node;
			}
			
			else
			{
				// 将链子连接起来
				tail.next = node; // 尾节点的下一个是新节点 
				node.next = head; // 新节点的下一个是头节点
				head.prve = node; // 头结点的上一个是新节点
				node.prve = tail; // 新节点的上一个节点是尾结点
				
				tail = node; // 记录这个节点 否则会被覆盖 
			}
			
		}
		
		// 链表的长度
		public int length()
		{
			GenericNode node = head; // 头节点
			int count = 0;
			while(true)
			{
				count ++;
				if(node.next == this.head) 
					break;
				node = node.next;
			}
			return count;
		}
		
		// 删除
		public void remove(Object value)
		{
			GenericNode node = head.next;
			while(node.next!=node)
			{
				if(node.value.equals(value))
				{
					node.prve.next =node.next; // 重新定义新的节点信息 当前节点的上一个节点 的下一个 等于 当前节点下一个
					node.next.prve =node.prve; // 当前节点的下一个的上一个节点 等当前节点的上一个  因为要链接上
					break;
				}
				node = node.next;
			}
		}
		
	}

报数游戏的实现代码（结构采用循环链表,以上代码↑）

// 测试循环链表 
	public static void TestLoopList() {
		
		// 插入数据 （代表同学信息）
		LoopLinkedList loopList = new LoopLinkedList();
		loopList.add(1);
		loopList.add(2);
		loopList.add(3);
		loopList.add(4);
		loopList.add(5);
		loopList.add(6);
		loopList.add(7);
		
		GenericNode newNode = loopList.head;  // 第一个数
		// ********************** 使用循环链表 做一个报数游戏 ********************** // 
		System.out.println("游戏规则:一共七个人( 1,2,3,4,5,6,7 )  数到三的就退出 然后重新数");
		int count = 0;
		// 等于自己就停止循环 (循环链表 想象成一个链子 转了一圈是不是回到自己的这个位置)
		while(newNode.next != newNode)
		{
			count++; 
			// 报数到三的人 将退出游戏
			if(count == 3)
			{
				System.out.println("三次循环结束!"+"当轮退出："+newNode.value);
				newNode.prve.next = newNode.next; // 当前节点的上一节点的下一个节点 应该指向当前节点的下一个节点
				newNode.next.prve = newNode.prve; // 当前节点的下一个节点的上一个节点 应该指向当前节点的上一个节点
				
				count = 0; // 重新报数

				// 如果是当前节点 是 head 就让下一个人当head
				if(newNode == loopList.head)
				{
					loopList.head = newNode.next;
				}
			}
			// 切换下一个人
			newNode= newNode.next;
		}
		System.out.println("最后胜出:"+newNode.value);
			
		
	}

本文地址：https://blog.csdn.net/wumingxiaozuzha/article/details/107596546