C++ 实现链表深入讲解

链表的基本概念

链表是一种常见的数据结构，它通过节点（Node）来存储数据，节点之间通过指针相互连接，形成一种链式的存储结构。与数组不同，链表的内存分配是动态的，不需要预先知道数据的数量，因此在某些场景下具有更高的灵活性。

在链表中，每个节点通常包含两部分：数据部分和指针部分。数据部分用于存储实际的数据，而指针部分则用于指向下一个节点（在单向链表中）或前一个节点和下一个节点（在双向链表中）。链表的起始节点称为头节点（Head），链表的最后一个节点的指针通常指向 nullptr（表示链表的结束）。

C++ 实现单向链表

1. 节点定义 首先，我们需要定义链表的节点结构。在 C++ 中，可以使用结构体（struct）或类（class）来定义节点。以下是使用结构体定义单向链表节点的示例：

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

在上述代码中，ListNode 结构体包含两个成员变量：val 用于存储节点的数据，类型为 int；next 是一个指针，指向下一个节点，初始化为 nullptr。构造函数 ListNode(int x) 用于初始化节点的数据 val。

2. 链表操作 - 插入节点 插入节点是链表常用的操作之一。我们可以在链表的头部插入节点，也可以在链表的尾部插入节点，还可以在指定位置插入节点。

   • 头部插入

ListNode* insertAtHead(ListNode* head, int val) {
    ListNode* newNode = new ListNode(val);
    newNode->next = head;
    return newNode;
}

上述代码实现了在链表头部插入节点的功能。首先创建一个新的节点 newNode，并将其 next 指针指向当前的头节点 head，然后返回新的头节点 newNode。

• 尾部插入

ListNode* insertAtTail(ListNode* head, int val) {
    ListNode* newNode = new ListNode(val);
    if (head == nullptr) {
        return newNode;
    }
    ListNode* current = head;
    while (current->next != nullptr) {
        current = current->next;
    }
    current->next = newNode;
    return head;
}

在链表尾部插入节点时，首先判断链表是否为空。如果为空，则新节点就是头节点，直接返回。否则，遍历链表找到最后一个节点（即 next 指针为 nullptr 的节点），然后将该节点的 next 指针指向新节点。

• 指定位置插入

ListNode* insertAtPosition(ListNode* head, int val, int pos) {
    if (pos == 0) {
        return insertAtHead(head, val);
    }
    ListNode* newNode = new ListNode(val);
    ListNode* current = head;
    int count = 0;
    while (current != nullptr && count < pos - 1) {
        current = current->next;
        count++;
    }
    if (current == nullptr) {
        return head;
    }
    newNode->next = current->next;
    current->next = newNode;
    return head;
}

在指定位置插入节点时，首先判断是否要在头部插入（pos == 0），如果是则调用 insertAtHead 函数。否则，遍历链表找到要插入位置的前一个节点，然后将新节点插入到该节点之后。

3. 链表操作 - 删除节点 删除节点也是链表的重要操作。同样，我们可以删除链表头部的节点、尾部的节点或指定位置的节点。

   • 头部删除

ListNode* deleteAtHead(ListNode* head) {
    if (head == nullptr) {
        return nullptr;
    }
    ListNode* temp = head;
    head = head->next;
    delete temp;
    return head;
}

在删除链表头部节点时，首先判断链表是否为空。如果不为空，保存当前头节点的指针 temp，将头节点指向下一个节点，然后释放 temp 所指向的内存。

• 尾部删除

ListNode* deleteAtTail(ListNode* head) {
    if (head == nullptr) {
        return nullptr;
    }
    if (head->next == nullptr) {
        delete head;
        return nullptr;
    }
    ListNode* current = head;
    while (current->next->next != nullptr) {
        current = current->next;
    }
    ListNode* temp = current->next;
    current->next = nullptr;
    delete temp;
    return head;
}

删除链表尾部节点时，先判断链表是否为空或只有一个节点。如果只有一个节点，直接删除并返回 nullptr。否则，遍历链表找到倒数第二个节点，保存其 next 指针（即最后一个节点的指针），将倒数第二个节点的 next 指针设为 nullptr，然后释放最后一个节点的内存。

