双向链表

?????? 今天我想跟大家来唠叨一下双向链表，何为双向链表？简而言之，每个结点存储两个链，并允许双向遍历的链表称为双向链表。我对于链表的理解是这样的，一个结点类，一个位置类，一个链表本身类。

一、结点类

public class DoubleLinkNode {
	public String iData;
	//前一个结点
	public DoubleLinkNode prev;
	//后一个结点
	public DoubleLinkNode next;
	
	public DoubleLinkNode(String iData){
		this(iData,null,null);
	}

	public DoubleLinkNode(String iData, DoubleLinkNode dln, DoubleLinkNode dln2) {
		this.iData=iData;
		this.prev=dln;
		this.next=dln2;
	}
	
}

?这个类比较简单，没什么好说，对于第二个构造器，主要是为了使后面结点之间的连接更简洁。你也可以不用这个构造器。

二、位置类（迭代器类）

public class DbLinkListIterator {
	//标识当前的位置
	DoubleLinkNode current;
	DbLinkListIterator(DoubleLinkNode dln) {
		current=dln;
	}
	//判断当前位置是否有效
	public boolean isValid(){
		return current!=null;
	}
	//向前行进
	public void advace(){
		if (isValid()) {
			current=current.next;
		}
	}
	//向后倒退
	public void back(){
		if (isValid()) {
			current=current.prev;
		}
	}
	//返回当前位置的标识符
	public String retrieve(){
		if (isValid()) {
			return current.iData;
		}
		return null;
	}
}

?这个类主要用来反馈链表当前的位置，如果你不想单独建这个类，你可以把它放在链表本身类的内部。但是本人觉得把它单独抽象出来成一个类，结构会更加的清晰。

三、链表本身类

public class LinkList_Double {
	//头结点
	private DoubleLinkNode header;
	//尾结点
	private DoubleLinkNode tail;
	//初始化头尾结点
	public LinkList_Double() {
		header=new DoubleLinkNode("header");
		tail=new DoubleLinkNode("tail",header,null);
		header.next=tail;
	}
	//判断双向链表是否为空
	public boolean isEmpty(){
		return header.next==tail||tail.prev==header;
	}
	//第一个结点之前的位置
	public DbLinkListIterator zero(){
		return new DbLinkListIterator(header);
	}
	//第一个结点的位置
	public DbLinkListIterator first(){
		if (!isEmpty()) {
			return new DbLinkListIterator(header.next);
		}
		return new DbLinkListIterator(header);
	}
	//最后一个结点的位置
	public DbLinkListIterator last(){
		if (!isEmpty()) {
			return new DbLinkListIterator(tail.prev);
		}
		return new DbLinkListIterator(tail);
	}
	//指定位置之后插入方法
	public void insertAfter(String obj,DbLinkListIterator pos){
		if (pos!=null&&pos.current!=null) {
			DoubleLinkNode newDoubleLinkNode=new DoubleLinkNode(obj,pos.current,pos.current.next);
			newDoubleLinkNode.prev.next=newDoubleLinkNode;
			newDoubleLinkNode.next.prev=newDoubleLinkNode;
		}
	}
	
	//指定位置之前插入方法
	public void insertBefore(String obj,DbLinkListIterator pos){
		if (pos.current!=header&&pos!=null&&pos.current!=null) {
			DoubleLinkNode newDoubleLinkNode=new DoubleLinkNode(obj,pos.current.prev,pos.current);
			newDoubleLinkNode.prev.next=newDoubleLinkNode;
			newDoubleLinkNode.next.prev=newDoubleLinkNode;
		}
	}
	
	//查找方法
	public DbLinkListIterator find(String key){
		DoubleLinkNode itr=header.next;
		while (itr!=null) {
			if (itr.iData.equals(key)) {
				return new DbLinkListIterator(itr);
			}
			itr=itr.next;
		}
		return null;
	}
	//删除方法
	public void delete(String key){
		DbLinkListIterator itr=find(key);
		if (itr==null) {
			System.out.println("不存在该关键字");
			return;
		}
			itr.current.prev.next=itr.current.next;
			itr.current.next.prev=itr.current.prev;
	}
	
	//向前显示
	public void displayBofore(){
		if (isEmpty()) {
			System.out.println("该双向链表为空");
		}else {
			DbLinkListIterator itr=first();
			while (itr!=null&&!itr.retrieve().equals("tail")) {
				System.out.print(itr.retrieve()+" ");
				itr.advace();
			}
		}
	}
	
	//向后显示
	public void displayAfter(){
		if (isEmpty()) {
			System.out.println("该双向链表为空");
		}else {
			DbLinkListIterator itr=last();
			while (itr!=null&&!itr.retrieve().equals("header")) {
				System.out.print(itr.retrieve()+" ");
				itr.back();
			}
		}
	}
}

为了方便，作者的想法是虚构两个结点，即头结点、尾结点，这样做的好处就是能够保证每次插入有效结点时，它的前后都有结点，这样就少了许多的条件判断。当然双向链表本身的方法肯定不止这么一点，我只是大概的列举了一些。

四、测试类

public class LinkList_doubleTest {
	public static void main(String[] args) {
		LinkList_Double linkList_Double=new LinkList_Double();
		//插入第一个结点
		linkList_Double.insertAfter("a", linkList_Double.zero());
		//在指定结点之后插入
		linkList_Double.insertAfter("b", linkList_Double.find("a"));
		linkList_Double.insertAfter("c", linkList_Double.find("b"));
		
		//在指定结点之前插入
		linkList_Double.insertBefore("e", linkList_Double.find("b"));
		linkList_Double.insertBefore("f", linkList_Double.first());
		//删除指定结点
		linkList_Double.delete("f");
		//顺序显示
		linkList_Double.displayBofore();
		//逆序显示
		linkList_Double.displayAfter();
	}
}

?最后，作者也是正在学习的过程中，自然还有很多?考虑不周全的地方，如有，还请见谅，并希望您能指出我的不足之处，大家一起学习、进步。

双向链表

原文：http://19900524.iteye.com/blog/2252478