Java实现双向循环链表
双向循环链表定义
相比于单链表，有两个指针，next指针指向下一个结点,prior指针指向上一个结点,最后一个结点的next指针指向头结点，头结点的prior指针指向最后一个结点
代码实现：
我们对单链表的实现加以修改
packagealgorithm.datastructure.doublelinkedlist;
importjava.util.NoSuchElementException;
/**
*双向循环链表
*两个指针，next指针指向下一个结点,prior指针指向上一个结点,最后一个结点的next指针指向头结点，
*头结点的prior指针指向最后一个结点
**/
publicclassLinkedList{
privateNodehead;//头节点
privateintsize;//链表长度
staticprivateclassNode{
privateintdata;//数据
privateNodenext;//下一个结点
privateNodeprior;//上一个结点
publicNode(){
}
publicNode(intdata){
this.data=data;
}
privateNode(intdata,Nodenext){
this.data=data;
this.next=next;
}
publicNode(Nodeprior,intdata,Nodenext){
this.prior=prior;
this.data=data;
this.next=next;
}
}
//初始化空链表
publicLinkedList(){
//head=null;
}
//添加元素
publicBooleanadd(intelement){
linkLast(element);
returntrue;
}
//在某个位置之前添加元素
publicBooleanadd(intindex,Integerelement){
checkPositionIndex(index);
if(index==size){
linkLast(element);
}else{
linkBefore(element,node(index));
}
returntrue;
}
//根据下标获取元素
publicintget(intindex){
checkElementIndex(index);
returnnode(index).data;
}
//获取第一个元素
publicIntegergetFirst(){
Nodef=head;
if(f==null){
thrownewNoSuchElementException();
}else{
returnf.data;
}
}
//获取最后一个元素
publicIntegergetLast(){
if(size==0){
thrownewNoSuchElementException();
}
returnhead.prior.data;
}
//删除第一个元素
publicIntegerremoveFirst(){
Nodef=head;
if(f==null){
thrownewNoSuchElementException();
}else{
returnunlink(head);
}
}
//删除最后一个元素
publicIntegerremoveLast(){
if(size==0){
thrownewNoSuchElementException();
}
intindex=size-1;
returnunlink(node(index));
}
//根据索引删除元素
publicIntegerremove(intindex){
checkElementIndex(index);
returnunlink(node(index));
}
//销毁链表
publicvoiddestroyList(){
clearList();
}
//将链表置为空表
publicvoidclearList(){
for(Nodep=head;p!=null;){
Nodenext=p.next;//记录下一个结点
p=null;//删除当前结点
p=next;//指向下一个结点
}
size=0;
head=null;
}
//遍历链表
publicvoidtraverseList(BooleanisReverseVisited){
if(!isEmpty()){
if(!isReverseVisited){
for(Nodep=head;p!=head.prior;p=p.next){
System.out.println(p.data);
}
System.out.println(head.prior.data);
}else{
for(Nodep=head.prior;p!=head;p=p.prior){
System.out.println(p.data);
}
System.out.println(head.data);
}
}
}
//返回链表元素个数
publicintsize(){
returnsize;
}
publicBooleanisEmpty(){
returnsize==0;
}
/**双向链表插入一个结点，要改变的指针如下:
*
*(1)前一个结点的next指针
*(2)后一个结点的prior指针
*(3)新创建的结点的prior指针和next指针
**/
//尾部添加结点
privatevoidlinkLast(intelement){
if(size==0){//没有结点时
head=newNode(element);
head.next=head;
head.prior=head;
size++;
}else{
//得到最后一个结点
NodeoldTail=head.prior;
//new新的尾结点newTail
//newTail的前一个结点设置为旧的尾结点,
//newTail的后一个结点指向head
NodenewTail=newNode(oldTail,element,head);
//head的下一个结点指向newTail
head.prior=newTail;
//旧的尾结点的下一个结点指向新的尾结点
oldTail.next=newTail;
size++;
}
}
//在某结点之前插入结点
privatevoidlinkBefore(intelement,Nodenode){
if(node==null){
linkLast(element);
}else{
Nodep=head;
if(node.data==p.data){
Nodeq=p.prior;
NodenewNode=newNode(q,element,p);
q.next=newNode;
p.prior=newNode;
size++;
}else{
for(p=p.next;p!=head;){
if(node.data==p.data){
Nodeq=p.prior;
NodenewNode=newNode(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)如果是删除的是头结点，指明当前头结点
**/
//删除结点
privateIntegerunlink(Nodenode){
IntegerdeleteNodeData=node.data;
Nodep=null,q=null;
if(deleteNodeData==head.data){//该结点为头结点
Nodecur=head;
p=head.prior;
q=head.next;
p.next=q;
q.prior=p;
head=q;
cur=null;
size--;
}else{
Nodem;
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;
}
}
returndeleteNodeData;
}
//数组下标是否越界
privateBooleanisElementIndex(intindex){
returnindex>=0&&index=0&&index<=size;
}
//检验下标是否越界，抛出异常
privatevoidcheckElementIndex(intindex){
if(!isElementIndex(index)){
try{
thrownewIndexOutOfBoundsException("下标越界");
}catch(Exceptione){
e.printStackTrace();
}
}
}
//检验插入下标是否越界，抛出异常
privatevoidcheckPositionIndex(intindex){
if(!isPositionIndex(index)){
try{
thrownewIndexOutOfBoundsException("下标越界");
}catch(Exceptione){
e.printStackTrace();
}
}
}
//返回指定位置的元素
privateNodenode(intindex){
intnowIndex=0;
if(size>0){
for(Nodep=head;p!=head.prior;){
if(nowIndex==index){
returnp;
}
p=p.next;
nowIndex++;
}
if(nowIndex==index){
returnhead.prior;
}
}
returnnull;
}
publicstaticvoidmain(String[]args){
java.util.LinkedListlinkedList0=newjava.util.LinkedList();
linkedList0.add(6);
linkedList0.remove(0);
linkedList0.size();
linkedList0.peek();
//linkedList0.getFirst();
linkedList0.clear();
//测试
LinkedListlinkedList=newLinkedList();
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();
}
}
总结
以上就是Java简单实现双向链表，更多功能可参考Java集合中的LinkedList实现。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。