C++双向链表怎么实现

发布时间：2021-12-08 14:30:24 作者：iii
来源：亿速云阅读：138

# C++双向链表怎么实现

## 1. 双向链表概述

双向链表（Doubly Linked List）是链表的一种重要变体，与单向链表相比，每个节点不仅包含指向下一个节点的指针，还包含指向前一个节点的指针。这种结构使得双向链表在操作上更加灵活，能够高效地进行双向遍历。

### 1.1 基本特点

- **前驱和后继指针**：每个节点包含`prev`和`next`两个指针
- **双向遍历**：可以从头到尾或从尾到头遍历链表
- **内存开销**：比单向链表多一个指针的空间开销
- **操作复杂度**：某些操作（如删除指定节点）时间复杂度更低

### 1.2 与单向链表的对比

| 特性            | 单向链表       | 双向链表         |
|----------------|--------------|----------------|
| 指针数量        | 1个(next)     | 2个(prev, next) |
| 遍历方向        | 只能单向       | 可以双向         |
| 删除指定节点复杂度 | O(n)         | O(1)           |
| 内存占用        | 较少          | 较多            |

## 2. 节点结构设计

### 2.1 基础节点类

```cpp
template <typename T>
class Node {
public:
    T data;         // 数据域
    Node<T>* prev;  // 前驱指针
    Node<T>* next;  // 后继指针
    
    // 构造函数
    Node(const T& value) : data(value), prev(nullptr), next(nullptr) {}
};

2.2 带模板的节点实现

为了增强通用性，我们使用模板类：

template <typename T>
struct ListNode {
    T val;
    ListNode* prev;
    ListNode* next;
    
    // 默认构造函数
    ListNode() : val(T()), prev(nullptr), next(nullptr) {}
    
    // 带值构造函数
    ListNode(T x) : val(x), prev(nullptr), next(nullptr) {}
    
    // 完整构造函数
    ListNode(T x, ListNode* p, ListNode* n) : val(x), prev(p), next(n) {}
};

3. 双向链表类实现

3.1 类框架设计

template <typename T>
class DoublyLinkedList {
private:
    Node<T>* head;  // 头指针
    Node<T>* tail;  // 尾指针
    size_t size;    // 链表长度
    
public:
    // 构造函数和析构函数
    DoublyLinkedList();
    ~DoublyLinkedList();
    
    // 基本操作
    bool isEmpty() const;
    size_t getSize() const;
    
    // 插入操作
    void insertFront(const T& value);
    void insertBack(const T& value);
    void insertAt(const T& value, size_t position);
    
    // 删除操作
    void removeFront();
    void removeBack();
    void removeAt(size_t position);
    void removeValue(const T& value);
    
    // 查找操作
    bool contains(const T& value) const;
    T getFront() const;
    T getBack() const;
    T getAt(size_t position) const;
    
    // 遍历操作
    void displayForward() const;
    void displayBackward() const;
    
    // 清空链表
    void clear();
};

3.2 构造函数和析构函数实现

// 构造函数
template <typename T>
DoublyLinkedList<T>::DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {}

// 析构函数
template <typename T>
DoublyLinkedList<T>::~DoublyLinkedList() {
    clear();
}

4. 基本操作实现

4.1 插入操作

头部插入

template <typename T>
void DoublyLinkedList<T>::insertFront(const T& value) {
    Node<T>* newNode = new Node<T>(value);
    
    if (isEmpty()) {
        head = tail = newNode;
    } else {
        newNode->next = head;
        head->prev = newNode;
        head = newNode;
    }
    
    size++;
}

尾部插入

template <typename T>
void DoublyLinkedList<T>::insertBack(const T& value) {
    Node<T>* newNode = new Node<T>(value);
    
    if (isEmpty()) {
        head = tail = newNode;
    } else {
        tail->next = newNode;
        newNode->prev = tail;
        tail = newNode;
    }
    
    size++;
}

指定位置插入

template <typename T>
void DoublyLinkedList<T>::insertAt(const T& value, size_t position) {
    if (position > size) {
        throw std::out_of_range("Position out of range");
    }
    
    if (position == 0) {
        insertFront(value);
    } else if (position == size) {
        insertBack(value);
    } else {
        Node<T>* current = head;
        for (size_t i = 0; i < position - 1; ++i) {
            current = current->next;
        }
        
        Node<T>* newNode = new Node<T>(value);
        newNode->next = current->next;
        newNode->prev = current;
        current->next->prev = newNode;
        current->next = newNode;
        
        size++;
    }
}

4.2 删除操作

头部删除

template <typename T>
void DoublyLinkedList<T>::removeFront() {
    if (isEmpty()) {
        throw std::runtime_error("List is empty");
    }
    
    Node<T>* temp = head;
    if (head == tail) {  // 只有一个节点
        head = tail = nullptr;
    } else {
        head = head->next;
        head->prev = nullptr;
    }
    
    delete temp;
    size--;
}

尾部删除

template <typename T>
void DoublyLinkedList<T>::removeBack() {
    if (isEmpty()) {
        throw std::runtime_error("List is empty");
    }
    
    Node<T>* temp = tail;
    if (head == tail) {  // 只有一个节点
        head = tail = nullptr;
    } else {
        tail = tail->prev;
        tail->next = nullptr;
    }
    
    delete temp;
    size--;
}

指定位置删除

template <typename T>
void DoublyLinkedList<T>::removeAt(size_t position) {
    if (position >= size) {
        throw std::out_of_range("Position out of range");
    }
    
    if (position == 0) {
        removeFront();
    } else if (position == size - 1) {
        removeBack();
    } else {
        Node<T>* current = head;
        for (size_t i = 0; i < position; ++i) {
            current = current->next;
        }
        
        current->prev->next = current->next;
        current->next->prev = current->prev;
        delete current;
        size--;
    }
}

4.3 查找操作

template <typename T>
bool DoublyLinkedList<T>::contains(const T& value) const {
    Node<T>* current = head;
    while (current != nullptr) {
        if (current->data == value) {
            return true;
        }
        current = current->next;
    }
    return false;
}

template <typename T>
T DoublyLinkedList<T>::getAt(size_t position) const {
    if (position >= size) {
        throw std::out_of_range("Position out of range");
    }
    
    Node<T>* current = head;
    for (size_t i = 0; i < position; ++i) {
        current = current->next;
    }
    
    return current->data;
}

5. 高级功能实现

5.1 迭代器实现

template <typename T>
class DoublyLinkedListIterator {
private:
    Node<T>* current;
    
public:
    DoublyLinkedListIterator(Node<T>* node) : current(node) {}
    
    // 前置++
    DoublyLinkedListIterator& operator++() {
        current = current->next;
        return *this;
    }
    
    // 后置++
    DoublyLinkedListIterator operator++(int) {
        DoublyLinkedListIterator temp = *this;
        current = current->next;
        return temp;
    }
    
    // 前置--
    DoublyLinkedListIterator& operator--() {
        current = current->prev;
        return *this;
    }
    
    // 后置--
    DoublyLinkedListIterator operator--(int) {
        DoublyLinkedListIterator temp = *this;
        current = current->prev;
        return temp;
    }
    
    T& operator*() const {
        return current->data;
    }
    
    bool operator==(const DoublyLinkedListIterator& other) const {
        return current == other.current;
    }
    
    bool operator!=(const DoublyLinkedListIterator& other) const {
        return !(*this == other);
    }
};

5.2 反向迭代器

template <typename T>
class DoublyLinkedListReverseIterator {
private:
    Node<T>* current;
    
public:
    DoublyLinkedListReverseIterator(Node<T>* node) : current(node) {}
    
    // 前置++
    DoublyLinkedListReverseIterator& operator++() {
        current = current->prev;
        return *this;
    }
    
    // 其他操作与正向迭代器类似...
};

6. 应用实例

6.1 实现LRU缓存

template <typename K, typename V>
class LRUCache {
private:
    struct CacheNode {
        K key;
        V value;
        CacheNode* prev;
        CacheNode* next;
        CacheNode(K k, V v) : key(k), value(v), prev(nullptr), next(nullptr) {}
    };
    
    std::unordered_map<K, CacheNode*> cacheMap;
    CacheNode* head;
    CacheNode* tail;
    int capacity;
    
    void moveToHead(CacheNode* node) {
        if (node == head) return;
        
        // 从当前位置移除节点
        if (node->prev) node->prev->next = node->next;
        if (node->next) node->next->prev = node->prev;
        
        // 如果节点是尾节点，更新尾指针
        if (node == tail) tail = node->prev;
        
        // 将节点移动到头部
        node->next = head;
        node->prev = nullptr;
        if (head) head->prev = node;
        head = node;
        
        // 如果链表为空，更新尾指针
        if (!tail) tail = head;
    }
    
public:
    LRUCache(int cap) : capacity(cap), head(nullptr), tail(nullptr) {}
    
    V get(K key) {
        if (cacheMap.find(key) == cacheMap.end()) {
            return V(); // 返回默认值
        }
        
        CacheNode* node = cacheMap[key];
        moveToHead(node);
        return node->value;
    }
    
    void put(K key, V value) {
        if (cacheMap.find(key) != cacheMap.end()) {
            CacheNode* node = cacheMap[key];
            node->value = value;
            moveToHead(node);
            return;
        }
        
        // 创建新节点
        CacheNode* newNode = new CacheNode(key, value);
        cacheMap[key] = newNode;
        
        // 添加到头部
        if (!head) {
            head = tail = newNode;
        } else {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
        
        // 检查容量
        if (cacheMap.size() > capacity) {
            // 移除尾节点
            cacheMap.erase(tail->key);
            CacheNode* toDelete = tail;
            tail = tail->prev;
            if (tail) tail->next = nullptr;
            delete toDelete;
            
            if (!tail) head = nullptr;
        }
    }
};

7. 性能分析与优化

7.1 时间复杂度分析

操作	时间复杂度
头部插入/删除	O(1)
尾部插入/删除	O(1)
指定位置插入/删除	O(n)
查找	O(n)
随机访问	O(n)

7.2 内存优化技巧

内存池技术：预分配节点内存，减少new/delete开销
节点复用：实现节点缓存机制
紧凑存储：对小对象可以考虑将数据和指针打包

7.3 线程安全考虑

#include <mutex>

template <typename T>
class ThreadSafeDoublyLinkedList {
private:
    DoublyLinkedList<T> list;
    mutable std::mutex mtx;
    
public:
    void insertFront(const T& value) {
        std::lock_guard<std::mutex> lock(mtx);
        list.insertFront(value);
    }
    
    // 其他线程安全封装方法...
};

8. 常见问题与解决方案

8.1 边界条件处理

空链表操作：所有操作前检查链表是否为空
单节点链表：头尾指针需要特殊处理
越界访问：严格检查位置参数

8.2 内存泄漏预防

析构函数：确保释放所有节点内存
异常安全：使用RI技术管理资源
智能指针：考虑使用shared_ptr或unique_ptr

8.3 调试技巧

可视化打印：实现链表的图形化输出

完整性检查：

bool checkIntegrity() const {
   if (head == nullptr) return tail == nullptr;


   Node<T>* current = head;
   size_t count = 0;


   while (current != nullptr) {
       if (current->next != nullptr && current->next->prev != current) {
           return false;
       }
       count++;
       current = current->next;
   }


   return count == size;
}

9. 总结

本文详细介绍了C++中双向链表的实现方法，包括： - 基础节点结构设计 - 完整的双向链表类实现 - 各种插入、删除、查找操作 - 迭代器实现 - 实际应用案例(LRU缓存) - 性能优化和线程安全考虑

双向链表作为一种基础数据结构，在需要频繁双向遍历和中间插入删除的场景下表现出色。理解其实现原理对于掌握更复杂的数据结构(如哈希链表、跳表等)具有重要意义。

10. 扩展阅读

《数据结构与算法分析》- Mark Allen Weiss
《STL源码剖析》- 侯捷
开源项目：Boost.Intrusive库中的链表实现
Linux内核中的链表实现(list.h)

”`