从线性到网状：双向链重构信息组织的核心路径（双向链表图文互联+完整源码）

胖咕噜的稞达鸭

发布于 2025-10-22 14:52:10

2400

代码可运行

文章被收录于专栏：C++初阶高阶C++初阶高阶

运行总次数：0

代码可运行

注意：这⾥的“带头”跟前⾯我们说的“头节点”是两个概念，实际前⾯的在单链表阶段称呼不严谨，但是为了同学们更好的理解就直接称为单链表的头节点。

带头链表⾥的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这⾥“放哨的“。

“哨兵位”存在的意义：遍历循环链表避免死循环。

1.1 双向链表定义

由数据 + 指向下一个节点的指针 + 指向前一个节点的指针

单链表为空时，phead=NULL;

双向链表为空的时候，phead只是一个放哨的节点，而且phead->next=phead->prev都是指向phead自身

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType  data;//保存数据
	struct ListNode* next;//指针保存下一个节点的地址
	struct ListNode* prev;//指针保存前一个节点的地址
}LTNode;

#include"List.h"

//申请节点
LTNode* LTBuyNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc failed!");
		exit(1);
	}
	node->data = x;
	node->next = node->prev = node;//指向下一个节点和前一个节点 通通指向自己node
	return node;//也就是说，双向链表每申请一个节点，都需要自循环，指向自己
}

1.1.1 链表初始化

上代码！

//链表在尾插之前，先要进行初始化
void LTInit(LTNode** pphead);

//链表在尾插之前，先要进行初始化
void LTInit(LTNode** pphead)
{
	//给双向链表创建一个哨兵位（哨兵位的位置不是有效的值）
	*pphead = LTBuyNode(-1);//哨兵位的位置申请一个节点，调用的函数必须传值，可以传一个随意的值，比如说-1
}
////当然还可以这样
//LTNode* LTInit()
//{
//	LTNode* phead = LTBuyNode(-1);
//	return phead;
//}

//LTNode* plist = LTInit();//以返回值的形式初始化链表
LTNode* plist = NULL;//这是以参数的形式初始化链表
LTInit(&plist);

1.1.2 打印链表

//打印链表
void LTPrint(LTNode* phead);

//打印链表
void LTPrint(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

2.1 尾插

//尾插入
void LTPushBack(LTNode* phead, LTDataType x);//插入数据之前，链表必须初始化到只有一个节点的情况
//哨兵位节点不能被删除，节点的地址也不能发生改变，所以这里传一级指针就好

//尾插入
void LTPushBack(LTNode* phead, LTDataType x) {
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//phead链表头节点   phead->prev链表尾节点   newnode插入的新节点
	newnode->prev = phead->prev;  //newnode的prev链接尾节点
	newnode->next = phead;        //newnode的next链接链表头节点
	
	phead->prev->next = newnode;  //链表尾节点的next链接newnode
	phead->prev = newnode;        //链表尾节点链接newnode
}

测试尾插！

2.2 头插

//头插
void LTPushFront(LTNode* phead, LTDataType x);

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;

	phead->next = newnode;
	phead->next->prev = newnode;
}

2.3 尾删

//尾删
void LTPopBack(LTNode* phead);

//尾删
void LTPopBack(LTNode* phead)
{
	//链表必须有效，而且不能为空
	assert(phead && phead->next != phead);
	LTNode* del = phead->prev;
	//phead  del  del->prev
	del->prev->next = phead;
	phead->prev = del->prev;

	free(del);
	del = NULL;
}

2.4 头删

//头删
void LTPopFront(LTNode* phead);

//头删
void LTPopFront(LTNode* phead)
{
	assert(phead && phead->next != phead);
	LTNode* del = phead->next;
	//phead del del->next
	
	phead->next = del->next;
	del->next->prev = phead;

	free(del);
	del = NULL;
}

2.5 在指定位置插入数据

2.5.1 查找

//查找
LTNode* LTFind(LTNode* phead, LTDataType x);

//先实现查找的方法
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;//没有找到
}

这里LTInsert方法包含了头插，但是头插不包含LTInsert !!!

//在指定位置插入数据
void LTInsert(LTNode* pos, LTDataType x);

//在指定位置插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* newnode = LTBuyNode(x);
	//pos newnode pos->next
	newnode->next = pos->next;
	newnode->prev = pos;

	
	pos->next->prev = newnode;
	pos->next = newnode;
}

2.6 删除pos节点

//删除指定位置的数据
void LTErase(LTNode* pos);

