链表操作详解

用户11029129

发布于 2024-06-04 13:02:45

840

发布于 2024-06-04 13:02:45

文章被收录于专栏：编程学习

一、单链表和双向链表基本介绍

（1）什么是单链表

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据 ————百度百科

单链表的访问都是由指针进行访问，不需要扩容，对于数据操作比较快速。

（2）什么是双链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表————百度百科

双链表的访问就比单链表有优势，当数据量比较大时，想要对末尾的节点进行操作需要有个变量把前面节点全都遍历，但是双向链表只需要头节点的前驱就索引到目标了。

二、链表与顺序表比较

顺序表的优点是数据存储是连续的，所以访问数据比较快速，但是要对顺序表元素进行操作，有时候会进行大量数据移动操作，是比较浪费时间的，而且扩容时有风险。

链表的优点是利用碎片化空间，对于数据操作比较快，但是要进行遍历等操作时，速度是比较慢的，当释放内存操作失误很容易内存泄漏。

三、单链表基本操作

（1）单链表结构定义：

typedef int LTDataType;

typedef struct ListNode {
	struct ListNode* next;//后继指针指向下一个节点
	LTDataType data;//数据域存放数据
}LTNode;

（2）单链表初始化：

LTNode* InitNewNode(LTDataType n)
{
	LTNode* p = (LTNode*)malloc(sizeof(LTNode));//开辟新节点
	if (p == NULL)//检查节点是否开辟失败
	{
		perror("malloc");
		exit(-1);
	}
	p->next = NULL;//指针域置空
	p->data = n;//数据域赋值
	return p;//返回新节点
}

（3）单链表头插：

LTNode* LTPushFront(LTNode *head, LTDataType x)
{
	if (head == NULL)
		return NULL;

	LTNode* node = InitNewNode(x);//插入新节点
	node->next = head;//头插

	return node;//返回新的头节点
}

（4）单链表头删：

LTNode* LTPopFront(LTNode* head)
{
	if (head == NULL)
		return NULL;
	if (head->next)//链表节点>1的时候
	{
		LTNode* newhead = head->next;
		free(head);//头删
		return newhead;//返回新头节点
	}
	else//只有头节点的时候
	{
		free(head);
		return NULL;
	}
}

（5）单链表尾插：

LTNode* LTPushBack(LTNode *head, LTDataType x)
{
	if (head == NULL)//为空返回空
		return NULL;

	LTNode* node = InitNewNode(x);//尾插的新节点
	LTNode* p = head;

	while (p -> next)//遍历到最后一个节点
	p = p->next;

	p->next = node;//尾插
	node->next = NULL;

	return head;//返回头节点
}

（6）单链表尾删：

LTNode* LTPopBack(LTNode *head)
{
	if (head == NULL)
		return NULL;

	if (head->next == NULL)//只有头节点直接删除
	{
		free(head);
		return NULL;
	}

	LTNode* p = head;
	while (p->next->next)//遍历到最后一个节点的前一个节点
	{
		p = p->next;
	}

	LTNode* tmp = p->next;//最后一个节点保存
	p->next = tmp->next;//尾删
	free(tmp);

	return head;//返回链表头节点
}

（7）单链表pos位置插入：

LTNode* LTPush(LTNode* head, int pos, LTDataType val)
{
	if (pos == 0)//插入位置在0为头插
	{
		LTNode* node = InitNewNode(val);
		node->next = head;
		return node;
	}

	LTNode* node = InitNewNode(val);

	LTNode* p = head;
	for (int i = 0; i < pos - 1; i++)
	p = p->next;

	node->next = p->next;//进行插入
	p->next = node;

	return head;
}

（8）销毁单链表：

void LTDestroy(LTNode* head)
{
	if (head == NULL)
		return;
	for (LTNode* p = head, *q; p; p = q)
	{
		q = p->next;//保存p的下一个节点
		free(p);//销毁当前节点
	}
	return;
}

（9）单链表随机插入：

int main()
{
	srand((unsigned int)time(0));//产生伪随机
	LTNode* head = InitNewNode(rand() % 100 + 1);
	for (int i = 0; i < MAX_OP; i++)//MAX_OP为7，表示七次插入
	{
		int pos = rand() % (i + 2), val = rand() % 100;//插入位置与值随机
		printf("Insert %d at %d to Linklist \n", val, pos);
		head = LTPush(head, pos, val);
		output(head);//每次插入都打印
	}
	LTDestroy(head);
	return 0;
}

（10）单链表打印：

