Java实现双向循环链表

 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=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(); } }