链表与邻接表

1. 链表

链表是一种线性数据结构，由一系列节点（Node）组成，每个节点包含两部分：

1. 数据域 - 存储实际数据

2. 指针域 - 存储下一个节点的地址（或前一个节点的地址）

与数组不同，链表中的元素在内存中不是连续存储的，而是通过指针链接在一起。

这样说可能还是很不直观。来看下面的说明：

像这样的结构就是链表。链表有什么用呢？举个很常见的例子，就是管理浏览器历史记录和文件系统：

单向链表

单向链表就是链表最简单的形式，

C++实现一个单向链表：

#include <iostream>

// 链表节点类
class Node {
public:
    int data;
    Node* next;
    
    Node(int val) : data(val), next(nullptr) {}
};

// 单向链表类
class LinkedList {
private:
    Node* head;
    
public:
    // 构造函数
    LinkedList() : head(nullptr) {}
    
    // 在链表尾部添加节点
    void append(int val) {
        Node* newNode = new Node(val);
        
        if (head == nullptr) {
            head = newNode;
            return;
        }
        
        Node* current = head;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newNode;
    }
    
    // 在链表头部添加节点
    void prepend(int val) {
        Node* newNode = new Node(val);
        newNode->next = head;
        head = newNode;
    }
    
    // 删除第一个匹配的节点
    bool remove(int val) {
        if (head == nullptr) return false;
        
        // 如果要删除的是头节点
        if (head->data == val) {
            Node* temp = head;
            head = head->next;
            delete temp;
            return true;
        }
        
        // 查找要删除的节点
        Node* current = head;
        while (current->next != nullptr && current->next->data != val) {
            current = current->next;
        }
        
        if (current->next == nullptr) return false;
        
        Node* temp = current->next;
        current->next = current->next->next;
        delete temp;
        return true;
    }
    
    // 查找节点
    bool contains(int val) {
        Node* current = head;
        while (current != nullptr) {
            if (current->data == val) return true;
            current = current->next;
        }
        return false;
    }
    
    // 打印链表
    void print() {
        Node* current = head;
        while (current != nullptr) {
            std::cout << current->data << " -> ";
            current = current->next;
        }
        std::cout << "nullptr" << std::endl;
    }
    
    // 获取链表长度
    int size() {
        int count = 0;
        Node* current = head;
        while (current != nullptr) {
            count++;
            current = current->next;
        }
        return count;
    }
    
    // 析构函数：释放所有节点
    ~LinkedList() {
        Node* current = head;
        while (current != nullptr) {
            Node* next = current->next;
            delete current;
            current = next;
        }
    }
    
    // 禁止拷贝构造和赋值（简化实现）
    LinkedList(const LinkedList&) = delete;
    LinkedList& operator=(const LinkedList&) = delete;
};

// 测试示例
int main() {
    LinkedList list;
    
    // 添加元素
    list.append(1);
    list.append(2);
    list.append(3);
    list.prepend(0);
    
    std::cout << "初始链表: ";
    list.print();  // 0 -> 1 -> 2 -> 3 -> nullptr
    
    std::cout << "链表长度: " << list.size() << std::endl;  // 4
    
    // 查找元素
    std::cout << "是否包含2: " << (list.contains(2) ? "是" : "否") << std::endl;  // 是
    std::cout << "是否包含5: " << (list.contains(5) ? "是" : "否") << std::endl;  // 否
    
    // 删除元素
    list.remove(2);
    std::cout << "删除2后: ";
    list.print();  // 0 -> 1 -> 3 -> nullptr
    
    list.remove(0);
    std::cout << "删除0后: ";
    list.print();  // 1 -> 3 -> nullptr
    
    // 删除不存在的元素
    if (!list.remove(5)) {
        std::cout << "删除5失败，元素不存在" << std::endl;
    }
    
    return 0;
}

双向链表

双向链表是在单向链表的基础上，在指针域中增加一个前驱指针，指向前一个节点。我们用左右来指代前后。

这样双向链表的可操作性得到了提升，它可以反向遍历。同时删除操作也比单向链表要简单，不需要遍历到前驱节点才删除。尾部操作也是直接指定删除就好，不需要遍历到最后一个节点。

