摘要：記得在一個(gè)公司面試上有一道題，寫(xiě)一個(gè)雙向鏈表，包含鏈表的基本操作，插入，刪除，獲取長(zhǎng)度等操作，由于時(shí)間匆忙，代碼寫(xiě)的比較亂，連自己都沒(méi)眼看了，后來(lái)細(xì)想自己從來(lái)都沒(méi)有細(xì)心的寫(xiě)過(guò)數(shù)據(jù)結(jié)構(gòu)，總覺(jué)得只要原理明白了就萬(wàn)事大吉了，事實(shí)證明，理論和實(shí)踐還

記得在一個(gè)公司面試上有一道題，寫(xiě)一個(gè)雙向鏈表，包含鏈表的基本操作，插入，刪除，獲取長(zhǎng)度等操作，由于時(shí)間匆忙，代碼寫(xiě)的比較亂，連自己都沒(méi)眼看了，后來(lái)細(xì)想自己從來(lái)都沒(méi)有細(xì)心的寫(xiě)過(guò)數(shù)據(jù)結(jié)構(gòu)，總覺(jué)得只要原理明白了就萬(wàn)事大吉了，事實(shí)證明，理論和實(shí)踐還是有很大差距的。
水平有限，如果有錯(cuò)誤，還請(qǐng)不吝賜教

class Node {
     private Node previous;//前驅(qū)節(jié)點(diǎn)
     private Node next;//后繼節(jié)點(diǎn)
     private E e;//泛型元素值
     public Node(Node previous, Node next, E e) {
         this.previous = previous;
         this.next = next;
         this.e = e;
    }

下面以removeElement(E value)為例簡(jiǎn)單介紹

    public void removeElement(E value){
        Node index=this.first;//創(chuàng)建index節(jié)點(diǎn)指向first節(jié)點(diǎn)
        while(index!=null){
            if(index.e==value)break;
            index=index.next;
        }//while循環(huán)用于遍歷整個(gè)鏈表來(lái)獲取指向要?jiǎng)h除的節(jié)點(diǎn)指針
        index.previous.next=index.next;
        index.next.previous=index.previous;
        length--;
    }

index.previous表示要?jiǎng)h除節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
  index.previous.next=index.next;意思是將前驅(qū)節(jié)點(diǎn)的后項(xiàng)指針指向要?jiǎng)h除節(jié)點(diǎn)的后繼節(jié)點(diǎn)

同理index.next表示要?jiǎng)h除節(jié)點(diǎn)的后繼節(jié)點(diǎn)
index.next.previous=index.previous;意思是將后繼節(jié)點(diǎn)的前向指針指向要?jiǎng)h除節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
可能有點(diǎn)繞，簡(jiǎn)單畫(huà)個(gè)鏈表結(jié)構(gòu)圖就可以很明了了

insertNext(E baseElement,E value)和insertPrevious(E baseElement,E value)同理，這里不再贅述

DoubleLinkedList包含兩個(gè)節(jié)點(diǎn)指針（偽指針，java中沒(méi)有指針的概念）first和last，分別指向鏈表的第一個(gè)元素和最后一個(gè)元素

public class DoubleLinkedList {
    private Node first;//指向第一個(gè)元素
    private Node last;//指向最后一個(gè)元素
    private int length=0;//鏈表長(zhǎng)度
    class Node {
        private Node previous;
        private Node next;
        private E e;

        public Node(Node previous, Node next, E e) {
            this.previous = previous;
            this.next = next;
            this.e = e;
        }
    }
    /***
     * 向頭節(jié)點(diǎn)添加元素，節(jié)點(diǎn)結(jié)構(gòu)對(duì)外應(yīng)該是不可見(jiàn)的，所以這里只傳遞一個(gè)泛型的值e
     */
    public void addFirst(E e) {
        if (first == null) {//鏈表為空判斷
            Node node = new Node(null, null, e);//創(chuàng)建一個(gè)新的節(jié)點(diǎn)，前驅(qū)和后繼都為空
            this.first = node;
            this.last=node;//將first和last指針指向鏈表的第一個(gè)元素
            length++;//鏈表長(zhǎng)度自增一，下同
        }else{
            Node node=new Node(null,first,e);//鏈表不為空創(chuàng)建一個(gè)前驅(qū)為空，后繼為當(dāng)前first節(jié)點(diǎn)的節(jié)點(diǎn)，值為傳入的參數(shù)e
            this.first.previous=node;//當(dāng)前first的前驅(qū)設(shè)置為node
            this.first=node;//將first指針指向新節(jié)點(diǎn)
            length++;
        }
    }
/***
*addLast同addFirst
*/
    public void addLast(E e) {
        if (last == null) {
            Node node = new Node(null, null, e);
            this.first = node;
            this.last=node;
            length++;
        }else{
            Node node=new Node(last,null,e);
            this.last.next=node;
            this.last=node;
            length++;
        }
    }
    public void insertPrevious(E baseElement,E value){
        Node index=this.first;
        while(index!=null){
            if(index.e==baseElement)break;
            index=index.next;
        }
        Node insertValue=new Node(index.previous,index,value);
        index.previous.next=insertValue;
        index.previous=insertValue;
        length++;
    }
    public void insertNext(E baseElement,E value){
        Node index=this.first;
        while(index!=null){
            if(index.e==baseElement)break;
            index=index.next;
        }
        Node insertValue=new Node(index,index.next,value);
        index.next.previous=insertValue;
        index.next=insertValue;
        length++;
    }
    public void removeElement(E value){
        Node index=this.first;
        while(index!=null){
            if(index.e==value)break;
            index=index.next;
        }
        index.previous.next=index.next;
        index.next.previous=index.previous;
        length--;
    }
    public int getLength(){
        return length;
    }
    @Override
    public String toString() {
        StringBuffer sb=new StringBuffer();
        Node current=this.first;
        while(current!=null){
            sb.append(current.e+"->");
            current=current.next;
        }
        return sb.toString();
    }
    public static void main(String[] args) {
        DoubleLinkedList list=new DoubleLinkedList<>();
        list.addLast("value1");
        list.addLast("value2");
        list.addLast("value3");
        list.addLast("value4");
        list.addFirst("value0");
        list.insertPrevious("value3","insertValue");
        list.insertNext("value3","insertValue2");
        System.out.println(list.toString());
        System.out.println("鏈表的長(zhǎng)度是"+list.getLength());
        list.removeElement("value3");
        System.out.println(list.toString());
        System.out.println("鏈表的長(zhǎng)度是"+list.getLength());
    }
}