一、教学目标：

1、 理解链表 “离散存储、通过指针连接” 的核心特性，区分链表与数组的存储差异；掌握单链表的基本概念（节点、头指针、尾指针）及核心操作（增、删、查、改）的定义。

2、 能基于 C++ 结构体 / 类实现单链表的节点定义，完成单链表的初始化、头插 / 尾插法添加节点、按值 / 按索引查找节点、删除指定节点等基础操作的代码编写；能手动模拟单链表操作的指针指向变化，处理空链表、删除头 / 尾节点等边界场景。

3、 能识别链表的基础适用场景（如频繁增删、数据量不固定），使用自定义单链表解决简单问题（如逆序输出链表元素、统计链表长度）。

二、 核心知识点

1. 链表基本概念

链表定义与特点

• 定义：由一系列节点组成的数据结构，每个节点包含数据和指向下一个节点的指针
• 特点：
  • 动态大小，无需预先分配空间
  • 内存不连续，通过指针链接
  • 插入删除高效（O(1)），随机访问低效（O(n)）

链表分类

1. 单向链表（Singly Linked List）
2. 双向链表（Doubly Linked List）
3. 循环链表（Circular Linked List）
4. 双向循环链表（Doubly Circular Linked List）

2. 节点结构定义

单向链表节点

struct ListNode {
    int val;          // 数据域
    ListNode* next;   // 指针域，指向下一个节点
    
    // 构造函数
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* nxt) : val(x), next(nxt) {}
};

双向链表节点

struct DoublyListNode {
    int val;
    DoublyListNode* prev;  // 指向前一个节点
    DoublyListNode* next;  // 指向下一个节点
    
    // 构造函数
    DoublyListNode(int x) : val(x), prev(nullptr), next(nullptr) {}
};

3. 基本操作实现

单向链表完整实现

class SinglyLinkedList {
private:
    ListNode* head;
    int size;
    
public:
    // 构造函数
    SinglyLinkedList() : head(nullptr), size(0) {}
    
    // 析构函数（重要！释放内存）
    ~SinglyLinkedList() {
        while (head) {
            ListNode* temp = head;
            head = head->next;
            delete temp;
        }
    }
    
    // 1. 获取链表大小
    int getSize() const {
        return size;
    }
    
    // 2. 判断是否为空
    bool isEmpty() const {
        return head == nullptr;
    }
    
    // 3. 头部插入
    void insertAtHead(int val) {
        ListNode* newNode = new ListNode(val);
        newNode->next = head;
        head = newNode;
        size++;
    }
    
    // 4. 尾部插入
    void insertAtTail(int val) {
        ListNode* newNode = new ListNode(val);
        
        if (!head) {
            head = newNode;
        } else {
            ListNode* current = head;
            while (current->next) {
                current = current->next;
            }
            current->next = newNode;
        }
        size++;
    }
    
    // 5. 指定位置插入
    void insertAtIndex(int index, int val) {
        if (index < 0 || index > size) {
            throw out_of_range("Index out of range");
        }
        
        if (index == 0) {
            insertAtHead(val);
            return;
        }
        
        ListNode* newNode = new ListNode(val);
        ListNode* current = head;
        
        // 移动到插入位置的前一个节点
        for (int i = 0; i < index - 1; i++) {
            current = current->next;
        }
        
        newNode->next = current->next;
        current->next = newNode;
        size++;
    }
    
    // 6. 删除头部
    void deleteAtHead() {
        if (!head) return;
        
        ListNode* temp = head;
        head = head->next;
        delete temp;
        size--;
    }
    
    // 7. 删除尾部
    void deleteAtTail() {
        if (!head) return;
        
        if (!head->next) {
            delete head;
            head = nullptr;
            size--;
            return;
        }
        
        ListNode* current = head;
        while (current->next && current->next->next) {
            current = current->next;
        }
        
        delete current->next;
        current->next = nullptr;
        size--;
    }
    
    // 8. 删除指定值
    void deleteByValue(int val) {
        if (!head) return;
        
        // 处理头节点就是要删除的情况
        while (head && head->val == val) {
            ListNode* temp = head;
            head = head->next;
            delete temp;
            size--;
        }
        
        if (!head) return;
        
        ListNode* current = head;
        while (current->next) {
            if (current->next->val == val) {
                ListNode* temp = current->next;
                current->next = current->next->next;
                delete temp;
                size--;
            } else {
                current = current->next;
            }
        }
    }
    
