C++如何实现一个链表_C++数据结构之单链表的节点定义与操作-C++-PHP中文网

C++如何实现一个链表_C++数据结构之单链表的节点定义与操作

尼克

发布： 2025-11-21 19:16:02

原创

537人浏览过

单链表通过节点结构实现，包含数据和指针域，支持头部插入、遍历等操作。定义ListNode结构体，含int型val和指向下一节点的next指针，并提供构造函数初始化；insertAtHead函数以引用接收头指针，在O(1)时间插入新节点；traverse函数遍历链表并输出各节点值，直至current为空。

c++如何实现一个链表_c++数据结构之单链表的节点定义与操作

在C++中实现一个单链表，核心是定义节点结构并封装常用操作。单链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。下面从节点定义开始，逐步说明基本操作的实现方式。

单链表节点的定义

节点是链表的基本单元。使用struct可以简洁地定义一个节点，包含数据域和指针域：

struct ListNode {
    int val;                // 数据域，存储整数值
    ListNode* next;         // 指针域，指向下一个节点
<pre class='brush:php;toolbar:false;'>// 构造函数，便于初始化
ListNode(int x) : val(x), next(nullptr) {}

登录后复制

};

构造函数让节点创建更方便，例如ListNode* node = new ListNode(10);会自动将值设为10，next设为nullptr。

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

常见操作的实现

基于上述节点结构，可以实现插入、删除、遍历等基础操作。以下是几个典型功能的写法：

1. 头部插入节点

将新节点插入到链表最前面，时间复杂度为O(1)：

void insertAtHead(ListNode*& head, int value) {
    ListNode* newNode = new ListNode(value);
    newNode->next = head;
    head = newNode;
}

登录后复制

注意参数使用引用（&head），确保头指针能被修改。

2. 遍历链表

AssemblyAI

转录和理解语音的AI模型

查看详情

从头到尾访问每个节点，打印数据：

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

登录后复制

3. 删除指定值的节点

找到第一个值等于给定值的节点并删除：

void deleteByValue(ListNode*& head, int value) {
    if (!head) return;
<pre class='brush:php;toolbar:false;'>if (head->val == value) {
    ListNode* temp = head;
    head = head->next;
    delete temp;
    return;
}

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

if (current->next) {
    ListNode* temp = current->next;
    current->next = current->next->next;
    delete temp;
}

登录后复制

}

完整使用示例

把上面的操作组合起来，可以这样测试：

int main() {
    ListNode* head = nullptr;
<pre class='brush:php;toolbar:false;'>insertAtHead(head, 3);
insertAtHead(head, 2);
insertAtHead(head, 1);

traverse(head);  // 输出: 1 2 3

deleteByValue(head, 2);
traverse(head);  // 输出: 1 3

return 0;

登录后复制

}

记得在程序结束前释放所有动态分配的内存，避免泄漏。

基本上就这些。单链表虽然结构简单，但指针操作容易出错，尤其要注意空指针判断和头指针更新。掌握这些基础后，可以进一步实现尾插、查找、反转等功能。

以上就是C++如何实现一个链表_C++数据结构之单链表的节点定义与操作的详细内容，更多请关注php中文网其它相关文章！