Java实现双向循环链表
作者:I like study. 发布时间:2023-11-08 04:14:40
标签:java,链表
双向循环链表定义
相比于单链表,有两个指针,next指针指向下一个结点,prior指针指向上一个结点,最后一个结点的next指针指向头结点,头结点的prior指针指向最后一个结点
代码实现:
我们对单链表的实现加以修改
package algorithm.datastructure.doublelinkedlist;
import java.util.NoSuchElementException;
/**
* 双向循环链表
* 两个指针,next指针指向下一个结点,prior指针指向上一个结点,最后一个结点的next指针指向头结点,
* 头结点的prior指针指向最后一个结点
* */
public class LinkedList {
private Node head;//头节点
private int size;//链表长度
static private class Node{
private int data;//数据
private Node next;//下一个结点
private Node prior;//上一个结点
public Node(){
}
public Node(int data){
this.data=data;
}
private Node(int data,Node next){
this.data=data;
this.next=next;
}
public Node(Node prior,int data,Node next){
this.prior=prior;
this.data=data;
this.next=next;
}
}
//初始化空链表
public LinkedList(){
//head=null;
}
//添加元素
public Boolean add(int element){
linkLast(element);
return true;
}
//在某个位置之前添加元素
public Boolean add(int index,Integer element){
checkPositionIndex(index);
if (index==size){
linkLast(element);
} else {
linkBefore(element,node(index));
}
return true;
}
//根据下标获取元素
public int get(int index){
checkElementIndex(index);
return node(index).data;
}
//获取第一个元素
public Integer getFirst(){
Node f=head;
if (f==null){
throw new NoSuchElementException();
} else {
return f.data;
}
}
//获取最后一个元素
public Integer getLast(){
if (size==0){
throw new NoSuchElementException();
}
return head.prior.data;
}
//删除第一个元素
public Integer removeFirst(){
Node f=head;
if (f==null){
throw new NoSuchElementException();
} else {
return unlink(head);
}
}
//删除最后一个元素
public Integer removeLast(){
if (size==0){
throw new NoSuchElementException();
}
int index=size-1;
return unlink(node(index));
}
//根据索引删除元素
public Integer remove(int index){
checkElementIndex(index);
return unlink(node(index));
}
//销毁链表
public void destroyList(){
clearList();
}
//将链表置为空表
public void clearList() {
for (Node p=head;p!=null;){
Node next=p.next;//记录下一个结点
p=null;//删除当前结点
p=next;//指向下一个结点
}
size=0;
head=null;
}
//遍历链表
public void traverseList(Boolean isReverseVisited){
if (!isEmpty()){
if (!isReverseVisited){
for (Node p=head;p!=head.prior;p=p.next){
System.out.println(p.data);
}
System.out.println(head.prior.data);
} else {
for (Node p=head.prior;p!=head;p=p.prior){
System.out.println(p.data);
}
System.out.println(head.data);
}
}
}
//返回链表元素个数
public int size(){
return size;
}
public Boolean isEmpty(){
return size==0;
}
/**双向链表插入一个结点,要改变的指针如下:
*
*(1)前一个结点的next指针
*(2)后一个结点的prior指针
*(3)新创建的结点的prior指针和next指针
* */
//尾部添加结点
private void linkLast(int element){
if (size==0){//没有结点时
head=new Node(element);
head.next=head;
head.prior=head;
size++;
} else {
//得到最后一个结点
Node oldTail=head.prior;
//new新的尾结点 newTail
//newTail的前一个结点设置为旧的尾结点,
//newTail的后一个结点指向head
Node newTail=new Node(oldTail,element,head);
//head的下一个结点指向newTail
head.prior=newTail;
//旧的尾结点的下一个结点指向新的尾结点
oldTail.next=newTail;
size++;
}
}
//在某结点之前插入结点
private void linkBefore(int element,Node node){
if (node==null){
linkLast(element);
} else {
Node p=head;
if (node.data==p.data){
Node q=p.prior;
Node newNode=new Node(q,element,p);
q.next=newNode;
p.prior=newNode;
size++;
} else {
for (p=p.next;p!=head;){
if (node.data==p.data){
Node q=p.prior;
Node newNode=new Node(q,element,p);
q.next=newNode;
p.prior=newNode;
size++;
}
p=p.next;
}
}
}
}
/*
* 双向链表删除一个结点:
* (1)找到该结点
* (2)找到该结点的前一结点(prior)p和下一结点(next)q
* (3)p的next指针指向q,q的prior指针指向p
* (4)如果是删除的是头结点,指明当前头结点
* */
//删除结点
private Integer unlink(Node node){
Integer deleteNodeData=node.data;
Node p=null,q=null;
if (deleteNodeData==head.data){//该结点为头结点
Node cur=head;
p=head.prior;
q=head.next;
p.next=q;
q.prior=p;
head=q;
cur=null;
size--;
} else {
Node m;
for (m=head.next;m!=head;){
if (m.data==deleteNodeData){
p=m.prior;
q=m.next;
p.next=q;
q.prior=p;
m=null;
size--;
break;
}
m=m.next;
}
}
return deleteNodeData;
}
//数组下标是否越界
private Boolean isElementIndex(int index){
return index>=0&&index<size;
}
//插入位置是否越界
public Boolean isPositionIndex(int index){
return index>=0&&index<=size;
}
//检验下标是否越界,抛出异常
private void checkElementIndex(int index){
if(!isElementIndex(index)){
try {
throw new IndexOutOfBoundsException("下标越界");
} catch (Exception e) {
e.printStackTrace();
}
}
}
//检验插入下标是否越界,抛出异常
private void checkPositionIndex(int index){
if(!isPositionIndex(index)){
try {
throw new IndexOutOfBoundsException("下标越界");
} catch (Exception e) {
e.printStackTrace();
}
}
}
//返回指定位置的元素
private Node node(int index){
int nowIndex = 0;
if(size>0){
for (Node p=head;p!=head.prior;){
if (nowIndex==index){
return p;
}
p=p.next;
nowIndex++;
}
if (nowIndex==index){
return head.prior;
}
}
return null;
}
public static void main(String[] args) {
java.util.LinkedList linkedList0=new java.util.LinkedList();
linkedList0.add(6);
linkedList0.remove(0);
linkedList0.size();
linkedList0.peek();
//linkedList0.getFirst();
linkedList0.clear();
//测试
LinkedList linkedList=new LinkedList();
linkedList.add(2);
linkedList.add(3);
linkedList.add(5);
linkedList.add(7);
linkedList.add(1);
linkedList.add(33);
linkedList.add(4,0);
linkedList.add(3,1);
linkedList.add(7,6);
linkedList.add(0,10);
linkedList.add(10,11);
linkedList.remove(0);
linkedList.remove(0);
linkedList.remove(0);
linkedList.remove(1);
linkedList.remove(4);
linkedList.remove(5);
linkedList.remove(0);
// linkedList.remove(0);
// linkedList.remove(0);
// linkedList.remove(0);
// linkedList.remove(0);
System.out.println(linkedList.get(0));
System.out.println(linkedList.get(1));
System.out.println(linkedList.get(2));
System.out.println(linkedList.get(3));
System.out.println(linkedList.getFirst());
System.out.println(linkedList.getLast());
linkedList.removeFirst();
linkedList.removeLast();
System.out.println("遍历链表");
linkedList.traverseList(false);
// System.out.println("逆向遍历链表");
// linkedList.traverseList(true);
System.out.println("链表长度");
System.out.println(linkedList.size());
linkedList.clearList();
}
}
来源:https://blog.csdn.net/rj2017211811/article/details/109316864
0
投稿
猜你喜欢
- 面试题1:说一下抽象类和接口有哪些区别?正经回答:抽象类和接口的主要区别:从设计层面来说,抽象类是对类的抽象,是一种模板设计;接口是行为的抽
- 基本介绍数据回显:模型数据导向视图(模型数据 ---> Controller ---> 视图)说明:SpringMVC在调用方法
- 本文实例讲述了Android中SeekBar和RatingBar用法。分享给大家供大家参考,具体如下:什么是SeekBar?可以拖动的进度条
- 项目需要去调用.NET的WebSrevice,本身是Java,研究了半天,终于有些头绪,记下来。1,新建.NET WebService。只在
- 前言工作中使用mybatis时我们需要根据数据表字段创建pojo类、mapper文件以及dao类,并且需要配置它们之间的依赖关系,这样的工作
- java 泛型方法:泛型是什么意思在这就不多说了,而Java中泛型类的定义也比较简单,例如:public class Test
- 在分支较多的时候,switch的效率比if高,在反汇编中我们即可看到效率高的原因一、switch语句1、在正向编码时,switch语句可以看
- 在项目迁移到Spring Boot之后,发生内存使用量过高的问题。本文介绍了整个排查过程以及使用到的工具,也非常适用于其他堆外内存排查。背景
- 前言Future的问题写多线程程序的时候,可以使用Future从一个异步线程中拿到结果,但是如果使用过程中会发现一些问题:如果想要对Futu
- 简介备忘录设计模式(Memento Design Pattern)也叫作快照(Snapshot)模式,主要用于实现防丢失、撤销、恢复等功能。
- 介绍:%是求余运算符,也叫模除运算符,用于求余数。%要求两个操作数均为整数(或可以隐式转换成整数的类型)。标准规定:如果%左边的操作数为负数
- 1、什么是 ThreadLocal:ThreadLocal,即线程本地变量,如果你创建了一个变量,那么访问这个变量的每个线程都会有这个变量的
- SlidingDrawer效果想必大家也见到过,它就是1.5模拟器上进入应用程序列表的效果。下面是截图一、简介 SlidingDr
- Android 显示GIF图片实例详解gif图动画在Android中还是比较常用的,比如像新浪微博中,有很多gif图片,而且展示非常好,所以
- 正则表达式是一种描述词素的重要表示方法。虽然正则表达式并不能表达出所有可能的模式(例如“由等数量的 a 和 b 组成的字符串”),但是它可以
- 一、打印直角三角形这个循环控制打印十行空格for (int x = 1; x <= 10; x++) {//因为要打印一个十行的直角三
- SharedPreferences是Android中最容易理解的数据存储技术,实际上SharedPreferences处理的就是一个key-
- 本文介绍了Flutter 通过Clipper实现各种自定义形状的示例代码,分享给大家,具体如下:ClipOval 圆形裁剪ClipOval(
- 一直使用Eclipse环境开发Android,也尝鲜使用过Android Studio去开发,各种IDE配合Android SDK及SDK原
- 希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是基于插入排序的以下两点性质而提出改进方