面试题：C++ 指针在动态内存管理与数据结构中的应用

Question

在实现一个简单的链表数据结构时，指针起到了哪些关键作用？请详细阐述，并给出相应的 C++ 代码示例，包括链表节点的定义、链表的插入和删除操作。

Answer 1

指针在链表数据结构中的关键作用

1. 连接节点：指针用于在链表中建立节点之间的逻辑关系。每个节点包含一个指向下一个节点的指针，从而形成链式结构。
2. 动态内存管理：通过指针，可以在需要时动态分配和释放节点的内存。这使得链表能够灵活地根据数据的插入和删除进行内存的动态调整。
3. 遍历链表：借助指针，可以方便地从链表的头节点开始，逐个访问每个节点，从而实现对链表中数据的遍历操作。

C++ 代码示例

#include <iostream>

// 链表节点定义
struct ListNode {
    int data;
    ListNode* next;
    ListNode(int val) : data(val), next(nullptr) {}
};

// 链表类定义
class LinkedList {
private:
    ListNode* head;
public:
    LinkedList() : head(nullptr) {}

    // 插入操作
    void insert(int val) {
        ListNode* newNode = new ListNode(val);
        if (!head) {
            head = newNode;
        } else {
            ListNode* current = head;
            while (current->next) {
                current = current->next;
            }
            current->next = newNode;
        }
    }

    // 删除操作
    void remove(int val) {
        if (!head) return;
        if (head->data == val) {
            ListNode* temp = head;
            head = head->next;
            delete temp;
            return;
        }
        ListNode* current = head;
        while (current->next && current->next->data != val) {
            current = current->next;
        }
        if (current->next) {
            ListNode* temp = current->next;
            current->next = current->next->next;
            delete temp;
        }
    }

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

可以通过以下方式测试代码：

int main() {
    LinkedList list;
    list.insert(1);
    list.insert(2);
    list.insert(3);
    list.printList();

    list.remove(2);
    list.printList();

    return 0;
}