c++中的通用链表

基础概念

C++中的通用链表是一种基本的数据结构，它由一系列节点组成，每个节点包含数据部分和一个指向下一个节点的指针。链表可以动态地分配内存，允许在任何位置插入或删除节点，而不需要移动其他元素。

优势

动态内存分配：链表不需要预先分配固定大小的内存空间。
插入和删除效率高：在链表中插入或删除节点只需要改变相邻节点的指针，不需要移动大量数据。
灵活性：链表的大小可以根据需要动态增长或缩小。

类型

单链表：每个节点只有一个指向下一个节点的指针。
双链表：每个节点有两个指针，一个指向前一个节点，一个指向后一个节点。
循环链表：链表的最后一个节点指向第一个节点，形成一个环。

应用场景

数据缓存：链表可以用于实现LRU（最近最少使用）缓存算法。
任务调度：操作系统可以使用链表来管理待处理的任务。
实现其他数据结构：如栈、队列等可以通过链表来实现。

示例代码

以下是一个简单的单链表的实现：

#include <iostream>

struct Node {
    int data;
    Node* next;
};

class LinkedList {
public:
    LinkedList() : head(nullptr) {}

    void append(int value) {
        if (!head) {
            head = new Node{value, nullptr};
        } else {
            Node* current = head;
            while (current->next) {
                current = current->next;
            }
            current->next = new Node{value, nullptr};
        }
    }

    void display() {
        Node* current = head;
        while (current) {
            std::cout << current->data << " -> ";
            current = current->next;
        }
        std::cout << "nullptr" << std::endl;
    }

private:
    Node* head;
};

int main() {
    LinkedList list;
    list.append(1);
    list.append(2);
    list.append(3);
    list.display();
    return 0;
}

可能遇到的问题及解决方法

问题：链表节点内存泄漏

原因：在删除节点时没有正确释放内存。

解决方法：确保在删除节点时释放其内存。

void deleteNode(int value) {
    if (!head) return;
    if (head->data == value) {
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
    }
    Node* current = head;
    while (current->next && current->next->data != value) {
        current = current->next;
    }
    if (current->next) {
        Node* temp = current->next;
        current->next = current->next->next;
        delete temp;
    }
}

问题：链表遍历时访问空指针

原因：在遍历链表时没有正确检查空指针。

解决方法：在访问下一个节点之前检查当前节点是否为空。

void display() {
    Node* current = head;
    while (current) {
        std::cout << current->data << " -> ";
        current = current->next;
    }
    std::cout << "nullptr" << std::endl;
}