一、概述：

　　1、什么時雙向鏈表：

　　鏈表中的每個節點即指向前面一個節點，也指向后面一個節點，就像丟手絹游戲一樣，每個人都手拉手

　　2、從頭部插入

　　要對鏈表進行判斷，如果為空則設置尾節點為新添加的節點，如果不為空，還要設置頭節點的一個前節點為新節點

 

3、從尾部進行插入

　　如果鏈表為空，則直接設置頭節點為新添加的節點，否則設置尾節點的后一個節點為新添加的節點。同時設置新添加的節點的前一個節點為尾節點

　　4、從頭部刪除

　　判斷節點是否有下個節點，如果沒有則設置節點為null，并且刪除下個節點指向前節點的指針

　　5、刪除尾部節點

　　如果頭節點沒有其它節點，把尾節點設置為Null。否則設置尾節點前一個節點的next為Null。設置尾節點為前一個節點

　　6、刪除方法

　　此時不需要記錄last的Node

　　刪除時使用current.previous.next= current.next;

二、實現

package com.struct.linklist;

/**

 * @描述         雙向鏈表

 * @項目名稱      Java_DataStruct

 * @包名         com.struct.linklist

 * @類名         LinkList

 * @author      chenlin

 * @date        2010年6月26日 上午8:00:28

 * @version     1.0 

 */

public class DoubleLinkList {

    //頭

    private Node first;

    //尾

    private Node last;

    public DoubleLinkList(){

        first = null;

        last = null;

    }

    /**

     * 插入數據

     * @param value

     */

    public void insertFirst(long value){

        Node newNode = new Node(value);

        if (first == null) {

            last = newNode;

        }else {

            first.previous = newNode;

            //把first節點往下移動

            newNode.next = first;

        }

        //把插入的節點作為新的節點

        first = newNode; 

    }

    /**

     * 插入數據

     * @param value

     */

    public void insertLast(long value){

        Node newNode = new Node(value);

        if (first == null) {

            first = newNode;

        }else {

            last.next = newNode;

            //first.previous = newNode;

            newNode.previous = last;

        }

        //把最后個節點設置為最新的節點

        last = newNode;

    }

    public boolean isEmpty(){

        return first == null;

    }

    /**

     * 刪除頭節點時要去除兩個指針,一個指向下個的next ,一個是next的previous指向前面的

     * 

     * @param value

     * @return

     */

    public Node deleteFirst(){

        if (first == null) {

            throw new RuntimeException("鏈表數據不存在");

        }

        Node temp = first;

        if (first.next == null) {

            last = null;

        }else {

            first.next.previous = null;

        }

        first = temp.next;

        return temp;

    }

    /**

     * 刪除頭節點時要去除兩個指針,一個指向下個的next ,一個是next的previous指向前面的

     * 

     * @param value

     * @return

     */

    public Node deleteLast(){

        if (first == null) {

            throw new RuntimeException("鏈表數據不存在");

        }

        Node temp = last;

        if (first.next == null) {

            last = null;

            //把第一個刪除

            first = null;

        }else {

            last.previous.next = null;

        }

        last = temp.previous;

        return temp;

    }

    /**

     * 刪除

     * @param key

     * @return

     */

    public Node deleteByKey(long key){

        Node current = first;

        while(current.data != key){

            if (current.next == null) {

                System.out.println("沒找到節點");

                return null;

            }

            current = current.next;

        }

        if (current == first) {

            //return deleteFirst();

            //指向下個就表示刪除第一個

            first = first.next;

        }else {

            current.previous.next = current.next;

        }

        return current;

    }

    /**

     * 顯示所有的數據

     */

    public void display(){

        if (first == null) {

            //throw new RuntimeException("鏈表數據不存在");

            return;

        }

        Node current = first;

        while(current != null){

            current.display();

            current = current.next;

        }

        System.out.println("---------------");

    }

    /**

     * 查找節點1

     * @param value

     * @return

     */

    public Node findByValue(long value){

        Node current = first;

        while(current != null){

            if (current.data != value) {

                current = current.next;

            }else {

                break;

            }

        }

        if (current == null) {

            System.out.println("沒找到");

            return null;

        }

        return current;

    }

    /**

     * 查找節點2

     * 

     * @param key

     * @return

     */

    public Node findByKey(long key) {

        Node current = first;

        while (current.data != key) {

            if (current.next == null) {

                System.out.println("沒找到");

                return null;

            }

            current = current.next;

        }

        return current;

    }

    /**

     * 根據索引查找對應的值

     * @param position

     * @return

     */

    public Node findByPosition(int position){

        Node current = first;

        //為什么是position - 1，因為要使用遍歷，讓current指向下一個， 所以position - 1的下個node就是要找的值

        for (int i = 0; i < position - 1 ; i++) {

            current  = current.next;

        }

        return current;

    }

    public static void main(String[] args) {

        DoubleLinkList linkList = new DoubleLinkList();

        linkList.insertFirst(21);

        linkList.insertFirst(22);

        linkList.insertFirst(23);

        linkList.insertLast(24);

        linkList.insertLast(25);

        linkList.insertLast(26);

        linkList.insertLast(27);

        linkList.display();

        System.out.println("---查找-------------------------------------");

        linkList.findByKey(25).display();

        System.out.println("--刪除first-------------------------------------");

        //linkList.deleteFirst().display();

        ///linkList.deleteFirst().display();

        //linkList.deleteFirst().display();

        //linkList.deleteFirst().display();

        System.out.println("-刪除指定值---------------------------------------");

        linkList.deleteByKey(27).display();

        linkList.deleteByKey(21).display();

        System.out.println("----------------------------------------");

        linkList.display();

    }

}