【数据结构】单双链表超详解！(图解+源码) |
您所在的位置：网站首页 › 双链表代码 › 【数据结构】单双链表超详解！(图解+源码) |
【数据结构】单双链表超详解！(图解+源码)
|
📑前言 什么是链表？链表有着什么样的结构性？它是怎么实现的？ 看完这篇文章，你对链表的理解将会上升新的高度！ 🌤️链表概念链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。下面是简单的单链表图。  在这里插入图片描述 在这里插入图片描述🌤️链表的分类链表的结构是多样的，以下的情况组合起来就有8种链表结构！ ☁️单向或双向链表 在这里插入图片描述☁️带头或不带头 在这里插入图片描述☁️循环或不循环 在这里插入图片描述☁️常用的链表 在这里插入图片描述无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单。🌤️无头单向循环链表（单链表）☁️单链表的定义对类型进行重命名，这样以后可以根据自己的实际需求改变数据的类型。 创建一个结构体类型，存储元素数据，然后需要一个同样类型的结构体指针，这个指针可以指向同类型的数据，这样就可以通过指针访问下一个结点的元素。 代码语言：javascript复制typedef int SLDatatype; typedef struct SListNode { SLDatatype data; struct SListNode* next; }SListNode;链表这里定义后可不做初始化。 ☁️结点代码语言：javascript复制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; }在堆区上开辟一个新的结点，给定结点的值，然后初始化，节点是链表较为重要的一部分，没有结点，链表就无法链接。 ☁️头插代码语言：javascript复制void SLPushFront(SListNode** phead,SLDatatype x) { SListNode* newnode = BuySListNode(x); newnode->next = *phead; *phead = newnode; }在链表前插入新结点，然后链接到原链表。 ☁️尾插代码语言：javascript复制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; } }在链表末尾插入新结点，使原链表链接到新结点。 ☁️查找代码语言：javascript复制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后一位插入代码语言：javascript复制void SListInsertAfter(SListNode** phead, SLDatatype x) { assert(phead); assert(*phead); SListNode* newnode = BuySListNode(x); newnode->next = (*phead)->next; (*phead)->next = newnode; }通过查找找到要插入的位置，在指定位置的后一位插入元素数据。 ☁️删除pos后一位代码语言：javascript复制void SListEraseAfter(SListNode* phead) { assert(phead); assert((phead)->next); SListNode* cur = phead->next; phead->next = cur->next; free(cur); cur = NULL; }通过查找找到要删除的位置，删除指定位置后一位的元素数据。 ☁️删除pos位置的值代码语言：javascript复制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可以置空也可以不置空，因为这是临时变量，出了函数就销毁了，好的习惯是可以置空的。 ☁️打印代码语言：javascript复制void SLPrint(SListNode* phead) { SListNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }链表不像是数组，不能使用常规的方式来遍历。 ☁️链表的释放当链表不再使用后，我们要对其进行销毁，释放空间内存。 代码语言：javascript复制void SListDestroy(SListNode* phead) { SListNode* current = phead; SListNode* next = NULL; while (current != NULL) { next = current->next; free(current); current = next; } }创建两个指针变量current和next，分别指向当前节点和下一个节点。进入一个循环，循环条件是当前节点current不为NULL。在循环内部，将next指针指向当前节点的下一个节点。使用free函数释放当前节点的内存空间。将current指针指向next，即将下一个节点赋给current，以便继续循环操作。重复步骤3-5，直到链表中的所有节点都被释放掉。🌤️带头双向循环链表☁️带头双向链表简介双向链表的节点通常包含两个部分：数据部分和指针部分。数据部分用于存储节点所包含的数据，指针部分包含两个指针，一个指向前一个节点，一个指向后一个节点。 双向链表的优点是可以在常数时间内在任意位置插入或删除节点，因为只需要修改相邻节点的指针即可。而在单向链表中，如果要在某个位置插入或删除节点，则需要遍历链表找到该位置的前一个节点。 双向链表相对于单向链表也有一些缺点。首先，双向链表需要额外的指针来存储前一个节点的地址，因此占用的内存空间比单向链表更大。其次，双向链表在插入或删除节点时需要修改两个指针的值，而单向链表只需要修改一个指针的值，因此操作起来更复杂。 到这里，想必大家就对双向链表有了个大概的认识，告诉你个小秘密哦：其实双向链表的实现比单链表要简单上不少，只是在数据的结构上双向链表看起来不让人觉得简单，别怕都是纸老虎，往下看一步步手撕它。 ☁️链表主体 在这里插入图片描述☁️链表头部结点在对链表一系列的操作之前，我们首要需要的就是头结点点，有了头结点后续数据的插入删除都会变得简单。 代码语言：javascript复制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; }因为是循环的双向链表，所以头结点初始化的时候，两个指针都是指向自己。  在这里插入图片描述☁️添加新结点在插入数据中，必不可少的就是结点的创建，然后再链接到表中。新新结点的前后指针均为空，不指向如何结点。 代码语言：javascript复制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; }☁️链表打印当链表有了数据以后，为了直观的方便我们对数据增删查改的观察，打印就起到了作用。 代码语言：javascript复制void ListPrint(List* pead) { assert(pead); List* cur = pead->next; printf("pead:"); while (cur != pead) { printf("《=》%d", cur->val); cur = cur->next; } printf("\n"); }☁️头插代码语言：javascript复制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位置前插入数据，这里可进行复用，后面会有实现 } 在这里插入图片描述新结点的前指针指向前一个节点，后指针指向后一个节点，就进行了链接。 ☁️尾插代码语言：javascript复制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位置前插入数据，这里可进行复用，后面会有实现 } 在这里插入图片描述在尾部插入和头插同理，需要改变的只有相邻节点间的指针。 ☁️头删代码语言：javascript复制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; } 在这里插入图片描述删除首节点，然后使头部指针指向后一个节点。 ☁️尾删代码语言：javascript复制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; } 在这里插入图片描述删除尾节点，然后使头部指针与尾节点前的节点链接。 ☁️查找代码语言：javascript复制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位置前插入代码语言：javascript复制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位置结点代码语言：javascript复制void ListErase(List* pos) { assert(pos); List* cur = pos->prev; List* second = pos->next; cur->next = second; second->prev = cur; free(pos); }断言确保输入的位置指针非空。将指定位置的前一个节点的后继指针指向指定位置的后一个节点，将指定位置的后一个节点的前驱指针指向指定位置的前一个节点，最后释放指定位置的内存空间。 ☁️链表销毁当链表我们不再需要使用的时候，就需要将其进行销毁，因为这些空间都是在堆上进行开辟的。 代码语言：javascript复制void ListDestroy(List* head) { assert(head); List* cur = head->next; while (cur != head) { List* tmp = cur; cur = cur->next; free(tmp); } free(head); }🌤️链表优缺点总结☁️优点动态性：链表的长度可以根据需要进行动态调整，可以方便地进行插入和删除操作，而不需要像数组那样需要预先分配固定大小的内存空间。灵活性：链表可以存储不同类型的数据，节点之间的连接关系可以根据需要进行调整，可以实现各种复杂的数据结构。内存利用率高：链表只在需要时分配内存空间，不会浪费额外的内存。☁️缺点随机访问的效率低：链表中的元素并不是连续存储的，要访问链表中的某个元素，需要从头节点开始遍历，直到找到目标节点，因此访问某个特定位置的元素的时间复杂度为O(n)，而不是O(1)。额外的内存开销：链表中每个节点除了存储数据外，还需要额外的指针来连接节点，这会占用额外的内存空间。不支持随机访问：由于访问链表中的元素需要遍历，因此无法像数组那样通过索引直接访问某个元素，这在某些应用场景下可能会造成不便。🌤️全篇总结本文对两种最常用到的链表形式进行了讲解,多方面由浅入深，让你真正掌握链表！ ☁️ 后序还会有更多的数据结构文章分享哦！ 看到这里希望给博主留个: 👍点赞🌟收藏⭐️关注！ 你们的点赞就是博主更新最大的动力！ |
【本文地址】