在数据结构中，根据不同的数据组织方式可以分为四类基本逻辑结构(关系)：集合结构、线性结构、树形结构、图状结构(网状结构);根据存储结构可以分为：顺序存储、离散存储。

链表是以线性结构加上离散存储组成，或者说是线性表的链式存储，是各个对象按照线性顺序排列的数据结构，链表元素的线性顺序是由对象里面的指针域决定的，所以在链式存储中不仅要存数据元素的信息外，还要存储它后一个元素的存储地址来表示来表示每个元素和它之后的下一个元素的逻辑关系。链表为元素集合提供了一种简单灵活的的表示方式，解决了顺序表插入和删除时需要移动大量元素的(下面会讲到)。

把n个数据元素用线性表的链式存储这种数据结构，通常可以表示如图形式

链表可以有多种形式。它可以是单链接的或双链接的，可以是以排序的或是未排序的，可以是循环的或非循环的

链表的操作：

在实现链表的通常情况下会给链表加上一个哨兵节点，来让代码更简单些，哨兵是一个哑对象，其作用只有简化边界条件的处理，哨兵节点位置是在第一个元素结点之前(哨兵结点在插入、删除元素为第一个元素时可以简化操作)。我们把指向第一个结点的存储位置叫做头指针，第一个结点叫做头节点(即哨兵结点)。

1、 创建空链表

2、 链表查找

从链表的第一个元素结点起，判断是否为第i结点，若是则返回该结点的指针，否则查找下一结点,依次类推

3、 链表插入

获取结点ai-1的指针p(ai 之前驱)，然后申请一个q结点，并将其插入p指向的结点之后

4、 链表删除

找到结点ai的前驱，将结点ai删除之

在链表的操作中，插入和删除操作就只是改变了几个指针的指向，时间复杂度都为O(1)，所以越是插入删除操作越频繁的数据集合采用链表的方式存储效率越高。