当然，双向链表占更大的内存（因为多了一个需要存储的指针），插入的时候需要照顾前后两个节点，所以相比之下需要操作两个指针。同样需要衡量性能来使用。

#include <iostream>
struct Node{
    int data;
    Node* prev;
    Node* next;
    Node(int val):data(val),prev(nullptr),next(nullptr){}
}

class DoublyLinkedList{
    private:
    Node* head;
    Node* tail;
    public:
    DoublyLinkedList():head(nullptr),tail(nullptr),size(0){}
    // 尾部添加一个节点
    void append(int val){
        Node* newNode = new Node(val);
        if(head==nullptr&&tail==nullptr){
            head = newNode;// 空链表中实现第一个节点
        }
        else{
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
        size++;
    }
    void prepend(int val){
        Node* newNode = new Node(val);
        if(head==nullptr&& tail==nullptr){
            head = newNode;
        }
        else{
            head->prev = newNode;
            newNode->next = head;
            head = newNode;
        }
        size++;
    }
    // 删除头部节点
    void removeHeadNode(void){
        if(head==nullptr)return;
        Node* tempNode = head;// 不存放原来head的地址会导致内存泄漏
        if(head==tail){
            // 处理只有一个节点的情况
            head = nullptr;
            tail = nullptr;
        }else{
            head = head->next;
            head->prev = nullptr;
        }
        delete tempNode;
        size--;
    }
    void removeTailNode(void){
        if(head==nullptr)return;
        Node* tempNode = tail;
        if(head==tail){
            head = nullptr;
            tail = nullptr;
        }
        else{
            tail = tail->prev;
            tail->next = nullptr;
        }
        delete tempNode;
        size--;
    }
    bool findNode(int val){
        Node* current = head;
        while(current!=nullptr){
            if(current->data==val){
                return true;
            }
            current = current->next;
        }
        return false;
    }
        // 获取链表长度
    int getSize() {
        return size;
    }
    
    // 判断是否为空
    bool isEmpty() {
        return size == 0;
    }
    
    // 清空链表
    void clear() {
        while (head != nullptr) {
            removeHead();
        }
    }
    
    // 正向打印链表
    void printForward() {
        Node* current = head;
        cout << "正向: ";
        while (current != nullptr) {
            cout << current->data;
            if (current->next != nullptr) {
                cout << " ↔ ";
            }
            current = current->next;
        }
        cout << endl;
    }
    
    // 反向打印链表
    void printBackward() {
        Node* current = tail;
        cout << "反向: ";
        while (current != nullptr) {
            cout << current->data;
            if (current->prev != nullptr) {
                cout << " ↔ ";
            }
            current = current->prev;
        }
        cout << endl;
    }

}
// 测试代码
int main() {
    DoublyLinkedList list;
    
    cout << "=== 测试尾部添加 ===" << endl;
    list.append(10);
    list.append(20);
    list.append(30);
    list.printForward();  // 输出: 10 ↔ 20 ↔ 30
    
    cout << "\n=== 测试头部添加 ===" << endl;
    list.prepend(5);
    list.prepend(1);
    list.printForward();  // 输出: 1 ↔ 5 ↔ 10 ↔ 20 ↔ 30
    list.printBackward(); // 输出: 30 ↔ 20 ↔ 10 ↔ 5 ↔ 1
    
    cout << "\n=== 测试删除操作 ===" << endl;
    list.removeHead();
    cout << "删除头部后: ";
    list.printForward();  // 输出: 5 ↔ 10 ↔ 20 ↔ 30
    
    list.removeTail();
    cout << "删除尾部后: ";
    list.printForward();  // 输出: 5 ↔ 10 ↔ 20
    
    cout << "\n=== 测试查找功能 ===" << endl;
    cout << "是否包含10: " << (list.contains(10) ? "是" : "否") << endl;
    cout << "是否包含99: " << (list.contains(99) ? "是" : "否") << endl;
    
    cout << "\n=== 测试链表大小 ===" << endl;
    cout << "链表长度: " << list.getSize() << endl;  // 输出: 3
    
    cout << "\n=== 测试清空链表 ===" << endl;
    list.clear();
    cout << "链表是否为空: " << (list.isEmpty() ? "是" : "否") << endl;
    
    return 0;
}

循环链表

单向循环链表

单向循环链表的尾部节点指向头节点或者第一个节点，成一个环。

这种链表的好处是可以从任意节点开始遍历整个链表，无需特殊处理尾节点，且能实现内存连续访问，适合实现轮询调度和环形缓冲区。

单向循环链表的实现：

#include <iostream>
using namespace std;

class CircularLinkedList {
private:
    CircularNode* tail;  // 通常维护尾指针，因为tail->next就是头节点
    
public:
    // 构造函数
    CircularLinkedList() : tail(nullptr) {}
    
