C++深入分析讲解链表

链表概述

链表是数据结构中最基本和重要的一种，它的实现可以分为链表的节点和链表的指针。每个节点都记录着链表中的一个元素，并带有一个指向下一个节点的指针，这样就可以通过遍历指针，达到遍历链表的目的。

链表数据结构

在C++中，链表可以通过结构体或者类来实现，比如以下这个结构体实现的单向链表：

struct Node {
    int data;
    Node* next;
};

这个结构体中包含了一个整型数据和一个指向下一个节点的指针。

链表的操作

链表的基本操作包括：

• 插入节点
• 删除节点
• 查找节点

插入节点

链表中新节点的插入可以分为四种情况：

• 在链表开头插入新节点
• 在链表中间插入新节点
• 在链表末尾插入新节点
• 创建新链表

以下代码给出了一个链表中在开头插入新节点的示例：

void insertAtBeginning(Node*& head, int newData) {
    Node* newNode = new Node{ newData, head };
    head = newNode;
}

删除节点

链表中删除节点的操作可以分为两种情况：

• 删除指定节点
• 删除整个链表

以下代码实现了链表中删除第一个节点的操作：

void deleteAtBeginning(Node*& head) {
    if (head == nullptr) {
        return;
    }
    Node* temp = head;
    head = head->next;
    delete temp;
}

查找节点

链表中查找节点的操作通常通过遍历链表来实现，以下代码给出了一个查找节点的示例：

Node* findNode(Node* head, int data) {
    while (head != nullptr) {
        if (head->data == data) {
            return head;
        }
        head = head->next;
    }
    return nullptr;
}

示例

以下是一个完整的链表代码示例：

#include <iostream>

struct Node {
    int data;
    Node* next;
};

void insertAtBeginning(Node*& head, int newData) {
    Node* newNode = new Node{ newData, head };
    head = newNode;
}

void deleteAtBeginning(Node*& head) {
    if (head == nullptr) {
        return;
    }
    Node* temp = head;
    head = head->next;
    delete temp;
}

Node* findNode(Node* head, int data) {
    while (head != nullptr) {
        if (head->data == data) {
            return head;
        }
        head = head->next;
    }
    return nullptr;
}

int main() {
    Node* head = nullptr;

    // 插入节点
    insertAtBeginning(head, 1);
    insertAtBeginning(head, 2);
    insertAtBeginning(head, 3);

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

    // 查找节点
    Node* found = findNode(head, 2);
    if (found != nullptr) {
        std::cout << "Found node: " << found->data << std::endl;
    } else {
        std::cout << "Node not found" << std::endl;
    }

    // 删除节点
    deleteAtBeginning(head);

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

    return 0;
}

运行代码结果为：

3 2 1
Found node: 2
2 1

以上示例包含了链表的插入、删除和查找操作。在实际应用中，链表还可以实现很多其他功能，比如反转链表、排序链表等等。