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