c++怎么实现一个单向链表_单向链表数据结构实现-C++-PHP中文网

c++怎么实现一个单向链表_单向链表数据结构实现

裘德小鎮的故事

发布： 2025-09-27 18:42:01

原创

176人浏览过

实现单向链表需定义节点结构和操作接口，C++中通过类封装头指针及插入、删除、查找、遍历等方法，使用构造函数初始化，析构函数释放内存，确保安全操作；示例展示了头插、尾插、删除、查找和打印功能，包含空指针处理与自动内存管理，可扩展模板与高级功能。

c++怎么实现一个单向链表_单向链表数据结构实现

实现一个单向链表，核心是定义节点结构和操作接口。C++中可以通过类封装数据和操作，让链表更易用、安全。

定义链表节点

每个节点包含数据和指向下一个节点的指针。

struct ListNode {
    int data;           // 存储的数据（以int为例）
    ListNode* next;     // 指向下一个节点的指针
<pre class='brush:php;toolbar:false;'>// 构造函数，方便初始化
ListNode(int val) : data(val), next(nullptr) {}

登录后复制

};

设计链表类

封装头指针和常用操作，如插入、删除、查找、遍历等。

立即学习“C++免费学习笔记（深入）”；

表单大师AI

一款基于自然语言处理技术的智能在线表单创建工具，可以帮助用户快速、高效地生成各类专业表单。

查看详情

class SinglyLinkedList {
private:
    ListNode* head;  // 头节点指针
<p>public:
// 构造函数
SinglyLinkedList() : head(nullptr) {}</p><pre class='brush:php;toolbar:false;'>// 析构函数：释放所有节点内存
~SinglyLinkedList() {
    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) {
        ListNode* temp = current->next;
        current->next = current->next->next;
        delete temp;
        return true;
    }
    return false;
}

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

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

// 判断链表是否为空
bool isEmpty() const {
    return head == nullptr;
}

登录后复制

};

使用示例

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

#include <iostream>
using namespace std;
<p>int main() {
SinglyLinkedList list;</p><pre class='brush:php;toolbar:false;'>list.insertAtTail(10);
list.insertAtTail(20);
list.insertAtHead(5);
list.print();  // 输出: 5 -> 10 -> 20 -> nullptr

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

cout << "Contains 20? " << (list.find(20) ? "Yes" : "No") << endl;

return 0;

登录后复制

}

基本上就这些。通过封装，我们实现了增删查改和自动内存管理。可以根据需要扩展功能，比如支持模板泛型、指定位置插入、反转链表等。不复杂但容易忽略细节，比如空指针判断和内存释放。

以上就是c++++怎么实现一个单向链表_单向链表数据结构实现的详细内容，更多请关注php中文网其它相关文章！