//删除pos节点
void LTErase(LTNode* pos)
{
	assert(pos);

	//pos->prev pos pos->next
	pos->prev -> next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

2.7 销毁链表

LTErase和LTDestroy理论上应该传二级，因为我们需要让形参的改变影响到实参，但是为了保持接口的一致性才传的二级。

传一级存在的问题，当形参phead置为NULL后，实参plist不会被修改为NULL，因此解决方法是：

调用完方法后将实参置为NULL

plist(保存的地址空间被释放掉了），若后续不再使用plist就不会出现问题，但是若还是要继续使用plist指针就会出现问题。

//销毁链表
void LTDestroy(LTNode* phead);

//销毁链表
void LTDestroy(LTNode* phead)
{
	assert(phead);

	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//此时pcur指向phead,而phead还没有被销毁
	free(phead);
	phead = NULL;
}

3.完整源码

//List.c中
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType  data;//保存数据
	struct ListNode* next;//指针保存下一个节点的地址
	struct ListNode* prev;//指针保存前一个节点的地址
}LTNode;

//链表在尾插之前，先要进行初始化
void LTInit(LTNode** pphead);

//打印链表
void LTPrint(LTNode* phead);

//尾插入
void LTPushBack(LTNode* phead, LTDataType x);//插入数据之前，链表必须初始化到只有一个节点的情况
//哨兵位节点不能被删除，节点的地址也不能发生改变，所以这里传一级指针就好

//头插
void LTPushFront(LTNode* phead, LTDataType x);

//尾删
void LTPopBack(LTNode* phead);

//头删
void LTPopFront(LTNode* phead);

//查找
LTNode* LTFind(LTNode* phead, LTDataType x);

//在指定位置插入数据
void LTInsert(LTNode* pos, LTDataType x);

//删除指定位置的数据
void LTErase(LTNode* pos);

//销毁链表
void LTDestroy(LTNode* phead);

//List.c中
#include"List.h"

//申请节点
LTNode* LTBuyNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc failed!");
		exit(1);
	}
	node->data = x;
	node->next = node->prev = node;//指向下一个节点和前一个节点 通通指向自己node
	return node;//也就是说，双向链表每申请一个节点，都需要自循环，指向自己
}

//链表在尾插之前，先要进行初始化
void LTInit(LTNode** pphead)
{
	//给双向链表创建一个哨兵位（哨兵位的位置不是有效的值）
	*pphead = LTBuyNode(-1);//哨兵位的位置申请一个节点，调用的函数必须传值，可以传一个随意的值，比如说-1
}
////当然还可以这样
//LTNode* LTInit()
//{
//	LTNode* phead = LTBuyNode(-1);
//	return phead;
//}

//打印链表
void LTPrint(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

//尾插入
void LTPushBack(LTNode* phead, LTDataType x) {
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//phead链表头节点   phead->prev链表尾节点   newnode插入的新节点
	newnode->prev = phead->prev;  //newnode的prev链接尾节点
	newnode->next = phead;        //newnode的next链接链表头节点
	
	phead->prev->next = newnode;  //链表尾节点的next链接newnode
	phead->prev = newnode;        //链表尾节点链接newnode
}

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;

	phead->next = newnode;
	phead->next->prev = newnode;
}

//尾删
void LTPopBack(LTNode* phead)
{
	//链表必须有效，而且不能为空
	assert(phead && phead->next != phead);
	LTNode* del = phead->prev;
	//phead  del  del->prev
	del->prev->next = phead;
	phead->prev = del->prev;

	free(del);
	del = NULL;
}

//头删
void LTPopFront(LTNode* phead)
{
	assert(phead && phead->next != phead);
	LTNode* del = phead->next;
	//phead del del->next
	
	phead->next = del->next;
	del->next->prev = phead;

	free(del);
	del = NULL;
}

//先实现查找的方法
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;//没有找到
}
//在指定位置插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* newnode = LTBuyNode(x);
	//pos newnode pos->next
	newnode->next = pos->next;
	newnode->prev = pos;

	
	pos->next->prev = newnode;
	pos->next = newnode;
}

//删除pos节点
void LTErase(LTNode* pos)
{
	assert(pos);

	//pos->prev pos pos->next
	pos->prev -> next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

//销毁链表
void LTDestroy(LTNode* phead)
{
	assert(phead);

	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//此时pcur指向phead,而phead还没有被销毁
	free(phead);
	phead = NULL;
}

#include "List.h"

void ListTest01()
{
	//LTNode* plist = LTInit();//以返回值的形式初始化链表
	LTNode* plist = NULL;//这是以参数的形式初始化链表
	LTInit(&plist);

	LTPushBack(plist, 1);
	LTPrint(plist);
	LTPushBack(plist, 2);
	LTPrint(plist);
	LTPushBack(plist, 3);
	LTPrint(plist);
	LTPushBack(plist, 4);
	LTPrint(plist);

	LTNode* find = LTFind(plist, 3);
	/*LTInsert(find,56);*/
	
	LTErase(find);
	LTPrint(plist);
	/*if (find == NULL)
	{
		printf("没有找到！\n");
	}
	else
	{
		printf("找到了!\n");
	}*/

	/*LTPushFront(plist, 5);
	LTPrint(plist);
	LTPushFront(plist, 6);
	LTPrint(plist);*/
	/*LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);*/
	/*LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);*/

	LTDestroy(plist);
	plist = NULL;
}

int main(void)
{
	ListTest01();
	return 0;
}

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

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

重构