假设L是LinkList型的变量，则L为单链表的头指针，它指向标中第一个结点。若L为“空”，则所表示的线性表为“空”表，其长度n为“零”。有时，我们在单链表的第一个结点之前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，也可存储如线性表的长度等类的附加信息，头结点的指针域存储指向第一个结点的指针（即第一个元素结点的存储位置）。如图（a）所示，此时，单链表的头指针指向头结点。若线性表为空，则头结点的指针域为“空”，如图（b）所示。

在线性表的顺序存储结构中，由于逻辑上相邻的两个元素在物理位置上紧邻，则每个元素的存储位置都可从线性表的起始位置计算得到。而在单链表中，任何两个元素的存储位置之间没有固定的联系。然而，每个元素的存储位置都包含在其直接前驱结点的信息之中。假设p是指向线性表中第i个数据元素的指针，则P—>next是指向第i+1个数据元素的指针。换句话说，若p—>data=ai，则p—>next—>data=ai+1.由此，在单链表中，取得第i个数据元素必须从头指针出发寻栈，因此，单链表是非随机存取的存储结构。下面看函数GetElem在单链表的实现。

Status GetElem_L(LinkList L,int i,ElemType &e){

//L为带头结点的单链表的头指针。

//当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR

p=L->next;j=1;             //初始化，p指向第一个结点，j为计数器

while (p&&j<1){          //顺指针向后查找，直到p指向第i个元素或p为空

p=p->next;++j;

}

if(!p||j>1)return ERROR;      //第i个元素不存在

e=p->data;                                  //取第i个元素

return OK;

}//GetElem_L

凌阳教育，全国唯一一家原厂式嵌入式培训机构，专业从事嵌入式人才培训13年，最近新开课程信息安全工程师培训，想了解更多嵌入式资料下载或者是凌阳教育的动态，请访问凌阳教育官网www.sunplusedu.com。