面试题：C++ 循环链表在多线程环境下的应用

设计思路

数据结构设计：
- 定义循环链表节点结构，包含数据成员和指向下一个节点的指针。
- 循环链表包含头指针（也可视为尾指针，因为是循环的）。
锁机制：
- 使用互斥锁（std::mutex）来保护对链表的操作。
- 在每个可能引发竞争条件的操作（插入、删除、遍历）前加锁，操作完成后解锁。
- 为避免死锁，采用固定的加锁顺序。例如，在涉及多个锁的操作中，总是先获取链表锁，再获取其他可能需要的锁（如果有）。

关键代码片段

#include <iostream>
#include <mutex>

// 定义链表节点
template <typename T>
struct ListNode {
    T data;
    ListNode* next;
    ListNode(const T& value) : data(value), next(nullptr) {}
};

// 定义循环链表
template <typename T>
class CircularList {
private:
    ListNode<T>* head;
    std::mutex listMutex;

public:
    CircularList() : head(nullptr) {}

    // 线程安全的插入操作
    void insert(const T& value) {
        std::lock_guard<std::mutex> guard(listMutex);
        ListNode<T>* newNode = new ListNode<T>(value);
        if (!head) {
            head = newNode;
            head->next = head;
        } else {
            ListNode<T>* current = head;
            while (current->next != head) {
                current = current->next;
            }
            current->next = newNode;
            newNode->next = head;
        }
    }

    // 线程安全的删除操作
    bool remove(const T& value) {
        std::lock_guard<std::mutex> guard(listMutex);
        if (!head) return false;
        ListNode<T>* current = head;
        ListNode<T>* prev = nullptr;
        do {
            if (current->data == value) {
                if (prev) {
                    prev->next = current->next;
                } else {
                    // 如果要删除的是头节点
                    if (current->next == head) {
                        delete current;
                        head = nullptr;
                    } else {
                        head = current->next;
                        ListNode<T>* last = head;
                        while (last->next != current) {
                            last = last->next;
                        }
                        last->next = head;
                    }
                }
                delete current;
                return true;
            }
            prev = current;
            current = current->next;
        } while (current != head);
        return false;
    }

    // 线程安全的遍历操作
    void traverse() {
        std::lock_guard<std::mutex> guard(listMutex);
        if (!head) return;
        ListNode<T>* current = head;
        do {
            std::cout << current->data << " ";
            current = current->next;
        } while (current != head);
        std::cout << std::endl;
    }

    ~CircularList() {
        std::lock_guard<std::mutex> guard(listMutex);
        if (head) {
            ListNode<T>* current = head;
            ListNode<T>* next;
            do {
                next = current->next;
                delete current;
                current = next;
            } while (current != head);
        }
    }
};

性能瓶颈及优化方向

性能瓶颈

锁粒度大：整个链表使用一个互斥锁，在高并发场景下，大量线程可能因等待锁而阻塞，导致并发性能下降。
遍历效率低：遍历链表时需要顺序访问每个节点，在链表较长时，遍历操作会成为性能瓶颈。

优化方向

减小锁粒度：
- 可以采用读写锁（std::shared_mutex），读操作可以并发执行，只有写操作（插入、删除）需要独占锁。
- 或者将链表划分为多个部分，每个部分使用独立的锁，这样不同部分的操作可以并发执行。
优化遍历：
- 可以在链表中维护额外的信息，如链表长度，以便在某些操作中减少不必要的遍历。
- 对于读操作频繁的场景，可以考虑使用无锁数据结构（如无锁链表）来提高并发性能。

星途面试题库

面试题：C++ 循环链表在多线程环境下的应用

知识考点

面试题答案

设计思路

关键代码片段

性能瓶颈及优化方向

性能瓶颈

优化方向