    // 析构函数
    ~CircularLinkedList() {
        if (tail == nullptr) return;
        
        // 需要特殊处理循环链表的销毁
        CircularNode* head = tail->next;
        CircularNode* current = head;
        CircularNode* nextNode;
        
        do {
            nextNode = current->next;
            delete current;
            current = nextNode;
        } while (current != head);  // 回到头节点时停止
        
        tail = nullptr;
    }
    
    // 1. 在尾部插入节点
    void append(int val) {
        CircularNode* newNode = new CircularNode(val);
        
        if (tail == nullptr) {  // 空链表
            tail = newNode;
            tail->next = tail;  // 指向自己，形成循环
        } else {
            newNode->next = tail->next;  // 新节点的next指向头节点
            tail->next = newNode;        // 原尾节点的next指向新节点
            tail = newNode;              // 更新尾节点为新节点
        }
    }
    
    // 2. 在头部插入节点
    void prepend(int val) {
        CircularNode* newNode = new CircularNode(val);
        
        if (tail == nullptr) {  // 空链表
            tail = newNode;
            tail->next = tail;
        } else {
            newNode->next = tail->next;  // 新节点的next指向原头节点
            tail->next = newNode;        // 尾节点的next指向新节点（新节点成为头节点）
            // tail不需要更新，因为插入在头部
        }
    }
    
    // 3. 删除头节点
    void removeHead() {
        if (tail == nullptr) return;  // 空链表
        
        if (tail->next == tail) {     // 只有一个节点
            delete tail;
            tail = nullptr;
        } else {
            CircularNode* head = tail->next;      // 当前头节点
            tail->next = head->next;              // 尾节点指向新的头节点
            delete head;
        }
    }
    
    // 4. 删除尾节点（需要遍历找到前一个节点）
    void removeTail() {
        if (tail == nullptr) return;  // 空链表
        
        if (tail->next == tail) {     // 只有一个节点
            delete tail;
            tail = nullptr;
        } else {
            // 需要找到尾节点的前一个节点
            CircularNode* current = tail->next;  // 从头节点开始
            while (current->next != tail) {
                current = current->next;
            }
            
            // current现在是尾节点的前一个节点
            current->next = tail->next;  // 前一个节点指向头节点
            delete tail;
            tail = current;              // 更新尾节点
        }
    }
    
    // 5. 查找节点是否存在
    bool contains(int val) {
        if (tail == nullptr) return false;
        
        CircularNode* current = tail->next;  // 从头节点开始
        do {
            if (current->data == val) {
                return true;
            }
            current = current->next;
        } while (current != tail->next);  // 回到头节点时停止
        
        return false;
    }
    
    // 6. 获取链表长度
    int getSize() {
        if (tail == nullptr) return 0;
        
        int count = 0;
        CircularNode* current = tail->next;  // 从头节点开始
        
        do {
            count++;
            current = current->next;
        } while (current != tail->next);  // 回到头节点时停止
        
        return count;
    }
    
    // 7. 判断链表是否为空
    bool isEmpty() {
        return tail == nullptr;
    }
    
    // 8. 清空链表
    void clear() {
        if (tail == nullptr) return;
        
        CircularNode* head = tail->next;
        CircularNode* current = head;
        CircularNode* nextNode;
        
        do {
            nextNode = current->next;
            delete current;
            current = nextNode;
        } while (current != head);
        
        tail = nullptr;
    }
    
    // 9. 正向打印链表
    void print() {
        if (tail == nullptr) {
            cout << "链表为空" << endl;
            return;
        }
        
        CircularNode* current = tail->next;  // 从头节点开始
        cout << "循环链表: ";
        
        do {
            cout << current->data;
            if (current->next != tail->next) {  // 不是最后一个节点
                cout << " → ";
            }
            current = current->next;
        } while (current != tail->next);  // 回到头节点时停止
        
        cout << " ↺" << endl;  // 循环符号
    }
    
