C++ 实现整数链表：创建、插入、删除、遍历、查询

链表是一种常见的数据结构，用于存储一系列的元素。每个节点包含一个值和一个指向下一个节点的指针。本文将详细介绍使用 C++ 实现整数链表的方法，包括链表节点类的定义、链表类的封装以及链表的基本操作，如插入节点、删除节点、遍历链表和查询节点。

链表节点类

首先，我们需要定义一个链表节点类 ListNode，它包含节点的值 val 和指向下一个节点的指针 next：

#include <iostream>
using namespace std;

// 链表节点类
class ListNode {
public:
    int val; // 节点的值
    ListNode* next; // 指向下一个节点的指针

    // 构造函数
    ListNode(int value) {
        val = value;
        next = nullptr;
    }
};

链表类

接下来，我们定义一个链表类 LinkedList，它包含链表的头节点 head：

// 链表类
class LinkedList {
private:
    ListNode* head; // 链表的头节点

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

    // 在链表末尾插入节点
    void insert(int value) {
        ListNode* newNode = new ListNode(value);
        if (head == nullptr) {
            head = newNode;
        } else {
            ListNode* cur = head;
            while (cur->next != nullptr) {
                cur = cur->next;
            }
            cur->next = newNode;
        }
    }

    // 删除指定值的节点
    void remove(int value) {
        ListNode* cur = head;
        ListNode* prev = nullptr;
        while (cur != nullptr) {
            if (cur->val == value) {
                if (prev == nullptr) {
                    head = cur->next;
                } else {
                    prev->next = cur->next;
                }
                delete cur;
                return;
            }
            prev = cur;
            cur = cur->next;
        }
    }

    // 遍历链表并打印节点的值
    void traverse() {
        ListNode* cur = head;
        while (cur != nullptr) {
            cout << cur->val << ' '; // 使用单引号
            cur = cur->next;
        }
        cout << endl;
    }

    // 查询链表中是否存在指定值的节点
    bool search(int value) {
        ListNode* cur = head;
        while (cur != nullptr) {
            if (cur->val == value) {
                return true;
            }
            cur = cur->next;
        }
        return false;
    }
};

链表操作

LinkedList 类中实现了以下几个方法：

• insert(int value)：在链表末尾插入一个节点。
• remove(int value)：删除链表中指定值的节点。
• traverse()：遍历链表并打印节点的值。
• search(int value)：查询链表中是否存在指定值的节点。

示例代码

下面是一个完整的示例代码，演示了链表的创建、插入节点、删除节点、遍历链表和查询节点的操作：

int main() {
    LinkedList myList;

    // 插入节点
    myList.insert(1);
    myList.insert(2);
    myList.insert(3);
    myList.insert(4);

    // 遍历链表
    cout << "链表："; // 使用双引号
    myList.traverse();

    // 删除节点
    myList.remove(2);

    // 遍历链表
    cout << "删除节点后的链表："; // 使用双引号
    myList.traverse();

    // 查询节点
    int value = 3;
    if (myList.search(value)) {
        cout << "链表中存在节点 " << value << endl;
    } else {
        cout << "链表中不存在节点 " << value << endl;
    }

    return 0;
}

总结

本文详细介绍了使用 C++ 实现整数链表的方法，包括链表节点类的定义、链表类的封装以及链表的基本操作，如插入节点、删除节点、遍历链表和查询节点。希望本文能够帮助你更好地理解链表这一重要的数据结构。