线性表之双链表

前言

双链表的每个结点有两个地址域，分别指向它的前驱结点和后继结点

双链表

双链表的结点声明如下

public class DLinkNode<T> {

	public T data;  //数据元素
	public DLinkNode<T> prev,next; //prev指向前驱结点，next指向后继结点
	
	public DLinkNode(T data, DLinkNode<T> prev, DLinkNode<T> next) {
		super();
		this.data = data;
		this.prev = prev;
		this.next = next;
	}
	
	public DLinkNode(){
		this(null,null,null);
	}
}

若带头结点的双链表为空双链表，则有head.next=null&&head.prev=null;

若p指向双链表中非两端的某个结点，则有p=p.next.prev=p.prev.next;

循环双链表

如果双链表的最后一个结点的next链指向头结点，头结点的prev链指向最后一个结点，则称为循环双链表，
对于空双链表有head.next=head&&head.prev=head
下面是循环双链表CirDoublyLinkedList的实现类
只有插入和删除和单链表不一样

public class CirDoublyLinkedList<T> implements LList<T>{

	public DLinkNode<T> head;
	
	public CirDoublyLinkedList(){
		this.head=new DLinkNode<T>();
		this.head.prev=head;
		this.head.next=head;
	}
	
	public void insert(int i, T x) {//将x对象插入在序号为i的结点
	if(x==null)
		return;
	DLinkNode<T> p=this.head;
	for(int j=0;p.next!=this.head&&j<i;j++) //寻找插入位置
		p=p.next;                           //循环停止时，p指向第i-1个结点
	 DLinkNode<T> q=new DLinkNode<T>(x,p,p.next);//插入在p结点之后
	 p.next.prev=q;
	 p.next=q;
		
	}

	public void append(T x) {
	 if(x==null)
		 return;
	 DLinkNode<T> q=new DLinkNode<T>(x,head.prev,head);
	 head.prev.next=q; //插入在头结点之前，相当于尾插入
	 head.prev=q;
		
	}

	public T remove(int i) {
	if(i>0)
	{
		DLinkNode<T> p=this.head.next;
		for(int j=0;p!=head&&j<i;j++)  //定位到待删除结点
			p=p.next;
		if(p!=head)
		{ 
			T old=p.data;     //获得原对象
			p.prev.next=p.next;  //删除p结点自己
			p.next.prev=p.prev;
			return old;
		}
	}
		return null;
	}

	public void removeAll() {
		this.head.prev=head;
		this.head.next=head;
		
	}

	。。。其余方法和单链表一样