数据结构--链表（C/C++）

概念

链表是一种通过指针串联在一起的线性结构，每一个节点是由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

链表的类型

1.单链表
链接的入口点称为列表的头结点也就是head。

2.双链表
单链表中的节点只能指向节点的下一个节点。而双链表每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。
双链表既可以向前查询也可以向后查询。

链表的存储方式

数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。链表是通过指针域的指针链接在内存中各个节点。所以链表中的节点在内存中不是连续分布的，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

链表的定义

// 单链表  
struct ListNode {  
    int val;  // 节点上存储的元素  
    ListNode *next;  // 指向下一个节点的指针  
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数  
};

同样我们可以使用C++默认生成的构造函数，但是这个构造函数不会初始化任何成员变化。下面两段程序可以体现对比。

ListNode* head = new ListNode(5);

下面这个使用默认构造函数

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

所以如果不定义构造函数使用默认构造函数的话，在初始化的时候就不能直接给变量赋值。

链表的常用操作实现

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

class MyLinkedList {  
public:  
    // 定义链表节点结构体  
    struct LinkedNode {  
        int val;  
        LinkedNode* next;  
        LinkedNode(int val):val(val), next(nullptr){}  
    };  

    // 初始化链表  
    MyLinkedList() {  
        _dummyHead = new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点  
        _size = 0;  
    }  

    // 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点  
    int get(int index) {  
        if (index > (_size - 1) || index < 0) {  
            return -1;  
        }  
        LinkedNode* cur = _dummyHead->next;  
        while(index--){ // 如果--index 就会陷入死循环  
            cur = cur->next;  
        }  
        return cur->val;  
    }  

    // 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点  
    void addAtHead(int val) {  
        LinkedNode* newNode = new LinkedNode(val);  
        newNode->next = _dummyHead->next;  
        _dummyHead->next = newNode;  
        _size++;  
    }  

    // 在链表最后面添加一个节点  
    void addAtTail(int val) {  
        LinkedNode* newNode = new LinkedNode(val);  
        LinkedNode* cur = _dummyHead;  
        while(cur->next != nullptr){  
            cur = cur->next;  
        }  
        cur->next = newNode;  
        _size++;  
    }  
  
    // 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。  
    // 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点  
    // 如果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个节点，如果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
（如有侵权请联系删除）