十天学完基础数据结构-第四天（链表（Linked List））

链表的基本概念

链表是一种线性数据结构，与数组不同，链表的元素（节点）之间通过指针相互连接。链表有以下基本概念：

• 节点：链表中的每个数据项称为节点，每个节点包含数据和一个指向下一个节点的指针。
• 头节点：链表的第一个节点称为头节点，它通常用来表示整个链表的起始位置。
• 尾节点：链表的最后一个节点称为尾节点，它的指针通常指向空值（null）。

单链表和双链表的区别

链表可以分为单链表和双链表两种主要类型。

• 单链表：每个节点只包含指向下一个节点的指针。单链表具有较小的内存开销，但不能轻松地反向遍历。
• 双链表：每个节点包含指向下一个节点和上一个节点的指针。双链表允许双向遍历，但内存开销较大。

链表的常见操作

链表支持以下常见操作：

1. 插入节点：在链表中插入一个新节点，通常需要更新相邻节点的指针。
2. 删除节点：从链表中删除一个节点，通常需要更新相邻节点的指针。
3. 反转链表：将链表中的节点顺序颠倒。
4. 获取链表长度：获取链表中节点的数量。

下面是一个简单的C++示例，创建一个单链表，插入和删除节点，以及获取链表长度：

#include <iostream>

// 链表节点定义
struct Node {
    int data;     // 节点数据
    Node* next;   // 指向下一个节点的指针
};

int main() {
    // 创建链表头节点
    Node* head = nullptr;
    
    // 插入节点
    Node* newNode1 = new Node;
    newNode1->data = 1;
    newNode1->next = nullptr;
    head = newNode1;

    Node* newNode2 = new Node;
    newNode2->data = 2;
    newNode2->next = nullptr;
    newNode1->next = newNode2;

    // 删除节点
    delete newNode1;
    head = newNode2;

    // 获取链表长度
    int length = 0;
    Node* current = head;
    while (current != nullptr) {
        length++;
        current = current->next;
    }

    std::cout << "链表长度：" << length << std::endl;

    return 0;
}

练习题：

1. 单链表和双链表有什么主要区别？在什么情况下你会选择使用单链表或双链表？
2. 描述一种情况，其中链表比数组更适合存储和管理数据。
3. 如何在链表中插入一个新节点？这个操作的时间复杂度是多少？
4. 如何删除链表中的一个节点？这个操作的时间复杂度是多少？

单链表和双链表有什么主要区别？在什么情况下你会选择使用单链表或双链表？

• 单链表：单链表中的每个节点只包含一个指针，通常是指向下一个节点的指针。这种结构内存开销较小，但只能单向遍历。单链表适合在内存开销有限的情况下，需要单向访问数据的场景。
• 双链表：双链表中的每个节点包含两个指针，一个指向下一个节点，另一个指向前一个节点。这允许双向遍历，但内存开销较大。双链表适用于需要双向遍历或频繁在链表中间插入和删除节点的情况。

选择使用单链表或双链表取决于需求。如果只需要单向访问或内存受限，单链表可能更合适。如果需要双向遍历或频繁插入和删除节点，双链表可能更合适。

描述一种情况，其中链表比数组更适合存储和管理数据。

链表比数组更适合以下情况：

• 动态大小：当数据集的大小在运行时不断变化时，链表更适合，因为它可以动态分配和释放内存，而数组的大小通常是固定的。
• 频繁插入和删除：如果需要频繁插入和删除数据项，链表比数组更高效，因为插入和删除操作的时间复杂度为O(1)，而数组中的相同操作通常需要O(n)。
• 没有随机访问需求：如果只需要按顺序访问数据而不需要随机访问（使用索引），链表是一个不错的选择。

如何在链表中插入一个新节点？这个操作的时间复杂度是多少？

插入新节点的步骤如下：

• 创建一个新节点，设置其数据和指针。
• 更新新节点的指针，使其指向原链表中适当位置的节点。
• 更新原链表中相邻节点的指针，使其指向新节点。

这个操作的时间复杂度取决于插入位置。如果插入位置是已知的，时间复杂度是O(1)，因为只需修改指针。如果需要在链表中间插入，并且需要遍历找到插入位置，时间复杂度是O(n)，其中n是链表的长度。

如何删除链表中的一个节点？这个操作的时间复杂度是多少？

删除链表中的节点的步骤如下：

• 找到要删除的节点。
• 更新相邻节点的指针，将其跳过要删除的节点。
• 释放要删除的节点的内存。

这个操作的时间复杂度取决于查找要删除的节点的时间。如果删除位置是已知的，时间复杂度是O(1)，因为只需修改指针。如果需要遍历链表来查找要删除的节点，时间复杂度是O(n)，其中n是链表的长度。

注意，在删除节点之前，始终要确保释放节点的内存，以避免内存泄漏。