摘要：前言數(shù)據(jù)結(jié)構(gòu)與算法專題會不定時更新，歡迎各位讀者監(jiān)督。本文介紹另一種數(shù)據(jù)結(jié)構(gòu)鏈表，包括鏈表的特點特點鏈表的創(chuàng)建刪除插入和輸出，文末給出代碼和一道常見的關(guān)于鏈表的面試題。

聲明：碼字不易，轉(zhuǎn)載請注明出處，歡迎文章下方討論交流。

前言：Java數(shù)據(jù)結(jié)構(gòu)與算法專題會不定時更新，歡迎各位讀者監(jiān)督。本文介紹另一種數(shù)據(jù)結(jié)構(gòu)——鏈表，包括鏈表的特點特點、鏈表的創(chuàng)建、刪除、插入和輸出，文末給出java代碼和一道常見的關(guān)于鏈表的面試題。

鏈表是由若干結(jié)點組成，每個結(jié)點至少包括兩部分信息：一個是元素數(shù)據(jù)，一個是指向下一個（上一個）元素地址的指針。鏈表的存儲在物理上是非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素之間是通過每個元素的指針來關(guān)聯(lián)的。

與數(shù)組相比，鏈表獨特的存儲結(jié)構(gòu)克服了數(shù)組提前需要設(shè)置長度的缺點，在運行時可以動態(tài)的快速的添加和刪除元素；計算機的存儲空間并非連續(xù)的，而鏈表則可以靈活的使用存儲空間，能更好的對計算機內(nèi)存進行動態(tài)管理。

鏈表分為單鏈表、雙鏈表、和循環(huán)鏈表，雙鏈表的每個結(jié)點有兩個指針，分別指向前一個元素和后一個元素，循環(huán)鏈表的尾結(jié)點指針不是null，而是指向頭結(jié)點元素的地址。

鏈表的操作包括了創(chuàng)建、刪除、插入、輸出。
創(chuàng)建就是空間的分配，將頭、尾指針及鏈表結(jié)點個數(shù)等初始化。
刪除和插入根據(jù)被操作元素的位置可以細分為頭刪除（插入），尾刪除（插入），中間刪除（插入），以下詳細介紹。

創(chuàng)建和輸出比較簡單，不做具體分析，后面直接給出代碼

2.1 插入操作

插入分為頭插入，尾插入，中間插入

頭插入
頭插入實際上是增加一個新節(jié)點，然后把新增加的結(jié)點指針指向原來頭指針指向的元素，再把頭指針指向新增的節(jié)點。

尾插入
尾插入也是增加一個新節(jié)點，該節(jié)點指針置為null，然后把原尾結(jié)點指針指向新增加的節(jié)點，最后把尾指針指向新增加的節(jié)點即可。

中間插入
中間插入稍復(fù)雜，首先增加一個節(jié)點，然后新增節(jié)點的指針指向插入位置的后一個節(jié)點，把插入位置的前一個節(jié)點指針指向新插入節(jié)點即可。

2.2 刪除操作

刪除與插入類似，根據(jù)被操作元素的位置分為頭刪除，尾刪除，中間刪除

頭刪除
刪除頭元素時，先將頭指針指向下一個節(jié)點，然后把原頭結(jié)點的指針置空即可

尾刪除
刪除尾元素時，首先找到鏈表倒數(shù)第2個元素，然后把尾指針指向這個元素，接著把原倒數(shù)第2個元素的指針置空。

中間刪除
刪除中間元素相對復(fù)雜一些，首先將要刪除的節(jié)點的前一個節(jié)點指針指向要刪除的節(jié)點的下一個節(jié)點，然后把要刪除節(jié)點的指針置空。

鏈表是由一系列節(jié)點組成，首先是節(jié)點部分

public class Node {
    private int data;  //數(shù)據(jù)
    private Node next;  //指針
    
    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }    
}

鏈表節(jié)點部分的代碼實現(xiàn)了兩個部分，一個是數(shù)據(jù)，一個是指向下一個節(jié)點的指針（由于java中摒棄了c++中的指針概念，準(zhǔn)確的說應(yīng)該是引用）
以下是鏈表的代碼實現(xiàn)：

public class Link {
    private int size = 0;
    private Node first;
    private Node last;
    
    /*鏈表初始化 */
    public Link(){}
    
    /**
     * 返回鏈表長度
     * @return 返回鏈表長度
     */
    public int getLength(){
        return size;
    }
    
    /**
     * 獲取指定位置的節(jié)點
     * @param index 位置[0~size]
     * @return 
     */
    public Node get(int index){
        Node temp = first;
        for(int i=0;isize){
                throw new IndexOutOfBoundsException("刪除位置超界");
            }else{
                Node temp = get(index-1);
                temp.setNext(get(index));
                temp.setNext(null);
                size--;
            }
        }
    }
    
    /**
     * 獲取鏈表
     */
    public void getAll(){
        Node temp = first;
        System.out.println(temp.getData());
        while(temp.getNext()!=null){
            System.out.print(temp.getData()+"-->");
            temp = temp.getNext();
            size--;
        }
    }    
}

public class LinkTest {
    public static void main(String[] args) {
        Link link = new Link();
        link.addHead(1); //1
        link.printLink();
        
        link.addHead(5); //5->1
        link.printLink();
        
        link.addTail(9); //5->1->9
        link.printLink();
        
        link.addTail(7); //5->1->9->7
        link.printLink();
        
        link.add(3,8);  //5->1->9->8->7
        link.printLink();        
        System.out.println("鏈表長度："+link.getLength()); //5
        
        link.deleFirst();  //1->9->8->7
        link.printLink();
        
        link.deleLast();  //1->9->8
        link.printLink();
        
        link.deleMid(1);  //1->8
        link.printLink();
        
        System.out.println("鏈表長度："+link.getLength()); //2        
    }
}

鏈表的操作稍稍復(fù)雜，插入和刪除要考慮很多因素（邊界條件、異常），寫完代碼要逐個測試，出現(xiàn)不一致的情況逐步調(diào)試、跟蹤變量。記住插入和刪除的步驟（六張圖），編碼時仔細一點一般不會出現(xiàn)問題。

以上代碼經(jīng)過測試無誤，歡迎收藏轉(zhuǎn)發(fā)，歡迎下方討論交流^_^
碼字——>畫圖——>編碼——>調(diào)試 一趟下來不容易，如果對您有幫助請收藏和點贊

更新：我的另一篇的文章Java數(shù)據(jù)結(jié)構(gòu)與算法——鏈表面試介紹了鏈表的特點，使用場景、鏈表的性能分析以及一道經(jīng)典的鏈表面試題——鏈的反轉(zhuǎn)問題，請移步閱讀參考。