C++如何实现单链表

单链表（Singly Linked List）是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。单链表的优点是插入和删除操作的时间复杂度为O(1)，但访问元素的时间复杂度为O(n)。本文将介绍如何使用C++实现一个简单的单链表。

1. 单链表的基本结构

首先，我们需要定义一个节点结构体，它包含两个成员：数据域和指针域。数据域用于存储节点的数据，指针域用于指向下一个节点。

struct Node {
    int data;       // 数据域
    Node* next;     // 指针域，指向下一个节点

    // 构造函数
    Node(int val) : data(val), next(nullptr) {}
};

2. 单链表的类定义

接下来，我们定义一个单链表类，它包含一个指向链表头节点的指针，并提供一些基本的操作，如插入、删除、查找等。

class SinglyLinkedList {
private:
    Node* head;  // 指向链表头节点的指针

public:
    // 构造函数
    SinglyLinkedList() : head(nullptr) {}

    // 析构函数
    ~SinglyLinkedList() {
        while (head) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }

    // 在链表头部插入节点
    void insertAtHead(int val) {
        Node* newNode = new Node(val);
        newNode->next = head;
        head = newNode;
    }

    // 在链表尾部插入节点
    void insertAtTail(int val) {
        Node* newNode = new Node(val);
        if (!head) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next) {
            temp = temp->next;
        }
        temp->next = newNode;
    }

    // 删除链表中的某个节点
    void deleteNode(int val) {
        if (!head) return;

        // 如果要删除的是头节点
        if (head->data == val) {
            Node* temp = head;
            head = head->next;
            delete temp;
            return;
        }

        Node* temp = head;
        while (temp->next && temp->next->data != val) {
            temp = temp->next;
        }

        if (temp->next) {
            Node* nodeToDelete = temp->next;
            temp->next = temp->next->next;
            delete nodeToDelete;
        }
    }

    // 查找链表中是否包含某个值
    bool search(int val) {
        Node* temp = head;
        while (temp) {
            if (temp->data == val) {
                return true;
            }
            temp = temp->next;
        }
        return false;
    }

    // 打印链表中的所有元素
    void printList() {
        Node* temp = head;
        while (temp) {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        }
        std::cout << "nullptr" << std::endl;
    }
};

3. 单链表的操作示例

现在，我们可以使用上面定义的SinglyLinkedList类来创建一个单链表，并进行一些基本操作。

int main() {
    SinglyLinkedList list;

    // 在链表头部插入节点
    list.insertAtHead(3);
    list.insertAtHead(2);
    list.insertAtHead(1);

    // 在链表尾部插入节点
    list.insertAtTail(4);
    list.insertAtTail(5);

    // 打印链表
    list.printList();  // 输出: 1 -> 2 -> 3 -> 4 -> 5 -> nullptr

    // 删除节点
    list.deleteNode(3);
    list.printList();  // 输出: 1 -> 2 -> 4 -> 5 -> nullptr

    // 查找节点
    if (list.search(4)) {
        std::cout << "4 is found in the list." << std::endl;
    } else {
        std::cout << "4 is not found in the list." << std::endl;
    }

    return 0;
}

4. 总结

本文介绍了如何使用C++实现一个简单的单链表。我们首先定义了节点结构体，然后实现了单链表类，并提供了插入、删除、查找和打印等基本操作。通过这些操作，我们可以轻松地管理链表中的数据。

单链表虽然简单，但在实际应用中非常有用，特别是在需要频繁插入和删除操作的场景中。希望本文能帮助你理解单链表的基本概念和实现方法。