双向链表详解及C++实现_c++双向链表

一、引言

链表是一种常见的数据结构，它允许动态地分配内存空间，并通过指针（或引用）将数据元素连接在一起。双向链表作为链表的一种，除了拥有普通链表的特性外，每个节点还包含两个指针：一个指向前一个节点（prev），另一个指向后一个节点（next）。这种结构使得双向链表在插入、删除以及遍历等操作上都具有独特的优势。

二、双向链表的基本结构

双向链表的基本结构通常包括一个节点（Node）类和一个双向链表（DoublyLinkedList）类。节点类用于存储数据元素以及指向前后节点的指针，而双向链表类则用于管理这些节点，提供插入、删除、遍历等操作的方法。

1. 节点类（Node）

节点类通常包含两个指针（prev和next）和一个数据元素（data）。在C++中，节点类可以定义如下：

template <typename T>
class Node {
public:
    T data;
    Node* prev;
    Node* next;

    Node(T data) : data(data), prev(nullptr), next(nullptr) {}
};
1
2
3
4
5
6
7
8
9

这里使用了模板类（template class），使得节点类可以存储任意类型的数据。

2. 双向链表类（DoublyLinkedList）

双向链表类需要包含一些基本操作，如插入节点、删除节点、遍历链表等。以下是一个简单的双向链表类的实现：

template <typename T>
class DoublyLinkedList {
private:
    Node<T>* head;  // 指向头节点的指针
    Node<T>* tail;  // 指向尾节点的指针
    int size;       // 链表的大小

    // 辅助函数，用于在指定位置插入节点
    void insertAt(int position, T data) {
        // ... 实现细节将在后文给出 ...
    }

    // 辅助函数，用于删除指定位置的节点
    void deleteAt(int position) {
        // ... 实现细节将在后文给出 ...
    }

public:
    DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {}

    // 插入节点到链表末尾
    void append(T data) {
        insertAt(size, data);
    }

    // 插入节点到链表开头
    void prepend(T data) {
        insertAt(0, data);
    }

    // 删除指定位置的节点
    void removeAt(int position) {
        if (position < 0 || position >= size) {
            throw std::out_of_range("Invalid position");
        }
        deleteAt(position);
    }

    // 删除指定值的节点（如果存在多个，只删除第一个）
    void remove(T data) {
        Node<T>* current = head;
        while (current != nullptr) {
            if (current->data == data) {
                removeAt(currentIndex(current));
                return;
            }
            current = current->next;
        }
    }

    // 遍历链表并打印节点数据
    void printList() {
        Node<T>* current = head;
        while (current != nullptr) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }

    // 获取链表大小
    int getSize() const {
        return size;
    }

    // 检查链表是否为空
    bool isEmpty() const {
        return size == 0;
    }

    // ... 其他可能的方法，如查找、反转等 ...
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

三、双向链表的操作实现

接下来，我们将详细实现双向链表类中的一些关键操作。

1. 插入节点（insertAt）

在指定位置插入节点时，我们需要考虑几种情况：插入到链表开头、插入到链表末尾以及插入到链表中间。以下是insertAt方法的实现：

template <typename T>
void DoublyLinkedList<T>::insertAt(int position, T data) {
    if (position < 0 || position > size) {
        throw std::out_of_range("Invalid position");
    }

    Node<T>* newNode = new Node<T>(data);

    if (size == 0) {  // 链表为空，新节点既是头节点也是尾节点
        head = tail = newNode;
    } else if (position == 0) {  // 插入到链表开头
        newNode->next = head;
        head->prev = newNode;
        head = newNode;
    } else if (position == size) {  // 插入到链表末尾
        newNode->prev = tail;
        tail->next = newNode;
        tail = newNode;
    } else {  // 插入到链表中间
        Node<T>* current = head;
        for (int i = 0; i < position - 1; ++i) {
            current = current->next;
        }
        newNode->prev = current;
        newNode->next = current->next;
        current->next->prev = newNode;
        current->next = newNode;
    }
    ++size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

2. 删除节点（deleteAt）

删除指定位置的节点时，我们需要考虑删除头节点、删除尾节点以及删除中间节点的情况。以下是deleteAt方法的实现：

template <typename T>
void DoublyLinkedList<T>::deleteAt(int position) {
    if (position < 0 || position >= size) {
        throw std::out_of_range("Invalid position");
    }

    Node<T>* target = head;
    if (position == 0) {  // 删除头节点
        head = head->next;
        if (head != nullptr) {
            head->prev = nullptr;
        } else {
            tail = nullptr;  // 如果链表为空，则尾节点也为空
        }
    } else if (position == size - 1) {  // 删除尾节点
        target = tail;
        tail = tail->prev;
        if (tail != nullptr) {
            tail->next = nullptr;
        } else {
            head = nullptr;  // 如果链表为空，则头节点也为空
        }
    } else {  // 删除中间节点
        for (int i = 0; i < position; ++i) {
            target = target->next;
        }
        target->prev->next = target->next;
        target->next->prev = target->prev;
    }
    delete target;
    --size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

四、测试代码

下面是一个简单的测试程序，用于演示双向链表的用法：

#include <iostream>

int main() {
    DoublyLinkedList<int> list;
    list.append(1);
    list.append(2);
    list.prepend(0);
    list.insertAt(1, 100);
    list.printList();  // 输出: 0 100 1 2

    std::cout << "Size: " << list.getSize() << std::endl;  // 输出: 4
    std::cout << "Is empty? " << (list.isEmpty() ? "Yes" : "No") << std::endl;  // 输出: No

    list.removeAt(1);  // 删除索引为1的节点（值为100）
    list.printList();  // 输出: 0 1 2

    list.remove(1);  // 删除值为1的节点
    list.printList();  // 输出: 0 2

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

五、总结

本文详细介绍了双向链表的基本结构、操作实现以及C++代码示例。双向链表通过引入两个指针（prev和next）来实现对前后节点的访问，从而在插入、删除和遍历等操作上提供了更高的灵活性。在实际应用中，双向链表常用于需要频繁进行节点插入和删除的场景，如LRU（最近最少使用）缓存淘汰算法等。通过掌握双向链表的基本原理和实现方法，读者可以更好地理解和应用这种数据结构。