java链表之--双向循环链表

我会带着你远行 2022-09-23 05:58 245阅读 0赞

在单链表中，查询下一个元素的时间是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();
    	    }
    }