    // 9. 查找元素
    bool contains(int val) const {
        ListNode* current = head;
        while (current) {
            if (current->val == val) {
                return true;
            }
            current = current->next;
        }
        return false;
    }
    
    // 10. 获取指定位置的元素
    int get(int index) const {
        if (index < 0 || index >= size) {
            throw out_of_range("Index out of range");
        }
        
        ListNode* current = head;
        for (int i = 0; i < index; i++) {
            current = current->next;
        }
        return current->val;
    }
    
    // 11. 修改指定位置的元素
    void set(int index, int val) {
        if (index < 0 || index >= size) {
            throw out_of_range("Index out of range");
        }
        
        ListNode* current = head;
        for (int i = 0; i < index; i++) {
            current = current->next;
        }
        current->val = val;
    }
    
    // 12. 打印链表
    void print() const {
        ListNode* current = head;
        cout << "List: ";
        while (current) {
            cout << current->val;
            if (current->next) {
                cout << " -> ";
            }
            current = current->next;
        }
        cout << " -> NULL" << endl;
        cout << "Size: " << size << endl;
    }
    
    // 13. 反转链表
    void reverse() {
        ListNode* prev = nullptr;
        ListNode* current = head;
        ListNode* next = nullptr;
        
        while (current) {
            next = current->next;  // 保存下一个节点
            current->next = prev;  // 反转指针
            prev = current;        // 移动prev
            current = next;        // 移动current
        }
        
        head = prev;
    }
};

双向链表实现（关键部分）

class DoublyLinkedList {
private:
    DoublyListNode* head;
    DoublyListNode* tail;
    int size;
    
public:
    DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {}
    
    ~DoublyLinkedList() {
        while (head) {
            DoublyListNode* temp = head;
            head = head->next;
            delete temp;
        }
    }
    
    // 尾部插入（双向链表的优势）
    void insertAtTail(int val) {
        DoublyListNode* newNode = new DoublyListNode(val);
        
        if (!tail) {
            // 链表为空
            head = tail = newNode;
        } else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
        size++;
    }
    
    // 头部插入
    void insertAtHead(int val) {
        DoublyListNode* newNode = new DoublyListNode(val);
        
        if (!head) {
            head = tail = newNode;
        } else {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
        size++;
    }
    
    // 删除尾部（O(1)复杂度）
    void deleteAtTail() {
        if (!tail) return;
        
        if (head == tail) {
            delete head;
            head = tail = nullptr;
        } else {
            DoublyListNode* temp = tail;
            tail = tail->prev;
            tail->next = nullptr;
            delete temp;
        }
        size--;
    }
};

4. C++ STL 链表使用

std::list（双向链表）

#include <iostream>
#include <list>
#include <algorithm>

using namespace std;

void demonstrateList() {
    // 1. 创建和初始化
    list<int> myList = {1, 2, 3, 4, 5};
    list<int> emptyList;
    list<int> sizedList(10);        // 10个0
    list<int> filledList(5, 42);    // 5个42
    
    // 2. 插入元素
    myList.push_front(0);           // 头部插入
    myList.push_back(6);            // 尾部插入
    
    auto it = myList.begin();
    advance(it, 3);                 // 移动迭代器
    myList.insert(it, 99);          // 指定位置插入
    
    // 3. 删除元素
    myList.pop_front();             // 删除头部
    myList.pop_back();              // 删除尾部
    myList.remove(3);               // 删除所有值为3的元素
    
    // 4. 遍历
    cout << "Forward: ";
    for (int val : myList) {
        cout << val << " ";
    }
    cout << endl;
    
    cout << "Backward: ";
    for (auto rit = myList.rbegin(); rit != myList.rend(); ++rit) {
        cout << *rit << " ";
    }
    cout << endl;
    
    // 5. 其他操作
    myList.sort();                  // 排序
    myList.reverse();               // 反转
    myList.unique();                // 删除连续重复元素
    myList.resize(10);              // 调整大小
}

std::forward_list（单向链表）

#include <forward_list>

void demonstrateForwardList() {
    // forward_list 只支持前向遍历
    forward_list<int> flist = {1, 2, 3, 4, 5};
    
    // 插入（使用 insert_after）
    auto it = flist.begin();
    flist.insert_after(it, 99);     // 在第一个元素后插入
    
    // 删除（使用 erase_after）
    it = flist.begin();
    flist.erase_after(it);          // 删除第二个元素
    
    // 遍历（只有前向迭代器）
    for (int val : flist) {
        cout << val << " ";
    }
}