数据结构——双向链表（C语言实现）_双向链表插入和删除

目录

什么是双向链表？

双向链表函数的声明和结构体定义

双向链表元素的插入（pos前插入）

双向链表元素的删除（pos处）

双向链表元素的查找

双向链表元素的打印

判断双向链表是否为空

双向链表的删除

双向链表的初始化

双向链表节点的建立

---

什么是双向链表？

上述文章已经解释了什么是单向链表数据结构——单向链表（C语言实现）-CSDN博客

那么正如字面意思，双向链表就是前后都可以指向的链表，就不仅仅是单一的连接后一个元素的链表。

双向链表函数的声明和结构体定义

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;
 
LTNode* LTInit();
void LTPrint(LTNode* phead);
 
bool LTEmpty(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);
 
// 在pos之前插入
void LTInsert(LTNode* pos, LTDataType x);
// 删除pos位置的值
void LTErase(LTNode* pos);
void LTDestroy(LTNode* phead);

有些友友可能会问“双向链表从结构上看也是有一个个指针结点连接而成，那么对其进行插入和删除的时候，为什么不是用二级指针来接收？”

这里我们要知道

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构。——概而言之，单向链表其实是一个整体，要对其改变的时候是进行整体的改变。

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都 是带头双向循环链表。——概而言之，双向链表是一个个单独的部分，进行改变的话只需要对于那一块进行改变即可。

双向链表元素的插入（pos前插入）

void LTInerst(LTNode* pos, LTDataType x)//获取到要插入位置的指针
{
    assert(pos);
    LTNode* prev=pos->prev;
    LTNode* newnode = BuyLTNode(x);
 
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

双向链表的连接是最简单的，不需要判断是否容量是满的，也不需要用到二级指针。

这里我们需要注意的是，要想连接，必须要先建立相对应的结点，然后还得要获得插入位置的指针。

将新建立的节点和前节点和后节点连接起来。

双向链表元素的删除（pos处）

void LTErase(LTNode* pos)
{
	assert(pos);
 
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
 
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}

双向链表元素的查找

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
 
	LTNode* cur = phead->next;
	while (cur != phead)//双向链表虽然简便了，但还是无法用下标来定位，需要用循环来进行遍历
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

双向链表元素的打印

void LTPrint(LTNode* phead)//形式就是单链表的形式
{
	assert(phead);
 
	printf("guard<==>");
	LTNode* cur = phead->next;//第一个是哨兵位，元素为空不打印
	while (cur != phead)//一次循环后就会回到开头phead处，故判断条件为这个
	{
		printf("%d<==>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

判断双向链表是否为空

bool LTEmpty(LTNode* phead)//判断是否链表里的元素不存在
{
	assert(phead);
	return phead->next == phead;
}

双向链表的删除

void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);//先进行释放，然后在锁定到下一个节点。
		cur = next;
	}
	free(phead);
}

双向链表的初始化

LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1);
	phead->next = phead;
	phead->prev = phead;
 
	return phead;
}

双向链表节点的建立

LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//开辟和结构体一样大小的字节空间
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

由于双向链表里的定义形式和顺序表类似，而且相较于单向链表，其连接方式仅仅多了一个前置指针，大家在写代码的时候别忘了连接前置指针即可，若有不懂的地方，可以画图来加深自己的理解。

以上的代码均为源码，注意将声明和定义分开放即可，可以直接在主函数里使用。