C++ 数据结构 单链表、双链表、循环单向链表、循环双向链表
单链表和双链表是常用的线性数据结构，它们都有各自的优缺点和适用场景。以下是它们的基本概念、实现示例以及各自的特点。
单链表
概念
单链表是由一系列节点组成的线性数据结构，每个节点包含数据和一个指向下一个节点的指针。最后一个节点的指针指向nullptr。
特点
- 插入和删除效率：在已知位置的情况下，插入和删除操作的时间复杂度为O(1)，但查找时间复杂度为O(n)。
- 内存占用：每个节点只存储一个指针，相对较省内存。
- 单向性：只能向一个方向遍历。
操作示意
插入操作：
- 在链表头插入 (插入1)：
[1] -> nullptr在尾部插入 (插入2)：
[1] -> [2] -> nullptr
在中间插入 (插入3，索引1)：
[1] -> [3] -> [2] -> nullptr
删除操作：
- 删除索引1的元素 (删除3)：
[1] -> [2] -> nullptr#include <iostream> // 单链表节点类 template <typename T> class Node { public: T data; // 节点的数据部分 Node* next; // 指向下一个节点的指针 Node(const T& value) : data(value), next(nullptr) {} // 构造函数 }; // 单链表类 template <typename T> class SinglyLinkedList { public: SinglyLinkedList() : head(nullptr) {} // 构造函数，初始化头指针为空 ~SinglyLinkedList() { while (head) { remove(0); // 删除所有节点 } } // 在指定索引处插入元素 void insert(int index, const T& value) { if (index < 0) return; // 索引无效 Node<T>* newNode = new Node<T>(value); // 创建新节点 if (index == 0) { // 插入到头部 newNode->next = head; // 新节点指向当前头节点 head = newNode; // 更新头指针为新节点 return; } Node<T>* current = head; // 找到插入位置的前一个节点 for (int i = 0; i < index - 1 && current != nullptr; ++i) { current = current->next; // 移动到下一个节点 } if (current) { // 在中间插入 newNode->next = current->next; // 新节点指向插入位置的下一个节点 current->next = newNode; // 前一个节点指向新节点 } else { delete newNode; // 超出范围，释放内存 } } // 删除指定索引的元素 bool remove(int index) { if (index < 0 || head == nullptr) return false; // 索引无效或链表为空 Node<T>* temp = head; // 从头节点开始 if (index == 0) { // 删除头节点 head = temp->next; // 更新头指针为下一个节点 delete temp; // 释放内存 return true; } // 找到要删除节点的前一个节点 for (int i = 0; i < index - 1 && temp != nullptr; ++i) { temp = temp->next; // 移动到下一个节点 } if (temp == nullptr || temp->next == nullptr) return false; // 超出范围 // 删除目标节点 Node<T>* nodeToDelete = temp->next; // 保存要删除的节点 temp->next = nodeToDelete->next; // 前一个节点指向目标节点的下一个节点 delete nodeToDelete; // 释放内存 return true; // 删除成功 } // 打印链表中的所有元素 void print() const { Node<T>* current = head; // 从头节点开始 while (current) { std::cout << current->data << " "; // 输出节点数据 current = current->next; // 移动到下一个节点 } std::cout << std::endl; // 换行 } private: Node<T>* head; // 链表的头指针 }; int main() { SinglyLinkedList<int> list; // 创建单链表实例 list.insert(0, 1); // 在索引0插入1 list.insert(1, 2); // 在索引1插入2 list.insert(1, 3); // 在索引1插入3 list.print(); // 输出: 1 3 2 list.remove(1); // 删除索引1的元素 list.print(); // 输出: 1 2 return 0; }双链表
概念
双链表是由一系列节点组成的线性数据结构，每个节点包含数据、一个指向下一个节点的指针和一个指向前一个节点的指针。第一个节点的前指针和最后一个节点的后指针均指向
nullptr。特点
- 双向遍历：可以从前向后和从后向前遍历。
- 插入和删除效率：与单链表相同，但双链表在删除时可以更方便地找到前驱节点。
- 内存占用：每个节点需存储两个指针，因此占用更多内存。
操作示意
插入操作：
- 在链表头插入 (插入1)：
[1] <-> nullptr
在尾部插入 (插入2)：
[1] <-> [2] <-> nullptr
在中间插入 (插入3，索引1)：
[1] <-> [3] <-> [2] <-> nullptr
删除操作：
- 删除索引1的元素 (删除3)：
[1] <-> [2] <-> nullptr
#include <iostream>
// 双链表节点类
template <typename T>
class DNode {
public:
T data; // 节点的数据部分
DNode* next; // 指向下一个节点的指针
DNode* prev; // 指向前一个节点的指针
DNode(const T& value) : data(value), next(nullptr), prev(nullptr) {} // 构造函数
};
// 双链表类
template <typename T>
class DoublyLinkedList {
public:
DoublyLinkedList() : head(nullptr), tail(nullptr) {} // 构造函数，初始化头和尾指针为空
~DoublyLinkedList() {
while (head) {
remove(0); // 删除所有节点
}
}
// 在指定索引处插入元素
void insert(int index, const T& value) {
if (index < 0) return; // 索引无效
DNode<T>* newNode = new DNode<T>(value); // 创建新节点
if (index == 0) {
// 插入到头部
newNode->next = head; // 新节点指向当前头节点
if (head) head->prev = newNode; // 旧头节点的前驱指向新节点
head = newNode; // 更新头指针为新节点
if (!tail) tail = newNode; // 如果是第一个节点，更新尾指针
return;
}
DNode<T>* current = head;
// 找到插入位置的前一个节点
for (int i = 0; i < index - 1 && current != nullptr; ++i) {
current = current->next; // 移动到下一个节点
}
if (current) {
// 在中间插入
newNode->next = current->next; // 新节点指向插入位置的下一个节点
newNode->prev = current; // 新节点的前驱指向当前节点
if (current->next) current->next->prev = newNode; // 旧下一个节点的前驱指向新节点
current->next = newNode; // 当前节点指向新节点
if (!newNode->next) tail = newNode; // 如果是最后一个节点，更新尾指针
} else {
delete newNode; // 超出范围，释放内存
}
}
// 删除指定索引的元素
bool remove(int index) {
if (index < 0 || head == nullptr) return false; // 索引无效或链表为空
DNode<T>* temp = head; // 从头节点开始
if (index == 0) {
// 删除头节点
head = temp->next; // 更新头指针为下一个节点
if (head) head->prev = nullptr; // 更新新头节点的前驱指针
else tail = nullptr; // 如果链表空了，更新尾指针
delete temp; // 释放内存
return true;
}
// 找到要删除节点的前一个节点
for (int i = 0; i < index && temp != nullptr; ++i) {
temp = temp->next; // 移动到下一个节点
}
if (temp == nullptr) return false; // 超出范围
// 删除目标节点
if (temp->prev) temp->prev->next = temp->next; // 前一个节点指向目标节点的下一个节点
if (temp->next) temp->next->prev = temp->prev; // 下一个节点的前驱指向前一个节点
if (temp == tail) tail = temp->prev; // 如果删除的是尾节点，更新尾指针
delete temp; // 释放内存
return true; // 删除成功
}
// 打印链表中的所有元素
void print() const {
DNode<T>* current = head; // 从头节点开始
while (current) {
std::cout << current->data << " "; // 输出节点数据
current = current->next; // 移动到下一个节点
}
std::cout << std::endl; // 换行
}
private:
DNode<T>* head; // 链表的头指针
DNode<T>* tail; // 链表的尾指针
};
int main() {
DoublyLinkedList<int> list; // 创建双链表实例
list.insert(0, 1); // 在索引0插入1
list.insert(1, 2); // 在索引1插入2
list.insert(1, 3); // 在索引1插入3
list.print(); // 输出: 1 3 2
list.remove(1); // 删除索引1的元素
list.print(); // 输出: 1 2
return 0;
}
单循环链表 (Circular Singly Linked List)
特性：
- 循环性：最后一个节点的
next指针指向头节点，形成一个环形结构。 - 单向遍历：只能从头节点开始向前遍历，无法反向访问。
- 动态大小：可以动态增加或减少节点，内存利用灵活。
- 不易删除：无法直接访问前一个节点，因此删除操作需要遍历链表。
操作顺序：
- 插入：
- 创建新节点。
- 如果链表为空，设置头节点为新节点，
next指向自身。 - 如果不为空，找到尾节点，将新节点插入到头前。
- 更新尾节点的
next指针指向新节点。
- 删除：
- 遍历链表找到目标节点及其前驱节点。
- 调整前驱节点的
next指向目标节点的next，以跳过目标节点。 - 释放目标节点的内存。
操作示意
-
插入操作：
- 在链表头插入 (插入3)：
[3] <-> [3]在链表头插入 (插入2)：
[2] <-> [3] <-> [2]在链表头插入 (插入1)：
[1] <-> [2] <-> [3] <-> [1]
- 在链表头插入 (插入3)：
删除操作：
操作顺序：
- 删除值为2的元素：
[1] <-> [3] <-> [1]#include <iostream> // 循环双链表节点类 template <typename T> class DNode { public: T data; // 节点的数据部分 DNode* next; // 指向下一个节点的指针 DNode* prev; // 指向前一个节点的指针 DNode(const T& value) : data(value), next(nullptr), prev(nullptr) {} // 构造函数 }; // 循环双链表类 template <typename T> class CircularDoublyLinkedList { public: CircularDoublyLinkedList() : head(nullptr) {} // 构造函数，初始化头指针为空 ~CircularDoublyLinkedList() { if (head) { DNode<T>* current = head; DNode<T>* nextNode; do { nextNode = current->next; // 保存下一个节点 delete current; // 删除当前节点 current = nextNode; // 移动到下一个节点 } while (current != head); // 直到回到头节点 } } // 在链表头插入元素 void insertAtHead(const T& value) { DNode<T>* newNode = new DNode<T>(value); // 创建新节点 if (!head) { head = newNode; // 如果链表为空，头指针指向新节点 head->next = head; // 新节点指向自己 head->prev = head; // 新节点的前驱指向自己 } else { newNode->next = head; // 新节点指向当前头节点 newNode->prev = head->prev; // 新节点的前驱指向尾节点 head->prev->next = newNode; // 尾节点指向新节点 head->prev = newNode; // 新节点成为新的头节点 head = newNode; // 更新头指针为新节点 } } // 删除指定值的元素 bool remove(const T& value) { if (!head) return false; // 链表为空 DNode<T>* current = head; do { if (current->data == value) { if (current == head) { // 删除头节点 if (current->next == head) { delete current; // 只有一个节点 head = nullptr; // 更新头指针为空 } else { head->prev->next = head->next; // 尾节点指向新头节点 head->next->prev = head->prev; // 新头节点的前驱指向尾节点 DNode<T>* temp = head; // 保存当前头节点 head = head->next; // 更新头指针 delete temp; // 删除旧头节点 } } else { // 删除中间或尾节点 current->prev->next = current->next; // 前一个节点跳过当前节点 current->next->prev = current->prev; // 后一个节点跳过当前节点 delete current; // 删除当前节点 } return true; // 删除成功 } current = current->next; // 移动到下一个节点 } while (current != head); // 直到回到头节点 return false; // 未找到元素 } // 打印链表中的所有元素 void print() const { if (!head) return; // 链表为空 DNode<T>* current = head; // 从头节点开始 do { std::cout << current->data << " "; // 输出节点数据 current = current->next; // 移动到下一个节点 } while (current != head); // 直到回到头节点 std::cout << std::endl; // 换行 } private: DNode<T>* head; // 链表的头指针 }; int main() { CircularDoublyLinkedList<int> list; // 创建循环双链表实例 list.insertAtHead(1); // 在头插入1 list.insertAtHead(2); // 在头插入2 list.insertAtHead(3); // 在头插入3 list.print(); // 输出: 3 2 1 list.remove(2); // 删除值为2的节点 list.print(); // 输出: 3 1 return 0; }双循环链表 (Circular Doubly Linked List)
特性：
- 循环性：尾节点的
next指针指向头节点，头节点的prev指针指向尾节点，形成环形结构。 - 双向遍历：可以从任意节点向前或向后遍历。
- 插入：
- 创建新节点。
- 如果链表为空，设置头节点为新节点，
next和prev均指向自身。 - 如果不为空：
- 更新新节点的
next和prev指向相应的节点。 - 更新相关节点的指针以保持循环结构。
- 更新新节点的
- 删除：
- 遍历链表找到目标节点。
- 调整前驱节点的
next和后继节点的prev指针，以跳过目标节点。 - 释放目标节点的内存。
- 动态大小：和单循环链表一样，动态增加或减少节点。
- 插入和删除灵活：可以在任何位置方便地进行插入和删除操作，因为每个节点都有前驱和后继指针。
#include <iostream>
// 循环双链表节点类
template <typename T>
class DNode {
public:
T data; // 节点的数据部分
DNode* next; // 指向下一个节点的指针
DNode* prev; // 指向前一个节点的指针
DNode(const T& value) : data(value), next(nullptr), prev(nullptr) {} // 构造函数
};
// 循环双链表类
template <typename T>
class CircularDoublyLinkedList {
public:
CircularDoublyLinkedList() : head(nullptr) {} // 构造函数，初始化头指针为空
~CircularDoublyLinkedList() {
if (head) {
DNode<T>* current = head;
DNode<T>* nextNode;
do {
nextNode = current->next; // 保存下一个节点
delete current; // 删除当前节点
current = nextNode; // 移动到下一个节点
} while (current != head); // 直到回到头节点
}
}
// 在链表头插入元素
void insertAtHead(const T& value) {
DNode<T>* newNode = new DNode<T>(value); // 创建新节点
if (!head) {
head = newNode; // 如果链表为空，头指针指向新节点
head->next = head; // 新节点指向自己
head->prev = head; // 新节点的前驱指向自己
} else {
newNode->next = head; // 新节点指向当前头节点
newNode->prev = head->prev; // 新节点的前驱指向尾节点
head->prev->next = newNode; // 尾节点指向新节点
head->prev = newNode; // 新节点成为新的头节点
head = newNode; // 更新头指针为新节点
}
}
// 删除指定值的元素
bool remove(const T& value) {
if (!head) return false; // 链表为空
DNode<T>* current = head;
do {
if (current->data == value) {
if (current == head) {
// 删除头节点
if (current->next == head) {
delete current; // 只有一个节点
head = nullptr; // 更新头指针为空
} else {
head->prev->next = head->next; // 尾节点指向新头节点
head->next->prev = head->prev; // 新头节点的前驱指向尾节点
DNode<T>* temp = head; // 保存当前头节点
head = head->next; // 更新头指针
delete temp; // 删除旧头节点
}
} else {
// 删除中间或尾节点
current->prev->next = current->next; // 前一个节点跳过当前节点
current->next->prev = current->prev; // 后一个节点跳过当前节点
delete current; // 删除当前节点
}
return true; // 删除成功
}
current = current->next; // 移动到下一个节点
} while (current != head); // 直到回到头节点
return false; // 未找到元素
}
// 打印链表中的所有元素
void print() const {
if (!head) return; // 链表为空
DNode<T>* current = head; // 从头节点开始
do {
std::cout << current->data << " "; // 输出节点数据
current = current->next; // 移动到下一个节点
} while (current != head); // 直到回到头节点
std::cout << std::endl; // 换行
}
private:
DNode<T>* head; // 链表的头指针
};
int main() {
CircularDoublyLinkedList<int> list; // 创建循环双链表实例
list.insertAtHead(1); // 在头插入1
list.insertAtHead(2); // 在头插入2
list.insertAtHead(3); // 在头插入3
list.print(); // 输出: 3 2 1
list.remove(2); // 删除值为2的节点
list.print(); // 输出: 3 1
return 0;
}
总结
下面是关于单链表、双链表、单向循环链表和双向循环链表的操作顺序的详细总结。
1. 单链表 (Singly Linked List)
在头插入：
- 创建新节点，设置新节点的数据。
- 将新节点的
next指向当前头节点。 - 更新头指针为新节点。
在尾插入：
- 创建新节点，设置新节点的数据。
- 如果链表为空，设置头指针为新节点，
next指向nullptr。 - 如果链表不为空，遍历链表找到最后一个节点。
- 将最后一个节点的
next指向新节点，并将新节点的next设置为nullptr。
在中间插入：
- 创建新节点，设置新节点的数据。
- 遍历链表，找到插入位置的前一个节点。
- 将新节点的
next指向前一个节点的next。 - 更新前一个节点的
next指向新节点。
删除操作：
2. 双链表 (Doubly Linked List)
删除操作：
3. 单向循环链表 (Circular Singly Linked List)
删除操作：
4. 双向循环链表 (Circular Doubly Linked List)
删除操作：
-
删除头节点：
- 如果链表为空，返回失败。
- 保存当前头节点，更新头指针为头节点的
next。 - 删除保存的头节点。
-
删除尾节点：
- 如果链表为空，返回失败。
- 如果链表只有一个节点，调用删除头节点。
- 遍历链表找到倒数第二个节点。
- 更新倒数第二个节点的
next为nullptr，删除尾节点。
-
删除中间节点：
- 遍历链表找到目标节点及其前驱节点。
- 更新前驱节点的
next指向目标节点的next。 - 删除目标节点。
-
在头插入：
- 创建新节点，设置新节点的数据。
- 如果链表为空，设置头指针为新节点，
next和prev均指向自身。 - 如果链表不为空，设置新节点的
next指向当前头节点。 - 更新当前头节点的
prev指向新节点。 - 新节点的
prev指向尾节点，更新尾节点的next指向新节点。 - 更新头指针为新节点。
-
在尾插入：
- 创建新节点，设置新节点的数据。
- 如果链表为空，调用在头插入。
- 如果链表不为空，遍历找到尾节点。
- 设置新节点的
prev指向当前尾节点，更新尾节点的next指向新节点。 - 更新新节点的
next指向头节点，头节点的prev指向新节点。
-
在中间插入：
- 创建新节点，设置新节点的数据。
- 遍历找到插入位置的前一个节点。
- 更新新节点的
next指向前一个节点的next，并更新前一个节点的next指向新节点。 - 更新新节点的
prev指向前一个节点。 - 更新新节点的
next的prev指向新节点。
-
删除头节点：
- 如果链表为空，返回失败。
- 保存当前头节点。
- 更新头指针为头节点的
next。 - 更新新头节点的
prev指向尾节点。 - 删除保存的头节点。
-
删除尾节点：
- 如果链表为空，返回失败。
- 如果链表只有一个节点，调用删除头节点。
- 找到倒数第二个节点，更新其
next为nullptr。 - 更新新尾节点的
next指向头节点，头节点的prev指向新尾节点。 - 删除原尾节点。
-
删除中间节点：
- 遍历链表找到目标节点。
- 更新目标节点的
prev的next和next的prev指向相应的节点，跳过目标节点。 - 删除目标节点。
-
在头插入：
- 创建新节点，设置数据。
- 如果链表为空，设置新节点的
next指向自身，头指针指向新节点。 - 如果不为空，找到尾节点，更新尾节点的
next为新节点，新节点的next为头节点。 - 更新头指针为新节点。
-
在尾插入：
- 创建新节点，设置数据。
- 如果链表为空，调用在头插入。
- 如果不为空，找到尾节点，更新尾节点的
next为新节点，新节点的next为头节点。
-
在中间插入：
- 创建新节点，设置数据。
- 遍历找到插入位置的前一个节点。
- 更新新节点的
next指向前一个节点的next，并更新前一个节点的next指向新节点。
-
删除头节点：
- 如果链表为空，返回失败。
- 保存当前头节点。
- 更新头指针为头节点的
next。 - 找到尾节点，更新尾节点的
next为新头节点。 - 删除保存的头节点。
-
删除尾节点：
- 如果链表为空，返回失败。
- 如果链表只有一个节点，调用删除头节点。
- 遍历找到倒数第二个节点，更新其
next指向头节点，删除尾节点。
-
删除中间节点：
- 遍历找到目标节点及其前驱节点。
- 更新前驱节点的
next指向目标节点的next。 - 删除目标节点。
-
在头插入：
- 创建新节点，设置数据。
- 如果链表为空，设置新节点的
next和prev均指向自身，头指针指向新节点。 - 如果不为空，更新新节点的
next为头节点，prev为尾节点。 - 更新头节点的
prev为新节点，尾节点的next为新节点。 - 更新头指针为新节点。
-
在尾插入：
- 创建新节点，设置数据。
- 如果链表为空，调用在头插入。
- 如果不为空，更新新节点的
prev为当前尾节点，next为头节点。 - 更新当前尾节点的
next为新节点，头节点的prev为新节点。
-
在中间插入：
- 创建新节点，设置数据。
- 遍历找到插入位置的前一个节点。
- 更新新节点的
next和prev指针，并更新相关节点的指针以保持循环结构。
-
删除头节点：
- 如果链表为空，返回失败。
- 保存当前头节点。
- 更新头指针为头节点的
next。 - 更新新头节点的
prev指向尾节点，尾节点的next指向新头节点。 - 删除保存的头节点。
-
删除尾节点：
- 如果链表为空，返回失败。
- 如果链表只有一个节点，调用删除头节点。
- 更新倒数第二个节点的
next为头节点，头节点的prev指向新尾节点。 - 删除原尾节点。
-
删除中间节点：
- 遍历链表找到目标节点。
- 更新目标节点的
prev和next的指针以跳过目标节点。 - 删除目标节点。
原文地址：https://blog.csdn.net/qq_50373827/article/details/143427254
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！