代码中有注释方便理解
概述
实现代码
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;
}
}
双向链表的实现代码
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;
}
}
}
应用示例!
问题:有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
如对本文有疑问, 点击进行留言回复!!
利用python将Mysql信息以Excel文件并作为邮件附件发送
springmvc+mybaits+mysql上传表情Incorrect string value: ‘\xF0\x9F\xA4\xB4\xF0\x9F...‘ for
SpringCloud Greenwich集成Seata1.2.0详解说明(原创by ulwfcyvi)
mybatis generator生成代码库 与指定的库不一致 为其他库的同名表
网友评论