C++数据结构之双向链表完整攻略
1. 什么是双向链表
双向链表是一种特殊的链表结构，每个节点拥有两个指针域，分别指向前继和后继节点。
双向链表不需要像单向链表那样从头到尾遍历整个链表，可以通过前后指针直接访问前后节点，提高了查找、删除、插入等操作的效率。
双向链表有一些常用的操作，如插入节点、删除节点、查找节点等。
2. 双向链表的实现
2.1 节点定义
template <typename T>
struct DListNode {
T data;
DListNode<T> *prev; // 指向前继节点指针
DListNode<T> *next; // 指向后继节点指针
};
2.2 双向链表类定义
template <typename T>
class DLinkedList {
public:
DLinkedList() : _head(nullptr), _tail(nullptr), _size(0) {}
~DLinkedList() {}
// 插入操作
void insertFront(T value); // 在头部插入节点
void insertBack(T value); // 在尾部插入节点
void insertAt(DListNode<T> *node, T value); // 在指定位置之后插入节点
// 删除操作
void deleteFront(); // 删除头部节点
void deleteBack(); // 删除尾部节点
void deleteAt(DListNode<T> *node); // 删除单个节点
// 查找操作
DListNode<T> *find(T value); // 根据值查找节点
DListNode<T> *findAt(int index); // 根据下标查找节点
// 判空操作
bool empty() { return _head == nullptr; }
// 返回链表长度
int size() { return _size; }
// 输出链表
void print();
private:
DListNode<T> *_head; // 头指针
DListNode<T> *_tail; // 尾指针
int _size; // 链表长度
};
2.3 插入节点操作
在头部插入节点，实现如下：
template <typename T>
void DLinkedList<T>::insertFront(T value) {
DListNode<T> *newNode = new DListNode<T>();
newNode->data = value;
if (empty()) {
_tail = newNode; // 如果链表为空，插入后的节点即为尾节点
} else {
_head->prev = newNode;
}
newNode->next = _head;
_head = newNode;
++_size;
}
在尾部插入节点，实现如下：
template <typename T>
void DLinkedList<T>::insertBack(T value) {
DListNode<T> *newNode = new DListNode<T>();
newNode->data = value;
if (empty()) {
_head = newNode; // 如果链表为空，插入后的节点即为头节点
} else {
_tail->next = newNode;
}
newNode->prev = _tail;
_tail = newNode;
++_size;
}
在指定位置插入节点，实现如下：
template <typename T>
void DLinkedList<T>::insertAt(DListNode<T> *node, T value) {
DListNode<T> *newNode = new DListNode<T>();
newNode->data = value;
newNode->prev = node;
newNode->next = node->next;
node->next = newNode;
if (node == _tail) {
_tail = newNode;
} else {
newNode->next->prev = newNode;
}
++_size;
}
2.4 删除节点操作
删除头部节点，实现如下：
template <typename T>
void DLinkedList<T>::deleteFront() {
if (empty()) {
return;
}
DListNode<T> *node = _head;
_head = node->next;
if (_head != nullptr) {
_head->prev = nullptr;
} else {
_tail = nullptr;
}
delete node;
--_size;
}
删除尾部节点，实现如下：
template <typename T>
void DLinkedList<T>::deleteBack() {
if (empty()) {
return;
}
DListNode<T> *node = _tail;
_tail = node->prev;
if (_tail != nullptr) {
_tail->next = nullptr;
} else {
_head = nullptr;
}
delete node;
--_size;
}
删除任意节点，实现如下：
template <typename T>
void DLinkedList<T>::deleteAt(DListNode<T> *node) {
if (node == nullptr) {
return;
}
if (node->prev == nullptr) {
deleteFront();
} else if (node->next == nullptr) {
deleteBack();
} else {
node->prev->next = node->next;
node->next->prev = node->prev;
delete node;
--_size;
}
}
2.5 查找节点操作
根据值查找节点，实现如下：
template <typename T>
DListNode<T> *DLinkedList<T>::find(T value) {
DListNode<T> *node = _head;
while (node != nullptr) {
if (node->data == value) {
return node;
}
node = node->next;
}
return nullptr;
}
根据下标查找节点，实现如下：
template <typename T>
DListNode<T> *DLinkedList<T>::findAt(int index) {
if (index >= size()) {
return nullptr;
}
DListNode<T> *node = _head;
int i = 0;
while (node != nullptr && i < index) {
node = node->next;
++i;
}
return node;
}
2.6 输出链表操作
template <typename T>
void DLinkedList<T>::print() {
DListNode<T> *node = _head;
while (node != nullptr) {
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
3. 示例说明
3.1 实现双向链表并遍历
int main() {
DLinkedList<int> list;
// 在头尾插入节点
list.insertFront(1);
list.insertBack(2);
// 在头部插入节点，使链表变为 3 1 2
DListNode<int> *node = list.find(1);
list.insertAt(node, 3);
// 删除尾部节点，使链表变为 3 1
list.deleteBack();
// 遍历输出链表
list.print();
return 0;
}
输出结果：
3 1
3.2 按下标查找节点并删除
int main() {
DLinkedList<int> list;
// 在头尾插入节点
list.insertFront(1);
list.insertBack(2);
// 在头部插入节点，使链表变为 3 1 2
DListNode<int> *node = list.find(1);
list.insertAt(node, 3);
// 删除下标为 1 的节点，即 1，使链表变为 3 2
node = list.findAt(1);
list.deleteAt(node);
// 遍历输出链表
list.print();
return 0;
}
输出结果：
3 2
本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：C++数据结构之双向链表 - Python技术站
微信扫一扫 
支付宝扫一扫 