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

穿越時空

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

475人浏览过

来源于php中文网

原创

首先定义节点结构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指向新节点。

删除节点（按值删除）：

情感家园企业站5.0 多语言多风格版

一套面向小企业用户的企业网站程序！功能简单，操作简单。实现了小企业网站的很多实用的功能，如文章新闻模块、图片展示、产品列表以及小型的下载功能，还同时增加了邮件订阅等相应模块。公告，友情链接等这些通用功能本程序也同样都集成了！同时本程序引入了模块功能，只要在系统默认模板上创建模块，可以在任何一个语言环境（或任意风格）的适当位置进行使用！

下载

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

查找节点：

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

完整示例代码

#include 
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
class LinkedList {
public:
ListNode* head;
LinkedList() : head(nullptr) {}

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

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

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

// 打印链表
void print() {
    ListNode* cur = head;
    while (cur) {
        cout zuojiankuohaophpcnzuojiankuohaophpcn cur-youjiankuohaophpcnval zuojiankuohaophpcnzuojiankuohaophpcn " ";
        cur = cur-youjiankuohaophpcnnext;
    }
    cout zuojiankuohaophpcnzuojiankuohaophpcn endl;
}

// 析构函数释放内存
~LinkedList() {
    while (head) {
        ListNode* tmp = head;
        head = head-youjiankuohaophpcnnext;
        delete tmp;
    }
}
};测试与使用
创建链表对象并进行基本操作验证功能正确性。
int main() {
    LinkedList list;
    list.append(1);
    list.append(2);
    list.append(3);
    list.print();        // 输出: 1 2 3
list.remove(2);
list.print();        // 输出: 1 3

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

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