一、链表内容简介
本篇文章主要介绍单链表，熟练掌握单链表之后，对循环链表、双向链表等稍加学习便能理解了。单链表也是数据结构的地基，直接影响到了后续对树、图等的学习。
链表其实就是线性表的链式存储结构，其特点如下：
逻辑相邻的元素，物理存储上不要求相邻
利用指针实现了元素逻辑相邻
每个元素除了存储本身数据外，还需存储其直接后继的地址
直接上代码，给出结点的存储表示和链表的封装：
//链表结点
template <class T>//类模板，T为任意数据类型
struct Node
{
T data;//数据域
Node<T>* next;//指针域，指向下一个元素
};
//链表的封装，创建一个模板类
template <class T>
class LinkList
{
private:
Node<T>* head;//链表的头结点，在单链表第一个结点前附设的结点, 能简化链表增删查改等操作的实现。
int m_length;//链表元素个数
};下图直观地表示了链表：
二、单链表基本操作?
在此只介绍插入和删除操作，其它具体的操作参见文章最后的代码。
1.单链表的插入
假设在结点p后面插入新结点s，其操作如下图所示：
?主要操作是修改p和s的指针域，即s的指针域指向p的下一个元素，p的指针域指向s。此处必须得注意先执行s->next = p->next;再执行p->next = s;如果调换顺序的话会造成p的下一个结点丢失。
2.单链表的删除
假设删除结点p的后继结点，其操作如下图所示：
?不难发现，删除操作是将p的指针域指向p的后继元素的后继元素，即p->next = p->next->next;，但这样写会造成内存泄漏，删除之后我们应该释放被删除结点的空间，则应该用q结点保存p的后继元素，再执行p->next = q->next;操作，最后释放被删除结点即delete q。
3.具体代码
//链表结点
template <class T>//类模板，T为任意数据类型
struct Node
{
T data;//数据域
Node<T>* next;//指针域，指向下一个元素
};
//链表的封装，创建一个模板类
template<class T>
class LinkList
{
private:
Node<T> *head;//链表头结点
int m_length;//链表当前长度
public:
//构造函数
LinkList()
{//初始化单链表，构造一个空表
m_length = 0;//初始长度置0
head = new Node<T>;//为头结点分配内存空间
head->next = NULL;//头结点指针域置空
}
//析构函数
~LinkList()
{//销毁单链表
Node<T> *p = head;
while(head)
{
head = p->next;
delete p;
p = head;
}
}
//返回链表长度
int getLength()
{
return m_length;
}
//遍历单链表，在此做简单打印操作
void print()
{
Node<T> *p = head->next;
while(p)
{
cout << p->data << "->";
p = p->next;
}
cout << endl;
}
//单链表的取值
void getElem(int i, T &e)
{//根据序号i获取元素的值，保存到e中
//p指向首元结点，计数器j赋值为0
Node<T> *p = head->next;
int j = 1;
//顺序向后扫描，直到p为空或p指向第i个元素退出循环
while(p && j < i)
{
p = p->next;
j++;
}
//判断i值是否合法
if(!p || j > i) //i>n或者i<1非法
{
cout << "LinkList::getElem()调用失败，获取值位置不合法。" << endl;
exit(-1);
}
e = p->data;//取值
}
//单链表的按值查找，返回结点地址，若不存在则返回空指针
Node<T>* locateElem(T e)
{
Node<T> *p = head->next;
while(p && p->data != e)
{
p = p->next;
}
return p;
}
//单链表的插入，在第i个位置插入值为e的新结点
void insertElem(int i, T e)
{
Node<T> *p = head;//p指向头结点
int j = 0;//计数器赋初值为0
while(p && j < i - 1)//循环结束后p的后面即为插入位置
{
p = p->next;
j++;
}
if(!p || j > i - 1)//i>n+1或者i<1位置非法
{
cout << "LinkList::insertElem()调用失败，插入位置不合法。" << endl;
exit(-1);
}
Node<T> *s = new Node<T>;//申请新结点s
s->data = e;//将传入的e赋值给s的数据域
s->next = p->next;//s的指针域指向p的后继元素
p->next = s;//p的指针域指向s
m_length++;//长度加1
}
//单链表的删除，删除第i个位置的元素
void deleteElem(int i)
{
Node<T> *p = head;
int j = 0;
while(p->next && j < i - 1)//循环结束后p的后继元素即为待删除结点
{
p = p->next;
j++;
}
if(!(p->next) || j > i - 1)//i>n或者i<1时位置非法
{
cout << "LinkList::deleteElem()调用失败，删除值位置不合法。" << endl;
exit(-1);
}
Node<T> *q = p->next;//q指向待删除结点
p->next = q->next;//修改指针便删除了该结点
delete q;//释放空间
m_length--;//长度减1
}
//使用头插法插入n个元素建立单链表
void create_H(int n)
{
Node<T> *p;
head->next = NULL;
for(int i = 0; i < n; i++)
{
p = new Node<T>;
cin >> p->data;
p->next = head->next;
head->next = p;
}
}
//使用尾插法插入n个元素创建单链表
void create_R(int n)
{
head->next = NULL;
Node<T> *p, *r;
r = head;
for(int i = 0; i < n; i++)
{
p = new Node<T>;
cin >> p->data;
p->next = NULL;
r->next = p;
r = p;r始终指向链表中最后一个元素
}
}
};感谢大家的观看，如有错误或者令你不解的地方可以评论区讨论，我都会一一回复的。后续会一直更新数据结构方面的内容。