前言
顺序存储结构的缺点：① 插入、删除操作需要移动大量的元素。 ② 预先分配空间需按最大空间分配，利用不充分。 ③ 表容量扩充十分不方便（可能会产生效率问题）。
而链式存储结构恰好弥补了顺序存储这些缺陷。
1.认识线性表链式存储
1.1线性表链式存储的构成
① 可用一组任意地址的存储单元存储线性表的数据元素。② 每个数据元素，除存储本身信息外，还需存储其直接（相邻）关系元素的存储地址 (指针)。 ③ 利用指针实现了逻辑上相邻的元素可以用不相邻的存储单元存放（顺序存储就是相邻存储单元）。④ 利用指针对指向的元素进行访问与操作。
数据域：元素本身信息。指针域（1个或多个）：指向具有直接关系元素的指针。
链式存储结构可看作由一个（或多个）定位指针 + 数个结点构成的一种数据结构。下图以单链表为例
每个结点中只含一个指针域的链表叫单链表。 单链表中每个结点的的指针域存放其直接后继结点的指针（存储地址）。 开始结点无前趋，故应设头指针head指向开始结点。 同时，由于终端结点无后继，故终端结点的指针域为空， 即null（图示中用^表示)。
1.2头结点
在第一个结点之前虚加一个 “头结点”，以指向头结点的指针为链表的头指针。其不表示真正元素的数据，只用于存放第一个结点的地址。 头结点指针域为空表示线性表为空。头结点类似于火车头，由头指针指向头结点，这样每次数据访问便从头结点开始访问，使得访问“有迹可循”。
1.3链式存储结构优缺点
优点： ① 任何操作都不需要移动结点，只要修改指针即可。适合做插入或删除操作。②不需预先分配空间。
缺点： ①不能随机存取，查找速度慢。 ② 指针占用额外存储空间。
2.线性表链式存储操作原理
基本操作：
（1）初始化InitList(&L)---创建一个新的空表
（2）销毁DestroyList(&L)---存在->不存在
（3）置空表ClearList(&L)---线性表->空集
（4）求长度ListLength(L)
（5）取元素GetElem(L ,position)---按序号查找
（6）定位函数LocateElem(L, x)---找出第一个与x相同值的位置
（7）插入ListInsert(&L, position, x)
（8）删除ListDelete(&L, position)
2.1初始化
#include<stdio.h>
using namespace std;
struct LNode{
int data; //数据域
LNode *next; //指针域
};
int main()
{
LNode *L; //创建头指针
L=new LNode; //将头指针指向新开的LNode地址，即头指针指向头结点
L->next=NULL;//将头结点的next指向NULL，至此完成头指针和头结点创建
}2.2求长度
求表长：从第一个元素开始逐个计数，直到最后一个指针域为空时，计数结束。
在链表中，头指针应始终指向头结点以保持链表访问稳定。因此在对链表进行操作时，应新建一个指针p，指向头指针指向的头结点，通过指针p来对链表访问与操作。我们用 “ p=p->next ” 进行遍历操作：将p指向头结点，进行条件判断（p->next是否为空）是否执行遍历操作。
LNode *p=L;
while(p->next!=NULL)
{
p=p->next;
}2.3取元素和找元素位置
运用p=p->next语句可完成查询，但需注意的是：不论位置position值“ i ”为多少，都必须从第1个结点开始起“点数”， 直数到第 i 个为止。
当 i 大于表长时，p后移若干个结点后就可能指空。这时，应该停止p的遍历过程。因此在循环中需要判断是否已经遍历到表尾。那么有两种情况导致循环的退出：1、找到第i个结点；2、i不在有效范围内。做链表的操作最好能自主画图深入理解。
2.4插入元素
如何创建新结点存储信息？
LNode *temp = new LNode;
temp->data = WhatYouGet;
temp->next = NULL;如何插入这个新结点在所选位置？①指针p指向位置前一个的结点，②新结点的next指针域指向p的next指针域 指向 的地址，③最后更新p的next指针域，使其指向新结点。
LNode *p = The_Front_Point;
指针p指向前一个结点
temp->next = p->next;
新结点的next指针域 指向 p的next指针域指向的地址
p->next = temp;
更新p的next指针域，使其指向新结点2.5删除元素
①指针p指向删除结点前一个的结点，创建一个新结点用于指向删除结点，②新结点指向p的next指针域 指向 的地址，③最后更新p的next指针域，使其指向新结点next指向的地址。最后delete新结点
LNode *p = The_Del_Front_Point;
LNode *del;
del = p->next;
p->next = del->next;
delete del;3.线性表链式存储操作实现
ps：算法代码以头指针、头结点、单链表为例
typedef int ElemType;
struct LNode{
ElemType data;
LNode *next;
};
typedef LNode* LinkList;
//1. 初始化链表
bool InitList( LinkList &L )
{
if( L!=NULL)
return false;
L = new LNode; //生成头结点
L->next = NULL; //头结点next指向NULL
return true;
}
//2. 销毁表
bool DestroyList( LinkList &L )
{
if(L->next!=NULL)
{
cout<<"请先执行清空表操作";
return false;
}
delete L;
return true;
}
//3. 清空表
bool ClearList( LinkList &L )
{
LNode *p=L->next;
LNode *del;
while(p)
{
del=p;
p=p->next;
delete del;
}
return true;
}
//4. 求表长
int ListLength_L( const LinkList &L )
{
LNode *p=L;
int count=0;
for(p=L; p->next!=NULL; p=p->next)
{
++count;
}
return count;
}
//5. 取表中第i个元素
bool GetElem_L( const LinkList &L , int i , ElemType &e )
{
if(i<=0)
return false;
LNode* p=L;
while(i!=0 || p)
{
--i;
p=p->next;
}
if(i>0)
{
cout<<"输入位置大于表长";
return false;
}
e=p->data;
return true;
}
//6. 定位函数,找出表中第一个与e相等的元素，并返回这个结点,如果没有找到,可返回NULL
LNode* LocateElem( const LinkList &L , ElemType e )
{
LNode *p=L->next;
while(p->data!=e)
{
p=p->next;
}
if(p)
return p;
return NULL;//实现时根据需要修改返回值,如果不存在该结点,返回NULL,否则返回结点指针
}
//7. 在第i个位置插入元素e
bool ListInsert( LinkList &L , int i , ElemType e )
{
LNode *p;
p=L;
int j=0;
while(p && j<i-1)
{
p=p->next;
}
if(!p || j>i-1) return false;
LNode *n=new LNode;
n->data=e;
n->next=p->next;
p->next=n;
return true;
}
//7.1 头插法
bool ListInsert_Head( LinkList &L , ElemType e)
{
LNode *p=L;
LNode *n=new LNode;
n->data=e;
n->next=p->next;
p->next=n;
return true;
}
//8. 删除表中第i个元素,并在主程序用“ElemType e”接收该元素的值
bool ListDelete( LinkList &L , int i , ElemType &e )
{
if(i<=0)
{
cout<<"请输入正确的位置（大于或等于1）";
return false;
}
LNode* p=L;
LNode* del;
--i;
while(i!=0 && p)
{
p=p->next;
--i;
}
if(i>0)
{
cout<<"输入位置大于表长";
return false;
}
del=p->next;
e=del->data;
p->next=del->next;
delete del;
return true;
}