双端链表的java实现

 * 双端链表，
 * 一、什么是双链表
 * 链表中保存着对最后一个链接点引用的链表
 * 二、从头部进行插入
 * 要对链表进行判断，如果为空则设置尾结点为新添加的结点
 * 三、从尾部进行插入
 * 如果链表为空，则直接设置头结点为新添加的结点，否则设置尾结点的后一个结点为新添加结点
 * 四、从头部进行删除
 * 判断头部结点是否有下一个结点，如果没有则设置结点为null

 

package com.algorithm;

/**
 * 双端链表，
 * 一、什么是双链表
 * 链表中保存着对最后一个链接点引用的链表
 * 二、从头部进行插入
 * 要对链表进行判断，如果为空则设置尾结点为新添加的结点
 * 三、从尾部进行插入
 * 如果链表为空，则直接设置头结点为新添加的结点，否则设置尾结点的后一个结点为新添加结点
 * 四、从头部进行删除
 * 判断头部结点是否有下一个结点，如果没有则设置结点为null
 * @author lenovo
 */
public class FirstLastLinkList {

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