    // 10. 约瑟夫环问题（经典应用）
    void josephusProblem(int m) {
        if (tail == nullptr) return;
        
        CircularNode* current = tail->next;  // 从头节点开始
        CircularNode* prev = tail;           // 前一个节点
        
        cout << "约瑟夫环删除顺序: ";
        
        while (current->next != current) {  // 直到只剩一个节点
            // 找到第m个节点
            for (int i = 1; i < m; i++) {
                prev = current;
                current = current->next;
            }
            
            // 删除当前节点
            cout << current->data << " ";
            prev->next = current->next;
            
            if (current == tail) {
                tail = prev;  // 如果删除的是尾节点，更新尾指针
            }
            
            delete current;
            current = prev->next;  // 从下一个节点继续
        }
        
        // 输出最后一个幸存者
        cout << "\n幸存者: " << current->data << endl;
        tail = current;
    }
};

// 测试代码
int main() {
    CircularLinkedList list;
    
    cout << "=== 创建单向循环链表 ===" << endl;
    list.append(1);
    list.append(2);
    list.append(3);
    list.append(4);
    list.append(5);
    list.print();
    cout << "链表长度: " << list.getSize() << endl;
    
    cout << "\n=== 在头部插入节点 ===" << endl;
    list.prepend(0);
    list.print();
    
    cout << "\n=== 查找元素 ===" << endl;
    cout << "是否包含3: " << (list.contains(3) ? "是" : "否") << endl;
    cout << "是否包含10: " << (list.contains(10) ? "是" : "否") << endl;
    
    cout << "\n=== 删除操作 ===" << endl;
    list.removeHead();
    cout << "删除头部后: ";
    list.print();
    
    list.removeTail();
    cout << "删除尾部后: ";
    list.print();
    
    cout << "\n=== 约瑟夫环问题演示 ===" << endl;
    // 创建新的循环链表来演示约瑟夫环
    CircularLinkedList josephusList;
    for (int i = 1; i <= 7; i++) {
        josephusList.append(i);
    }
    cout << "初始环: ";
    josephusList.print();
    josephusList.josephusProblem(3);
    cout << "最终链表: ";
    josephusList.print();
    
    return 0;
}

由于成环结构，析构的时候需要特别处理。

算法题中，检测链表是否有环和找到环的入口节点这两类问题是单向循环链表比较擅长对付的。

双向循环链表

双向循环链表即每个节点都有前驱和后驱节点的环结构，它是一个完整的双向环。

双向循环链表的实现：

class DoublyCircularLinkedList {
private:
    DCNode* head;    // 头指针（也可以只维护头指针）
    int size;        // 链表长度
    
public:
    // 构造函数
    DoublyCircularLinkedList() : head(nullptr), size(0) {}
    
    // 析构函数
    ~DoublyCircularLinkedList() {
        clear();
    }
    
    // 1. 获取头节点
    DCNode* getHead() {
        return head;
    }
    
    // 2. 获取尾节点
    DCNode* getTail() {
        if (head == nullptr) return nullptr;
        return head->prev;  // 头节点的prev就是尾节点
    }
    
    // 3. 在尾部插入节点
    void append(int val) {
        DCNode* newNode = new DCNode(val);
        
        if (head == nullptr) {  // 空链表
            head = newNode;
            head->next = head;
            head->prev = head;
        } else {
            DCNode* tail = head->prev;  // 获取当前尾节点
            
            // 设置新节点的指针
            newNode->next = head;
            newNode->prev = tail;
            
            // 更新头尾节点的指针
            tail->next = newNode;
            head->prev = newNode;
        }
        size++;
    }
    
    // 4. 在头部插入节点
    void prepend(int val) {
        DCNode* newNode = new DCNode(val);
        
        if (head == nullptr) {  // 空链表
            head = newNode;
            head->next = head;
            head->prev = head;
        } else {
            DCNode* tail = head->prev;  // 获取当前尾节点
            
            // 设置新节点的指针
            newNode->next = head;
            newNode->prev = tail;
            
            // 更新头尾节点的指针
            tail->next = newNode;
            head->prev = newNode;
            
            // 更新头指针
            head = newNode;
        }
        size++;
    }
    
