头插法和尾插法建立单链表详解与实现

article/2025/9/30 3:31:57

写在前面：本文使用C语言和C++引用，学C和C++的同学都是可以看懂的，C++毕竟向下兼容C。很详细，一篇能搞懂代码和原理。

先来了解几个简单概念

单链表就是线性表的链式存储；

头结点：单链表在第一个结点之前附加了一个结点，这个结点里面没有存放我们要使用的数据，只是头结点方便我们对链表进行操作而设立的；

头指针：用来标识一个单链表，头指针为NULL的话就是一个空表，本文的头指针就是LinkList L；

头插法：从一个空表开始，生成一个新的结点之后，将这个数据插在头结点和头结点指向的数据（原来的第一个数据）之间，此时这个新结点就变成了第一个数据，简单说就是把数据插入在表头。最终数据是倒序输出来的；

尾插法：也就是把数据从表尾插入进去，最后数据是你怎么输入的他就怎么输出；

头插法过程：申请好空间，输入我们要插入的数据之后，我们申请的新的结点的指针(s->next)指向后一个数据的空间（L->next）,头部的指针（L->next）指向新生成的空间(s)，就这么简单！

第一步：先创建结构体，结构体里面一个存放数据的变量，一个存放指向下一个元素的指针的变量

/*：第一步：定义结构体*/
typedef int ElemType;//可随时修改数据的类型
typedef struct LNode {ElemType data;struct LNode* next;
}LNode,*LinkList;

第二步：创建变量和初始化

/*第二步：创建变量和初始化*/
int main()
{LinkList L;Fore_insert(L);Print_list(L);return 0;
}

第三步：编写头插法函数

/*第三步：头插法*/
LinkList Fore_insert(LinkList &L)
{L = (LinkList)malloc(sizeof(LNode));//申请链表空间，最开始是空链表L->next = NULL;//链表的结构体指针赋值为空int x;//我们要插入的数据LinkList s;scanf("%d", &x);while (x != 9999) {//输入9999就停下了s = (LinkList)malloc(sizeof(LNode));//申请新结点的空间s->data = x;//把x放到结点里面去s->next = L->next;L->next = s;scanf("%d", &x);}return L;
}

尾插法的过程：最开始链表是空的，申请空间之后，r表示链表尾部，链表尾部的结构体指针（r->next）指向新结点的空间(s)，然后链表尾部变成了新空间s，要把r移向链表尾部（r=s），方便对接下来插入的数据进行操作，对于最后一个插入的数据，它的结构体指针要赋值成NULL。

第四步：编写尾插法函数

/*第四步：尾插法*/
LinkList Final_insert(LinkList& L)
{L = (LinkList)malloc(sizeof(LNode));int x;LinkList s;//新结点的指针LinkList r = L;//r指向链表尾部，插入一个数据就要移动到链表尾部哦！scanf("%d", &x);while (x != 9999) {s = (LinkList)malloc(sizeof(LNode));s->data = x;r->next = s;r = s;//r移动到链表尾部scanf("%d", &x);}r->next = NULL;//一定不要忘记把最后一个结点的指针赋值为NULLreturn L;
}

第五步：把结构体打印出来看看

/*第五步：打印结构体数据*/
void Print_list(LinkList L)//注意前面的头插和尾插都是传址调用，这里是传值调用
{L = L->next;//L是头结点，L->next指向第一个数据while (L != NULL) {//遍历到NULL也就是最后一个数据的指针就是NULL，循环结束printf("%d ", L->data);L = L->next;}printf("\n");
}

总的代码在这里：

#include<stdio.h>
#include<stdlib.h>/*：第一步：定义结构体*/
typedef int ElemType;
typedef struct LNode {ElemType data;struct LNode* next;
}LNode,*LinkList;/*第三步：头插法*/
LinkList Fore_insert(LinkList &L)
{L = (LinkList)malloc(sizeof(LNode));L->next = NULL;int x;LinkList s;scanf("%d", &x);while (x != 9999) {s = (LinkList)malloc(sizeof(LNode));s->data = x;s->next = L->next;L->next = s;scanf("%d", &x);}return L;
}/*第四步：尾插法*/
LinkList Final_insert(LinkList& L)
{L = (LinkList)malloc(sizeof(LNode));int x;LinkList s;LinkList r = L;scanf("%d", &x);while (x != 9999) {s = (LinkList)malloc(sizeof(LNode));s->data = x;r->next = s;r = s;scanf("%d", &x);}r->next = NULL;//一定不要忘记把最后一个结点的指针赋值为NULLreturn L;
}/*第五步：打印结构体数据*/
void Print_list(LinkList L)
{L = L->next;//L是头结点，L->next指向第一个数据while (L != NULL) {//遍历到NULL也就是最后一个数据的指针就是NULL，循环结束printf("%d ", L->data);L = L->next;}printf("\n");
}/*第二步：创建变量和初始化*/
int main()
{LinkList L;Fore_insert(L);Print_list(L);//Final_insert(L);//Print_list(L);return 0;
}

最后的控制台输出结果如图所示：

头插法结果：