当前位置：网站首页>链表API设计
链表API设计
2022-08-10 05:32:00 【cbys-1357】
1.单向链表
单向链表是链表的一种，它由多个结点组成，每个结点都由一个数据域和一个指针域组成，数据域用来存储数据， 指针域用来指向其后继结点。链表的头结点的数据域不存储数据，指针域指向第一个真正存储数据的结点。
代码实现：
public class LinkList<T> implements Iterable<T>{
private Node head;
private int N;
// 结点类(内部类)
private class Node{
// 储存数据
T item;
// 下一个结点
Node next;
public Node(T item,Node next) {
this.item=item;
this.next=next;
}
}
// 构造方法
public LinkList(){
this.head=new Node(null,null);
this.N=0;
}
// 清空链表
public void clear() {
head.next=null;
this.N=0;
}
// 判断链表是否为空
public boolean isEmpty() {
return N==0;
}
// 获取链表的长度
public int length() {
return N;
}
// 获取指定位置i的元素
public T get(int i) {
Node n=head.next;
for(int index=0;index<i;index++) {
n=n.next;
}
return n.item;
}
// 向链表中添加元素
public void insert(T t) {
Node n=this.head;
// 获取链表中最后一个节点
while(n.next!=null) {
n=n.next;
}
Node newNode=new Node(t,null);
n.next=newNode;
N++;
}
// 向链表中指定位置添加元素
public void insert(int i,T t) {
Node pre=this.head;
//找到i位置的前一个节点
for(int index=0;index<i;index++) {
pre=pre.next;
}
// 找到i位置的节点
Node curr=pre.next;
// 创建新节点
Node newNode=new Node(t,curr);
pre.next=newNode;
N++;
}
// 删除指定位置的元素,并返回元素的值
public T remove(int i) {
Node pre=this.head;
for(int index=0;index<i;index++) {
pre=pre.next;
}
Node curr=pre.next;
Node nextNode=curr.next;
pre.next=nextNode;
N--;
return curr.item;
}
// 返回元素t在链表中第一次出现的位置
public int index(T t) {
Node node=this.head;
for(int i=0;node.next!=null;i++) {
node=node.next;
if(node.item==t) {
return i;
}
}
return -1;
}
@Override
public Iterator<T> iterator() {
return new LIterator();
}
private class LIterator implements Iterator{
private Node n;
public LIterator(){
this.n=head;
}
@Override
public boolean hasNext() {
return n.next!=null;
}
@Override
public Object next() {
n=n.next;
return n.item;
}
}
// 整个链表反转
public void reverse() {
if(isEmpty()) {
return;
}
reverse(head.next);
}
// 单个节点之间顺序反转
public Node reverse(Node curr) {
if(curr.next==null) {
head.next=curr;
return curr;
}
Node pre=reverse(curr.next);
pre.next=curr;
curr.next=null;
return curr;
}
}
2.双向链表
双向链表也叫双向表，是链表的一种，它由多个结点组成，每个结点都由一个数据域和两个指针域组成，数据域用 来存储数据，其中
一个指针域用来指向其后继结点，另一个指针域用来指向前驱结点。链表的头结点的数据域不存 储数据，指向前驱结点的指针域值为null，指向后继结点的指针域指向第一个真正存储数据的结点。
代码实现：
public class TowWayList<T> implements Iterable<T>{
private Node head;//首结点
private Node last;//最后一个结点
private int N;
public class Node {
private T item;//储存数据
private Node next;//下一个结点
private Node pre;//上一个结点
public Node(T t,Node pre,Node next) {
this.item=t;
this.next=next;
this.pre=pre;
}
}
// 构造方法
public TowWayList() {
this.head=new Node(null,null,null);
this.last=null;
this.N=0;
}
// 清空链表
public void clear() {
this.head.next=null;
this.head.item=null;
this.head=null;
this.N=0;
}
// 判断链表是否为空
public boolean isEmpty() {
return N==0;
}
// 返回链表的长度
public int length() {
return N;
}
// 获取链表中指定位置的元素
public T get(int i) {
Node n=head.next;
for(int index=0;index<i;index++) {
n=n.next;
}
return n.item;
}
// 向链表的末尾处添加元素
public void insert(T t) {
if(isEmpty()) {
Node newNode=new Node(t,head,null);
last=newNode;
head.next=last;
}else {
Node oldLast=last;
Node newNode=new Node(t,oldLast,null);
oldLast.next=newNode;
last=newNode;
}
N++;
}
// 向链表指定位置i处添加元素
public void insert(int i,T t) {
Node pre=head;
for(int index=0;index<i;i++) {
pre=pre.next;
}
Node curr=pre.next;
Node newNode=new Node(t,pre,curr);
pre.next=newNode;
N++;
}
// 删除链表指定位置i处的元素,并返回指定位置的元素值
public T remove(int i) {
Node pre=head;
for(int index=0;index<i;index++) {
pre=pre.next;
}
Node curr=pre.next;
Node nextNode=curr.next;
pre.next=nextNode;
return curr.item;
}
// 返回元素t在链表中第一次出现的位置
public int indexOf(T t) {
Node n=head;
for(int i=0;n.next!=null;i++) {
n=n.next;
if(n.item.equals(t)) {
return i;
}
}
return -1;
}
// 获取第一个元素
public T getFirst() {
if(isEmpty()) {
return null;
}
return head.next.item;
}
// 获取最后一个元素
public T getLast() {
if(isEmpty()) {
return null;
}
return last.item;
}
@Override
public Iterator<T> iterator() {
return new TIterator();
}
private class TIterator implements Iterator<T>{
private Node n;
public TIterator() {
this.n=head;
}
@Override
public boolean hasNext() {
return n.next!=null;
}
@Override
// 正向遍历
public T next() {
n=n.next;
return n.item;
}
}
}
3.应用
1.快慢指针
快慢指针指的是定义两个指针，这两个指针的移动速度一块一慢，以此来制造出自己想要的差值，这个差值可以然 我们找到链表上相应的结点。一般情况下，快指针的移动步长为慢指针的两倍
1.中间值问题
原理:
利用快慢指针，我们把一个链表看成一个跑道，假设a的速度是b的两倍，那么当a跑完全程后，b刚好跑一半，以 此来达到找到中间节点的目的。
代码实现:
public class FastSlowTest {
public static void main(String[] args) {
Node<String> first=new Node<String>("aa",null);
Node<String> second=new Node<String>("bb",null);
Node<String> third=new Node<String>("cc",null);
Node<String> forth=new Node<String>("dd",null);
Node<String> fifth=new Node<String>("ee",null);
Node<String> six=new Node<String>("ff",null);
Node<String> seven=new Node<String>("gg",null);
first.next=second;
second.next=third;
third.next=forth;
forth.next=fifth;
fifth.next=six;
six.next=seven;
String mid=getMid(first);
System.out.println("中间值:"+mid);
}
private static boolean isCircle(Node<String> first) {
Node<String> fast=first;
Node<String> Slow=first;
while(fast!=null&&fast.next!=null) {
fast=fast.next.next;
Slow=Slow.next;
if(fast.equals(Slow)) {
return true;
}
}
return false;
}
private static String getMid(Node<String> first) {
Node<String> fast=first;//快指针
Node<String> Slow=first;//慢指针
while(fast!=null&&fast.next!=null) {
fast=fast.next.next;
Slow=Slow.next;
}
return Slow.item;
}
private static class Node<T>{
T item;
Node next;
public Node(T item,Node next) {
this.item=item;
this.next=next;
}
}
}2.单向链表是否有环问题
原理:
使用快慢指针的思想，还是把链表比作一条跑道，链表中有环，那么这条跑道就是一条圆环跑道，在一条圆环跑道 中，两个人有速度差，那么迟早两个人会相遇，只要相遇那么就说明有环。
代码实现:
public class FastSlowTest02 {
public static void main(String[] args) {
Node<String> first=new Node<String>("aa",null);
Node<String> second=new Node<String>("bb",null);
Node<String> third=new Node<String>("cc",null);
Node<String> forth=new Node<String>("dd",null);
Node<String> fifth=new Node<String>("ee",null);
Node<String> six=new Node<String>("ff",null);
Node<String> seven=new Node<String>("gg",null);
first.next=second;
second.next=third;
third.next=forth;
forth.next=fifth;
fifth.next=six;
six.next=seven;
// 产生环
seven.next=third;
//判断链表是否有环
boolean circle=isCircle(first);
System.out.println("first的链表是否有环:"+circle);
}
private static boolean isCircle(Node<String> first) {
Node<String> fast=first;
Node<String> Slow=first;
while(fast!=null&&fast.next!=null) {
fast=fast.next.next;
Slow=Slow.next;
if(fast.equals(Slow)) {
return true;
}
}
return false;
}
private static String getMid(Node<String> first) {
Node<String> fast=first;//快指针
Node<String> Slow=first;//慢指针
while(fast!=null&&fast.next!=null) {
fast=fast.next.next;
Slow=Slow.next;
}
return Slow.item;
}
//内部类
private static class Node<T>{
T item;
Node next;
public Node(T item,Node next) {
this.item=item;
this.next=next;
}
}
}
3.有环链表入口问题
原理:
当快慢指针相遇时，我们可以判断到链表中有环，这时重新设定一个新指针指向链表的起点，且步长与慢指针一样 为1，则慢指针与“新”指针相遇的地方就是环的入口。
代码实现：
public class CircleListInTest {
public static void main(String[] args) {
// TODO 自动生成的方法存根
// 构建节点
Node<String> first=new Node<String>("aa",null);
Node<String> second=new Node<String>("bb",null);
Node<String> third=new Node<String>("cc",null);
Node<String> forth=new Node<String>("dd",null);
Node<String> fifth=new Node<String>("ee",null);
Node<String> six=new Node<String>("ff",null);
Node<String> seven=new Node<String>("gg",null);
// 构建链表
first.next=second;
second.next=third;
third.next=forth;
forth.next=fifth;
fifth.next=six;
six.next=seven;
// 产生环
seven.next=third;
// 判断链表是否有环
if(isCircle(first)) {
Node<String> entrance=getEntrance(first);
System.out.println("first链表环的入口节点元素:"+entrance.item);
}else {
System.out.println("该链表未形成环");
}
}
private static Node<String> getEntrance(Node<String> first) {
Node<String> fast=first;
Node<String> slow=first;
Node<String> tem=null;
// 遍历节点，先找到环(快慢指针相遇),准备临时指针，指向链表的首节点，继续遍历，直至那个慢指针和临时指针相遇，那个相遇的地方就是环的入口节点（要用数论来证明）
while(fast!=null&&fast.next!=null) {
fast=fast.next.next;
slow=slow.next;
if(fast.equals(slow)) {
tem=first;
continue;
}
if(tem!=null) {
tem=tem.next;
if(tem.equals(slow)) {
break;
}
}
}
return tem;
}
private static boolean isCircle(Node<String> first) {
// TODO 自动生成的方法存根
Node<String> fast=first;
Node<String> Slow=first;
while(fast!=null&&fast.next!=null) {
fast=fast.next.next;
Slow=Slow.next;
if(fast.equals(Slow)) {
return true;
}
}
return false;
}
private static class Node<T>{
T item;
Node next;
public Node(T item,Node next) {
this.item=item;
this.next=next;
}
}
} 4. 约瑟夫问题
问题描述：
传说有这样一个故事，在罗马人占领乔塔帕特后，39 个犹太人与约瑟夫及他的朋友躲到一个洞中，39个犹太人决 定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，第一个人从1开始报数，依次往 后，如果有人报数到3，那么这个人就必须自杀，然后再由他的下一个人重新从1开始报数，直到所有人都自杀身亡 为止。然而约瑟夫和他的朋友并不想遵从。于是，约瑟夫要他的朋友先假装遵从，他将朋友与自己安排在第16个与 第31个位置，从而逃过了这场死亡游戏。
问题转换：
41个人坐一圈，第一个人编号为1，第二个人编号为2，第n个人编号为n。
1.编号为1的人开始从1报数，依次向后，报数为3的那个人退出圈；
2.自退出那个人开始的下一个人再次从1开始报数，以此类推；
3.求出最后退出的那个人的编号。
解题思路：
1.构建含有41个结点的单向循环链表，分别存储1~41的值，分别代表这41个人；
2.使用计数器count，记录当前报数的值；
3.遍历链表，每循环一次，count++；
4.判断count的值，如果是3，则从链表中删除这个结点并打印结点的值，把count重置为0；
代码实现:
public class JosephTest {
public static void main(String[] args) {
// TODO 自动生成的方法存根
// 第一个结点（元素）
Node<Integer> first=null;
// 记录前一个结点
Node<Integer> pre=null;
// 1.构建循环链表
for(int i=1;i<=41;i++) {
if(i==1) {
first=new Node(i,null);
pre=first;
continue;
}
Node<Integer> newNode=new Node(i,null);
pre.next=newNode;
pre=newNode;
if(i==41) {
pre.next=first;//构建循环链表，让最后一个结点指向第一个结点
}
}
int count=0;
Node<Integer> n=first;
Node<Integer> before=null;
while(n!=n.next) {
count++;//4.判断count的值，如果是3，则从链表中删除这个结点并打印结点的值，把count重置为0；
if(count==3) {
// 删除当前结点
before.next=n.next;
System.out.print(n.item+",");
count=0;
n=n.next;
}else {
before=n;
n=n.next;
}
}
System.out.print(n.item);//打印剩余的最后那个人
}
private static class Node<T> {
T item;
Node next;
public Node(T item,Node next) {
this.item=item;
this.next=next;
}
}
}
边栏推荐
猜你喜欢
随机推荐
Knowledge Distillation Thesis Learning
Link reading good article: What is the difference between hot encrypted storage and cold encrypted storage?
tinymce富文本编辑器
R语言：修改chart.Correlation（）函数绘制相关性图——完美出图
集合 Map
redis常见的面试题
图片批量添加水印批量加背景缩放批量合并工具picUnionV4.0
三维点云分割
智能合约和去中心化应用DAPP
ResNet的基础：残差块的原理
Batch add watermark to pictures batch add background zoom batch merge tool picUnionV4.0
小程序学习笔记：小程序组件间通信方式
Operation table Function usage
Chain Reading Good Article: Jeff Garzik Launches Web3 Production Company
Chained Picks: Starbucks looks at digital collectibles and better engages customers
matlab中的常用的类型转换
cesium 监听地图缩放或放大来控制地图上添加的内容是否展示
Mockito基本使用指南
String常用方法
PCL点云滤波