    // 5. 在指定位置插入节点
    bool insertAt(int index, int val) {
        if (index < 0 || index > size) {
            return false;  // 位置无效
        }
        
        if (index == 0) {
            prepend(val);
            return true;
        }
        
        if (index == size) {
            append(val);
            return true;
        }
        
        // 找到插入位置的前一个节点
        DCNode* current = head;
        for (int i = 0; i < index - 1; i++) {
            current = current->next;
        }
        
        // 创建新节点
        DCNode* newNode = new DCNode(val);
        
        // 设置新节点的指针
        newNode->prev = current;
        newNode->next = current->next;
        
        // 更新相邻节点的指针
        current->next->prev = newNode;
        current->next = newNode;
        
        size++;
        return true;
    }
    
    // 6. 删除头节点
    bool removeHead() {
        if (head == nullptr) return false;  // 空链表
        
        if (size == 1) {  // 只有一个节点
            delete head;
            head = nullptr;
        } else {
            DCNode* oldHead = head;
            DCNode* tail = head->prev;
            
            // 更新头指针
            head = head->next;
            
            // 更新指针连接
            tail->next = head;
            head->prev = tail;
            
            // 删除原头节点
            delete oldHead;
        }
        
        size--;
        return true;
    }
    
    // 7. 删除尾节点
    bool removeTail() {
        if (head == nullptr) return false;  // 空链表
        
        if (size == 1) {  // 只有一个节点
            delete head;
            head = nullptr;
        } else {
            DCNode* tail = head->prev;
            DCNode* newTail = tail->prev;
            
            // 更新指针连接
            newTail->next = head;
            head->prev = newTail;
            
            // 删除原尾节点
            delete tail;
        }
        
        size--;
        return true;
    }
    
    // 8. 删除指定位置的节点
    bool removeAt(int index) {
        if (index < 0 || index >= size) {
            return false;  // 位置无效
        }
        
        if (index == 0) {
            return removeHead();
        }
        
        if (index == size - 1) {
            return removeTail();
        }
        
        // 找到要删除的节点
        DCNode* current = head;
        for (int i = 0; i < index; i++) {
            current = current->next;
        }
        
        // 更新相邻节点的指针
        current->prev->next = current->next;
        current->next->prev = current->prev;
        
        // 删除节点
        delete current;
        size--;
        
        return true;
    }
    
    // 9. 删除指定值的节点（第一个匹配的）
    bool removeValue(int val) {
        if (head == nullptr) return false;
        
        DCNode* current = head;
        for (int i = 0; i < size; i++) {
            if (current->data == val) {
                // 根据位置调用相应的删除函数
                if (i == 0) {
                    return removeHead();
                } else if (i == size - 1) {
                    return removeTail();
                } else {
                    current->prev->next = current->next;
                    current->next->prev = current->prev;
                    delete current;
                    size--;
                    return true;
                }
            }
            current = current->next;
        }
        
        return false;  // 未找到
    }
    
    // 10. 查找节点
    DCNode* find(int val) {
        if (head == nullptr) return nullptr;
        
        DCNode* current = head;
        for (int i = 0; i < size; i++) {
            if (current->data == val) {
                return current;
            }
            current = current->next;
        }
        
        return nullptr;  // 未找到
    }
    
    // 11. 判断是否包含某值
    bool contains(int val) {
        return find(val) != nullptr;
    }
    
    // 12. 获取链表长度
    int getSize() {
        return size;
    }
    
    // 13. 判断链表是否为空
    bool isEmpty() {
        return size == 0;
    }
    
    // 14. 清空链表
    void clear() {
        if (head == nullptr) return;
        
        DCNode* current = head;
        DCNode* nextNode;
        
        for (int i = 0; i < size; i++) {
            nextNode = current->next;
            delete current;
            current = nextNode;
        }
        
        head = nullptr;
        size = 0;
    }
    
    // 15. 正向打印链表
    void printForward() {
        if (head == nullptr) {
            cout << "链表为空" << endl;
            return;
        }
        
        DCNode* current = head;
        cout << "正向循环: ";
        
        for (int i = 0; i < size; i++) {
            cout << current->data;
            if (i < size - 1) {
                cout << " ⇄ ";
            }
            current = current->next;
        }
        cout << " → 回到头节点" << endl;
    }
    
