概念

?鏈表是一種通過指針串聯(lián)在一起的線性結構舰罚，每一個節(jié)點是由兩部分組成朴肺，一個是數(shù)據(jù)域一個是指針域（存放指向下一個節(jié)點的指針）玷室，最后一個節(jié)點的指針域指向null（空指針的意思）俏扩。

鏈表的類型

1.單鏈表
鏈接的入口點稱為列表的頭結點也就是head花颗。

鏈表的存儲方式

?數(shù)組是在內(nèi)存中是連續(xù)分布的，但是鏈表在內(nèi)存中可不是連續(xù)分布的唬滑。鏈表是通過指針域的指針鏈接在內(nèi)存中各個節(jié)點告唆。所以鏈表中的節(jié)點在內(nèi)存中不是連續(xù)分布的 莫秆，而是散亂分布在內(nèi)存中的某地址上，分配機制取決于操作系統(tǒng)的內(nèi)存管理悔详。

鏈表的定義

// 單鏈表  
struct ListNode {  
    int val;  // 節(jié)點上存儲的元素  
    ListNode *next;  // 指向下一個節(jié)點的指針  
    ListNode(int x) : val(x), next(NULL) {}  // 節(jié)點的構造函數(shù)  
};  

同樣我們可以使用C++默認生成的構造函數(shù)镊屎，但是這個構造函數(shù)不會初始化任何成員變化。下面兩段程序可以體現(xiàn)對比茄螃。

ListNode* head = new ListNode(5);  

下面這個使用默認構造函數(shù)

ListNode* head = new ListNode();  
head->val = 5;  

所以如果不定義構造函數(shù)使用默認構造函數(shù)的話缝驳，在初始化的時候就不能直接給變量賦值。

鏈表的常用操作實現(xiàn)

• get(index)：獲取鏈表中第 index 個節(jié)點的值归苍。如果索引無效用狱，則返回-1。
• addAtHead(val)：在鏈表的第一個元素之前添加一個值為 val 的節(jié)點拼弃。插入后夏伊，新節(jié)點將成為鏈表的第一個節(jié)點。
• addAtTail(val)：將值為 val 的節(jié)點追加到鏈表的最后一個元素吻氧。
• addAtIndex(index,val)：在鏈表中的第 index 個節(jié)點之前添加值為 val 的節(jié)點溺忧。如果 index 等于鏈表的長度，則該節(jié)點將附加到鏈表的末尾盯孙。如果 index 大于鏈表長度鲁森，則不會插入節(jié)點。如果index小于0振惰，則在頭部插入節(jié)點歌溉。
• deleteAtIndex(index)：如果索引 index 有效，則刪除鏈表中的第 index 個節(jié)點骑晶。

class MyLinkedList {  
public:  
    // 定義鏈表節(jié)點結構體  
    struct LinkedNode {  
        int val;  
        LinkedNode* next;  
        LinkedNode(int val):val(val), next(nullptr){}  
    };  

    // 初始化鏈表  
    MyLinkedList() {  
        _dummyHead = new LinkedNode(0); // 這里定義的頭結點 是一個虛擬頭結點痛垛，而不是真正的鏈表頭結點  
        _size = 0;  
    }  

    // 獲取到第index個節(jié)點數(shù)值，如果index是非法數(shù)值直接返回-1桶蛔， 注意index是從0開始的匙头，第0個節(jié)點就是頭結點  
    int get(int index) {  
        if (index > (_size - 1) || index < 0) {  
            return -1;  
        }  
        LinkedNode* cur = _dummyHead->next;  
        while(index--){ // 如果--index 就會陷入死循環(huán)  
            cur = cur->next;  
        }  
        return cur->val;  
    }  

    // 在鏈表最前面插入一個節(jié)點，插入完成后羽圃，新插入的節(jié)點為鏈表的新的頭結點  
    void addAtHead(int val) {  
        LinkedNode* newNode = new LinkedNode(val);  
        newNode->next = _dummyHead->next;  
        _dummyHead->next = newNode;  
        _size++;  
    }  

    // 在鏈表最后面添加一個節(jié)點  
    void addAtTail(int val) {  
        LinkedNode* newNode = new LinkedNode(val);  
        LinkedNode* cur = _dummyHead;  
        while(cur->next != nullptr){  
            cur = cur->next;  
        }  
        cur->next = newNode;  
        _size++;  
    }  
  
    // 在第index個節(jié)點之前插入一個新節(jié)點乾胶，例如index為0，那么新插入的節(jié)點為鏈表的新頭節(jié)點朽寞。  
    // 如果index 等于鏈表的長度，則說明是新插入的節(jié)點為鏈表的尾結點  
    // 如果index大于鏈表的長度斩郎，則返回空  
    void addAtIndex(int index, int val) {  
        if (index > _size) {  
            return;  
        }  
        LinkedNode* newNode = new LinkedNode(val);  
        LinkedNode* cur = _dummyHead;  
        while(index--) {  
            cur = cur->next;  
        }  
        newNode->next = cur->next;  
        cur->next = newNode;  
        _size++;  
    }  

    // 刪除第index個節(jié)點脑融，如果index 大于等于鏈表的長度，直接return缩宜，注意index是從0開始的  
    void deleteAtIndex(int index) {  
        if (index >= _size || index < 0) {  
            return;  
        }  
        LinkedNode* cur = _dummyHead;  
        while(index--) {  
            cur = cur ->next;  
        }  
        LinkedNode* tmp = cur->next;  
        cur->next = cur->next->next;  
        delete tmp;  
        _size--;  
    }  

    // 打印鏈表  
    void printLinkedList() {  
        LinkedNode* cur = _dummyHead;  
        while (cur->next != nullptr) {  
            cout << cur->next->val << " ";  
            cur = cur->next;  
        }  
        cout << endl;  
    }  
private:  
    int _size;  
    LinkedNode* _dummyHead;  

};  

文章參考引用：
https://mp.weixin.qq.com/s/ntlZbEdKgnFQKZkSUAOSpQ
https://mp.weixin.qq.com/s/Cf95Lc6brKL4g2j8YyF3Mg
（如有侵權請聯(lián)系刪除）