2024.3.15
芝士wa
参考视频：bilibli-数据结构-链表 “印度小哥讲得真好”
链表
- 对于链表来说，存储数据需要两个部分，一是数据本身，二是指针，该指针指向下一个数据的地址，依次链接，直到最后一个元素，指针指向空（NULL）
-
遍历的时间复杂度为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://www.toymoban.com/news/detail-840923.html
template<class T>
class Node
{
T data;
Node* prev;
Node* next;
};
总结
本文介绍了链表的概念和特性，并用C++实现了单链表。文章来源地址https://www.toymoban.com/news/detail-840923.html
到了这里，关于链表 Linked List的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