    // 16. 反向打印链表
    void printBackward() {
        if (head == nullptr) {
            cout << "链表为空" << endl;
            return;
        }
        
        DCNode* current = head->prev;  // 从尾节点开始
        cout << "反向循环: ";
        
        for (int i = 0; i < size; i++) {
            cout << current->data;
            if (i < size - 1) {
                cout << " ⇄ ";
            }
            current = current->prev;
        }
        cout << " → 回到尾节点" << endl;
    }
    
    // 17. 约瑟夫环问题（双向循环链表版本）
    void josephusProblem(int m) {
        if (head == nullptr || size == 0) return;
        
        DCNode* current = head;
        DCNode* prev = nullptr;
        
        cout << "约瑟夫环删除顺序: ";
        
        while (size > 1) {
            // 找到第m个节点
            for (int i = 1; i < m; i++) {
                current = current->next;
            }
            
            // 输出并删除当前节点
            cout << current->data << " ";
            
            // 保存前一个节点
            prev = current->prev;
            
            // 删除当前节点
            if (current == head) {
                removeHead();
                current = head;
            } else if (current == head->prev) {
                removeTail();
                current = head;
            } else {
                current->prev->next = current->next;
                current->next->prev = current->prev;
                DCNode* toDelete = current;
                current = current->next;
                delete toDelete;
                size--;
            }
        }
        
        cout << "\n幸存者: " << head->data << endl;
    }
    
    // 18. 旋转链表（向右移动k个位置）
    void rotateRight(int k) {
        if (head == nullptr || size == 0 || k % size == 0) return;
        
        k = k % size;  // 处理k大于size的情况
        
        // 找到新的头节点位置
        DCNode* newHead = head;
        for (int i = 0; i < k; i++) {
            newHead = newHead->next;
        }
        
        head = newHead;
    }
    
    // 19. 反转链表
    void reverse() {
        if (head == nullptr || size <= 1) return;
        
        DCNode* current = head;
        DCNode* temp = nullptr;
        
        // 遍历所有节点，交换每个节点的prev和next指针
        do {
            // 交换当前节点的prev和next指针
            temp = current->prev;
            current->prev = current->next;
            current->next = temp;
            
            // 移动到下一个节点（原prev）
            current = current->prev;
        } while (current != head);
        
        // 更新头指针指向原尾节点（现在是新头节点）
        head = head->next;
    }
};

// 测试代码
int main() {
    DoublyCircularLinkedList list;
    
    cout << "=== 创建双向循环链表 ===" << endl;
    list.append(1);
    list.append(2);
    list.append(3);
    list.append(4);
    list.append(5);
    list.printForward();
    list.printBackward();
    cout << "链表长度: " << list.getSize() << endl;
    
    cout << "\n=== 在头部插入节点 ===" << endl;
    list.prepend(0);
    list.printForward();
    
    cout << "\n=== 在指定位置插入节点 ===" << endl;
    list.insertAt(3, 99);
    list.printForward();
    
    cout << "\n=== 查找元素 ===" << endl;
    cout << "是否包含3: " << (list.contains(3) ? "是" : "否") << endl;
    cout << "是否包含10: " << (list.contains(10) ? "是" : "否") << endl;
    
    cout << "\n=== 删除操作 ===" << endl;
    list.removeHead();
    cout << "删除头部后: ";
    list.printForward();
    
    list.removeTail();
    cout << "删除尾部后: ";
    list.printForward();
    
    list.removeAt(2);
    cout << "删除位置2后: ";
    list.printForward();
    
    list.removeValue(99);
    cout << "删除值99后: ";
    list.printForward();
    
    cout << "\n=== 约瑟夫环问题演示 ===" << endl;
    DoublyCircularLinkedList josephusList;
    for (int i = 1; i <= 7; i++) {
        josephusList.append(i);
    }
    cout << "初始环: ";
    josephusList.printForward();
    josephusList.josephusProblem(3);
    cout << "最终链表: ";
    josephusList.printForward();
    
    cout << "\n=== 链表旋转演示 ===" << endl;
    DoublyCircularLinkedList rotateList;
    for (int i = 1; i <= 5; i++) {
        rotateList.append(i);
    }
    cout << "旋转前: ";
    rotateList.printForward();
    rotateList.rotateRight(2);
    cout << "向右旋转2位后: ";
    rotateList.printForward();
    
    cout << "\n=== 链表反转演示 ===" << endl;
    DoublyCircularLinkedList reverseList;
    for (int i = 1; i <= 5; i++) {
        reverseList.append(i);
    }
    cout << "反转前: ";
    reverseList.printForward();
    reverseList.reverse();
    cout << "反转后: ";
    reverseList.printForward();
    
    return 0;
}

静态链表

这个相当于不使用指针域（即不使用动态内存分配）的用数组模拟的链表，使用游标表示下一个节点的索引。

#include <iostream>
#include <iomanip>
using namespace std;

const int MAX_SIZE = 10;  // 为了演示，设置较小的容量

class StaticLinkedList {
private:
    struct StaticNode {
        int data;
        int next;
        
