双向链表(Doubly Linked List)是一种数据结构,它由一系列节点组成,每个节点包含了当前元素的值以及指向前一个节点和后一个节点的指针。
在C++中实现双向链表,可以定义一个双向链表的节点类,该类包含当前节点的值以及指向前一个节点和后一个节点的指针。然后通过对节点的连接来构建链表。
下面是一个简单的示例代码:
#include <iostream>
using namespace std;
// 双向链表节点类
class ListNode {
public:
int val;
ListNode* prev;
ListNode* next;
ListNode(int value) {
val = value;
prev = nullptr;
next = nullptr;
}
};
// 双向链表类
class DoublyLinkedList {
public:
ListNode* head;
ListNode* tail;
DoublyLinkedList() {
head = nullptr;
tail = nullptr;
}
// 后插入操作
void insertAfter(int value, ListNode* prevNode) {
if (prevNode == nullptr) {
cout << "Previous node is null." << endl;
return;
}
ListNode* newNode = new ListNode(value);
newNode->prev = prevNode;
newNode->next = prevNode->next;
if (prevNode->next != nullptr) {
prevNode->next->prev = newNode;
}
prevNode->next = newNode;
if (tail == prevNode) {
tail = newNode;
}
}
// 打印链表元素
void printList() {
ListNode* currentNode = head;
while (currentNode != nullptr) {
cout << currentNode->val << " ";
currentNode = currentNode->next;
}
cout << endl;
}
};
int main() {
DoublyLinkedList dll;
// 创建节点
ListNode* node1 = new ListNode(1);
ListNode* node2 = new ListNode(2);
ListNode* node3 = new ListNode(3);
// 构建链表
dll.head = node1;
node1->next = node2;
node2->prev = node1;
node2->next = node3;
node3->prev = node2;
dll.tail = node3;
cout << "初始链表:" << endl;
dll.printList();
// 后插入节点
cout << "后插入节点后的链表:" << endl;
dll.insertAfter(4, node2);
dll.printList();
return 0;
}
在上述示例代码中,我们定义了一个ListNode
类表示双向链表的节点,包含了当前节点的值以及指向前一个节点和后一个节点的指针。然后定义了一个DoublyLinkedList
类表示双向链表,包含了链表的头节点和尾节点,并实现了后插入操作和打印链表元素的方法。
在insertAfter
函数中,我们首先判断前一个节点是否为空,如果为空则无法进行插入操作。然后创建新节点,并将新节点的指针连接到前一个节点和后一个节点。同时,我们需要更新前一个节点和后一个节点的指针,确保链表的连续性。如果插入节点是尾节点,则需要更新链表的尾节点。
最后,我们在main
函数中创建一个双向链表对象,并进行初始化和后插入节点的操作,最后打印链表的元素。
注意:上述代码仅为示例,实际应用中可能需要考虑内存管理和异常处理等其他方面的问题。
腾讯云相关产品和产品介绍链接:
领取专属 10元无门槛券
手把手带您无忧上云