• 指定位置删除

ListNode* deleteAtPosition(ListNode* head, int pos) {
    if (pos == 0) {
        return deleteAtHead(head);
    }
    ListNode* current = head;
    int count = 0;
    while (current != nullptr && count < pos - 1) {
        current = current->next;
        count++;
    }
    if (current == nullptr || current->next == nullptr) {
        return head;
    }
    ListNode* temp = current->next;
    current->next = current->next->next;
    delete temp;
    return head;
}

删除指定位置节点时，首先判断是否要删除头部节点（pos == 0），如果是则调用 deleteAtHead 函数。否则，遍历链表找到要删除位置的前一个节点，保存要删除节点的指针 temp，将前一个节点的 next 指针绕过要删除的节点，然后释放 temp 所指向的内存。

4. 链表遍历 遍历链表是为了访问链表中的每一个节点。在单向链表中，通常从头部开始，通过 next 指针依次访问每个节点，直到遇到 nullptr。

void traverse(ListNode* head) {
    ListNode* current = head;
    while (current != nullptr) {
        std::cout << current->val << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

上述代码实现了链表的遍历功能，它从链表的头节点开始，输出每个节点的数据，直到链表结束。

C++ 实现双向链表

1. 节点定义 双向链表的节点除了包含数据部分和指向下一个节点的指针外，还包含一个指向前一个节点的指针。以下是双向链表节点的定义：

struct DoublyListNode {
    int val;
    DoublyListNode* prev;
    DoublyListNode* next;
    DoublyListNode(int x) : val(x), prev(nullptr), next(nullptr) {}
};

在 DoublyListNode 结构体中，prev 指针指向前一个节点，next 指针指向后一个节点。

2. 链表操作 - 插入节点
   • 头部插入

DoublyListNode* insertAtHeadDoubly(DoublyListNode* head, int val) {
    DoublyListNode* newNode = new DoublyListNode(val);
    if (head != nullptr) {
        head->prev = newNode;
        newNode->next = head;
    }
    return newNode;
}

在双向链表头部插入节点时，首先创建新节点 newNode。如果链表不为空，将当前头节点的 prev 指针指向新节点，新节点的 next 指针指向当前头节点，然后返回新节点作为新的头节点。

• 尾部插入

DoublyListNode* insertAtTailDoubly(DoublyListNode* head, int val) {
    DoublyListNode* newNode = new DoublyListNode(val);
    if (head == nullptr) {
        return newNode;
    }
    DoublyListNode* current = head;
    while (current->next != nullptr) {
        current = current->next;
    }
    current->next = newNode;
    newNode->prev = current;
    return head;
}

在双向链表尾部插入节点时，与单向链表类似，先判断链表是否为空。如果不为空，遍历到链表尾部，将当前尾节点的 next 指针指向新节点，新节点的 prev 指针指向当前尾节点。

• 指定位置插入

DoublyListNode* insertAtPositionDoubly(DoublyListNode* head, int val, int pos) {
    if (pos == 0) {
        return insertAtHeadDoubly(head, val);
    }
    DoublyListNode* newNode = new DoublyListNode(val);
    DoublyListNode* current = head;
    int count = 0;
    while (current != nullptr && count < pos - 1) {
        current = current->next;
        count++;
    }
    if (current == nullptr) {
        return head;
    }
    newNode->next = current->next;
    newNode->prev = current;
    if (current->next != nullptr) {
        current->next->prev = newNode;
    }
    current->next = newNode;
    return head;
}

在双向链表指定位置插入节点时，首先判断是否要在头部插入。如果不是，遍历链表找到指定位置的前一个节点。然后调整指针，将新节点插入到该位置，注意要同时调整 prev 和 next 指针。

3. 链表操作 - 删除节点
   • 头部删除

DoublyListNode* deleteAtHeadDoubly(DoublyListNode* head) {
    if (head == nullptr) {
        return nullptr;
    }
    DoublyListNode* temp = head;
    head = head->next;
    if (head != nullptr) {
        head->prev = nullptr;
    }
    delete temp;
    return head;
}

在双向链表头部删除节点时，保存当前头节点指针 temp，将头节点指向下一个节点。如果新的头节点不为空，将其 prev 指针设为 nullptr，然后释放 temp 所指向的内存。

• 尾部删除

DoublyListNode* deleteAtTailDoubly(DoublyListNode* head) {
    if (head == nullptr) {
        return nullptr;
    }
    if (head->next == nullptr) {
        delete head;
        return nullptr;
    }
    DoublyListNode* current = head;
    while (current->next->next != nullptr) {
        current = current->next;
    }
    DoublyListNode* temp = current->next;
    current->next = nullptr;
    delete temp;
    return head;
}

在双向链表尾部删除节点时，与单向链表类似，先判断链表是否为空或只有一个节点。如果只有一个节点，直接删除并返回 nullptr。否则，遍历到倒数第二个节点，保存最后一个节点的指针 temp，将倒数第二个节点的 next 指针设为 nullptr，然后释放 temp 所指向的内存。

• 指定位置删除

DoublyListNode* deleteAtPositionDoubly(DoublyListNode* head, int pos) {
    if (pos == 0) {
        return deleteAtHeadDoubly(head);
    }
    DoublyListNode* current = head;
    int count = 0;
    while (current != nullptr && count < pos - 1) {
        current = current->next;
        count++;
    }
    if (current == nullptr || current->next == nullptr) {
        return head;
    }
    DoublyListNode* temp = current->next;
    if (current->next->next != nullptr) {
        current->next->next->prev = current;
    }
    current->next = current->next->next;
    delete temp;
    return head;
}

在双向链表指定位置删除节点时，首先判断是否要删除头部节点。如果不是，遍历链表找到要删除位置的前一个节点。然后调整指针，绕过要删除的节点，同时调整 prev 和 next 指针，最后释放要删除节点的内存。

4. 链表遍历 双向链表可以正向遍历和反向遍历。
   • 正向遍历

void traverseForwardDoubly(DoublyListNode* head) {
    DoublyListNode* current = head;
    while (current != nullptr) {
        std::cout << current->val << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

• 反向遍历

void traverseBackwardDoubly(DoublyListNode* head) {
    if (head == nullptr) {
        return;
    }
    DoublyListNode* current = head;
    while (current->next != nullptr) {
        current = current->next;
    }
    while (current != nullptr) {
        std::cout << current->val << " ";
        current = current->prev;
    }
    std::cout << std::endl;
}

正向遍历从链表头部开始，通过 next 指针依次访问每个节点。反向遍历则先找到链表尾部节点，然后通过 prev 指针反向访问每个节点。

链表的应用场景

1. 动态数据存储 链表适用于需要动态添加或删除数据的场景。例如，在实现一个简单的任务队列时，新任务可以随时添加到队列尾部，完成的任务可以从队列头部删除。链表的动态内存分配特性使得它在这种场景下比数组更高效，因为数组在添加或删除元素时可能需要移动大量的数据。

2. 实现栈和队列 栈和队列是常见的数据结构，链表可以很方便地实现它们。栈的操作特性是后进先出（LIFO），可以通过在链表头部进行插入和删除操作来实现栈。队列的操作特性是先进先出（FIFO），可以通过在链表头部删除元素，在链表尾部插入元素来实现队列。

3. 哈希表的冲突解决 在哈希表中，当不同的键值对映射到相同的哈希桶时，就会发生冲突。链表是解决哈希冲突的常用方法之一。每个哈希桶可以是一个链表的头节点，当发生冲突时，新的键值对被插入到链表中。

4. 操作系统中的内存管理 操作系统的内存管理模块可能会使用链表来管理空闲内存块。每个空闲内存块可以表示为链表中的一个节点，节点中存储内存块的大小和地址等信息。当需要分配内存时，从链表中查找合适大小的节点并将其从链表中删除；当释放内存时，将新的空闲内存块作为节点插入到链表中。

链表与数组的比较

1. 内存分配

   • 数组：数组在内存中是连续存储的，这意味着数组元素在内存中按顺序排列，地址是连续的。因此，数组在访问元素时效率很高，可以通过数组下标直接计算出元素的内存地址，时间复杂度为 O(1)。但是，数组的大小在声明时就必须确定，而且在运行时不能轻易改变，这限制了其灵活性。如果数组声明过大，会浪费内存；声明过小，可能无法满足数据存储需求。
   • 链表：链表的内存分配是动态的，每个节点在堆内存中独立分配空间，节点之间通过指针连接。这使得链表在运行时可以根据需要随时添加或删除节点，非常灵活。然而，由于链表节点的内存地址不连续，访问链表中的某个节点时需要从头部开始遍历，时间复杂度为 O(n)，其中 n 是链表的长度。

2. 插入和删除操作

   • 数组：在数组中插入或删除元素时，如果在数组中间或开头位置操作，需要移动大量元素。例如，在数组中间插入一个元素，需要将插入位置后面的所有元素向后移动一位，时间复杂度为 O(n)。在数组尾部插入或删除元素相对简单，时间复杂度为 O(1)，但前提是数组有足够的预留空间。
   • 链表：在链表中插入或删除节点时，只需要修改相关节点的指针即可，不需要移动大量数据。例如，在单向链表的头部插入节点，只需要修改新节点的 next 指针和头节点指针，时间复杂度为 O(1)。在链表中间或尾部插入或删除节点，虽然需要先找到插入或删除位置，但整体时间复杂度仍然比数组在相同位置操作要低，通常为 O(n)，因为不需要移动数据，只需要修改指针。

3. 内存利用率

   • 数组：由于数组内存连续，可能会存在内存碎片问题。如果数组大小声明过大，会浪费大量内存空间。而且，数组的内存是一次性分配的，如果系统没有足够的连续内存块，可能无法分配成功。
   • 链表：链表的内存是动态分配的，每个节点按需分配内存，相对更能有效利用内存。但是，链表每个节点除了存储数据外，还需要额外的指针空间来存储指向下一个节点（或前一个节点）的地址，这会增加内存开销。

链表实现中的注意事项

1. 内存管理 在链表的实现中，动态内存分配和释放是非常关键的。每次使用 new 关键字创建新节点时，都要确保在不再需要该节点时使用 delete 关键字释放其内存，否则会导致内存泄漏。例如，在删除节点的操作中，一定要记得释放被删除节点所占用的内存。

2. 指针操作 链表中大量使用指针，指针操作不当很容易导致程序崩溃。例如，在修改节点的 next 指针或 prev 指针时，要确保指针的正确性。特别是在双向链表中，同时修改 prev 和 next 指针时，要注意操作顺序，避免出现悬空指针（指向已释放内存的指针）。

3. 边界条件处理 在链表的各种操作中，要充分考虑边界条件。例如，链表为空时的插入、删除操作，链表只有一个节点时的各种操作等。在编写代码时，对这些边界条件进行特殊处理可以提高程序的健壮性。

4. 性能优化 在一些频繁操作链表的场景下，可以考虑性能优化。例如，在双向链表中，如果经常需要从尾部插入和删除节点，可以维护一个尾指针，这样在尾部操作时时间复杂度可以从 O(n) 降低到 O(1)。另外，在遍历链表时，如果链表长度较长，可以考虑使用更高效的遍历算法，或者在某些情况下使用缓存来减少对链表的重复遍历。

通过以上对 C++ 实现链表的深入讲解，我们了解了链表的基本概念、单向链表和双向链表的实现方法、链表的应用场景、链表与数组的比较以及链表实现中的注意事项。链表作为一种重要的数据结构，在计算机编程中有着广泛的应用，熟练掌握链表的实现和操作对于提高编程能力和解决实际问题具有重要意义。无论是在算法设计、数据存储还是操作系统等领域，链表都发挥着不可或缺的作用。在实际应用中，根据具体的需求和场景，合理选择使用链表或其他数据结构，可以提高程序的效率和性能。