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

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

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

鏈表是由若干結點組成，每個結點至少包括兩部分信息：一個是元素數據，一個是指向下一個（上一個）元素地址的指針。鏈表的存儲在物理上是非連續、非順序的存儲結構，數據元素之間是通過每個元素的指針來關聯的。

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

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

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

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

2.1 插入操作

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

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

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

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

2.2 刪除操作

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

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

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

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

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

public class Node {
    private int data;  //數據
    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;
    }    
}

鏈表節點部分的代碼實現了兩個部分，一個是數據，一個是指向下一個節點的指針（由于java中摒棄了c++中的指針概念，準確的說應該是引用）
以下是鏈表的代碼實現：

public class Link {
    private int size = 0;
    private Node first;
    private Node last;
    
    /*鏈表初始化 */
    public Link(){}
    
    /**
     * 返回鏈表長度
     * @return 返回鏈表長度
     */
    public int getLength(){
        return size;
    }
    
    /**
     * 獲取指定位置的節點
     * @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        
    }
}

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

以上代碼經過測試無誤，歡迎收藏轉發，歡迎下方討論交流^_^
碼字——>畫圖——>編碼——>調試 一趟下來不容易，如果對您有幫助請收藏和點贊

更新：我的另一篇的文章Java數據結構與算法——鏈表面試介紹了鏈表的特點，使用場景、鏈表的性能分析以及一道經典的鏈表面試題——鏈的反轉問題，請移步閱讀參考。