java連結清單之--雙向循環連結清單

在單連結清單中，查詢下一個元素的時間是O(1)。查詢上一個元素的時間卻是O(n)。

為了克服這種缺點，有了雙向連結清單----繼而為了更加高效-----雙向循環連結清單

此外引用不知哪位大神的一句話：判斷資料結構使用

如果你要把資料集合看成一個環，可以順時針走，也可以逆時針走，那你就可以用雙向循環連結清單來描述

如果你要把資料集合看成一條鍊，可以雙向周遊，那你就可以用雙向連結清單來描述

如果你要把資料集合看成一個層次結構，那你可以用樹來描述

如果你要把資料集合看成……，比方說，你完全想不到誰跟誰會有關系，那你可以用圖來描述

下面是個測試例子，實作了基本功能

import java.util.Scanner;
public class DoubleLinkedList<AnyType>{
	//定義雙向連結清單節點
	private class Node<AnyType>{
        AnyType data;
        Node<AnyType> next;
        Node<AnyType> prev;
   //構造函數
    private Node()
      {
    	data=null;
    	prev=null;
    	next=null;
    	}
    private Node(AnyType data){
    	this.data=data;
    	this.prev=null;
    	this.next=null;
    }
    private Node(AnyType data,Node<AnyType> prev,Node<AnyType> next){
    	this.data=data;
    	this.prev=prev;
        this.next=next;
       }
}
	private int size=0;
	private Node<AnyType> beginMarker;
	private Node<AnyType> endMarker;
	
	//初始化一個空的雙向循環連結清單
	public DoubleLinkedList(){
		beginMarker=new Node<AnyType>();
		endMarker=new Node<AnyType>();
		//key point
		beginMarker.prev=endMarker;
		beginMarker.next=null;
		endMarker.prev=null;
		//together
		endMarker.next=beginMarker;
		}
	public void init(){
		System.out.println("雙向循環連結清單的操作：");
		System.out.println("1.空的雙向循環連結清單已經建立");
	}
	//2.用于向空的雙向循環連結清單裡面添加資料
	public void addInit(){
		Scanner sc=new Scanner(System.in);
		System.out.println("2.該步驟執行初始化節點操作");
		System.out.println("a.請輸入要插入節點的個數");
		
		int n=sc.nextInt();
		
		for(int i=0;i<n;i++){
			System.out.println("b.請輸入要插入的元素的數值:");
			AnyType data=(AnyType)sc.next();
			if(beginMarker.next==null){
			Node<AnyType> node=new Node<AnyType>(data);
			beginMarker.next=node;
			node.prev=beginMarker;
			endMarker=node;
			endMarker.next=beginMarker;
			beginMarker.prev=endMarker;
			} 
		else{
			Node<AnyType> node=new Node<AnyType>(data);
			endMarker.next=node;
			node.prev=endMarker;
			endMarker=node;
			endMarker.next=beginMarker;
			beginMarker.prev=endMarker;
			}
		}
}
	// add 方法
	public void add(AnyType data){
		if(beginMarker.next==null){
			Node<AnyType> node=new Node<AnyType>(data);
			beginMarker.next=node;
			node.prev=beginMarker;
			endMarker=node;
			endMarker.next=beginMarker;
			} 
		else{
			Node<AnyType> node=new Node<AnyType>(data);
			endMarker.next=node;
			node.prev=endMarker;
			endMarker=node;
			endMarker.next=beginMarker;
			}
	}

