链表 Linked List
2024.3.15芝士wa
参考视频：bilibli-数据结构-链表“印度小哥讲得真好”
链表
[*]对于链表来说，存储数据需要两个部门，一是数据本身，二是指针，该指针指向下一个数据的地址，依次链接，直到末了一个元素，指针指向空（NULL）
https://img2024.cnblogs.com/blog/3408897/202403/3408897-20240315161823920-2125958019.png
[*]遍历的时间复杂度为O(n)
[*]插入的时间复杂度为O(n)
[*]删除的时间复杂度为O(n)
链表VS数组
[*]数组是连续存储空间，链表通过指针维系，存储数据并不连续
[*]数组可以通过下标访问元素，只需要O(1)的时间复杂度，而链表则必须按照顺序访问，因此时间复杂度为O(n/2) = O(n)
[*]数组的大小是固定的，在创建数组时确认
[*]上风：链表在添加或删除元素时，制止了不相关元素的复制移动，空间复杂度较小
[*]使用链表时，要格外注意指针问题
链表的C++实现
完整代码#pragma once
#include <iostream>
using namespace std;
template<class T>
class Node
{
public:
T data;
Node* next;
};
template<class T>
class LinkedList
{
public:
LinkedList();
~LinkedList();
Node<T>* head;
int m_num;//记录节点个数
//尾插法
void Insert(T x);
//在特定位置添加
void Insert(T x, int n);
//打印，遍历法
void print();
//递归方法打印
void Rprint(Node<T>* p);
//特定位置删除
void remove(int n);
//反转链表，迭代法
void reverse();
//反转链表，递归方法
void Reverse(Node<T>* p);
};
template<class T>
LinkedList<T>::LinkedList()
{
head = new Node<T>;
head->next = NULL;
this->m_num = 0;
}
template<class T>
LinkedList<T>::~LinkedList()
{
Node<T>* ite = head;
Node<T>* next;
while (ite != NULL) {
next = ite->next;
delete ite;
ite = next;
}
this->m_num = 0;
}
template<class T>//尾插法添加元素
void LinkedList<T>::Insert(T x)
{
Node<T>* end = new Node<T>;
end->data = x;
end->next = NULL;
if (head== NULL) {
//链表为空
head = end;
this->m_num++;
cout << "添加成功，当前节点数量：" << this->m_num << endl;
}
else {
Node<T>* ite = head;
//链表不为空，得到末尾end
while (ite->next != NULL) {
ite = ite->next;
}
//现在ite指向最后一个元素
ite->next = end;
}
this->m_num++;
cout << "添加成功，当前节点数量：" << this->m_num << endl;
}
template<class T>//特定位置添加元素
void LinkedList<T>::Insert(T x, int n)
{
Node<T>* temp = new Node<T>;
temp->data = x;
temp->next = NULL;
if (n == 1) {
//在头节点之后添加
temp->next = head->next;
head = temp;
this->m_num++;
cout << "添加成功，当前节点数量：" << this->m_num << endl;
return;
}
else if(n > 1 && n <= this->m_num){
Node<T>* ite = head;
//找到第n-1个元素，
for (int i = 0; i <= n - 2; i++) {
ite = ite->next;
}
temp->next = ite->next;
ite->next = temp;
this->m_num++;
cout << "添加成功，当前节点数量：" << this->m_num << endl;
return;
}
else {
cout << "越界" << endl;
return;
}
}
template<class T>
void LinkedList<T>::print()
{
Node<T>* ite = head;
while (ite!= NULL) {
cout << ite->data << "\t";
ite = ite->next;
}
cout << endl;
}
template<class T>
void LinkedList<T>::Rprint(Node<T> * p)
{
if (p == NULL) {
return;
}
Rprint(p->next);
cout << p->data << "\t";
}
template<class T>
void LinkedList<T>::remove(int n)
{
Node<T>* temp = head;
//第一个节点
if (n == 1) {
head = head->next;
delete temp;
this->m_num--;
cout << "删除成功，当前节点数量：" << this->m_num << endl;
return;
}
//第2~num之间删除节点
else if (n > 1 && n <= this->m_num) {
for (int i = 0; i < n - 2; i++) {
temp = temp->next;
}
//现在temp指向的是第n-1个节点
Node<T>* temp1 = temp->next;//指向第n个
temp->next = temp1->next;
delete temp1;
this->m_num--;
cout << "删除成功，当前节点数量：" << this->m_num << endl;
return;
}
else {
cout << "越界" << endl;
return;
}
}
template<class T>
void LinkedList<T>::reverse()
{
Node<T>* current, * prev, * next;
current = head;
prev = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
head = prev;
}
template<class T>
void LinkedList<T>::Reverse(Node<T>* p)
{
if (p->next == NULL) {
head = p;
return;
}
Reverse(p->next);
p->next->next = p;
p->next = NULL;
}
[*]模板，泛型
[*]内部维护链表长度
[*]分别用递归和迭代的方式实现了打印和反转
[*]进行了简单的越界判定处置惩罚
双向链表
https://img2024.cnblogs.com/blog/3408897/202403/3408897-20240317161026788-1062783523.png
template<class T>
class Node
{
T data;
Node* prev;
Node* next;
};总结
本文先容了链表的概念和特性，并用C++实现了单链表。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]