双向链表的java实现

 * 一、什么是双链表
 * 每个结点除了保存对下一个结点的引用，同时还保存着对前一个结点的引用
 * 二、从头部进行插入
 * 要对链表进行判断，如果为空则设置尾结点为新添加的结点，如果不为空，还需要设置设置头结点的前一个结点为新添加的结点
 * 三、从尾部进行插入
 * 如果链表为空，则直接设置头结点为新添加的结点，否则设置尾结点的后一个结点为新添加结点，同时设置新添加的结点的前一个结点的尾结点
 * 四、从头部进行删除
 * 判断头部结点是否有下一个结点，如果没有则设置结点为null，否则设置头结点的下一个结点的previous为null
 * 五、从尾部进行删除
 * 如果头结点后没有其他结点，则设置尾结点为null，否则设置尾结点前一个结点的next为ull，设置尾结点为其前一个结点
 * 六、删除方法
 * 不需要再使用一个临时的指针域

 

package com.algorithm;

/**
 * 链表的链结点，相当于车厢
 * @author lenovo
 *
 */
public class DoubleNode {

	/**
	 * 数据域
	 */
	public long data;
	
	//结点域(指针域)，相当于火车与火车的链接
	public DoubleNode next;
	
	/**
	 * 前一个结点
	 */
	public DoubleNode previous;
	
	public DoubleNode(long value){
		this.data =value;
	}
	
	/**
	 * 显示方法
	 */
	public void display(){
		System.out.print(data+" ");
	}
}

 

package com.algorithm;

/**
 * 双向链表，
 * 一、什么是双链表
 * 每个结点除了保存对下一个结点的引用，同时还保存着对前一个结点的引用
 * 二、从头部进行插入
 * 要对链表进行判断，如果为空则设置尾结点为新添加的结点，如果不为空，还需要设置设置头结点的前一个结点为新添加的结点
 * 三、从尾部进行插入
 * 如果链表为空，则直接设置头结点为新添加的结点，否则设置尾结点的后一个结点为新添加结点，同时设置新添加的结点的前一个结点的尾结点
 * 四、从头部进行删除
 * 判断头部结点是否有下一个结点，如果没有则设置结点为null，否则设置头结点的下一个结点的previous为null
 * 五、从尾部进行删除
 * 如果头结点后没有其他结点，则设置尾结点为null，否则设置尾结点前一个结点的next为ull，设置尾结点为其前一个结点
 * 六、删除方法
 * 不需要再使用一个临时的指针域 
 * @author lenovo
 */
public class DoubleLinkList {

	/**
	 * 头结点，相当于火车头
	 */
	private DoubleNode first;
	
	/**
	 * 尾结点
	 */
	private DoubleNode last;
	
	public DoubleLinkList(){
		first =null;
		last=null;
	}
	
	/**
	 * 插入一个结点，在头结点插入
	 */
	public void insertFirst(long value){
		DoubleNode node = new DoubleNode(value);
		//要对链表进行判断，如果为空则设置尾结点为新添加的结点，如果不为空，还需要设置设置头结点的前一个结点为新添加的结点
		if(isEmpty()){
			last=node;
		}else{
			first.previous=node;
		}
		node.next = first;
		first =node;
	}
	
	/**
	 * 插入一个结点，在尾结点插入
	 */
	public void insertLast(long value){
		DoubleNode node = new DoubleNode(value);
		//如果链表为空，则直接设置头结点为新添加的结点，否则设置尾结点的后一个结点为新添加结点，同时设置新添加的结点的前一个结点的尾结点
		if(isEmpty()){
			first=node;
		}else{
			last.next = node;
			node.previous=last;
		}
		
		last =node;
	}
	
	/**
	 * 删除一个结点，在头结点删除
	 */
	public DoubleNode deleteFirst(){
		DoubleNode node = first;
		//判断头部结点是否有下一个结点，如果没有则设置结点为null，否则设置头结点的下一个结点的previous为null
		if(first.next==null){
			last=null;
		}else{
			first.next.previous=null;
		}
		first=node.next;
		return node;
	}
	
	/**
	 * 删除一个结点，在尾结点删除
	 */
	public DoubleNode deleteLast(){
		DoubleNode node = last;
		//如果头结点后没有其他结点，则设置头结点为null，否则设置尾结点前一个结点的next为ull，设置尾结点为其前一个结点
		if(first.next==null){
			first=null;
		}else{
			last.previous.next=null;
			last=last.previous;
		}
		
		return last;
	}
	
	/**
	 * 显示方法
	 */
	public void display(){
		DoubleNode current = first;
		
		while(current!=null){
			current.display();
			current = current.next;
		}
		System.out.println();
	}
	
	/**
	 * 查找方法
	 * @param value
	 * @return
	 */
	public DoubleNode find(long value){
		DoubleNode current = first;
		while(current.data!=value){
			if(current.next==null){
				return null;
			}
			current = current.next;
		}
		return current;
	}
	
	/**
	 * 删除方法，根据数据域删除
	 * @param value
	 * @return
	 */
	public DoubleNode delete(long value){
		//不需要再使用一个临时的指针域 
		DoubleNode current = first;
		while(current.data!=value){
			if(current.next==null){
				return null;
			}
			current = current.next;
			
		}
		if(current == first) {
			first = first.next;
		} else {
			current.previous.next = current.next;
		}
		return current;
	}
	
	/**
	 * 判断是否为空
	 * @return
	 */
	public boolean isEmpty(){
		return first==null;
	}
	
	public static void main(String[] args) {
		DoubleLinkList linkList = new DoubleLinkList();
		linkList.insertLast(45);
		linkList.insertLast(56);
		linkList.insertLast(90);
		linkList.display();
		
		//linkList.deleteLast();
		
		linkList.display();
		
		while (!linkList.isEmpty()) {
			linkList.deleteLast();
			linkList.display();
		}
	}
}