void output(LTNode* head)//我觉得这样会更美观一些
{
	int n = 0;
	for (LTNode* p = head; p; p = p->next)
		n++;
	for (int i = 0; i < n; i++)
	{
		printf("%3d", i);
		printf("  ");
	}
	printf("\n");

	for (int i = 0; i < n; i++)
	{
		printf("-----");
	}
	printf("\n");

	for (LTNode* p = head; p; p = p->next)
	{
		printf("%3d", p->data);
		printf("->");
	}

	printf("\n");
	printf("\n");
	printf("\n");
	return;
}

打印效果：

（11）单链表操作测试：

void Test(LTNode *head)
{
	printf("PushBack:\n");
	head = LTPushBack(head, 1);
	head = LTPushBack(head, 2);
	head = LTPushBack(head, 3);
	output(head);

	printf("PopBcak:\n");
	head = LTPopBack(head);
	head = LTPopBack(head);
	head = LTPopBack(head);
	output(head);

	printf("PushFront:\n");
	head = LTPushFront(head, 3);
	head = LTPushFront(head, 2);
	head = LTPushFront(head, 1);
	output(head);

	printf("PopFront:\n");
	head = LTPopFront(head);
	head = LTPopFront(head);
	head = LTPopFront(head);
	output(head);
	return;
}

打印结果：

四、双向链表基本操作

（1）双向链表结构定义：

typedef int LTDataType;

typedef struct ListNode {
	struct ListNode* next;//后继指针
	struct ListNode* pre;//前驱指针
	LTDataType data;
}LTNode;

（2）双链表初始化：

LTNode* BuyLTNode(LTDataType n)
{
	LTNode* p = (LTNode*)malloc(sizeof(LTNode));//开辟新节点
	p->pre = p;//前后指针都指向自己
	p->next = p;
	p->data = n;
	return p;//返回新节点
}

（3）双链表头插：

void LTPushFront(LTNode* phead, LTDataType n)
{
	assert(phead);//断言不为空指针
	LTNode* tail = phead->pre;//找到尾节点
	LTNode* node = BuyLTNode(n);

	node->next = phead;//新节点指向头指针
	phead->pre = node;//头指针前驱指向新节点

	tail->next = node;//尾节点指向新节点
	node->pre = tail;//新节点前驱指向尾节点
	return;
}

（4）双链表尾插：

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);//断言是否为空指针
	LTNode* tail = phead->pre;//找到尾指针
	LTNode* newnode = BuyLTNode(x);
	tail->next = newnode;//尾指针指向新节点

	newnode->next = phead;//新节点指向头指针
	newnode->pre = tail;//新节点前驱指向尾指针
	phead->pre = newnode;//头节点前驱指向新节点
}

（5）双链表头删：

void LTPopFront(LTNode* phead)
{
	assert(phead);
	LTNode* tail = phead->pre;//保存尾节点
	tail->next = phead->next;//尾节点指向头节点下一个节点

	phead->next->pre = tail;//头节点下一个节点前驱指向尾节点
	free(phead);
	tail->next = phead;//尾节点指向新的头节点
	return;
}

（6）双链表尾删：

void LTPopBack(LTNode* phead)
{
	assert(phead);

	LTNode* tail = phead->pre;//找到尾节点
	tail->pre->next = phead;//尾节点前驱节点指向头节点
	phead->pre = tail->pre;//头节点前驱指向尾节点前驱

	free(tail);
	return;
}

（7）双链表pos位置插入：

void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* prev = pos->pre;//保存pos位置前一个节点
	LTNode* node = BuyLTNode(x);

	node->next = pos;//新节点指向pos
	pos->pre = node;//pos前驱指向新节点

	node->pre = prev;//新节点前驱指向pos前节点
	prev->next = node;//pos前节点指向新节点
	return;
}

（8）双链表删除节点：

void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* prev = pos->pre;//保存要删除位置前一个节点
	prev->next = pos->next;//前一个结点指向pos的下一个节点
	pos->next->pre = prev;//pos的下一个节点的前驱指向前一个节点
	return;
}

（9）双链表销毁：

void ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* p = phead->next;//保存头节点下一个节点
	while (p)
	{
		free(phead);
		if (p->next)
		{
			phead = p;
			p = p->next;
		}
	}
	return;
}

（10）双链表打印：

void ListPrint(LTNode* phead)//打印双链表
{
	assert(phead);
	LTNode* p = phead;
	do {
		printf("%d ", p->data);
		if (p->next != phead)
		{
			printf("<->");
		}
		p = p->next;
	} while (p != phead);
	printf("\n\n\n");
	return;
}

如果这篇文章对您有帮助的话，还望三连支持一下作者啦~

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-11-11，如有侵权请联系 cloudcommunity@tencent.com 删除

return