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