        StaticNode() : data(0), next(-1) {}
        StaticNode(int d, int n) : data(d), next(n) {}
    };
    
    StaticNode nodes[MAX_SIZE];  // 节点数组
    int head;                    // 主链表头节点下标
    int freeListHead;            // 空闲链表头节点下标
    int size;                    // 主链表节点数
    
public:
    // 构造函数
    StaticLinkedList() : head(-1), freeListHead(0), size(0) {
        // 初始化空闲链表：将所有节点连接成空闲链表
        for (int i = 0; i < MAX_SIZE - 1; i++) {
            nodes[i].next = i + 1;
        }
        nodes[MAX_SIZE - 1].next = -1;  // 最后一个节点的next为-1
    }
    
    // 从空闲链表分配一个节点
    int allocateNode() {
        if (freeListHead == -1) {
            cout << "错误：内存不足！" << endl;
            return -1;
        }
        
        int allocated = freeListHead;          // 分配空闲链表的第一个节点
        freeListHead = nodes[freeListHead].next; // 更新空闲链表头
        nodes[allocated].next = -1;            // 新节点的next初始化为-1
        return allocated;
    }
    
    // 释放节点到空闲链表
    void freeNode(int index) {
        if (index < 0 || index >= MAX_SIZE) {
            cout << "错误：无效的节点索引！" << endl;
            return;
        }
        
        // 将节点插入空闲链表头部
        nodes[index].next = freeListHead;
        freeListHead = index;
        nodes[index].data = 0;  // 可选：清空数据
    }
    
    // 在尾部添加节点
    void append(int data) {
        int newNodeIndex = allocateNode();
        if (newNodeIndex == -1) return;
        
        nodes[newNodeIndex].data = data;
        
        if (head == -1) {  // 空链表
            head = newNodeIndex;
        } else {
            // 找到最后一个节点
            int current = head;
            while (nodes[current].next != -1) {
                current = nodes[current].next;
            }
            nodes[current].next = newNodeIndex;
        }
        size++;
    }
    
    // 在头部添加节点
    void prepend(int data) {
        int newNodeIndex = allocateNode();
        if (newNodeIndex == -1) return;
        
        nodes[newNodeIndex].data = data;
        nodes[newNodeIndex].next = head;
        head = newNodeIndex;
        size++;
    }
    
    // 在指定位置插入节点
    bool insert(int pos, int data) {
        if (pos < 0 || pos > size) {
            cout << "错误：插入位置无效！" << endl;
            return false;
        }
        
        if (pos == 0) {
            prepend(data);
            return true;
        }
        
        int newNodeIndex = allocateNode();
        if (newNodeIndex == -1) return false;
        
        nodes[newNodeIndex].data = data;
        
        // 找到插入位置的前一个节点
        int current = head;
        for (int i = 0; i < pos - 1; i++) {
            current = nodes[current].next;
        }
        
        // 插入新节点
        nodes[newNodeIndex].next = nodes[current].next;
        nodes[current].next = newNodeIndex;
        size++;
        
        return true;
    }
    
