---

目录

 

1. 单向链表

---

1. 单向链表

我们都熟悉数组，它作为一个顺序储存方式数据结构为我们的程序设计带来了大量的便利，几乎任何的高级程序设计，算法设计都离不开数组的灵活使用。

但是，数组最大的缺点就是我们的插入和删除时需要移动大量的元素，显然这需要消耗大量的时间。

数组找到指定元素很快，O（1）复杂度就可以，而链表只能是遍历，O(n)的复杂度。

数组是顺序存储的，链表是通过指针实现不连续的存储

相比起数组，链表解决了数组不方便移动，插入，删除元素的弊端，但相应的，链表付出了更加大的内存牺牲换来的这些功能的实现。

链表的基本思维是，利用结构体的设置，额外开辟出一份内存空间去作指针，它总是指向下一个结点，一个个结点通过NEXT指针相互练习，串联，这就形成了我们的链表。

单链表结构：

几种常见的链表结构：

对于链表、队列、栈、树的实现，指针 指来指去的，必须要自己画图来理解，注意节点指针的顺序

使用c语言的结构体定义单链表的节点

1. 首先定义节点类型

// 定义节点类型
typedef struct Node{
	int data;
	struct Node *next;
}Node, *LinkedList;

LinkedList表示指向Node结点类型的指针类型

 

2. 循环遍历链表的节点，打印输出

由于head 是没有数据的，所以 head = head->next 放在前面

// 打印节点
void printList(LinkedList head){
	while (head->next != NULL){
		head = head->next;
		printf("node is : %d \n", head->data);
	}
}

 

3. 头插入法实现创建链表

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

// 实现单链表的一些操作


// 定义节点类型
typedef struct Node{
	int data;
	struct Node *next;
}Node, *LinkedList;

// 使用头插法插入节点

LinkedList createH(){
	// 创建头节点
	Node *head;
	head = (Node*)malloc(sizeof(Node));
	head->next = NULL;
	// 输入节点
	int da;
	while (scanf_s("%d", &da) != EOF){  // Ctrl+z,可以强行停止输入
		Node *node;
		node = (Node*)malloc(sizeof(Node));
		node->data = da;

		node->next = head->next; // 头部插入节点
		head->next = node;
	}
	return head;
}

// 打印节点
void printList(LinkedList head){
	while (head->next != NULL){
		head = head->next;
		printf("node is : %d \n", head->data);
	}
}


int main(){
	LinkedList head = createH(); 
	printList(head);
}

4. 尾部 插入法  实现链表的 创建

// 从尾部插入节点
LinkedList creatT(){
	Node *head;
	head = (Node*)malloc(sizeof(Node));
	Node *p = head; // 保存head 的值

	int da;
	while (scanf_s("%d", &da) != EOF){
		Node* node = (Node*)malloc(sizeof(Node));
		node->data = da;

		p->next = node;
		p = node;
	}
	p->next = NULL;
	return head;

}

5. 链表的插入操作

链表的增加结点操作主要分为查找到第i个位置，将该位置的next指针修改为指向我们新插入的结点，而新插入的结点next指针指向我们i+1个位置的结点。其操作方式可以设置一个前驱结点，利用循环找到第i个位置，再进行插入。

只需要找到前驱结点【1个节点】

从原来的链表状态

 

到新的链表状态：

// 在指定位置 i 插入 节点
LinkedList insertNode(LinkedList head, int index, int value){
	LinkedList p = head; // 保存头节点数据

	for (int tempi = 1; tempi < index; tempi++){
		p = p->next;
		if (p == NULL) printf("请输入正确的节点位置  \n");

	}
	LinkedList node = (Node*)malloc(sizeof(Node));
	node->data = value;
	
	node->next = p->next;  // 先对后一个指针操作
	p->next = node;
	return head;

}

 

6. 链表的删除操作

删除元素要建立一个前驱结点和一个当前结点【需要找到2 个节点】，当找到了我们需要删除的数据时，直接使用前驱结点跳过要删除的结点指向要删除结点的后一个结点，再将原有的结点通过free函数释放掉。

