（详解）数据结构线性表的创建——前插法、后插法_线性表的后插入

目录

引言

一、结点的定义

二、前插法（头插法）创建单链表

1.步骤：

2.算法描述：

3.时间复杂度：

三、后插法（尾插法）创建单链表

1.步骤：

2.算法描述：

3.时间复杂度：

---

引言

        前插法与后插法属于链表的创建方法。

        链表的创建与顺序表不同，链表是一种动态结构。整个可用存储空间可以为多个 链表共同享用，每个链表不需要像顺序表那样提前分配好占用空间，而是由系统按照需求即使生成。

        即从空表的初始化后，依次建立各元素结点，并逐个插入链表。

---

一、结点的定义

        在创建链表之前，需要自定义结点类型。

typedef struct
{
	char data;
	struct node* next;
}LinkList;

---

二、前插法（头插法）创建单链表

        前插法（头插法）是通过将新结点逐个插入链表的头部（头结点之后）来创建链表，每次申请一个新结点，读入相应的数据元素值，然后将新结点插入到头结点之后。

1.步骤：

1. 创建一个只有头结点的空链表。
2. 根据带创建链表包括的元素个数n，循环n次执行以下操作：

• 生成一个新结点*p；
• 输入元素值赋给新结点*p的数据域；
• 将新结点*p插入到头结点之后。

2.算法描述：

 
void CreateList_H(LinkList $L, int n) {
	//逆位序输入n个元素的值，建立代表头结点的单链表L
	L = new LNode;
	L->next = NULL;	//先建立一个带头结点的空链表
	for (i = 0; i < n; i++) {
		p = new LNode;	//生成新结点*P
		cin >> p->data;	//输入元素值赋给新结点*p的数据域
		p->next = L->next; L->next = p;	//将新结点*p插入到头结点之后
	}
}

3.时间复杂度：

        前插法的时间复杂度为O(n)。

---

三、后插法（尾插法）创建单链表

        后插法是通过将新结点逐个插入链表的尾部来创建链表。与前插法一致，每次申请一个新结点，读入相应的数据元素值。除此之外，必须增加一个尾指针，使其始终指向当前链表的尾结点。

1.步骤：

1. 创建一个只有头结点的空链表。
2. 尾指针r初始化，指向头节点。
3. 根据创建链表包括的元素个数n，循环n次执行以下操作：

• 生成一个新结点*p；
• 输入元素值赋给新结点*p的数据域；
• 将新结点*p插入尾结点*r之后；
• 尾指针r指向新的尾结点*p。

2.算法描述：

void CreateList_R(LinkList $L, int n) {
	//正位序输入n个元素的值，建立代表头结点的单链表L
	L = new LNode;
	L->next = NULL;
	r = L;
	for (i = 0; i < n; i++) {
		p = new LNode;	//生成新结点*P
		cin >> p->data;	//输入元素值赋给新结点*p的数据域
		p->next = NULL; r->next = p;	//将新结点*p插入到尾结点*r之后
		r = p;	//r指向新的尾结点*p
	}
}

3.时间复杂度：

        后插法的时间复杂度为O(n)。