一、链式存储
用一组地址任意的存储单元（地址可以连续也可以不连续），依次存储线性表中的各数据元素。
链式存储结构中的每个存储单元称为“结点”，结点包含一个数据域和一个指针域。
数据元素之间的逻辑关系通过结点中的指针表示
数据域存放数据元素信息；指针域存放后继结点地址。
通常由第一个结点开始，逐一访问所有结点。
具有n个数据元素的线性表对应的n个结点通过链接方式链接成一个链表，即为线性表的链式存储结构。

二、单链表
由于链表中每个链结点中仅包含一个指针域，故称这样的链表为线性链表或单链表。
单链表的结点结构：

单链表的数据类型：

typedef int ElemType; // ElemType数据元素的数据类型
typedef struct LNode  // LNode为结点类型名
{ElemType data;      // data代表数据元素struct LNode *next; // next为指向下一结点的指针
} LinkNode;  

单链表结构有两种，一种是不带头节点的，一种是带头节点的：
不带头节点的：

带头节点的：

头节点和头指针的区别：
如上两个带头节点和不带头节点的图，头指针是指向单链表的第一个节点，不管单链表有没有头节点，头指针都指向第一节点，所以，单链表必有一个头指针，而头节点不一定有。

单链表增加一个头结点的优点如下：
第一个结点的操作和表中其他结点的操作相一致，无需进行特殊处理；
无论链表是否为空，都有一个头结点，因此空表和非空表的处理也就统一了。

三、单链表的基本操作：
如上图：p、q为指向任意结点的指针
判断单链表为空：
头指针的下一个节点为空时，则这个单链表为空

head->next == NULL; 

到达单链表的尾部：

p->next == NULL

指针后移：

p = p->next

结点点之间的连接：

p = p->next

单链表的插入（添加结点）
在任意节点插入（链表的头插法和尾插法都时根据这个原理）
单链表结点的插入是利用修改结点指针域的值，使其指向新的链接位置来完成插入操作，无需移动任何元素。
假定在链表中指定结点之前插入一个新结点，要完成这种插入必须首先找到所插位置的前一个结点，再进行插入。假设指针 p 指向待插位置的前驱结点，指针 t 指向新结点。

注意：②③的顺序不能交换，先②再到③。
代码：

bool ListInsert(LinkNode *L, int pos, ElemType item)
{ LinkNode *p = L;  int i = 0;while (p && i != pos - 1)  { // 查找pos的前驱p = p->next;    i++;}if (p == NULL)  // 查找不成功，退出运行{ cout << "插入位置无效" << endl;return false;}LinkNode *t = new LinkNode;t->data = item;    //①t->next = p->next; //②p->next = t;       //③return true;
}

单链表的删除
首先找到被删除位置的前一个结点，并用指针 p 指向删除位置的前驱结点，指针 t 指向被删除的结点；
将指针p所指结点的指针域修改为t所指结点的后继；
释放被删结点t，即delete t

单链表的查找
获取单链表中指定位置上的数据元素

// L为指向单链表的头指针
bool Find_pos(LinkNode *L, int pos, ElemType &item)
{ LinkNode *p = L->next;int i = 1; // 结点位序while (p && i != pos){ p = p->next;i++;}if (p == NULL)  // 查找不成功，退出运行{ cout << "位置无效" << endl;return false;}item = p->data;return true;
}

撤销单链表

// L为指向单链表的头指针
void DestroyList(LinkNode *&L)
{ LinkNode *p;while (L)  {p = L;   L = L->next;  // 使用L指针保存下一结点的位置delete p;  //删除节点}
}

链式存储结构的特点
优点：
不需占用连续存储空间，使用链表前不用事先估计存储空间大小。
插入和删除操作时，不需要移动大量元素。
缺点：
操作算法较复杂。
不能随机存取。
需要额外空间来表示元素间的关系，空间代价较高。