链表的类模板，构造函数，删除、插入、查找

#include <iostream>
using namespace std;

//节点的定义
template <class AA>
struct Node
{
	AA data;
	Node* next;
};

//类模板的定义
template <class AA>
class LinkList
{
public:
	LinkList() { front = new Node; front->next = NULL; }//无参构造函数
	LinkList(AA a[], int n);                            //含参构造函数，给一个连续的数据，用链表的形式把他储存起来
	~LinkList();                                        //析构函数，针对堆区的new的使用
	void PrintList();                                   //把链表的所有元素输出
	int GetLength();                                    //返回链表的长度
	Node* GetI(int i);
	int Locate(AA x);
	void Insert(int i, AA x);
	AA Delete(int i);
private:
	Node* front;//只有一个私有数据，front头指针，如果空就指向堆区的空，如果有，就指向一个Node，使Node指向a1，保持a1的统一性
};

//构造函数
template <class AA>//头插法插入n-1，n-2....
LinkList<AA>::LinkList(AA a[], int n)
{
	front = new Node*;
	front->next = NULL;//处理头指针
	for (int i = n - 1; i >= 0; i--)
	{
		//建立新节点
		Node<AA>* s = new Node;
		//把数据域写入
		s->data = a[i];
		//前面一个连上
		s->next = front->next;
		//后面一个连上
		front->next = s;
	}
}

//析构函数
template <class AA>
LinkList<AA>::~LinkList()
{
	//初始化工作指针
	while (front)
	{
		Node<AA>* p = front;
		delete front;
		front = p->next;
	}
}

//查找算法
template <class AA>
Node<AA> * LinkList<AA>::GetI(int i)
{
	Node<AA>* p = front->next;
	int j = 1;
	while (p && j != i)
	{
		p = p->next;
		j++;

	}
	return p; 
}

//插入操作
template<class AA>
void LinkList<AA>::Insert(int i, AA x)
{
	//初始化工作指针
	Node<AA>* p = front;
	if (i != 1)p = GetI(i - 1);
	if (p)
	{
		//建立新结点
		Node<AA>* s = new Node<AA>;
		s->data = x;
		s->next = p->next;
		p->next = s;
	}
}

//删除第i个位置上的元素，并且返回
template <class AA>
AA LinkList<AA>::Delete(int i)
{
	Node<AA>* p = front;//创建工作指针
	if (i != 1)p = GetI(i - 1);//把要插入位置前一个的地址保存在p;
	Node<AA>* q = p->next;//这个也是要删除的
	p->next = q->next;
	AA x = q->data;
	delete q;
	return x;

}