参考如图

// 删除指定数据的节点：
LinkedList deleteNode(LinkedList head, int value){
	LinkedList pre, p;
	p = head;
	p = head->next;
	pre = p;
	if (p == NULL) return NULL;  // 如果是空链表，则直接退出
	if (p->data == value && p->next==NULL){ // 如果只有 1 个节点，且刚好是要删除的节点
		head->next = NULL;
		return head;
	}

	while (p->data != value){  // 找到 2 个节点
		pre = p;
		p = p->next;
		if (p == NULL){  // 判断边界条件
			printf("找不到指定删除的节点。。。。\n");
			return NULL;
		}
	}
	pre->next = p->next;
	free(p);
	return head;

}

 

完整的实现代码：

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

// 实现单链表的一些操作


// 定义节点类型
typedef struct Node{
	int data;
	struct Node *next;
}Node, *LinkedList;

// 使用头插法插入节点

LinkedList createH(){
	// 创建头节点
	Node *head;
	head = (Node*)malloc(sizeof(Node));
	head->next = NULL;
	// 输入节点
	int da;
	while (scanf_s("%d", &da) != EOF){  // Ctrl+z,可以强行停止输入
		Node *node;
		node = (Node*)malloc(sizeof(Node));
		node->data = da;

		node->next = head->next; // 头部插入节点
		head->next = node;
	}
	return head;
}

// 从尾部插入节点
LinkedList creatT(){
	Node *head;
	head = (Node*)malloc(sizeof(Node));
	Node *p = head; // 保存head 的值

	int da;
	while (scanf_s("%d", &da) != EOF){
		Node* node = (Node*)malloc(sizeof(Node));
		node->data = da;

		p->next = node;
		p = node;
	}
	p->next = NULL;
	return head;

}

// 打印节点
void printList(LinkedList head){
	while (head->next != NULL){
		head = head->next;
		printf("node is : %d \n", head->data);
	}
}

// 在指定位置 i 插入 节点
LinkedList insertNode(LinkedList head, int index, int value){
	LinkedList p = head; // 保存头节点数据

	for (int tempi = 1; tempi < index; tempi++){
		p = p->next;
		if (p == NULL) {
			printf("请输入正确的节点位置  \n");
			return NULL;
		}			
	}
	LinkedList node = (Node*)malloc(sizeof(Node));
	node->data = value;
	
	node->next = p->next;
	p->next = node;
	return head;
}

// 删除指定数据的节点：
LinkedList deleteNode(LinkedList head, int value){
	LinkedList pre, p;
	p = head;
	p = head->next;
	pre = p;
	if (p == NULL) return NULL;  // 如果是空链表，则直接退出
	if (p->data == value && p->next==NULL){ // 如果只有 1 个节点，且刚好是要删除的节点
		head->next = NULL;
		return head;
	}

	while (p->data != value){  // 找到 2 个节点
		pre = p;
		p = p->next;
		if (p == NULL){  // 判断边界条件
			printf("找不到指定删除的节点。。。。\n");
			return NULL;
		}
	}
	pre->next = p->next;
	free(p);
	return head;

}



int main(){
	LinkedList head;
	head = creatT(); // 创建一个链表
	printList(head);

	printf("删除指定节点后： \n");
	head = deleteNode(head, 3);
	printList(head);

	//head = insertNode(head, 3, 100);
	//printf("插入新节点后的链表： \n");
	//printList(head);

}

 

项目推荐：

2000多G的计算机各行业电子资源分享（持续更新）

2020年微信小程序全栈项目之喵喵交友【附课件和源码】

Spring Boot开发小而美的个人博客【附课件和源码】

Java微服务实战296集大型视频-谷粒商城【附代码和课件】

Java开发微服务畅购商城实战【全357集大项目】-附代码和课件

最全最详细数据结构与算法视频-【附课件和源码】