C++ 链表的全面解析

一、什么是链表

链表是一种线性数据结构，与数组不同的是，链表元素不存储在连续的内存空间中，而是通过指针链接在一起。链表的每个节点由两个部分组成，一个是存储数据的部分，另一个是指向下一个节点的指针。

链表主要分为单向链表、双向链表和循环链表。其中，单向链表每个节点只有一个指针指向下一个节点，双向链表每个节点有两个指针，一个指向前一个节点，一个指向后一个节点，循环链表最后一个节点指向链表的头结点，形成一个环。

二、链表的优点和缺点

链表相比于数组的优点在于：

1、动态分配内存，节点数可以随时改变；

2、插入和删除操作方便，不需要移动大量元素；

3、不需要预先分配大量内存空间，节省内存。

链表相比于数组的缺点在于：

1、不支持随机访问，只能从头或尾开始遍历；

2、空间占用多，需要额外的指针存储节点间关系；

3、缓存不友好，由于链表元素间不连续，不易被缓存。

三、链表的基本操作

1. 创建链表

class ListNode {
public:
    int val;
    ListNode* next;
    ListNode(int val) {
        this->val = val;
        this->next = nullptr;
    }
};

ListNode* createList(vector nums) {
    ListNode* head = new ListNode(0);
    ListNode* cur = head;
    for (int num : nums) {
        ListNode* node = new ListNode(num);
        cur->next = node;
        cur = cur->next;
    }
    return head->next;
}

  

2. 遍历链表

void traverseList(ListNode* head) {
    ListNode* cur = head;
    while (cur != nullptr) {
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << endl;
}

3. 插入节点

void insertNode(ListNode* head, int val, int index) {
    ListNode* node = new ListNode(val);
    ListNode* cur = head;
    for (int i = 0; cur != nullptr && i < index - 1; i++) {
        cur = cur->next;
    }
    if (cur == nullptr) {
        return;
    }
    node->next = cur->next;
    cur->next = node;
}

4. 删除节点

void deleteNode(ListNode* head, int index) {
    ListNode* cur = head;
    for (int i = 0; cur != nullptr && i < index - 1; i++) {
        cur = cur->next;
    }
    if (cur == nullptr || cur->next == nullptr) {
        return;
    }
    ListNode* del = cur->next;
    cur->next = del->next;
    delete del;
}

四、链表的应用场景

链表常用于实现如下的数据结构：

1、队列和栈；

2、图、树等复杂数据结构的节点存储和遍历；

3、处理海量数据，如链表分段处理大文件。

五、总结

链表作为一种常用的数据结构，具有一些独特的特点。在实际的编程工作中，我们需要根据具体情况选择合适的数据结构。掌握链表的基本操作，有助于我们更加高效地处理链表相关问题。