文章目录

• 📑前言
• 🌤️链表概念
• 🌤️链表的分类
• • ☁️单向或双向链表
  • ☁️带头或不带头
  • ☁️循环或不循环
  • ☁️常用的链表
  • 🌤️无头单向循环链表（单链表）
  • • ☁️单链表的定义
    • ☁️结点
    • ☁️头插
    • ☁️尾插
    • ☁️查找
    • ☁️pos后一位插入
    • ☁️删除pos后一位
    • ☁️删除pos位置的值
    • ☁️打印
    • ☁️链表的释放
    • 🌤️带头双向循环链表
    • • ☁️带头双向链表简介
      • ☁️链表主体
      • ☁️链表头部结点
      • ☁️添加新结点
      • ☁️链表打印
      • ☁️头插
      • ☁️尾插
      • ☁️头删
      • ☁️尾删
      • ☁️查找
      • ☁️pos位置前插入
      • ☁️删除pos位置结点
      • ☁️链表销毁
      • 🌤️链表优缺点总结
      • • ☁️优点
        • ☁️缺点
        • 🌤️全篇总结

          📑前言

          什么是链表？链表有着什么样的结构性？它是怎么实现的？

          看完这篇文章，你对链表的理解将会上升新的高度！

          🌤️链表概念

          链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。下面是简单的单链表图。

          

          

          🌤️链表的分类

          链表的结构是多样的，以下的情况组合起来就有8种链表结构！

          ☁️单向或双向链表

          

          ☁️带头或不带头

          

          ☁️循环或不循环

          

          ☁️常用的链表

          

          1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
          2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单。

          🌤️无头单向循环链表（单链表）

          ☁️单链表的定义

          对类型进行重命名，这样以后可以根据自己的实际需求改变数据的类型。

          创建一个结构体类型，存储元素数据，然后需要一个同样类型的结构体指针，这个指针可以指向同类型的数据，这样就可以通过指针访问下一个结点的元素。

          typedef int SLDatatype;
           
          typedef struct SListNode
          {
          	SLDatatype data;
          	struct SListNode* next;
          }SListNode;
          

          链表这里定义后可不做初始化。

          ☁️结点

          SListNode* BuySListNode(SLDatatype x)
          {
          	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
          	if (newnode == NULL)
          	{
          		perror("BuySListNode");
          		exit(-1);
          	}
          	newnode->data = x;
          	newnode->next = NULL;
          	return newnode;
          }
          

          在堆区上开辟一个新的结点，给定结点的值，然后初始化，节点是链表较为重要的一部分，没有结点，链表就无法链接。

          ☁️头插

          void SLPushFront(SListNode** phead,SLDatatype x)
          {
          	SListNode* newnode = BuySListNode(x);
          	newnode->next = *phead;
          	*phead = newnode;
          }
          

          在链表前插入新结点，然后链接到原链表。

          ☁️尾插

          void SLPushBack(SListNode** phead, SLDatatype x)
          {
          	SListNode* newnode = BuySListNode(x);
          	if (*phead == NULL)
          	{
          		*phead = newnode;
          	}
          	else
          	{
          		SListNode* tail = *phead;
          		while (tail->next != NULL)
          		{
          			tail = tail->next;
          		}
          		tail->next = newnode;
          	}
          }
          

          在链表末尾插入新结点，使原链表链接到新结点。

          ☁️查找

          SListNode* SListFind(SListNode* phead, SLDatatype x)
          {
          	assert(phead);
          	SListNode* pos = phead;
          	while (pos)
          	{
          		if (pos->data == x)
          			return pos;
          		pos = pos->next;
          	}
          	return NULL;
          }
          

          给定要查找的链表中的元素，让pos去遍历，找到并返回当前元素的地址。

          ☁️pos后一位插入

          void SListInsertAfter(SListNode** phead, SLDatatype x)
          {
          	assert(phead);
          	assert(*phead);
           
          	SListNode* newnode = BuySListNode(x);
          	newnode->next = (*phead)->next;
          	(*phead)->next = newnode;
          }
          

          通过查找找到要插入的位置，在指定位置的后一位插入元素数据。

          ☁️删除pos后一位

          void SListEraseAfter(SListNode* phead)
          {
          	assert(phead);
          	assert((phead)->next);
           
          	SListNode* cur = phead->next;
          	phead->next = cur->next;
          	free(cur);
          	cur = NULL;
          }
          

          通过查找找到要删除的位置，删除指定位置后一位的元素数据。

          ☁️删除pos位置的值

          void SListErase(SListNode** phead, SListNode* pos)
          {
          	assert(pos);
          	if (pos == *phead)
          	{
          		SLPopFront(phead);
          	}
          	else
          	{
          		SListNode* cur = *phead;
          		while(cur->next != pos)
          		{
          			cur = cur->next;
          		}
          		cur->next = pos->next;
          		free(pos);
          		//pos = NULL;
          	}
          }
          

          还给定链表的某个结点位置，然后删除，这里的pos可以置空也可以不置空，因为这是临时变量，出了函数就销毁了，好的习惯是可以置空的。

          ☁️打印

          void SLPrint(SListNode* phead)
          {
          	SListNode* cur = phead;
          	while (cur)
          	{
          		printf("%d->", cur->data);
          		cur = cur->next;
          	}
          	printf("NULL\n");
          }
          

          链表不像是数组，不能使用常规的方式来遍历。

          ☁️链表的释放

          当链表不再使用后，我们要对其进行销毁，释放空间内存。

          void SListDestroy(SListNode* phead)
          {
          	SListNode* current = phead;
          	SListNode* next = NULL;
           
          	while (current != NULL)
          	{
          		next = current->next;
          		free(current);
          		current = next;
          	}
          }
          

          1. 创建两个指针变量current和next，分别指向当前节点和下一个节点。
          2. 进入一个循环，循环条件是当前节点current不为NULL。
          3. 在循环内部，将next指针指向当前节点的下一个节点。
          4. 使用free函数释放当前节点的内存空间。
          5. 将current指针指向next，即将下一个节点赋给current，以便继续循环操作。
          6. 重复步骤3-5，直到链表中的所有节点都被释放掉。

          🌤️带头双向循环链表

          ☁️带头双向链表简介

          双向链表的节点通常包含两个部分：数据部分和指针部分。数据部分用于存储节点所包含的数据，指针部分包含两个指针，一个指向前一个节点，一个指向后一个节点。

          ​ 双向链表的优点是可以在常数时间内在任意位置插入或删除节点，因为只需要修改相邻节点的指针即可。而在单向链表中，如果要在某个位置插入或删除节点，则需要遍历链表找到该位置的前一个节点。

          ​ 双向链表相对于单向链表也有一些缺点。首先，双向链表需要额外的指针来存储前一个节点的地址，因此占用的内存空间比单向链表更大。其次，双向链表在插入或删除节点时需要修改两个指针的值，而单向链表只需要修改一个指针的值，因此操作起来更复杂。

          到这里，想必大家就对双向链表有了个大概的认识，告诉你个小秘密哦：其实双向链表的实现比单链表要简单上不少，只是在数据的结构上双向链表看起来不让人觉得简单，别怕都是纸老虎，往下看一步步手撕它。

          ☁️链表主体

          

          ☁️链表头部结点

          在对链表一系列的操作之前，我们首要需要的就是头结点点，有了头结点后续数据的插入删除都会变得简单。

          List* ListCreate()
          {
          	List* newnode = (List*)malloc(sizeof(List));
          	if (newnode == NULL)
          	{
          		perror("malloc fail");
          		exit(-1);
          	}
          	newnode->prev = newnode;
          	newnode->next = newnode;
          	newnode->val = 0;
          	return newnode;
          }
          

          因为是循环的双向链表，所以头结点初始化的时候，两个指针都是指向自己。

          

          ☁️添加新结点

          在插入数据中，必不可少的就是结点的创建，然后再链接到表中。新新结点的前后指针均为空，不指向如何结点。

          List* BuyListNode(ListDatatype x)
          {
          	List* newnode = (List*)malloc(sizeof(List));
          	if (newnode == NULL)
          	{
          		perror("malloc fail");
          		exit(-1);
          	}
          	newnode->val = x;
          	newnode->prev = NULL;
          	newnode->next = NULL;
          	return newnode;
          }
          

          ☁️链表打印

          当链表有了数据以后，为了直观的方便我们对数据增删查改的观察，打印就起到了作用。

          void ListPrint(List* pead)
          {
          	assert(pead);
          	List* cur = pead->next;
           
          	printf("pead:");
          	while (cur != pead)
          	{
          		printf("《=》%d", cur->val);
          		cur = cur->next;
          	}
          	printf("\n");
          }
          

          ☁️头插

          void ListPushFront(List* pead, ListDatatype x)
          {
          	assert(pead);
          	List* newnode = BuyListNode(x);
          	
          	List* cur =pead->next;
          	
          	pead->next = newnode;
          	newnode->prev = pead;
          	newnode->next = cur;
          	cur->prev = newnode;
          	//ListInsert(pead->next, x);这是在pos位置前插入数据，这里可进行复用，后面会有实现
          }
          

          

          新结点的前指针指向前一个节点，后指针指向后一个节点，就进行了链接。

          ☁️尾插

          void ListPushBack(List* pead, ListDatatype x)
          {
          	assert(pead);
           
          	List* newnode = BuyListNode(x);
          	List* cur = pead->prev;
           
          	pead->prev = newnode;
          	newnode->next = pead;
          	cur->next = newnode;
          	newnode->prev = cur;
          	//ListInsert(pead, x);这是在pos位置前插入数据，这里可进行复用，后面会有实现
          }
          

          

          在尾部插入和头插同理，需要改变的只有相邻节点间的指针。

          ☁️头删

          void ListPopFront(List* pead)
          {
          	assert(pead);
          	assert(pead->next !=pead);
          	List* cur = pead->next;
          	List* second = cur->next;
           
          	free(cur);
          	pead->next = second;
          	second->prev = pead;
          }
          

          

          删除首节点，然后使头部指针指向后一个节点。

          ☁️尾删

          void ListPopBack(List* pead)
          {
          	assert(pead);
          	assert(pead->prev);
          	List* cur = pead->prev;
          	List* second = cur->prev;
           
          	free(cur);
          	second->next = pead;
          	pead->prev = second;
          }
          

          

          删除尾节点，然后使头部指针与尾节点前的节点链接。

          ☁️查找

          List* ListFind(List* pead, ListDatatype x)
          {
          	assert(pead);
           
          	List* cur = pead->next;
          	while (cur != pead)
          	{
          		if (cur->val == x)
          		{
          			return cur;
          		}
          		cur = cur->next;
          	}
          	return NULL;
          }
          

          给定一个元素的数据，然后在链表中进行遍历，找到后返回元素地址 。

          ☁️pos位置前插入

          void ListInsert(List* pos, ListDatatype x)
          {
          	assert(pos);
          	List* cur = pos->prev;
          	List* newnode = BuyListNode(x);
           
          	newnode->prev = cur;
          	cur->next = newnode;
          	newnode->next = pos;
          	pos->prev = newnode;
          }
          

          通过断言确保输入的位置指针非空。创建新节点，并将其插入到指定位置之前。

          • 将指定位置的前一个节点保存为cur。
          • 创建一个新节点newnode，并将其数据域初始化为x。
          • 将新节点的前驱指针指向cur。
          • 将cur的后继指针指向新节点。
          • 将新节点的后继指针指向指定位置。
          • 将指定位置的前驱指针指向新节点。

            ☁️删除pos位置结点

            void ListErase(List* pos)
            {
            	assert(pos);
            	List* cur = pos->prev;
            	List* second = pos->next;
            	
            	cur->next = second;
            	second->prev = cur;
            	free(pos);
            }
            

            断言确保输入的位置指针非空。将指定位置的前一个节点的后继指针指向指定位置的后一个节点，将指定位置的后一个节点的前驱指针指向指定位置的前一个节点，最后释放指定位置的内存空间。

            ☁️链表销毁

            当链表我们不再需要使用的时候，就需要将其进行销毁，因为这些空间都是在堆上进行开辟的。

            void ListDestroy(List* head) 
            {
            	assert(head);
             
            	List* cur = head->next;
            	while (cur != head) 
            	{
            		List* tmp = cur;
            		cur = cur->next;
            		free(tmp);
            	}
            	free(head);
            }
            

            🌤️链表优缺点总结

            ☁️优点

            1. 动态性：链表的长度可以根据需要进行动态调整，可以方便地进行插入和删除操作，而不需要像数组那样需要预先分配固定大小的内存空间。
            2. 灵活性：链表可以存储不同类型的数据，节点之间的连接关系可以根据需要进行调整，可以实现各种复杂的数据结构。
            3. 内存利用率高：链表只在需要时分配内存空间，不会浪费额外的内存。

            ☁️缺点

            1. 随机访问的效率低：链表中的元素并不是连续存储的，要访问链表中的某个元素，需要从头节点开始遍历，直到找到目标节点，因此访问某个特定位置的元素的时间复杂度为O(n)，而不是O(1)。
            2. 额外的内存开销：链表中每个节点除了存储数据外，还需要额外的指针来连接节点，这会占用额外的内存空间。
            3. 不支持随机访问：由于访问链表中的元素需要遍历，因此无法像数组那样通过索引直接访问某个元素，这在某些应用场景下可能会造成不便。

            🌤️全篇总结

            本文对两种最常用到的链表形式进行了讲解,多方面由浅入深，让你真正掌握链表！

            ☁️ 后序还会有更多的数据结构文章分享哦！

            看到这里希望给博主留个: 👍点赞🌟收藏⭐️关注！

            你们的点赞就是博主更新最大的动力！

            有问题可以评论或者私信呢秒回哦。

            

             
             动态网页如何制作  自己免费建站平台推荐  一般通过男性  大一网页设计作业代码  怎么做网络平台  网易企业邮箱登陆