    // 删除指定位置的节点
    bool remove(int pos) {
        if (pos < 0 || pos >= size) {
            cout << "错误：删除位置无效！" << endl;
            return false;
        }
        
        int nodeToDelete;
        
        if (pos == 0) {  // 删除头节点
            nodeToDelete = head;
            head = nodes[head].next;
        } else {
            // 找到要删除节点的前一个节点
            int current = head;
            for (int i = 0; i < pos - 1; i++) {
                current = nodes[current].next;
            }
            
            nodeToDelete = nodes[current].next;
            nodes[current].next = nodes[nodeToDelete].next;
        }
        
        freeNode(nodeToDelete);
        size--;
        return true;
    }
    
    // 删除指定值的节点（第一个匹配的）
    bool removeByValue(int data) {
        if (head == -1) return false;
        
        // 如果删除头节点
        if (nodes[head].data == data) {
            int temp = head;
            head = nodes[head].next;
            freeNode(temp);
            size--;
            return true;
        }
        
        // 查找要删除节点的前一个节点
        int current = head;
        while (nodes[current].next != -1) {
            if (nodes[nodes[current].next].data == data) {
                int nodeToDelete = nodes[current].next;
                nodes[current].next = nodes[nodeToDelete].next;
                freeNode(nodeToDelete);
                size--;
                return true;
            }
            current = nodes[current].next;
        }
        
        return false;
    }
    
    // 查找节点
    int find(int data) {
        int current = head;
        int pos = 0;
        
        while (current != -1) {
            if (nodes[current].data == data) {
                return pos;
            }
            current = nodes[current].next;
            pos++;
        }
        
        return -1;  // 未找到
    }
    
    // 遍历链表
    void traverse() {
        if (head == -1) {
            cout << "链表为空" << endl;
            return;
        }
        
        cout << "链表内容：";
        int current = head;
        while (current != -1) {
            cout << nodes[current].data;
            if (nodes[current].next != -1) {
                cout << " -> ";
            }
            current = nodes[current].next;
        }
        cout << endl;
    }
    
    // 获取链表长度
    int getSize() {
        return size;
    }
    
    // 判断链表是否为空
    bool isEmpty() {
        return size == 0;
    }
    
    // 清空链表
    void clear() {
        // 将所有主链表节点释放到空闲链表
        int current = head;
        while (current != -1) {
            int nextNode = nodes[current].next;
            freeNode(current);
            current = nextNode;
        }
        head = -1;
        size = 0;
    }
    
    // 获取指定位置的元素
    int get(int pos) {
        if (pos < 0 || pos >= size) {
            throw out_of_range("位置越界");
        }
        
        int current = head;
        for (int i = 0; i < pos; i++) {
            current = nodes[current].next;
        }
        
        return nodes[current].data;
    }
};

// 测试代码
int main() {
    StaticLinkedList list;
    
    cout << "=== 初始化静态链表 ===" << endl;
    list.printStatus();
    
    cout << "\n=== 测试添加操作 ===" << endl;
    list.append(10);
    list.append(20);
    list.append(30);
    list.traverse();
    list.printStatus();
    
    cout << "\n=== 测试头部插入 ===" << endl;
    list.prepend(5);
    list.traverse();
    
    cout << "\n=== 测试指定位置插入 ===" << endl;
    list.insert(2, 15);
    list.traverse();
    
    cout << "\n=== 测试删除操作 ===" << endl;
    list.remove(2);
    cout << "删除位置2后：";
    list.traverse();
    
    list.removeByValue(20);
    cout << "删除值20后：";
    list.traverse();
    
    cout << "\n=== 测试查找操作 ===" << endl;
    int pos = list.find(30);
    if (pos != -1) {
        cout << "找到元素30，位置：" << pos << endl;
    } else {
        cout << "未找到元素30" << endl;
    }
    
    cout << "\n=== 测试获取操作 ===" << endl;
    try {
        cout << "位置1的元素：" << list.get(1) << endl;
    } catch (const exception& e) {
        cout << "错误：" << e.what() << endl;
    }
    
    cout << "\n=== 测试清空操作 ===" << endl;
    list.clear();
    list.traverse();
    list.printStatus();
    
    return 0;
}

跳跃链表（跳表）

跳表是一种概率性的数据结构，通过“空间换时间”的方法加速搜索。时间复杂度为$O(log n)$。在普通有序链表的基础上，增加多级索引，索引层级是随机生成的，类似"抛硬币"。

异或链表（XOR表）

自组织链表

多级链表

十字链表

块状链表