2.3.1 单链表和指针

　　线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素 与其直接后继数据元素 之间的逻辑关系，对数据元素 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。由这两部分信息组成一个"结点"（如下图所示），表示线性表中一个数据元素 。

数据域 data
指针域 next

　　其中存储数据元素信息的域称作数据域（设域名为data），存储直接后继存储位置的域称为指针域（设域名为next）。指针域中存储的信息又称做指针或链。

　　由分别表示,,…, 的N 个结点依次相链构成的链表，称为线性表的链式存储表示，由于此类链表的每个结点中只包含一个指针域，故又称单链表或线性链表，如下图所示。
　

　
 
　　前面已经提到，由于在顺序表中插入或删除一个数据元素，平均约需移动表中一半元素。因此，对于需要经常进行插入和删除操作、表中元素相对不稳定的线性表，不应该采用顺序存储表示，而应该采用链式存储表示。

  思考题 何谓"链式存储表示"？

　　由于链式存储不要求线性表的元素依次"紧挨"存放，因此在进行插入和删除操作改变元素之间的关系时就不需要移动元素，因此它没有顺序存储结构所具有的弱点，但同时也失去了顺序表可随机存取的优点。
　		  
  　　和顺序表类似，在链式存储结构中仍以第一个数据元素的存储地址作为线性表的基地址，通常称它为头指针，线性表中所有数据元素都可以从头指针出发找到。因为线性表的最后一个数据元素没有后继，因此最后一个结点中的"指针"是一个特殊的值 "NULL" （在图上用∧表示），通常称它为"空指针"。
　		   　　头指针的值为第一个结点的存储位置，第一个结点中的"指针"指向第二个结点，即它的值为第二个结点的存储位置，第二个结点中的"指针"指向第三个结点，……，依次类推，直至最后一个结点。  
  　　 为了便于处理一些特殊情况，在第一个结点之前附加一个"头结点"，令该结点中指针域的指针指向第一个元素结点，并令头指针指向头结点，如下图所示。
　

　
   　　头结点的结构和链表中其它结点相同，只是它的数据域中不存放任何信息，但它的指针域存放的是第一个数据元素的存储地址，即线性表的基地址。此时称指向头结点的指针为头指针。通常称这类单链表为"带头结点的单链表"。
　		  
  　　 值得注意的是，若线性表为空，在不带头结点的情况下，头指针为空(NULL)，但在带头结点的情况下，链表的头指针不为空，而是其头结点中指针域的指针为空，如下图所示。
　
  　　如果不特别声明的话，那么以后各节中讨论的单链表都指的是这种带头结点的链表。