[数据结构与算法]DataStruct单链表的基本操作

什么是单链表？

单链表(Linked List):由各个内存结构通过一个next指针链接在一起组成，每一个内存结构都存在后继内存结构(链尾除外)，内存结构由数据域和next指针域组成。

Data 数据 + Next 指针，组成一个单链表的内存结构；第一个内存结构称为 链头，最后一个内存结构称为 链尾；链尾的 Next 指针设置为 NULL （指向空）；单链表的方向单一（只能从链头一直遍历到链尾）

单链表的基本操作

单链表的结构体定义

typedef int DataType;
typedef struct ListNode
{
	DataType data;
	struct ListNode* next;
}ListNode;

创建节点

//动态申请一个节点，赋值X
ListNode* BuyListNode(DataType x) {
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	assert(node);//使用断言检测空间申请失败与否，一搬不会失败，当代计算机的内存足够大几百行的代码一般不会申请失败
	node->data = x;
	node->next = NULL;
	return node;//返回此节点的地址
}

打印链表

//定义一个ListNode型的指针来遍历打印Data值
void ListPrint(ListNode* head) {
	ListNode* cur = head;
	while (cur) {//当cur走到链表尾时判出
		printf("%d--->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

为什么要使用二级指针？

单链表尾插
ATTENTION:此处函数的参数传了一个二级指针

如图，如果我们不修改head指针的指向时，使用一级指针，可如果我们想修改head的指向时就要使用二级指针，与普通变量类似，若要修改普通变量的值，则需要传入变量的地址，若只是使用变量则传值即可。同理，若要修改head的指向，则需要传入二级指针，若使用一级指针，则只能修改所对应的内存块中的值，却无法修改指针本身的值即指针指向的是哪个内存块。
函数中传递指针，在函数中改变指针的值，就是在改变实参中的数据信息。但是这里改变指针的值实际是指改变指针指向地址的值，因为传递指针就是把指针指向变量的地址传递过来，而不是像值传递一样只是传进来一个实参的拷贝。所以当我们改变指针的值时，实参也改变了。

void ListPushBack(ListNode** head, DataType x) {
	assert(head);//检测head是否存在
	if (*head == NULL) {//如果链表为空直接申请一个节点地址赋给*head
		*head = BuyListNode(x);
	}
	else {
		ListNode* cur = *head;
		while (cur->next) {//遍历找到尾节点
			cur = cur->next;
		}
		cur->next= BuyListNode(x);
	}
}

单链表尾删

void ListPopBack(ListNode** head) {
	assert(head);
	if (*head == NULL) {//链表为空
		return;
	}
	else {
		if ((*head)->next==NULL ) {//只有一个节点时
			*head= NULL;//让头节点指向NULL
			free(*head);
		}
		else {
			ListNode* cur = *head;//cur来遍历，prev储存cur前一个节点的地址
			ListNode* prev = NULL;
			while (cur->next) {//cur走到最后一个节点时判出
				prev = cur;
				cur = cur->next;
			}
			prev->next = NULL;
			free(cur);
		}
	}
}

** 单链表头插**

void ListPushFront(ListNode** head, DataType x) {
	assert(head);
	if (NULL == *head) {//如果链表为空，直接申请一个新节点给head
		*head = BuyListNode(x);
	}
	else {
		ListNode* cur = BuyListNode(x);//申请新节点
		cur->next = *head;//让新节点成为头
		*head = cur;
	}
}

单链表头删

void ListPopFront(ListNode** head) {
	assert(head);
	if (*head == NULL) {//如果链表为空则删除不了
		return;
	}
		else {
			ListNode* cur = *head;//让head指向它的下一个节点
			*head = (*head)->next;
			free(cur);
		}
}

单链表查找

ListNode* ListFind(ListNode* head, DataType x) {
	assert(head);
	if (head == NULL) {
		return NULL;
	}
	else {
		ListNode* cur = head;
		while (cur) {
			if (cur->data == x) {
				return cur;
			}
			cur = cur->next;
		}
		return NULL;
	}
}

单链表在pos之后插入值

void ListInsertAfter(ListNode** pos, DataType x) {
	assert(pos);
	if (pos == NULL) {
		return;
	}
	ListNode* node = BuyListNode(x);
	node->next = (*pos)->next;//申请一个节点指向pos->next，再让pos指向它
	(*pos)->next = node;
}

单链表删除pos之后的值

void ListEraseAfter(ListNode** pos) {
	assert(pos);
	if (*pos == NULL) {
		return;
	}
	else {
		if ((*pos)->next == NULL) {//如果是尾节点则删不了
			return;
		}
		ListNode* node = (*pos)->next;
		(*pos)->next = node->next;//让pos指向pos的下下个节点
		free(node);
	}
}

单链表销毁
如果不销毁的话会造成内存泄露

void  ListDestory(ListNode** head) {
	assert(head);
	ListNode* cur = *head;//遍历删除并释放空间
	while (cur) {
		*head = cur->next;
		free(cur);
		cur = *head;
	}
	*head = NULL;
}

完整代码

//"singleList.c"
#include<stdio.h>
#include<malloc.h>
#include "List.h"
#include<assert.h>
//动态申请一个节点，赋值X
ListNode* BuyListNode(DataType x) {
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	assert(node);
	node->data = x;
	node->next = NULL;
	return node;
}
// 单链表销毁
void  ListDestory(ListNode** head) {
	assert(head);
	ListNode* cur = *head;//遍历删除并释放空间
	while (cur) {
		*head = cur->next;
		free(cur);
		cur = *head;
	}
	*head = NULL;
}
// 单链表打印
void ListPrint(ListNode* head) {
	
	ListNode* cur = head;
	while (cur) {
		printf("%d--->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
// 单链表尾插
void ListPushBack(ListNode** head, DataType x) {
	assert(head);
	if (*head == NULL) {
		*head = BuyListNode(x);
	}
	else {
		ListNode* cur = *head;
		while (cur->next) {
			cur = cur->next;
		}
		cur->next= BuyListNode(x);
	}
	
}
// 单链表尾删
void ListPopBack(ListNode** head) {
	assert(head);
	if (*head == NULL) {
		return;
	}
	else {
		if ((*head)->next==NULL ) {
			(*head)->next = NULL;
			free(*head);
		}
		else {
			ListNode* cur = *head;
			ListNode* prev = NULL;
			while (cur->next) {
				prev = cur;
				cur = cur->next;
			}
			prev->next = NULL;
			free(cur);
		}
	}
}
// 单链表头插
void ListPushFront(ListNode** head, DataType x) {
	assert(head);
	if (NULL == *head) {
		*head = BuyListNode(x);
	}
	else {
		ListNode* cur = BuyListNode(x);
		cur->next = *head;
		*head = cur;
	}
}
// 单链表头删
void ListPopFront(ListNode** head) {
	assert(head);
	if (*head == NULL) {
		return;
	}
		else {
			ListNode* cur = *head;
			*head = (*head)->next;
			free(cur);
		}
}
// 单链表查找
ListNode* ListFind(ListNode* head, DataType x) {
	assert(head);
	if (head == NULL) {
		return NULL;
	}
	else {
		ListNode* cur = head;
		while (cur) {
			if (cur->data == x) {
				return cur;
			}
			cur = cur->next;
		}
		return NULL;
	}
}
// 单链表在pos之后插入值
void ListInsertAfter(ListNode** pos, DataType x) {
	assert(pos);
	if (pos == NULL) {
		return;
	}
	ListNode* node = BuyListNode(x);
	node->next = (*pos)->next;
	(*pos)->next = node;
}
// 单链表删除pos之后的值
void ListEraseAfter(ListNode** pos) {
	assert(pos);
	if (*pos == NULL) {
		return;
	}
	else {
		if ((*pos)->next == NULL) {
			return;
		}
		ListNode* node = (*pos)->next;
		(*pos)->next = node->next;
		free(node);
	}
}
void test() {
	ListNode* head = NULL;
	ListPushBack(&head, 1);//尾插
	ListPushBack(&head, 2);
	ListPushBack(&head, 3);
	ListPushBack(&head, 4);
	ListPushBack(&head, 5);
	ListPushBack(&head, 6);
	ListPrint(head);
	ListPopBack(&head);//尾删
	ListPrint(head);
	ListPushFront(&head, 0);//头插
	ListPrint(head);
	ListPopFront(&head);//头删
	ListPrint(head);
	ListPrint(ListFind(head, 5));//查找结点
	ListNode* pos = ListFind(head, 5);
	ListInsertAfter(&pos, 6);//pos位置之后插入
	ListPrint(head);
	ListEraseAfter(&pos);//删除pos之后的值
	ListPrint(head);
	ListDestory(&head);//销毁链表
	ListPrint(head);
}

//"main.c"
#include "List.h"
int main() {
	test();
	return 0;
}

//"List.h"
typedef int DataType;
typedef struct ListNode
{
	DataType data;
	struct ListNode* next;
}ListNode;

// 创建结点.
ListNode* BuyListNode();
// 单链表销毁
void ListDestory(ListNode** pHead);
// 单链表打印
void ListPrint(ListNode* pHead);
// 单链表尾插
void ListPushBack(ListNode** pHead, DataType x);
// 单链表尾删
void ListPopBack(ListNode** pHead);
// 单链表头插
void ListPushFront(ListNode** pHead, DataType x);
// 单链表头删
void ListPopFront(ListNode** pHead);
// 单链表查找
ListNode* ListFind(ListNode* pHead, DataType x);
// 单链表在pos之后插入值
void ListInsertAfter(ListNode** pos, DataType x);
// 单链表删除pos之后的值
void ListEraseAfter(ListNode** pos);
void test();

测试结果

void test() {
	ListNode* head = NULL;
	ListPushBack(&head, 1);//尾插
	ListPushBack(&head, 2);
	ListPushBack(&head, 3);
	ListPushBack(&head, 4);
	ListPushBack(&head, 5);
	ListPushBack(&head, 6);
	ListPrint(head);
	ListPopBack(&head);//尾删
	ListPrint(head);
	ListPushFront(&head, 0);//头插
	ListPrint(head);
	ListPopFront(&head);//头删
	ListPrint(head);
	ListPrint(ListFind(head, 5));//查找结点
	ListNode* pos = ListFind(head, 5);
	ListInsertAfter(&pos, 6);//pos位置之后插入
	ListPrint(head);
	ListEraseAfter(&pos);//删除pos之后的值
	ListPrint(head);
	ListDestory(&head);//销毁链表
	ListPrint(head);
}