C++怎么实现单链表

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

单链表的基本结构

单链表的基本结构包括两个部分：

1. 节点（Node）：每个节点包含两个部分，一个是存储数据的data，另一个是指向下一个节点的指针next。
2. 链表（LinkedList）：链表包含一个指向第一个节点的指针head，以及一些操作链表的方法。

定义节点结构

首先，我们需要定义一个节点结构体，用于存储数据和指向下一个节点的指针。

struct Node {
    int data;       // 存储数据
    Node* next;     // 指向下一个节点的指针

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

在这个结构体中，data用于存储节点的数据，next是指向下一个节点的指针。构造函数用于初始化节点的数据和指针。

定义链表类

接下来，我们定义一个链表类LinkedList，它包含一个指向链表头节点的指针head，以及一些操作链表的方法。

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

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

    // 析构函数
    ~LinkedList() {
        Node* current = head;
        Node* nextNode;
        while (current != nullptr) {
            nextNode = current->next;
            delete current;
            current = nextNode;
        }
    }

    // 在链表头部插入节点
    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 == nullptr) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
    }

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

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

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

        if (temp->next == nullptr) return;

        Node* nodeToDelete = temp->next;
        temp->next = temp->next->next;
        delete nodeToDelete;
    }

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

方法说明

1. 构造函数：初始化链表，将head指针设置为nullptr。
2. 析构函数：释放链表占用的内存，防止内存泄漏。
3. insertAtHead(int val)：在链表头部插入一个新节点。
4. insertAtTail(int val)：在链表尾部插入一个新节点。
5. deleteNode(int val)：删除链表中第一个值为val的节点。
6. printList()：打印链表中的所有节点。

使用链表

下面是一个简单的示例，展示如何使用LinkedList类。

int main() {
    LinkedList list;

    list.insertAtHead(3);
    list.insertAtHead(2);
    list.insertAtHead(1);
    list.insertAtTail(4);
    list.insertAtTail(5);

    std::cout << "链表内容: ";
    list.printList();

    list.deleteNode(3);
    std::cout << "删除节点3后的链表: ";
    list.printList();

    return 0;
}

输出结果

链表内容: 1 -> 2 -> 3 -> 4 -> 5 -> nullptr
删除节点3后的链表: 1 -> 2 -> 4 -> 5 -> nullptr

总结

本文介绍了如何使用C++实现一个简单的单链表。通过定义节点结构体和链表类，我们可以实现链表的插入、删除和打印等基本操作。单链表是一种基础的数据结构，理解其实现原理对于学习更复杂的数据结构和算法非常重要。