头插法建立链表详解

头插法就是建立一个头节点，进行初始化定义，next存储下一个节点位置的地址，初始化定义指针域为空，表示该头部节点后面指向任何位置的地址，开始时只有一个头部节点。

head -> next = NULL;

图形化表示为

申请一个新节点A1,将A1按照头插法插入到head节点的后面，实现代码为

p -> next = head -> next;
head -> next = p;

p -> next表示p后面指向的地址，将该地址赋值给为头部节点的所指向的下一个节点，也就是空节点(head->next初始化为NULL)

也就是相当于p->next = head -> next =NULL

head -> next 表示头部节点指向的下一个节点，为p，表示head的下一个节点为p, p的下一个节点为空

图像化表示为(该节点用A1表示)

当继续采用头插法插入节点A2时，依旧执行代码

p -> next = head -> next;
head -> next = p;

在此时各个节点的对应情况为

p -> next = head -> next = p(A1) 也就是说A2 后面对应的是节点A1

head -> next = p(A2) 头节点后面对应的节点是A2

图像化表示为

新来的A2破坏了原本head和A1之间的关系，并且建立了新联系

后面的操作过程就是不断地重复上诉过程，把头节点和新插入的节点之间建立联系，新插入的节点和上一个插入的节点之间建立联系，最终实现一个完整的链表

c语言代码实现如下

#include <stdio.h>
#include <stdlib.h>

typedef int Elemtype;
//结构体的定义
typedef struct{
    Elemtype data;//数据域，存储数据
    struct LNode *next;//指针域，存储指针,存放后继节点信息
}LNode;
typedef LNode *Linklist;//定义结构体指针型变量，将结构体指针等价于Linklist

//头插法建立链表
void CreateListHead(Linklist *L, int n){//n为创建链表的大小空间
    //Linklist p;//p代表指针，代表地址 *P代表数据
    LNode *p;
    int i;
    (*L) = (LNode *)malloc(sizeof(LNode));//定义申请一个LNode大小的空间，该空间大小可以存储节点域，数据域信息，该地址的初始地址赋值给*L
    (*L)->next = NULL;//开始时，该节点的指针域为空，也就是下一个节点为空，不包含其他节点
    for(i = 0; i < n; i ++){//定义含有i个空间大小的空间
        p = (LNode *)malloc(sizeof(LNode));//申请足够大小的空间，将该空间的基地址赋值给p
        p->data = i;//在数据域中存储数据
        p->next = (*L)->next;
        (*L)->next = p;//重新定义头指针的下一个，为当前的开始位置


    }

}
//链表的遍历输出
void TraverseList(Linklist *L){
    LNode *p, *q;
    p = *L;//将头指针赋值给p
    while(p->next != NULL){
        q = p->next;
        printf("%d", q->data);
        p = p->next;
    }
}
int main()
{
    LNode *L;
    CreateListHead(&L, 5);
    TraverseList(&L);
    return 0;
}