C语言：数据结构（双向链表）

目录

• 1、双向链表的结构
• 2、顺序表和双向链表的优缺点分析
• 3、双向链表的实现

  1、双向链表的结构

  

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

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

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

  2、顺序表和双向链表的优缺点分析

  不同点	顺序表	链表
  存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
  随机访问	支持O(1)	不支持O(N)
  任意位置插⼊或者删除元素	可能需要搬移元素，效率低	只需修改指针指向
  插入	动态顺序表，空间不够时需要扩容	没有容量的概念
  应用场景	元素高效存储和频繁访问	任意位置频繁插入和删除

  3、双向链表的实现

  ListNode.h

  #pragma once
  #include 
  #include 
  #include 
  //定义双向链表节点的结构
  typedef int Ltdatatype;
  typedef struct ListNode
  {
  	Ltdatatype data;
  	struct ListNode* prev;//指向前一个节点的指针
  	struct ListNode* next;//指向后一个节点的指针
  }ListNode;
  //双向链表的初始化
  ListNode* LtInit();
  //尾插
  //不改变哨兵位的地址，所以传一级即可
  void LtPushBack(ListNode* phead, Ltdatatype x);//插入数据之前，链表必须初始化到只有一个头结点的情况
  //打印链表
  void LtPrint(ListNode* phead);
  //头插
  void LtPushFront(ListNode* phead, Ltdatatype x);
  //尾删
  LtPopBack(ListNode* phead);
  //头删
  LtPopFront(ListNode* phead);
  //查找
  ListNode* LtFind(ListNode* phead, Ltdatatype x);
  //指定位置前插入
  void LtInsert(ListNode* pos, Ltdatatype x);
  //删除pos位置
  void LtErase(ListNode* pos);
  //销毁链表
  void LtDestroy(ListNode* phead);
  

  ListNode.c

  #define _CRT_SECURE_NO_WARNINGS
  #include "ListNode.h"
  //申请节点
  ListNode* LtBuyNode(Ltdatatype x)
  {
  	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
  	if (node == NULL)
  	{
  		perror("malloc fail");
  		exit(1);
  	}
  	//申请成功
  	node->data = x;
  	node->next = node->prev = node;
  	return node;
  }
  //双向链表的初始化
  ListNode* LtInit()
  {
  	ListNode*phead = LtBuyNode(-1);
  	return phead;
  }
  //尾插
  void LtPushBack(ListNode* phead, Ltdatatype x)
  {
  	assert(phead);
  	ListNode* newnode = LtBuyNode(x);
  	//改变新节点的指向
  	newnode->prev = phead->prev;
  	newnode->next = phead;
  	//改变尾节点和哨兵位的指向
  	phead->prev->next = newnode;
  	phead->prev = newnode;
  }
  //打印链表
  void LtPrint(ListNode* phead)
  {
  	ListNode* pcur = phead->next;
  	//遍历链表
  	while (pcur != phead)
  	{
  		printf("%d->", pcur->data);
  		pcur = pcur->next;
  	}
  	printf("\n");
  }
  //头插
  void LtPushFront(ListNode* phead,Ltdatatype x)
  {
  	assert(phead);
  	ListNode* newnode = LtBuyNode(x);
  	newnode->prev = phead;
  	newnode->next = phead->next;
  	//修改哨兵位和第一个有效节点的指向
  	phead->next->prev = newnode;
  	phead->next = newnode;
  }
  //尾删
  LtPopBack(ListNode* phead)
  {
  	//链表必须有效且链表不能为空（只有一个哨兵位）
  	assert(phead && phead->next != phead);
  	ListNode* Del = phead->prev;//尾节点
  	ListNode* DelPrev = Del->prev;//尾节点的前一个节点
  	phead->prev = DelPrev;
  	DelPrev->next = phead;
  	free(Del);//删除Del节点
  	Del = NULL;
  }
  //头删
  LtPopFront(ListNode* phead)
  {
  	//判断链表是否有效和链表是否为空
  	assert(phead && phead->next != phead);
  	ListNode* Del = phead->next;//第一个有效节点
  	ListNode* DelNext = Del->next;//有效节点的下一个节点
  	phead->next = DelNext;
  	DelNext->prev = phead;
  	free(Del);//删除Del节点
  	Del = NULL;
  }
  //查找
  ListNode* LtFind(ListNode* phead, Ltdatatype x)
  {
  	ListNode* pcur = phead->next;
  	//遍历链表
  	while (pcur != phead)
  	{
  		if (pcur->data == x)
  			return pcur;
  		pcur = pcur->next;//继续让pcur往下遍历
  	}
  	return NULL;//没有找到
  }
  //在pos位置之前插入数据
  void LtInsert(ListNode* pos,Ltdatatype x)
  {
  	ListNode* newnode = LtBuyNode(x);
  	newnode->prev = pos->prev;
  	newnode->next = pos;
  	pos->prev->next = newnode;
  	pos->prev = newnode;
  }
  //删除pos位置
  void LtErase(ListNode* pos)
  {
  	assert(pos);
  	ListNode* PosPrev = pos->prev;//pos的前一个节点
  	ListNode* PosNext = pos->next;//pos的后一个节点
  	PosPrev->next = PosNext;
  	PosNext->prev = PosPrev;
  	free(pos);
  	//pos = NULL;这里就算置空了，也不会影响实参
  }
  //销毁链表
  void LtDestroy(ListNode* phead)
  {
  	ListNode* pcur = phead->next;
  	//边遍历边释放节点
  	while (pcur != phead)
  	{
  		ListNode* Next = pcur->next;//保存要释放掉节点的下一个地址
  		free(pcur);
  		pcur = Next;
  	}
  	//此时pcur指向phead，而phead还没有被销毁
  	free(phead);
  	pcur = NULL;
  }
  

  text.c

  #define _CRT_SECURE_NO_WARNINGS
  #include "ListNode.h"
  void LtnodeTest()
  {
  	//测试初始化
  	ListNode* plist = LtInit();
  	//测试尾插
  	LtPushBack(plist,1);
  	LtPushBack(plist,2);
  	LtPushBack(plist,3);
  	//测试打印
  	LtPrint(plist);
  	//测试头插
  	//LtPushFront(plist,4);
  	//LtPushFront(plist,5);
  	//LtPushFront(plist,6);
  	//LtPrint(plist);
  	//测试尾删
  	LtPopBack(plist);
  	LtPrint(plist);
  	//测试头删
  	//LtPopFront(plist);
  	//LtPrint(plist);
  	//测试查找
  	//ListNode*find = LtFind(plist,2);
  	//if (find)
  	//	printf("找到了！\n");
  	//else
  	//	printf("没找到！\n");
  	//测试在pos位置之前插入数据
  	//LtInsert(find,88);
  	//LtPrint(plist);
  	//测试删除pos位置
  	//LtErase(find);
  	//find = NULL;//形参的改变不会影响实参，所以要在函数调用结束之后置为空
  	//LtPrint(plist);
  	//测试销毁链表
  	//LtDestroy(plist);
  	//plist = NULL;
  }
  int main()
  {
  	LtnodeTest();
  	return 0;
  }
  

  ---

  如果对你有所帮助的话，别忘了一键三连哟，谢谢宝子们😘！