链表 Linked List

#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;
};