头插法和尾插法建立单链表详解与实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了头插法和尾插法建立单链表详解与实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

写在前面：本文使用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;//一定不要忘记把最后一个结点的指针赋值为NULL
	return 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;//一定不要忘记把最后一个结点的指针赋值为NULL
	return 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;
}

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

头插法结果：

头插法创建单链表并输出,数据结构,链表