关于链表中头指针和头结点的理解

线性表使用顺序（数组）存储时有个弊端，那就是在插入和删除时需要大量的移动数据，这显示是非常消耗时间的，所以可以采用链式存储，即有一个指针域（单链表），来记录下个结点的存储位置（地址），这样在插入和删除结点时只需要修改指针域即可，从而大量减少移动数据所消耗的时间。来看链表的定义：

struct node {
	int data;
	struct node *next;
};

其中有两个元素，data为数据域，用于存储数据，next为指针域，用于存储下个结点的位置（地址）。

       单链表的示意图如下：

                                           
      Head指针为单链表的头指针，单链表L：L既是单链表的名字，也是其头指针。链表中的最后一个结点的指针域定义为空指针(NULL)。
      单链表的定义：当一个序列中只含有指向它的后继结点的链接时，就称该链表为单链表。

[plain] view plain copy

1. struct Node  
2. {  
3.   ElemType data;  
4.   struct Node *next;  
5. };  
6. typedef struct Node LNode;  
7. typedef struct Node *LinkedList;  

那么什么是头指针呢？我们把指向第一个结点的指针称为头指针，那么每次访问链表时都可以从这个头指针依次遍历链表中的每个元素，例如：

struct node first;
struct node *head = &first;

这个head指针就是头指针。
这个头指针的意义在于，在访问链表时，总要知道链表存储在什么位置（从何处开始访问），由于链表的特性（next指针），知道了头指针，那么整个链表的元素都能够被访问，也就是说头指针是必须存在的。示例如下：

[cpp] view plain copy

1. #include <stdio.h>  
2.   
3. struct node {  
4.     int data;  
5.     struct node *next;  
6. };  
7.   
8. int main(void)  
9. {  
10.     struct node *head, first, second;  
11.   
12.     head = &first;  
13.     first.data = 1;  
14.     first.next = &second;  
15.       
16.     second.data = 2;  
17.     second.next = NULL;  
18.       
19.     while (head) {  
20.         printf("%d\n", head->data);  
21.         head = head->next;  
22.     }  
23.     return 0;  
24. }  

需要着重注意的是while那部分（通过头指针遍历完整个链表）。     

单链表有带头结点和不带头结点之分。

       上图为没有头结点的单链表，下图为带有头结点的单链表：

1.单链表的初始化，即建立一个空链表。

[plain] view plain copy

1. //不带头结点的单链表的初始化  
2. void LinkedListInit1(LinkedList L)  
3. {  
4.   L=NULL;  
5. }  
6. //带头结点的单链表的初始化  
7. void LinkedListInit2(LinkedList L)  
8. {  
9.   L=(LNode *)malloc(sizeof(LNode));  
10.   if(L==NULL)  
11.   {  
12.     printf("申请空间失败！");  
13.     exit(0);  
14.   }  
15.   L->next=NULL;  
16. }  

那么什么又是头结点呢？很多时候，会在链表的头部附加一个结点，该结点的数据域可以不存储任何信息，这个结点称为头结点，
头结点的指针域指向第一个结点，例如：

struct node head, first;
head.next = &first;

那么这里的头指针又是谁呢，不在是指向第一个结点的指针，而是指向头结点的指针，例如：

struct node *root = &head;

即root指针才是头指针。示例如下：

[cpp] view plain copy

1. #include <stdio.h>  
2.   
3. struct node {  
4.     int data;  
5.     struct node *next;  
6. };  
7.   
8. int main(void)  
9. {  
10.     struct node *root, head, first, second;  
11.       
12.     root = &head;  
13.     root->data = 0;  
14.     root->next = &first;  
15.       
16.     first.data = 1;  
17.     first.next = &second;  
18.       
19.     second.data = 2;  
20.     second.next = NULL;  
21.       
22.     while (root) {  
23.         printf("%d\n", root->data);  
24.         root = root->next;  
25.     }  
26.       
27.     return 0;  
28. }  

注：在Linux kernel中，定义头结点使用宏LIST_HEAD。