链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。 每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，链表比较方便插入和删除操作。

用一组地址任意的存储单元存放线性表中的数据元素。以元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点。 以“结点的序列”表示线性表,称作线性链表（单链表）。单链表是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。 链表的结点结构:　 ┌──┬──┐──┐ │data│next│ └──┴──┘──┘ data域：存放结点值的数据域 　　 next域：存放结点的直接后继的地址（位置）的指针域（链域）。 注意：①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。 　　 ②每个结点只有一个链域的链表称为单链表（Single Linked List）。 所谓的链表就好像火车车厢一样，从火车头开始，每一节车厢之后都连着后一节车厢。

和数组相比，链表的优势在于长度不受限制，并且在进行插入和删除操作时，不需要移动数据项，故尽管某些操作的时间复杂度与数组想同，实际效率上还是比数组要高很多

劣势在于随机访问，无法像数组那样直接通过下标找到特定的数据项

• 邮箱 ：charon.chui@gmail.com
• Good Luck!