C++如何实现一个链表_C++手写单向链表的实现方法-C++-PHP中文网

C++如何实现一个链表_C++手写单向链表的实现方法

穿越時空

发布： 2025-11-12 12:12:04

原创

443人浏览过

首先定义节点结构ListNode，包含值和指向下一节点的指针，并提供构造函数初始化；接着实现LinkedList类，包含head指针及append、remove、find、print等方法，分别用于尾部插入、按值删除、查找和遍历输出，同时在析构函数中释放内存；最后通过main函数测试链表的基本操作，验证插入、删除、查找功能正确性。

c++如何实现一个链表_c++手写单向链表的实现方法

在C++中实现一个单向链表，核心是定义节点结构和管理指针操作。通过手动管理内存和指针链接，可以深入理解数据结构的底层机制。下面是一个简洁、实用的手写单向链表实现方法。

定义链表节点结构

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

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

登录后复制

这里使用构造函数初始化节点值，并将指针设为nullptr，避免野指针问题。

实现链表类的基本操作

封装链表操作到一个类中，便于管理和调用。常见操作包括插入、删除、查找和遍历。

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

插入节点（尾部插入）：

如果链表为空，新节点成为头节点。
否则遍历到末尾，将最后一个节点的next指向新节点。

删除节点（按值删除）：

表单大师AI

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

查看详情

从头开始查找目标值。
找到后调整前一个节点的next指针，跳过目标节点。
释放被删除节点的内存，防止泄漏。

查找节点：

从头节点开始逐个比较，直到找到匹配值或到达链表末尾。

完整示例代码

#include <iostream>
using namespace std;
<p>struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};</p><p>class LinkedList {
public:
ListNode* head;</p><pre class='brush:php;toolbar:false;'>LinkedList() : head(nullptr) {}

// 尾插法
void append(int val) {
    ListNode* newNode = new ListNode(val);
    if (!head) {
        head = newNode;
        return;
    }
    ListNode* cur = head;
    while (cur->next) {
        cur = cur->next;
    }
    cur->next = newNode;
}

// 删除第一个等于val的节点
bool remove(int val) {
    if (!head) return false;
    if (head->val == val) {
        ListNode* tmp = head;
        head = head->next;
        delete tmp;
        return true;
    }
    ListNode* cur = head;
    while (cur->next && cur->next->val != val) {
        cur = cur->next;
    }
    if (cur->next) {
        ListNode* tmp = cur->next;
        cur->next = tmp->next;
        delete tmp;
        return true;
    }
    return false;
}

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

// 打印链表
void print() {
    ListNode* cur = head;
    while (cur) {
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << endl;
}

// 析构函数释放内存
~LinkedList() {
    while (head) {
        ListNode* tmp = head;
        head = head->next;
        delete tmp;
    }
}

登录后复制

};

测试与使用

创建链表对象并进行基本操作验证功能正确性。

int main() {
    LinkedList list;
    list.append(1);
    list.append(2);
    list.append(3);
    list.print();        // 输出: 1 2 3
<pre class='brush:php;toolbar:false;'>list.remove(2);
list.print();        // 输出: 1 3

cout << list.find(3) << endl;  // 输出: 1 (true)

return 0;

登录后复制

}

基本上就这些。这个实现涵盖了单向链表的核心操作，适合学习和基础应用。注意手动管理new和delete，避免内存问题。不复杂但容易忽略细节，比如空指针判断和析构处理。

以上就是C++如何实现一个链表_C++手写单向链表的实现方法的详细内容，更多请关注php中文网其它相关文章！