0.引言
链表是一种相对简单的数据结构，但衍生种类繁多，并且在某些方面举足轻重。
关于链表的内容回分多篇文章简要介绍，此文仅介绍单链表。
和所有数据结构一样，最基础的部分无非是建立、增、删、改、查、遍历。
（本文以带头结点的链表为例）
1.建立
01.定义链表的结点
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode* next;//指向下一个节点
}LNode,*LinkList;02.建立链表
（1）头插法建立链表
不妨设输入9999为结束
LinkList CreateList1(LinkList &L)//头插法新建链表
{
LNode* s;
int x;
L = (LinkList)malloc(sizeof(LNode));//带头结点的链表
L->next = NULL;//L->data里面没放东西
scanf("%d", &x);//从标准输入读取数据
//3 4 5 6 7 9999
while (x != 9999)
{
s = (LNode*)malloc(sizeof(LNode));//申请一个空间，强制类型转换
s->data = x;//把读取到的值，给新空间中的data成员
s->next = L->next;//让新结点的next指针指向链表的第一个元素
L->next = s;//让s作为第一个元素
scanf("%d", &x);//读取标准输入
}
return L;
}（2）尾插法建立链表
LinkList CreateList2(LinkList& L)//尾插法新建链表
{
int x;
L = (LinkList)malloc(sizeof(LNode));//带头节点的链表
LNode* s, * r = L;//LinkList s,r=L;也可以，r代表链表表尾结点，指向链表尾部
//3 4 5 6 7 9999
scanf("%d", &x);
while (x!=9999)
{
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
r->next = s;//让尾部指向新节点
r = s;//r指向新的表尾结点
scanf("%d", &x);
}
r->next = NULL;
return L;
}03.初始化链表
（1）带头结点
bool InitList(LinkList& L)
{
L = (LNode*)malloc(sizeof(LNode));//分配一个头结点
if (L == NULL) //内存不足，分配失败
{
return false;
}
L->next = NULL; //头结点之后暂时还没有结点
return true;
}（2）不带头结点
//不带头结点
bool InitList(LinkList& L)
{
L = NULL;//空表，暂时还没有任何结点
return true;
}
2.增：插入元素
01.按位序插入
（1）带头结点
//按位序插入
bool ListFrontInsert(LinkList L, int i, ElemType e)//往第i个位置插入元素
{
if (i < 1)
{
return false;
}
LinkList p = GetElem(L, i - 1);//拿到要插入位置的前一个位置的地址值
if (NULL == p)
{
return false;//i不对
}
LinkList s = (LNode*)malloc(sizeof(LNode));//为新插入的结点申请空间
s->data = e;//要插入的值放入空间
s->next = p->next;//插入的步骤
p->next = s;
return true;
}（2）不带头结点
//按位序插入
bool ListInsert(LinkList& L, int i, ElemType e)
{
if (i < 1)
{
return false;
}
if (i == 1)//插入第一个结点的操作与其它结点操作不同
{
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = L;
L = s;//头指针指向新结点
return true;
}
LNode* p;//指针p指向当前扫描到的结点
int j = 1;//当前p指向的是第几个结点
p = L;//p指向第一个结点（注意：不是头结点）
while (p != NULL && j < i - 1)//循环找到第i-1个结点
{
p = p->next;
j++;
}
if (p == NULL)//i值不合法
{
return false;
}
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return true;//插入成功
}02.后插操作
//后插操作：在p结点之后插入元素e
bool InsertNextNode(LNode* p, ElemType e)
{
if (p == NULL)
{
return false;
}
LNode* s = (LNode*)malloc(sizeof(LNode));
if (s == NULL)//内存分配失败
{
return false;
}
s->data = e;//用结点s保存数据元素e
s->next = p->next;
p->next = s;//将结点s连到p之后
return true;
}03.前插操作
//前插操作：在p结点之前插入元素e
bool InsertPriorNode(LNode* p, ElemType e)
{
if (p == NULL)
{
return false;
}
LNode* s = (LNode*)malloc(sizeof(LNode));
if (s == NULL)//内存分配失败
{
return false;
}
s->next = p->next;
p->next = s;//新结点s连到p之后
s->data = p->data;//将p中元素复制到s中
p->data = e;//p中元素覆盖为e
return true;
}3.删：删除元素
01.按位序删除
bool ListDelete(LinkList L, int i)//删除第i个元素的位置
{
LinkList p = GetElem(L, i - 1);//查找删除位置的前驱结点
if (NULL==p)
{
return false;
}
LinkList q = p->next;
if (NULL==q)
{
return false;
}
p->next = q->next;
free(q);
q = NULL;
return true;
}02.按结点删除
//删除指定结点p
bool DeleteNode(LNode* p)
{
if (p == NULL)
{
return false;
}
LNode* q = p->next;//令q指向*p的后继节点
p->data = p->next->data;//和后继节点交换数据域
p->next = q->next;//将*q结点从链中“断开”
free(q);//释放后继结点的存储空间
return true;
}4.查：查找元素
01.按位序查找
LinkList GetElem(LinkList L, int i)//按序查找元素
{
int j = 1;
LNode* p = L->next;//让p指向第一个结点
if (0==i)
{
return L;//i是零就返回头节点
}
if (i < 1)
{
return NULL;//i是负值就返回空
}
while (p && j < i)
{
p = p->next;//让p指向下一个结点
j++;
}
return p;
}02.按元素查找
LinkList LocateElem(LinkList L, int e)//按值查找元素
{
LinkList p = L->next;
while (p && p->data != e)
{
p = p->next;
}
return p;
}5.检查是否为空
（1）带头结点
bool Empty(LinkList L)
{
if (L->next == NULL)
{
return true;
}
else
{
return false;
}
}（2）不带头结点
//不带头结点
bool Empty(LinkList L)
{
if (L == NULL)
{
return true;
}
else
{
return false;
}
}6.遍历链表并打印
void PrintList(LinkList L)//打印链表
{
L = L->next;
while (L!=NULL)
{
printf("%3d", L->data);//打印当前结点数据
L = L->next;//指向下一个结点
}
printf("\n");
}7.链表长度
int Length(LinkList L)
{
int len = 0;
LNode* p = L;
while (p->next != NULL)
{
p = p->next;
len++;
}
return len;
}附：
1.关于销毁和改
销毁只需遍历链表并free一下即可
关于改，直接访问修改即可。
2.此文代码中语法问题
以上因为书写方便，故使用到布尔类型、引用等C++语法，所以使用以上代码文件名后缀要改为cpp，其余书写与C++几乎无关。
