循环链表,双向链表

循环链表

循环链表与顺序链表之间的区别:循环链表最后一个数据的next指针域不为空,而是指向头结点,其他基本操作大体相同,只是在判断表结束的条件变为判断节点的引用域是否为头引用

双向链表

/**  
* @author NeoSong
* @date Oct 10, 2017 
* 4:43:01 PM
* program OF information:实现双向链表
* 为何定义双向链表?在单向链表中查询A节点的后继节点,时间复杂度为O(1),而查询A节点的前驱节点,时间复杂度为O(n)
*                   而双向链表查询前驱和后继节点的时间复杂度都为O(1) 
*                        1.定义节点类    
*/
public class DbNode
   
     {
	//定义构造方法,初始化
	public DbNode(){
	}
	public DbNode(T val){
		data=val;
		next=null;
	}
	
	private DbNode
    
      next;//后继
	private DbNode
     
       pre;//前驱
	private T data;//数据域
	
	public DbNode
      
        getNext() {
		return next;
	}
	public void setNext(DbNode
       
         next) { this.next = next; } public DbNode
        
          getPre() { return pre; } public void setPre(DbNode
         
           pre) { this.pre = pre; } public T getData() { return data; } public void setData(T data) { this.data = data; } } /** * @author NeoSong * @date Oct 10, 2017 * 4:48:33 PM * program OF information: 2.定义双向链表的方法 */ public class DbLinkList
          
            { public DbLinkList(){ head=new DbNode(); } private DbNode
           
             head;//定义头结点 /* * 插入操作,双向链表比单向链表的插入操作复杂 * 方法需要两个参数,i为插入的位置,val为值 */ public void insert(int i,T val){ DbNode
            
              r=new DbNode(val);//需插入的节点 DbNode
             
               q=head;//定义节点,用于循环,初始令其等于头结点 DbNode
              
                p=new DbNode(); for(int j=1;j
               
                 q=head;//定义节点q,用于循环 DbNode
                
                  p=new DbNode(); for(int j=1;j<=i;j++){ p=q.getNext(); q=p; } q.getPre().setNext(q.getNext());; q.setPre(q.getPre()); } /* * 附加操作 */ public void attend(T val){ DbNode
                 
                   p=new DbNode(val); DbNode
                  
                    q=head; while(q.getNext()!=null){ q=q.getNext(); } q.setNext(p); p.setPre(q); } /* * 打印链表 */ public void printList(){ DbNode
                   
                     p=head; System.out.print("["); while(p.getNext()!=null){ p=p.getNext(); System.out.print(" "+p.getData()+" "); } System.out.println("]"); } /* * 是否为空 */ public boolean isEmpty(){ return head.getNext()==null; } }
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

    原文作者:NEO_THEONE_
    原文地址: https://blog.csdn.net/NEO_THEONE_/article/details/78196213
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