单链表的定义和链式存储的优点

由于顺序表的插入、删除操作需要移动大量的元素，影响了运行效率，由此引入了线性表的链式存储。链式存储线性表时，不需要使用地址连续的存储单元，即它不要求逻辑上相邻的两个元素在物理位置上也相邻，它是通过“链”建立起数据元素之间的逻辑关系，因此，对线性表的插入、删除不需要移动元素，而只需要修改指针。

线性表的链式存储又称为单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立起数据元素之间的线性关系，对每个链表结点，除了存放元素自身的信息之外，还需要存放一个指向其后继的指针。单链表结点结构如图2-2所示，其中，data为数据域，存放数据元素；next为指针域，存放其后继结点的地址。

图2-2  单链表结点结构

单链表中结点类型的描述如下：

typedef struct LNode{  //定义单链表结点类型
    ElemType  data; //数据域
    struct  LNode  *next;  //指针域
}LNode, *LinkList;

利用单链表可以解决顺序表需要大量的连续存储空间的缺点，但是单链表附加指针域，也带来了浪费存储空间的缺点。由于单链表的元素是离散地分布在存储空间中，所以单链表是非随机存取的存储结构。

通常用“头指针”来标识一个单链表，如单链表L，头指针为“NULL”时则表示一个空表。此外，为了操作上的方便，在单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，但可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点，如图2-3所示。

头结点和头指针的区分：不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点链表中的第一个结点，结点内通常不存储信息。 

图2-3  带头结点的单链表

引入头结点后，可以带来两个优点：

• 由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理。
• 无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。