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;
}
  • 模板，泛型
  • 内部维护链表长度
  • 分别用递归和迭代的方式实现了打印和反转
  • 进行了简单的越界判断处理

双向链表

双向链表

template<class T>
class Node
{
  T data;
  Node* prev;
  Node* next;
};

总结

本文介绍了链表的概念和特性，并用C++实现了单链表。