C++单链表教程

单链表是一种常见的数据结构，由多个节点组成，每个节点包含数据和指向下一个节点的指针。链表的优点是插入和删除操作效率高，但随机访问效率低。

下面是一个完整的单链表实现示例：

#include <iostream>

// 定义单链表节点结构体
struct Node {
    int data;         // 节点存储的数据
    Node* next;       // 指向下一个节点的指针
    
    // 构造函数，方便节点初始化
    Node(int value) : data(value), next(nullptr) {}
};

// 单链表类，封装链表操作
class LinkedList {
private:
    Node* head;       // 头指针，指向链表的第一个节点
    Node* tail;       // 尾指针，指向链表的最后一个节点
    int size;         // 链表的大小
    
public:
    // 构造函数，初始化空链表
    LinkedList() : head(nullptr), tail(nullptr), size(0) {}
    
    // 析构函数，释放链表占用的内存
    ~LinkedList() {
        clear();
    }
    
    // 判断链表是否为空
    bool isEmpty() const {
        return size == 0;
    }
    
    // 获取链表的大小
    int getSize() const {
        return size;
    }
    
    // 在链表尾部添加元素
    void append(int value) {
        Node* newNode = new Node(value);
        
        if (isEmpty()) {
            // 如果链表为空，新节点既是头节点也是尾节点
            head = tail = newNode;
        } else {
            // 否则将新节点连接到尾部，并更新尾指针
            tail->next = newNode;
            tail = newNode;
        }
        
        size++;
    }
    
    // 在链表头部添加元素
    void prepend(int value) {
        Node* newNode = new Node(value);
        
        if (isEmpty()) {
            // 如果链表为空，新节点既是头节点也是尾节点
            head = tail = newNode;
        } else {
            // 否则将新节点插入到头部，并更新头指针
            newNode->next = head;
            head = newNode;
        }
        
        size++;
    }
    
    // 在指定位置插入元素
    bool insert(int index, int value) {
        if (index < 0 || index > size) {
            std::cout << "插入位置无效" << std::endl;
            return false;
        }
        
        if (index == 0) {
            prepend(value);
            return true;
        }
        
        if (index == size) {
            append(value);
            return true;
        }
        
        // 找到插入位置的前一个节点
        Node* prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev->next;
        }
        
        // 创建新节点并插入到链表中
        Node* newNode = new Node(value);
        newNode->next = prev->next;
        prev->next = newNode;
        
        size++;
        return true;
    }
    
    // 删除指定位置的元素
    bool remove(int index) {
        if (index < 0 || index >= size) {
            std::cout << "删除位置无效" << std::endl;
            return false;
        }
        
        Node* toDelete;
        
        if (index == 0) {
            // 删除头节点
            toDelete = head;
            head = head->next;
            
            if (head == nullptr) {
                // 如果链表只有一个节点，删除后尾指针也要置空
                tail = nullptr;
            }
        } else {
            // 找到删除位置的前一个节点
            Node* prev = head;
            for (int i = 0; i < index - 1; i++) {
                prev = prev->next;
            }
            
            toDelete = prev->next;
            prev->next = toDelete->next;
            
            if (toDelete == tail) {
                // 如果删除的是尾节点，更新尾指针
                tail = prev;
            }
        }
        
        // 释放删除节点的内存
        delete toDelete;
        size--;
        return true;
    }
    
    // 查找元素在链表中的位置
    int find(int value) const {
        Node* current = head;
        int index = 0;
        
        while (current != nullptr) {
            if (current->data == value) {
                return index;
            }
            current = current->next;
            index++;
        }
        
        return -1;  // 未找到元素
    }
    
    // 打印链表中的所有元素
    void print() const {
        Node* current = head;
        
        while (current != nullptr) {
            std::cout << current->data << " ";
            current = current->next;
        }
        
        std::cout << std::endl;
    }
    
    // 清空链表
    void clear() {
        Node* current = head;
        
        while (current != nullptr) {
            Node* nextNode = current->next;
            delete current;
            current = nextNode;
        }
        
        head = tail = nullptr;
        size = 0;
    }
};

// 使用示例
int main() {
    LinkedList list;
    
    // 在尾部添加元素
    list.append(10);
    list.append(20);
    list.append(30);
    
    std::cout << "链表内容: ";
    list.print();  // 输出: 10 20 30
    
    // 在头部添加元素
    list.prepend(5);
    
    std::cout << "在头部添加5后: ";
    list.print();  // 输出: 5 10 20 30
    
    // 在指定位置插入元素
    list.insert(2, 15);
    
    std::cout << "在位置2插入15后: ";
    list.print();  // 输出: 5 10 15 20 30
    
    // 删除指定位置的元素
    list.remove(3);
    
    std::cout << "删除位置3的元素后: ";
    list.print();  // 输出: 5 10 15 30
    
    // 查找元素
    int pos = list.find(15);
    std::cout << "元素15的位置是: " << pos << std::endl;  // 输出: 2
    
    // 清空链表
    list.clear();
    std::cout << "清空链表后，链表大小: " << list.getSize() << std::endl;  // 输出: 0
    
    return 0;
}

代码解释

1. Node结构体：

   • 包含一个整数data存储节点数据
   • 包含一个指向下一个节点的指针next
   • 构造函数用于初始化节点数据

2. LinkedList类：

   • head和tail指针分别指向链表的头部和尾部
   • size记录链表的大小
   • 提供了链表的基本操作方法，如添加、删除、查找等

3. 主要方法说明：

   • append(): 在链表尾部添加元素
   • prepend(): 在链表头部添加元素
   • insert(): 在指定位置插入元素
   • remove(): 删除指定位置的元素
   • find(): 查找元素位置
   • print(): 打印链表内容
   • clear(): 清空链表

单链表的核心在于节点之间通过指针连接，插入和删除操作只需要修改指针指向，无需移动大量数据，因此效率较高。但访问元素需要从头节点开始遍历，时间复杂度为O(n)。