C++手撕单链表及逆序打印

在学习数据结构的过程中，链表是一个非常重要的基础数据结构。今天，我们将通过C++手动实现一个单链表，并添加一个逆序打印的功能，帮助大家更好地理解链表的实现和操作。

一、链表简介

链表是一种线性数据结构，其中每个元素（称为节点）包含数据部分和指向下一个节点的指针。与数组不同，链表的内存空间是动态分配的，因此可以灵活地插入和删除节点，而不需要移动其他元素。

单链表是最简单的链表形式，每个节点只有一个指向下一个节点的指针。

二、单链表的实现

1. 定义链表节点

我们首先定义链表节点的结构。每个节点包含一个整数值和一个指向下一个节点的指针。

#include <iostream>
using namespace std;// 定义链表节点结构
struct ListNode {int val;          // 节点存储的数据ListNode* next;   // 指向下一个节点的指针// 构造函数ListNode(int x) : val(x), next(nullptr) {}
};

2. 定义链表类

接下来，我们定义一个链表类，包含链表的基本操作，如插入、删除和遍历。

class LinkedList {
private:ListNode* head; // 链表的头指针public:// 构造函数LinkedList() : head(nullptr) {}// 析构函数，释放链表内存~LinkedList() {ListNode* current = head;while (current != nullptr) {ListNode* temp = current;current = current->next;delete temp;}}// 插入节点到链表头部void insertAtHead(int value) {ListNode* newNode = new ListNode(value);newNode->next = head;head = newNode;}// 插入节点到链表尾部void insertAtTail(int value) {ListNode* newNode = new ListNode(value);if (head == nullptr) {head = newNode;return;}ListNode* current = head;while (current->next != nullptr) {current = current->next;}current->next = newNode;}// 删除节点void deleteNode(int value) {if (head == nullptr) return; // 链表为空if (head->val == value) {ListNode* temp = head;head = head->next;delete temp;return;}ListNode* current = head;while (current->next != nullptr && current->next->val != value) {current = current->next;}if (current->next != nullptr) {ListNode* temp = current->next;current->next = current->next->next;delete temp;}}// 打印链表void printList() {ListNode* current = head;while (current != nullptr) {cout << current->val << " -> ";current = current->next;}cout << "nullptr" << endl;}// 逆序打印链表void reversePrint(ListNode* node) {if (node == nullptr) return;reversePrint(node->next);cout << node->val << " ";}// 调用逆序打印void reversePrint() {reversePrint(head);cout << endl;}
};

3. 测试链表

我们编写一个简单的测试程序来验证链表的功能，包括插入、删除、正序打印和逆序打印。

int main() {LinkedList list;// 插入节点list.insertAtHead(3);list.insertAtHead(2);list.insertAtHead(1);list.insertAtTail(4);list.insertAtTail(5);// 打印链表cout << "链表内容: ";list.printList();// 逆序打印链表cout << "逆序打印链表: ";list.reversePrint();// 删除节点list.deleteNode(3);cout << "删除节点 3 后的链表: ";list.printList();// 删除头节点list.deleteNode(1);cout << "删除头节点后的链表: ";list.printList();return 0;
}

4. 输出示例

运行上述代码后，输出如下：

链表内容: 1 -> 2 -> 3 -> 4 -> 5 -> nullptr
逆序打印链表: 5 4 3 2 1
删除节点 3 后的链表: 1 -> 2 -> 4 -> 5 -> nullptr
删除头节点后的链表: 2 -> 4 -> 5 -> nullptr

三、逆序打印的实现

逆序打印链表的关键在于递归。我们定义了一个递归函数 reversePrint，它先递归到链表的尾部，然后在回溯过程中打印每个节点的值。这种方法利用了递归的调用栈，自然地实现了逆序打印。

逆序打印函数

void reversePrint(ListNode* node) {if (node == nullptr) return;reversePrint(node->next);cout << node->val << " ";
}

调用逆序打印

void reversePrint() {reversePrint(head);cout << endl;
}

四、总结

通过手动实现单链表，我们不仅加深了对链表数据结构的理解，还学会了如何操作链表节点，包括插入、删除和遍历。此外，逆序打印功能的实现进一步展示了递归在链表操作中的强大作用。