数据结构———链表

链表是经常用到的一种基础数据结构，接下来我们讲讲链表。

链表：

特点：

链表可分为有头/无头链表，循环/无环，双向/单向链表，每个链表节点都包含一个数据和下一个链表节点的地址。

每个链表节点都指向下一个链表节点，以达到连接的目的。

接下来我们基于C语言实现一个无头无环单向链表的增删查改功能。

代码实现：

链表数据结构定义：

首先定义链表节点的数据结构，用于后续链表实现：

typedef struct Node {
	int data;
	struct Node* Next;
}Node;

初始化链表节点：

有了链表的数据结构定义，接下来就应该是用值val初始化一个链表节点，并且返回该新节点的地址

Node* GetNewNode(int val) {
	Node* p = (Node*)malloc(sizeof(Node));
	p->data = val;
	p->Next = NULL;
	return p;
}

销毁链表：

由于使用了malloc函数来分配内存空间，所以我们就必须要实现一个函数用于释放分配的内存空间以防止内存泄漏：

void Free(Node *head) {
	if (head == NULL) {
		return;
	}
	for (Node *p = head, *q; p; p = q) {
		q = p->Next;
		free(p);
	}
	return;
}

链表的插入：

有了初始化和销毁链表的函数，那么接下来我们应该实现一个函数用于链表插入

在链表节点插入过程中，我们的操作顺序一定不能错，假设有链表节点D要插入到链表节点B后，第一步，首先将寻找链表节点B的地址，使链表指针指向链表节点B；

第二步，让链表节点D指向链表节点C；

第三步，让链表节点B指向链表节点D；

至此就完成了链表的插入。

对于头部和尾部的插入则更是简单，对于头部插入，只需要将待插入节点指向链表头部即可；

对于尾部插入，只需要将链表尾部指向待插入链表节点即可。

接下来是插入函数的C语言代码：

Node* Insert(Node* head, int pos, int val) {
	if (pos == 0) {
		Node* p = GetNewNode(val);
		p->Next = head;
		return p;
	}
	Node* p = head;
	for (int i = 0; i < pos - 1; i++) {
		p = p->Next;
	}
	Node* q = GetNewNode(val);
	q->Next = p->Next;
	p->Next = q;
	return head;
}

链表的删除：

假设删除某个链表节点B，我们只需要寻找到该链表节点的前一个链表节点A的地址并且保存链表节点B的地址，让链表节点A指向链表节点B的下一个节点，最后释放链表节点B即可。

其中，操作顺序一定不能改变，一定是先将A链表指向的B节点的下一个节点地址，然后释放链表节点B。

Node* Delete(Node* head, int pos) {
	if (pos == 0) {
		return;
	}
	Node* p = head;
	for (int i = 0; i < pos - 1; i++) {
		p = p->Next;
	}
	Node* q = p->Next;
	p->Next = q->Next;
	return head;
}

链表的查找：

假如查找某个特定数值A的链表节点地址，我们只需要顺序遍历一遍链表即可，若找到该链表节点则返回该节点的地址，反之返回一个NULL即可。

int Check(Node* head, int val) {
	Node* p = head;
	int n = 0;
	for (; p; p = p->Next) {
		if (p->data == val) {
			return n;
		}
		n++;
	}
	return NULL;
}

至此，我们就学习完了链表这一基础数据结构。

如果我的文章对你有所帮助，不妨给我个关注何点赞吧