【数据结构】双向奔赴的爱恋 --- 双向链表

关注小庄 顿顿解馋๑ᵒᯅᵒ๑

引言：上回我们讲解了单链表(单向不循环不带头链表)，我们可以发现他是存在一定缺陷的，比如尾删的时候需要遍历一遍链表，这会大大降低我们的性能，再比如对于链表中的一个结点我们是无法直接访问它的上一个结点，那有什么解决方法呢？这里就得请出我们今天的主角----双链表。

文章目录

• 一. 🏠 什么是双链表
• 二. 🏠 双链表的实现
• • 👿 双链表结点
  • 👿 双链表哨兵位的创建
  • 👿 双链表插入数据
  • 👿 双链表删除数据
  • 👿 双链表查找
  • 👿 pos结点前插入数据和删除pos结点数据
  • 👿 双链表打印和销毁
  • 三. 🏠 双链表的分析

    一. 🏠 什么是双链表

    在这里我们讲的双链表有三个特点 ：双向 ， 循环 ， 带头 。我们分别理解这三个特点~

    • 双向 循环

      

      优势：1.每一个结点都能很方便访问它的后一个结点和前一个结点 2.方便找到尾节点，提高了效率。

    • 带头

      

      图中的head就是哨兵位

      1. 这里的带头跟我们之前所说的头节点有所不同，这里的带头,不存储有效数据起到一个哨兵的作用。
      2. 哨兵位的作用：遍历循环链表避免死循环，其次涉及到头节点的删除和插入时，无需考虑NULL的问题。

      双链表的这三个特点将会使得实现它比实现单链表更简单~

      ---

      二. 🏠 双链表的实现

      👿 双链表结点

      为了能循环和双向，我们双链表的一个结点需要两个指针。

      typedef int Datatype;
      typedef struct ListNode
      {
      	struct ListNode* next;
      	struct ListNode* pre;
      	Datatype x;
      }ListNode;
      

      👿 双链表哨兵位的创建

      ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
      	if (NULL == newnode)
      	{
      		perror("malloc failed");
      		return;
      	}
      	newnode->x = x;
      	newnode->next = newnode;
      	newnode->pre = newnode;
      

      1.注意next指针和pre指针都要指向自己。

      2.由于插入数据也要创建新结点，所以我们可以直接创建一个申请结点的接口方便复用。

      //申请新结点的接口
      ListNode* BuyNode(Datatype x)
      {
      	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
      	if (NULL == newnode)
      	{
      		perror("malloc failed");
      		return;
      	}
      	newnode->x = x;
      	newnode->next = newnode;
      	newnode->pre = newnode;
      	return newnode;
      }
      // 创建返回链表的头结点.
      ListNode* ListCreate()
      {
      	ListNode* phead = BuyNode(-1); //哨兵位
      	return phead;
      }
      

      👿 双链表插入数据

      • 尾插

        双链表的尾插指的是将新节点插入到哨兵位之前

        

        1.黄色箭头和蓝色箭头是我们要修改的指针指向

        2.注意：要先改变蓝色箭头的对应关系，如果先让head的pre变成newnode话，后边newnode->pre = plist就会指向自己

        3.小技巧：不管三七二十一，插入直接先改newnode的next和pre

        // 双向链表尾插  尾插是插到plist的前面
        void ListPushBack(ListNode* plist, Datatype x)
        {
        	assert(plist);
        	ListNode* newnode = BuyNode(x);
        	newnode->next = plist;
        	newnode->pre = plist->pre;
        	plist->pre->next = newnode;
        	plist->pre = newnode;
        }
        

        • 头插

          

          // 双向链表头插 头插是插到哨兵位的后面
          void ListPushFront(ListNode* plist, Datatype x)
          {
          	ListNode* newnode = BuyNode(x);
          	ListNode* del = plist->next;
          	newnode->next = del;
          	newnode->pre = plist;
          	del->pre = newnode;
          	plist->next = newnode;
          }
          

          *是不是很easy，跟单链表比起来 ~ *

          👿 双链表删除数据

          • 尾删

            

            对于尾删 只需要改它前面一个结点next和哨兵位的pre就好了，存好pre结点的位置

            void ListPopBack(ListNode* plist)
            {
            	assert(plist);
            	assert(plist->next != plist);
            	ListNode* ptail = plist->pre;
            	ListNode* pre = ptail->pre;
            	pre->next = plist;
            	plist->pre = pre;
            	free(ptail);
            	ptail = NULL;
            }
            

            • 头删

              

              // 双向链表头删
              void ListPopFront(ListNode* plist)
              {
              	assert(plist);
              	assert(plist->next != plist);
              	ListNode* pNext = plist->next->next;
              	ListNode* pcur = plist->next;
              	plist->next = pNext;
              	pNext->pre = plist;
              	free(pcur);
              	pcur = NULL;
              }
              

              👿 双链表查找

              遍历链表找到就停下，如果没找到循环到head停止，返回NULL。大大提现了哨兵位的好处

              // 双向链表查找
              ListNode* ListFind(ListNode* plist, Datatype x)
              {
              	assert(plist);
              	ListNode* pcur = plist->next;
              	while (pcur != plist)
              	{
              		if (pcur->x == x)
              		{
              			return pcur;
              		}
              		pcur = pcur->next;
              	}
              	return NULL;
              }
              

              👿 pos结点前插入数据和删除pos结点数据

              类似尾插尾删，头插头删，改变指针指向即可

              // 双向链表在pos的前面进行插入
              void ListInsert(ListNode* pos, Datatype x)
              {
              	assert(pos);
              	ListNode* newnode = BuyNode(x);
              	ListNode* pre = pos->pre;
              	newnode->next = pos;
              	newnode->pre = pre;
              	pre->next = newnode;
              	pos->pre = newnode;
              }
              // 双向链表删除pos位置的结点
              void ListErase(ListNode* pos)
              {
              	assert(pos);
              	ListNode* pre = pos->pre;
              	ListNode* pNext = pos->next;
              	pre->next = pNext;
              	pNext->pre = pre;
              	free(pos);
              	pos = NULL;
              }
              

              👿 双链表打印和销毁

              循环遍历到phead停止~

              // 双向链表打印
              void ListPrint(ListNode* plist)
              {
              	assert(plist);
              	ListNode* pcur = plist->next;
              	while (pcur != plist)
              	{
              		printf("%d->", pcur->x);
              		pcur = pcur->next;
              	}
              	printf("\n");
              }
              // 双向链表销毁
              void ListDestory(ListNode* plist)
              {
              	ListNode* pcur = plist->next;
              	while (pcur != plist)
              	{
              		ListNode* del = pcur->next;
              		free(pcur);
              		pcur = del;
              	}
              	free(pcur);
              	pcur = NULL; //无效
              }
              

              注意：由于函数形参是实参的一份临时拷贝，所以要在函数外手动置空！

              ---

              三. 🏠 双链表的分析

              经过如上我们实现的双链表结构，我们不禁发现它比单链表功能的强大，那它是否是完美的呢？答案是否的，没有完美的人，也没有完美的数据结构。

              优点：

              1.双链表单次任意位置插入和删除效率较高，比单链表还要效率高

              2.双链表不存在空间浪费，按需申请和释放空间

              3.双链表的一个结点可以访问前后结点(相比于单链表)

              缺点：

              1.和单链表一样，虽然双链表访问尾结点快，但是任然不支持随机访问

              2.cpu高速缓存命中率低，因为结点地址可能是分散的。

              ---

              本次双链表的讲解就到此结束啦，各位看官能否与我双向奔赴来个三连呢！ ！ ！