	public void add(){
		Scanner sc=new Scanner(System.in);
		System.out.println("3.該步驟/執行插入節點操作");
		System.out.print("*請輸入要插入節點的個數*");
		System.out.println("(可用于插入第一個和最後一個節點)");
		int n=sc.nextInt();
		for(int i=0;i<n;i++){
			System.out.println("a.請輸入要插入節點的位置:");
			int index=sc.nextInt();
		    System.out.println("b.請輸入要插入的元素的數值");
			AnyType data=(AnyType)sc.next();
		int j=0;
		if (beginMarker==null){
			Node<AnyType> Node = new Node<AnyType>(data);
			beginMarker.next=Node;
			Node.prev=beginMarker;
			endMarker=Node;
			endMarker.next=beginMarker;
		}
		else if(index==0){
			Node<AnyType> Node=new Node<AnyType>(data);
			Node<AnyType> temp=beginMarker.next;
			beginMarker.next=Node;
			Node.prev=beginMarker;
			Node.next=temp;
			temp.prev=Node;
		} 
		else if(index>=size()){
			add(data);
		} else 
		{
			Node<AnyType>Node=new Node<AnyType>(data);
			Node<AnyType> prior=beginMarker;
			while (j<index)
			{
				j++;
				prior=prior.next;
			}
			Node<AnyType> temp=prior.next;
			prior.next=Node;
			Node.prev=prior;
			Node.next=temp;
			temp.prev=Node;
			}
		}
	}
   public void remove() {
		int j=0;
		Scanner sc=new Scanner(System.in);
		System.out.println("4.該步驟執行删除節點操作");
		System.out.println("a.請輸入要删除節點的個數:");
		int n=sc.nextInt();
		for(int i=0;i<n;i++){
			System.out.println("b.請輸入要删除節點的位置:");
			int index=sc.nextInt();
		    if (index<0||index>=size()) 
		{
		    	System.out.println("數組越界");
				
		} else if(index==0||size()==1) {
			if (size()==0){
				beginMarker.next=null;
				endMarker=null;
			} else {
				Node<AnyType> fitst=beginMarker.next;
				beginMarker.next=fitst.next;
				fitst=null;
			}
		} else if(index==(size()-1)){
			if(size()==1) 
			{
				if (size()==0){
					beginMarker.next=null;
					endMarker=null;
				} else {
					Node<AnyType> fitst=beginMarker.next;
					beginMarker.next=fitst.next;
					fitst=null;
				}
			} 
			else{
				Node<AnyType> pre=endMarker.prev;
				pre.next=null;
				endMarker=pre;
				endMarker.next=beginMarker;
				endMarker=null;
			}

		} else {
			Node<AnyType> prior=beginMarker.next;
			while(j<index){
				j++;
				prior=prior.next;
			}
			Node<AnyType> delete=prior;
			Node<AnyType> pre=delete.prev;
			Node<AnyType> after=delete.next;
			pre.next=delete.next;
			after.prev=pre;
			delete=null;
		}
		}
		System.out.println("**************");
	}
	
//用于計算連結清單的大小
	public int size(){ 
		int size=0;
		Node<AnyType> node=beginMarker.next;
		while(node.data!=null) {
			size++;
			node=node.next;
		}
		return size;
	}
//用于得到節點
	public Node<AnyType> getNode(int index) {
		int j=0;
		Node<AnyType> firstNode=beginMarker.next;
		if(index<0||index>=size())
		{
			System.out.println("數組越界");
		}
		while(j<index){
			j++;
			firstNode=firstNode.next;
		}
		
		return firstNode;
	} 

public void check(DoubleLinkedList list){
	  System.out.println("5.是否執行逆置操作(是/否)?");
	  Scanner sc=new Scanner(System.in);
	  String str=sc.next();
	  if(str.equals("是")){
		 this.inverse(list);
	  }
	  else
		  System.out.println("所有操作都已完成");
  }
//實作連結清單的逆置操作
   public void inverse(DoubleLinkedList<AnyType> list1){
	   System.out.println("逆置後的結果為:");
	   int size=size();
	 for(int i=size-1;i>=0;i--)
	 {
	 list1.add(this.getNode(i).data);
	}
	 list1.print();
	 System.out.println("所有操作都已結束");
	 }
 //該方法用于輸對外連結表中的所有數值
	public void print(){
		Node<AnyType> firstNode=beginMarker.next;
		if(firstNode==null){
			System.out.println("該連結清單為空");
		} 
		else
		{
			while(firstNode.data!=null)
			{
				System.out.println(firstNode.data);
				firstNode=firstNode.next;
				}
			}
		}
   public static void main(String[] args) {
	   DoubleLinkedList<Object> list=new DoubleLinkedList<Object>();
		list.init();
		DoubleLinkedList<Object> list1=new DoubleLinkedList<Object>();
		list.addInit();
		list.add();
		list.remove();
	    list.check(list1);
	    list.print();
	    }
}