循环链表，双向链表

循环链表

循环链表与顺序链表之间的区别：循环链表最后一个数据的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;
	}	

}