c++如何实现一个简单的链表_c++数据结构之链表实现_技术教程

链表通过指针连接非连续内存节点，实现高效插入删除。C++中定义ListNode结构含数据与指针，LinkedList类封装增删查遍功能，头插O(1)尾插O(n)，析构防泄漏，示例展示增删查操作，可扩展模板、逆序、双向等特性。

链表是一种常见的线性数据结构，它通过指针将一组零散的内存块串联起来，每个内存块称为一个节点。与数组不同，链表不需要连续的内存空间，因此在插入和删除操作上效率更高。下面介绍如何用 C++ 实现一个简单的单向链表。

定义链表节点

链表的基本单元是节点，每个节点包含两部分：数据域和指向下一个节点的指针。

struct ListNode { int data; // 存储的数据 ListNode* next; // 指向下一个节点的指针

// 构造函数，方便初始化
ListNode(int val) : data(val), next(nullptr) {}

};

这里使用结构体定义节点，构造函数用于简化节点创建过程。

实现链表类

我们可以封装一个简单的链表类，支持插入、删除、查找和遍历等基本操作。

class LinkedList { private: ListNode* head; // 头指针，指向链表第一个节点

public: // 构造函数 LinkedList() : head(nullptr) {}

// 析构函数：释放所有节点内存
~LinkedList() {
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

// 在链表头部插入新节点
void insertAtHead(int val) {
    ListNode* newNode = new ListNode(val);
    newNode->next = head;
    head = newNode;
}

// 在链表尾部插入新节点
void insertAtTail(int val) {
    ListNode* newNode = new ListNode(val);
    if (head == nullptr) {
        head = newNode;
        return;
    }
    ListNode* current = head;
    while (current->next != nullptr) {
        current = current->next;
    }
    current->next = newNode;
}

// 删除第一个值为val的节点
bool remove(int val) {
    if (head == nullptr) return false;

    if (head->data == val) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
        return true;
    }

    ListNode* current = head;
    while (current->next != nullptr && current->next->data != val) {
        current = current->next;
    }

    if (current->next == nullptr) return false;

    ListNode* temp = current->next;
    current->next = temp->next;
    delete temp;
    return true;
}

// 查找是否存在值为val的节点
bool find(int val) {
    ListNode* current = head;
    while (current != nullptr) {
        if (current->data == val) return true;
        current = current->next;
    }
    return false;
}

// 打印链表所有元素
void print() {
    ListNode* current = head;
    while (current != nullptr) {
        std::cout << current->data << " -> ";
        current = current->next;
    }
    std::cout << "nullptr" << std::endl;
}

};

说明：

insertAtHead：在链表开头插入，时间复杂度 O(1)
insertAtTail：遍历到末尾插入，时间复杂度 O(n)
remove：找到目标节点并释放内存，注意处理头节点特殊情况
find 和 print：遍历链表完成查找或输出
析构函数：防止内存泄漏，逐个释放节点

使用示例

下面是一个简单的测试代码，演示如何使用这个链表：

#include iostream> using namespace std;

int main() { LinkedList list;

list.insertAtTail(10);
list.insertAtTail(20);
list.insertAtHead(5);
list.print();  // 输出: 5 -> 10 -> 20 -> nullptr

cout zuojiankuohaophpcnzuojiankuohaophpcn "查找10: " zuojiankuohaophpcnzuojiankuohaophpcn (list.find(10) ? "存在" : "不存在") zuojiankuohaophpcnzuojiankuohaophpcn endl;

list.remove(10);
list.print();  // 输出: 5 -> 20 -> nullptr

return 0;

}