C++实现数据结构——链表
·
线性表的链式存储方式为链表（Linked List）
链表中的每个元素结点都需要保存以下两部分信息。
- 存储数据信息的部分，称为数据域。
- 存储前驱（prior)或后继(next)结点的逻辑关系，称为指针域(也称链域 )。
根据元素结点中指针域存储的指针个数和类型的不同，链表还可细分为单向链表、双向链表、单向环形链表（单向循环链表）、双向环形链表（双向循环链表）以及静态链表。
单向链表
如果元素结点只包含一个指针域，则称该链表为单向链表(Singly Linked List)。单向链表的结点结构如图所示。
data为数据域，用来存储数据元素自身的信息;
next为指针域，用来存放结点的后继结点的地址。
单链表正是通过每个结点的链域next将线性表的n个结点按其逻辑次序链接在一起的。显然，单链表中每个结点的存储地址是存放在其前驱结点的next域中的，而表中的第一个结点a1无前驱，故应设置一个头指针(Head Pointer)head指向a1。此外，由于最后一个结点an无后继，故an的指针域为空，即 NULL(在图示中常用符号^表示 )。单链表的结构如图所示。
在C++中，通常采用结构体类型定义链表的结点。
template <class T>
//单向链表的结点结构
struct Node{
T data;
Node* next;
Node(const T& value, Node* n = nullptr) {
data = value;
next = n;
}
};
SinglyLinkedList.h实现单向链表
//
// 单向链表
//
#ifndef DS_SINGLYLINKEDLIST_H
#define DS_SINGLYLINKEDLIST_H
#include <iostream>
using namespace std;
template <class T>
//单向链表的结点结构
struct Node{
T data;//数据
Node* next;//指针，指向下一个结点的地址
Node(const T& value, Node* n = nullptr) {
data = value;
next = n;
}
};
template <class T>
class SinglyLinkedList {
private:
Node<T>* head;//始终指向链表头部的指针
public:
SinglyLinkedList():head(nullptr){}
~SinglyLinkedList() {
auto* current = head;
while (current != nullptr) {//通过head指针遍历链表并删除每个结点，直到链表为空
auto next = current->next;
delete current;//释放当前结点内存
current = next;
}
head = nullptr;
}
//在链表头部添加一个元素
void prepend(const T& data) {
Node<T>* newNode = new Node(data);
newNode->next = head;//新结点的next指针指向原头结点
head = newNode;//更新头结点为新结点
}
//向链表末尾添加一个元素
void append(const T& data) {
Node<T>* newNode = new Node(data);
if (head == nullptr) {
head = newNode;
} else {
Node<T>* current = head;
while (current->next != nullptr) {//通过next指针遍历到最后一个结点
current = current->next;
}
current->next = newNode;//最后一个结点的next指针指向新结点
}
}
//按data查找结点，返回指针
Node<T>* findNode(const T& data) {
auto currentNode = head;//从头结点开始遍历
while (currentNode != nullptr) {
if (currentNode->data == data) {
return currentNode;
}
currentNode = currentNode->next;//继续遍历下一个结点
}
return nullptr;//如果未找到返回nullptr
}
//按data删除结点
void remove(const T& data) {
if (head == nullptr) return;//链表为空直接返回
if (head->data == data) {//如果头结点就是要删除的结点
auto temp = head;
head = head->next;//将原头结点的下一个结点更新为头结点
delete temp;//释放原头结点的内存
return;
}
auto current = head;
while (current->next != nullptr) {//遍历当前结点的下一个结点
if(current->next->data == data) {//找到要删除的结点
auto* temp = current->next;//保存要删除的结点指针
current->next = current->next->next;//变更当前结点的next指向
delete temp;//释放结点的内存
return;
}
current = current->next;
}
}
//遍历所有元素
void traverse() const {
auto current = head;
while (current != nullptr) {
cout << current->data << " -> ";
current = current->next;
}
cout << "nullptr" << endl;
}
};
#endif //DS_SINGLYLINKEDLIST_H
main.cpp测试单向链表
//
// 测试SinglyLinkedList
//
#include <iostream>
using namespace std;
#include "SinglyLinkedList.h"
int main() {
SinglyLinkedList<string> sll;
sll.append("b");
sll.prepend("a");
sll.append("c");
sll.append("d");
sll.append("e");
sll.traverse();
sll.remove("d");
sll.traverse();
sll.remove("a");
sll.traverse();
sll.remove("e");
sll.traverse();
cout << sll.findNode("c");
return 0;
}
双向链表
在单向循环链表中，虽然从任意结点出发可以扫描到其他结点，但平均时间复杂度是O(n)，而要找到其前驱结点，则需要遍历整个单向循环链表，如果希望快速确定表中任一结点的前驱结点，可以在单向链表的每个结点中再设置一个指向其前驱结点的指针域，这样形成的链表中有两个方向不同的链，故称为双向链表(Double Linked List)，其结点结构如图 2.27 所示。
data：数据域，用来存储数据的信息;
prior：前驱指针域，存放该结点的前驱结点的地址;
next：后继指针域，存放该结点的后继结点的地址。
和单向链表类似，双向链表一般也是由头指针唯一确定，增加头结点也能使双向链表的某些操作变得方便，将头结点和尾结点链接起来也能构成双向循环链表，这样，无论是插入还是删除操作，对链表中的开始结点、尾结点和中间任意结点的操作过程都相同。实际应用中常采用带头结点的双向循环链表，如图 2.28所示。
DoubleLinkedList.cpp实现双向链表
//
// 双向链表
//
#ifndef DS_DOUBLELINKEDLIST_H
#define DS_DOUBLELINKEDLIST_H
#include <iostream>
using namespace std;
template <class T>
//双向链表的结点结构
struct Node{
T data;//数据
Node* prior;//指向前一个结点的指针
Node* next;//指向后一个结点的指针
Node(const T& value, Node* p = nullptr, Node* n = nullptr) {
data = value;
prior = p;
next = n;
}
};
template <class T>
class DoubleLinkedList {
private:
Node<T>* head; //指向链表头部结点的指针
Node<T>* tail; //指向链表尾部结点的指针
public:
DoubleLinkedList() : head(nullptr), tail(nullptr) {}
~DoubleLinkedList() {
while (head != nullptr) {
Node<T>* current = head;
head = head->next;
delete current;
}
tail = nullptr;
}
// 在链表头部添加新结点
void prepend(const T& data) {
Node<T>* newNode = new Node(data);
if (head == nullptr) { //如果链表为空，新结点同时是头结点和尾结点
head = tail = newNode;
} else {
newNode->next = head;//新结点的next指向原头部结点
head->prior = newNode;//原头部结点的prior指向新结点
head = newNode;
}
}
// 在链表末尾添加新结点
void append(const T& data) {
Node<T>* newNode = new Node(data);
if (tail == nullptr) {//如果链表为空，新结点同时是头部结点和尾部结点
head = tail = newNode;
} else {
tail->next = newNode;//原尾部结点的next指向新结点
newNode->prior = tail;//新结点的prior指向原尾部结点
tail = newNode;
}
}
// 删除指定值的结点（只删除第一个匹配的结点）
void remove(const T& data) {
Node<T>* current = head;
while (current != nullptr) {
if (current->data == data) { //找到匹配的结点，进行删除操作
if (current->prior != nullptr) { // 如果不是头结点，则重新链接前一个结点和后一个结点
current->prior->next = current->next;
} else { // 是头结点的情况，更新头指针
head = current->next;
}
if (current->next != nullptr) { // 如果不是尾结点，则重新链接前一个结点和后一个结点
current->next->prior = current->prior;
} else { // 是尾结点的情况，更新尾指针
tail = current->prior;
}
delete current; // 删除当前结点并退出循环（只删除第一个匹配的结点）
return;
}
current = current->next; //继续搜索下一个结点
}
cout << "未找到值为 " << data << " 的结点" << endl;
}
//按data查找结点，返回指针
Node<T>* findNode(const T& data) {
Node<T>* currentNode = head;//从头结点开始遍历
while (currentNode != nullptr) {
if (currentNode->data == data) {
return currentNode;
}
currentNode = currentNode->next;//继续遍历下一个结点
}
return nullptr;//如果未找到返回nullptr
}
//遍历所有元素
void traverse() const {
Node<T>* current = head;
while (current != nullptr) {
cout << current->data << " -> ";
current = current->next;
}
cout << "nullptr" << endl;
}
};
#endif //DS_DOUBLELINKEDLIST_H
main.cpp测试双向链表
//
// 测试DoubleLinkedList
//
#include <iostream>
using namespace std;
#include "DoubleLinkedList.h"
int main() {
DoubleLinkedList<string> dll;
dll.append("b");
dll.prepend("a");
dll.append("c");
dll.append("d");
dll.append("e");
dll.traverse();
dll.remove("d");
dll.traverse();
dll.remove("a");
dll.traverse();
dll.remove("e");
dll.traverse();
cout << dll.findNode("c");
return 0;
}
循环链表(Circular Linked List)是一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。
在某些场景中，为了使链表的操作更加简洁和高效，往往会将链表的终端结点与表头结点连接起来，形成循环链表，有时也叫环形链表。
根据链表中包含的环的个数，循环链表可以分为两类:单循环链表和多重链的循环链表(简称多重循环链表)。
单循环链表(Simgle Circular Linked List)是指在单向链表的基础上，将终端结点的指针域 NULL改为指向头部结点或开始结点，从而实现了循环(只有一个循环)。从单循环链表中任意结点出发均可找到表中其他结点。
多重循环链表(Multiple Circular Linked List)：在某些场景中，链表L里的结点可能隶属于多个链表(也就是链表中的结点有多个指针)，如果这多个链表每个都是一个单循环链表，那么L就称为多重循环链表(链表中有多个循环 )。最常见的多重循环链表是双向循环链表,十字链表就是双向循环链表。
为了使空表和非空表的处理一致，循环链表中也可设置一个头部结点。这样，空单循环链表仅有一个自成循环的头结点表示，如图 (a)所示，非空单循环链表则如图(b)所示。
在用头指针表示的单向循环链表中，找到开始结点a1的时间复杂度是O(1)，然而，要找到尾结点则需从头指针开始遍历整个链表，其时间复杂度是O(n)。
在很多实际问题中，表的操作常常是在表的尾位置上进行，此时头指针表示的单循环链表就显得不太方便。为提高此类场景的效率，可改用尾指针rear来表示单向循环链表，则查找开始结点a1和尾结点an都将很方便。用尾指针表示的单循环链表如图 2.26 所示。此时,头结点的地址是rear→next,尾结点的地址是rear，显然，查找头结点和尾结点的时间复杂度都O(1)。
循环链表给结点查找带来方便，但由于链表中没有 NULL 指针，即链表中没有明显的尾端，可能会使循环链表的操作进入死循环，因此需格外注意。在涉及遍历操作时，单循环链表的终止条件不再像非循环链表那样判断某个指针是否为空，而是判断该指针是否等于某一特定指针(如头指针或尾指针)。
循环链表的类定义与单链表的一样，只是使用时将尾结点的指针域由空改为指向头结点。循环链表基本操作的实现与单链表类似，不同之处是循环条件不一样
循环链表在插入和删除时需要维护循环性质，特别是在空链表插入第一个结点时，其next指向自己（形成循环）。
删除结点时，如果删除后链表为空，则头指针应设置为nullptr
我们也可以选择另一种方式：引入哨兵结点（Sentinel Node）。
哨兵结点可以简化链表的操作，特别是在插入和删除节点时。哨兵节点通常位于链表的头部，它的作用是作为链表的起始点，使得链表操作更加直观和安全。
通常使用哨兵结点更容实现循环链表相关功能，因为可以避免很多空指针判断。
这里先实现不使用哨兵结点的版本，再实现使用哨兵结点的版本。
SinglyCircularLinkedList.h单向循环链表（不使用哨兵结点）的实现
//
// 单向循环链表（不使用哨兵结点）
//
#ifndef DS_SINGLYCIRCULARLINKEDLIST_H
#define DS_SINGLYCIRCULARLINKEDLIST_H
#include <iostream>
using namespace std;
template <class T>
//单向循环链表的结点结构
struct Node{
T data;
Node* next;
Node(const T& value, Node* n = nullptr) {
data = value;
next = n;
}
};
template <class T>
class SinglyCircularLinkedList {
private:
Node<T>* head;
public:
SinglyCircularLinkedList():head(nullptr){}
~SinglyCircularLinkedList() {
clear();
}
//向链表添加一个元素(由于是循环链表，所以不区分链表头部和尾部，没有prepend(const T& data))
void append(const T& data) {
auto newNode = new Node(data);
if (head == nullptr) {//空链表
head = newNode;
head->next = head;//头结点的next指向自己，形成环形
} else {
auto current = head;
while (current->next != head) {//通过next指针遍历到最后一个结点
current = current->next;
}
current->next = newNode;//最后一个结点的next指针指向新结点
newNode->next = head;//新结点的next指向头结点，保持环形
}
}
//按data查找结点，返回指针
Node<T>* findNode(const T& data) {
if (!head) return nullptr; // 如果链表为空，直接返回nullptr
auto current = head;
//使用do-while循环确保至少执行一次，即使链表只有一个结点
//因为是环形，所以终止条件为回到头结点，即current->next == head
do {
if (current->data == data) { // 找到元素，返回指向该结点的指针
return current;
}
current = current->next; // 移动到下一个结点
} while (current != head); // 回到头结点时停止
return nullptr; // 未找到元素，返回nullptr
}
//按data删除结点
void remove(const T& data) {
if (!head) return;//链表为空直接返回
auto temp = head;
Node<T>* prior = nullptr; // 用于记录要删除结点的前一个结点
do {
if (temp->data == data) { // 找到要删除的结点
if (temp == head && temp->next == head) { // 只有一个结点的情况
delete head; // 删除该结点并重置head为nullptr
head = nullptr;
} else if (temp == head) { // 要删除的是头结点的情况（但不是唯一结点）
prior = temp; // 先找到最后一个结点（即当前头结点的前一个结点）
while (prior->next != head) { // 找到最后一个结点
prior = prior->next;
}
prior->next = head->next; // 让最后一个结点的next指向头结点的下一个结点（即新的头结点）
delete head; // 删除原头结点并更新头指针为新头结点
head = head->next; // 新头结点即为原来的下一个结点
} else { //要删除的是中间或尾部的结点的情况（但不是头结点）
prior->next = temp->next; // 让前一个结点的next指向当前结点的下一个结点，从而删除当前结点
}
delete temp; // 删除当前结点
return; // 删除后直接返回。因为这里只删除一个符合匹配的结点，不再继续查找其他匹配项。
}
// 未找到，继续查找下一个结点
prior = temp; // 更新前一个结点的引用为当前结点，以防需要删除当前结点的下一个结点时使用。
temp = temp->next; // 移动到下一个结点。在循环链表中，最终会回到头结点
} while (temp != head); //当回到头结点时结束循环
cout << "不存在：" << data << endl;
}
//清空链表
void clear() {
if (!head) return; // 如果链表为空，直接返回。
auto current = head;
do {
auto toDelete = current; // 记录要删除的结点。
current = current->next; //移动到下一个结点。
delete toDelete; // 删除当前结点。
} while (current != head); // 当回到头结点时停止（对于非空循环链表）。
head = nullptr; // 清空头结点指针。
}
//遍历所有元素
void traverse() const {
if (!head) {
cout << "List is empty." << endl;
return;
}
auto current = head;
do {
cout << current->data << " -> "; // 打印当前结点的数据。
current = current->next; //移动到下一个结点。
} while (current != head); // 当回到头结点时停止（对于非空循环链表）
cout << endl;
}
};
#endif //DS_SINGLYCIRCULARLINKEDLIST_H
main.cpp测试单向循环链表（不使用哨兵结点）
//
// 测试SinglyCircularLinkedList
//
#include <iostream>
using namespace std;
#include "SinglyCircularLinkedList.h"
int main() {
SinglyCircularLinkedList<int> scll;
scll.append(10);
scll.append(20);
scll.append(30);
scll.traverse();
cout << scll.findNode(20) << endl;
scll.remove(20);
scll.traverse();
scll.clear();
scll.traverse();
return 0;
}
单向循环链表（使用哨兵结点）的实现
通过引入哨兵结点（Sentinel Node），链表的操作（如插入、删除）可以统一处理，避免了对空链表或头结点的特殊处理。
SentinelSinglyCircularLinkedList.h单向循环链表（使用哨兵结点）的实现
//
// 使用哨兵结点实现的单向循环链表
//
#ifndef DS_SENTINELSINGLYCIRCULARLINKEDLIST_H
#define DS_SENTINELSINGLYCIRCULARLINKEDLIST_H
#include <iostream>
using namespace std;
template <class T>
//结点结构
struct Node{
T data;
Node* next;
Node(const T& val) : data(val), next(nullptr) {}
Node() : data(T()), next(nullptr) {}
};
template <class T>
class SentinelSinglyCircularLinkedList {
private:
Node<T>* sentinel;//哨兵结点
public:
SentinelSinglyCircularLinkedList() {
sentinel = new Node<T>();
sentinel->next = sentinel;//哨兵结点的next指向自己，形成环形
}
~SentinelSinglyCircularLinkedList() {
clear();
}
//向链表添加一个元素
void append(const T& data) {
auto newNode = new Node(data);
newNode->next = sentinel->next;//新结点的next指向原头结点(哨兵结点的下一个结点)
sentinel->next = newNode;//哨兵结点的next指向新结点
}
//按data查找结点，返回指针
Node<T>* findNode(const T& data) {
auto current = sentinel->next;//从哨兵结点的下一个结点开始遍历
if (!current) {
throw out_of_range("List is empty.");
}
while (current != sentinel) { // 遍历到哨兵结点为止
if (current->data == data) {
return current;
}
current = current->next;
}
return nullptr;//如果未找到返回nullptr
}
//按data删除结点
void remove(const T& data) {
auto current = sentinel; // 从哨兵开始遍历
while (current->next != sentinel && current->next->data != data) { //查找要删除的结点，但不越过哨兵结点本身
current = current->next;
}
if (current->next != sentinel) { // 如果找到了要删除的结点
auto temp = current->next; // 保存要删除的结点指针
current->next = temp->next; // 跳过要删除的结点，实现删除操作
delete temp; // 释放内存
}else {
cout << "不存在：" << data << endl;
}
}
//清空链表
void clear() {
auto current = sentinel->next;//从哨兵结点的下一个结点开始遍历
Node<T>* nextNode = nullptr;
while (current != sentinel) { // 遍历到哨兵结点为止
nextNode = current->next;
delete current;
current = nextNode;
}
delete sentinel;//释放哨兵结点内存
}
//遍历所有元素
void traverse() const {
auto current = sentinel->next;//从哨兵结点的下一个结点开始遍历
if (!current) {
cout << "List is empty." << endl;
return;
}
do {
cout << current->data << " -> "; // 打印当前结点的数据。
current = current->next; //移动到下一个结点。
} while (current != sentinel); // 当回到哨兵结点时停止
cout << endl;
}
};
#endif //DS_SENTINELSINGLYCIRCULARLINKEDLIST_H
main.cpp测试单向循环链表（使用哨兵结点）
//
// 测试SentinelSinglyCircularLinkedList
//
#include <iostream>
using namespace std;
#include "SentinelSinglyCircularLinkedList.h"
int main() {
SentinelSinglyCircularLinkedList<string> sscll;
sscll.append("10");
sscll.append("20");
sscll.append("30");
sscll.traverse();
cout << sscll.findNode("20") << endl;
sscll.remove("20");
sscll.traverse();
sscll.clear();
sscll.traverse();
return 0;
}
DoublyCircularLinkedList.h实现双向循环链表（不使用哨兵结点）
//
// 双向循环链表
//
#ifndef DS_DOUBLYCIRCULARLINKEDLIST_H
#define DS_DOUBLYCIRCULARLINKEDLIST_H
#include <iostream>
using namespace std;
template <class T>
//双向循环链表的结点结构
struct Node{
T data;
Node* prior;
Node* next;
Node(const T& value, Node* p = nullptr, Node* n = nullptr) {
data = value;
prior = p;
next = n;
}
};
template <class T>
class DoublyCircularLinkedList {
private:
Node<T>* head;
public:
DoublyCircularLinkedList() : head(nullptr) {}
~DoublyCircularLinkedList() { // 析构函数，释放所有结点内存
clear();
}
//向链表添加一个元素
void append(const T& data) {
auto newNode = new Node(data);
if (!head) { //如果链表为空，新结点即为头结点和尾结点
head = newNode;
newNode->next = newNode; //指向自己形成环形
newNode->prior = newNode; //指向自己形成环形
} else { // 如果链表不为空，找到尾部并插入新结点
auto tail = head->prior; // 尾部结点是头结点的前一个结点
tail->next = newNode; // 新结点成为尾部结点
newNode->prior = tail; // 新结点的prior指向原尾部结点
newNode->next = head; // 新结点的next指向头结点形成环
head->prior = newNode; // 头结点的prior指向新结点形成环
}
}
//按data查找结点，返回指针
Node<T>* findNode(const T& data) {
if (!head) return nullptr; // 如果链表为空，直接返回nullptr
auto current = head;
//使用do-while循环确保至少执行一次
//因为是环形，所以终止条件为回到头结点，即current->next == head
do {
if (current->data == data) { // 找到元素，返回指向该结点的指针
return current;
}
current = current->next;
} while (current != head); // 回到头结点时停止
return nullptr; // 未找到元素，返回nullptr
}
//按data删除结点
void remove(const T& data) { // 删除指定值的结点
if (!head) return; // 如果链表为空，直接返回
auto current = head;
Node<T>* priorNode = nullptr; // 用于记录当前结点的前一个结点，初始为空（用于删除操作）
do {
if (current->data == data) { // 找到要删除的结点
if (current == head && current->next == head) { // 只有一个结点的情况
delete head; // 删除头结点，并置为空
head = nullptr;
} else if (current == head) { // 要删除的是头结点的情况
head = head->next; // 更新头结点为下一个结点
delete current->prior; // 删除尾结点的上一个结点（原头结点）
head->prior = head->prior->prior; // 更新尾结点的prior指向新的尾结点（原头结点的prior）
} else { // 要删除的是中间或尾部的结点的情况
priorNode->next = current->next; // 前一个结点的next指向当前结点的下一个结点
current->next->prior = priorNode; // 下一个结点的prior指向前一个结点
}
delete current; // 删除当前结点
return; // 删除后直接返回，避免重复遍历已删除的结点
}
priorNode = current; //更新前一个结点为当前结点
current = current->next; //移动到下一个结点
} while (current != head); //循环直到回到头结点
}
//遍历所有元素
void traverse() const {
if (!head) {
cout << "List is empty." << endl;
return;
}
auto current = head;
do {
cout << current->data << " -> ";
current = current->next;
} while (current != head); //循环直到回到头结点
cout << endl;
}
void clear() {
if (!head) return; // 如果链表为空，直接返回
auto current = head;
do {
auto temp = current;
current = current->next;
delete temp;
}while (current != head); // 当回到头结点时停止
delete head;
}
};
#endif //DS_DOUBLYCIRCULARLINKEDLIST_H
main.cpp测试双向循环链表（不使用哨兵结点）
//
// 测试DoublyCircularLinkedList
//
#include <iostream>
using namespace std;
#include "DoublyCircularLinkedList.h"
int main() {
DoublyCircularLinkedList<string> dcll;
dcll.append("a");
dcll.append("b");
dcll.append("c");
dcll.traverse();
cout << dcll.findNode("b") << endl;
dcll.remove("b");
dcll.traverse();
dcll.clear();
dcll.traverse();
return 0;
}
SentinelDoublyCircularLinkedList.h实现双向循环链表（不使用哨兵结点）
//
// 使用哨兵结点实现的双向循环链表
//
#ifndef DS_SENTINELDOUBLYCIRCULARLINKEDLIST_H
#define DS_SENTINELDOUBLYCIRCULARLINKEDLIST_H
#include <iostream>
using namespace std;
template <class T>
struct Node{
T data;
Node* prior;
Node* next;
Node(const T& val) : data(val), prior(nullptr), next(nullptr) {}
Node() : data(T()), prior(nullptr), next(nullptr) {}
};
template <class T>
class SentinelDoublyCircularLinkedList {
private:
Node<T>* sentinel;//哨兵结点
public:
SentinelDoublyCircularLinkedList() {
sentinel = new Node<T>();
sentinel->prior = sentinel;//哨兵结点的prior指向自己，形成环形
sentinel->next = sentinel;//哨兵结点的next指向自己，形成环形
}
~SentinelDoublyCircularLinkedList() {
clear();
}
//向链表添加一个元素
void append(const T& data) {
auto newNode = new Node(data);
auto lastNode = sentinel->prior;//原链表最后一个结点(哨兵结点的上一个结点)
newNode->next = sentinel;//新结点的next指向哨兵结点
newNode->prior = lastNode;//新结点的prior指向原链表最后一个结点
lastNode->next = newNode;//原链表最后一个结点的next指向新结点
sentinel->prior = newNode;//哨兵结点的prior指向新结点
}
//按data查找结点，返回指针
Node<T>* findNode(const T& data) {
auto current = sentinel->next;//从哨兵结点的下一个结点开始遍历
if (!current) {
throw out_of_range("List is empty.");
}
while (current != sentinel) { // 遍历到哨兵结点为止
if (current->data == data) {
return current;
}
current = current->next;
}
return nullptr;//如果未找到返回nullptr
}
//按data删除结点
void remove(const T& data) {
auto current = sentinel; // 从哨兵开始遍历
while (current->next != sentinel && current->next->data != data) { //查找要删除的结点，但不越过哨兵结点本身
current = current->next;
}
if (current->next != sentinel) { // 如果找到了要删除的结点
auto temp = current->next; // 保存要删除的结点指针
current->next = temp->next; // 跳过要删除的结点，实现删除操作
delete temp; // 释放内存
}else {
cout << "不存在：" << data << endl;
}
}
//遍历所有元素
void traverse() const {
auto current = sentinel->next;//从哨兵结点的下一个结点开始遍历
if (!current) {
cout << "List is empty." << endl;
return;
}
do {
cout << current->data << " -> "; // 打印当前结点的数据。
current = current->next; //移动到下一个结点。
} while (current != sentinel); // 当回到哨兵结点时停止
cout << endl;
}
//清空链表
void clear() {
auto current = sentinel->next;//从哨兵结点的下一个结点开始遍历
Node<T>* nextNode = nullptr;
while (current != sentinel) { // 遍历到哨兵结点为止
nextNode = current->next;
delete current;
current = nextNode;
}
delete sentinel;//释放哨兵结点内存
}
};
#endif //DS_SENTINELDOUBLYCIRCULARLINKEDLIST_H
main.cpp测试双向循环链表（使用哨兵结点）
//
// 测试SentinelDoublyCircularLinkedList
//
#include <iostream>
using namespace std;
#include "SentinelDoublyCircularLinkedList.h"
int main() {
SentinelDoublyCircularLinkedList<string> sdcll;
sdcll.append("apple");
sdcll.append("boy");
sdcll.append("cat");
sdcll.append("dog");
sdcll.traverse();
cout << sdcll.findNode("boy") << endl;
sdcll.remove("boy");
sdcll.traverse();
sdcll.clear();
sdcll.traverse();
return 0;
}
静态链表在不支持指针的编程语言（如Fortran或某些嵌入式环境）中很有用，但现代主流语言（如C++）更倾向使用动态内存管理，所以这里不作讨论。
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
1
0- 0
已为社区贡献7条内容
所有评论(0)