单链表的头尾插法详解
单链表头尾插法详解- 头插法构造单链表
- 代码实现
- 头插法过程
- 尾插法构造单链表
- 代码实现
- 尾插法过程
- 单链表头尾插法对比
- 代码实现
- 头插法过程
- 代码实现
- 尾插法过程
#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
typedef int ElemType; // 单链表存储元素的数据类型
// 定义单链表结构体
typedef struct Node(){
ElemType data; // 单链表结点数据域
struct Node *next; // 单链表结点地址域（指向下一个结点）
}*LinkList, Node;头插法构造单链表
代码实现
/*
* 头插法创建单链表(带头结点)
* datas 接收数组，用于赋值链表的结点数据
* len datas数组的长度，便于遍历
*/
LinkList CreateHeadListH(ElemType *datas, int len){
// 创建头结点
LinkList head, new_node;
head = (LinkList)malloc(sizeof(Node));
// head -> data = len; // 可以把链表长度存在头结点的数据域中
head -> next = NULL;
// 分配新节点并用头插法链接起来
for(int i=0;i<len;i++){
new_node = (LinkList)malloc(sizeof(Node));
new_node -> data = datas[i];
new_node -> next = head -> next;
head -> next = new_node;
}
return head;
}头插法过程
头插法往单链表头部插入，假设
datas[] = {2, 4, 6};首先创建头结点
分配第一个新节点时
head 结点的数据域为空 head -> data = NULL, ，地址域为空 head -> next = NULL;
new_code -> data = datas[0]; --> new_code -> data = 2;
new_code -> next = head -> next; --> new_code -> next = NULL;
然后让 head 结点的地址域指向新结点(这里指第一个结点)
head -> next = new_code1;最终形成
分配第二个新结点时
head 结点的数据域为空 head -> data = NULL, ，地址域也为第一个结点的地址 head -> next = new_node1;
new_code -> data = datas[1]; --> new_code -> data = 4;让第二结点的地址域指向第一个结点（此时第一个结点位置存在 head 结点的地址域）
new_code -> next = head -> next; --> new_code -> next = new_code1;
然后让 head 头结点的地址域指向第二个结点的位置
head -> next = new_code2;最终形成
分配第三个新结点后
关键代码
头插法每次插入新结点时都是往头结点处插入。
new_node -> next = head -> next; // 先让新结点地址域指向头结点地址域的结点位置
head -> next = new_node; // 然后让头结点的地址域指向新结点位置如此循环就形成了头插法构造单链表。
尾插法构造单链表
代码实现
/*
* 尾插法创建单链表(带头结点)
* datas 接收数组，用于赋值链表的结点数据
* len datas数组的长度，便于遍历
*/
LinkList CreateHeadListT(ElemType *datas, int len){
// 创建头结点
LinkList head, p, new_node;
head = (LinkList)malloc(sizeof(Node));
head -> next = NULL;
p = head;
// 分配新节点并用尾插法链接起来
for(int i=0;i<len;i++){
new_node = (LinkList)malloc(sizeof(Node));
new_node -> data = datas[i];
new_node -> next = NULL;
p -> next = new_node;
p = new_node;
}
return head;
}尾插法过程
尾插法往单链表尾部插入，还是假设单链表的结点数据分别为。
datas[] = {2, 4, 6};创建头结点跟头插法是一样的我就不重复叙述了。
分配第一个新结点时
head 结点的数据域为空 head -> data = NULL, ，地址域为空 head -> next = NULL; 变量p等于头结点 p = head;。
先让新结点赋值
new_code -> data = datas[0]; --> new_code -> data = 2;
new_code -> next = NULL; --> new_code -> next = NULL后让链表链接起来
p -> next = new_code;
p = new_code;
一开始 p = head 所以让头结点的地址域指向新结点，，后让 p 等于新结点（此时新结点代表第一个结点）。
分配第二个新结点时
head 结点的数据域为空 head -> data = NULL, ，地址域为空 head -> next = new_node1;
此时变量 p 就等于第一个结点，不再等于头结点。
继续让新结点与单链表链接起来
p -> next = new_code;
p = new_code; 让第一个结点的地址域指向新结点(此时新结点代表第二个结点)，让p等于第二个结点。
分配第三个新结点后
关键代码
p -> next = new_code; // 让p的地址域指向新结点
p = new_code; // 然后让p等于新插入进来的结点(一直等于最后一个结点)尾插法每次插入新结点时都是往尾结点处插入。
如此循环就形成了尾插法构造单链表。
单链表头尾插法对比
同样是数据 datas[] = {2, 4, 6, 8}; 但链接的效果是不一致的，思想也不同。
头插法： head --> 8 --> 6 --> 4 --> 2
结点一直往 单链表头部插入，先进入的数据结点链接在末尾端（刚好逆序），有点像栈的特性，先进后出。
尾插法： head --> 2 --> 4 --> 6 --> 8
结点一直往 单链表尾部插入，先进入的数据结点还是在前驱。