网站开发 专有名词,为国外的公司提供网站建设 维护,网站建设招标信息,app制作公司报价c语言中的小小白-CSDN博客c语言中的小小白关注算法,c,c语言,贪心算法,链表,mysql,动态规划,后端,线性回归,数据结构,排序算法领域.https://blog.csdn.net/bhbcdxb123?spm1001.2014.3001.5343 给大家分享一句我很喜欢我话#xff1a; 知不足而奋进#xff0c;望远山而前行,c语言,贪心算法,链表,mysql,动态规划,后端,线性回归,数据结构,排序算法领域.https://blog.csdn.net/bhbcdxb123?spm1001.2014.3001.5343 给大家分享一句我很喜欢我话 知不足而奋进望远山而前行 铁铁们成功的路上必然是孤独且艰难的但是我们不可以放弃远山就在前方但我们能力仍然不足所有我们更要奋进前行 今天我们更新了双链表内容 欢迎大家关注点赞收藏⭐️留言 什么是双链表
双链表的定义 为什么引入双链表 单链表的结点中只有一个指向其后继的指针使得单链表要访问某个结点的前驱结点时只能从头开始遍历访问后驱结点的复杂度为O(1)访问前驱结点的复杂度为O(n)。为了克服上述缺点引入了双链表。 双链表的结点中有两个指针prior和next分别指向前驱结点和后继结点。 双链表中结点类型的描述
typedef int ListDataType;struct ListNode
{ListDataType data;struct ListNode* next;struct ListNode* prev;
}ListNode;typedef struct ListNode LTNode;
这里可以看到我们把int变为ListNodeType类型因为我们这个节点不一定就是int类型用ListData代替int就可以存储别的类型的数据了。啥时候用啥时候换。
然后用LTNode代替struct ListNode这样更方便一些。
双链表上的操作
1.1双链表的初始化
在初始化之前我们这里先说一下如何创建一个新节点。因为刚开始数据为空因此我们先要创建新节点才可以。
//创建新节点
LTNode* BuyNode(ListDataType x)
{LTNode* newhead (LTNode*)malloc(sizeof(LTNode));if (newhead NULL){perror(malloc fail !!!);}newhead-next newhead-prev NULL;newhead-data x;return newhead;
}
这就是创建新节点的代码。
下面我们来看一下初始化的代码
//初始化
LTNode* InitNode()
{LTNode* phead BuyNode(-1);phead-next phead;phead-prev phead;return phead;
}
这样我们就完成了第一步链表的初始化。这里记住我们创建出来的第一个节点不能直接去使用而是要指向本身才可以。否则会将自身变为NULL。
1.2打印链表
这里也是非常简单就是我们遍历链表即可。
void ListNodeprint(LTNode* head)
{assert(head);LTNode* cur head-next;while (cur ! head){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}
这里要注意的就是while循环中条件不能是cur否则这样就会无限的进行下去我们要令curhead。这里的head就是我们的第一个节点我们也叫它为哨兵位。
1. 3后插
后插相对来说也是比较简单的下面我们来看一下代码。
//后插
void LTNPushBack(LTNode* phead, ListDataType x)
{assert(phead);LTNode* newhead BuyNode(x);LTNode* Tail phead-prev;Tail-next newhead;newhead-prev Tail;newhead-next phead;phead-prev newhead;}
首先我们要对phead进行断言防止传过来的是空指针。
然后这个交换的过程需要大家自己慢慢去琢磨原理很简单就是将原本的最后一个变成新的节点哨兵位的上一个变成新的节点。只是存在一些细节需要大家去注意一下。 1.4前插
//前插
void LTPushFront(LTNode* phead, ListDataType x)
{assert(phead);LTNode* newhead BuyNode(x);LTNode* Tail phead-next;newhead-next Tail;Tail-prev phead;phead-next newhead;newhead-prev phead;}这个是前插的代码原理和后插也大差不差还是将哨兵位的下一个变成新节点原本的第一个节点变成第二个节点。 1.5头删
//头删
void LTPopFront(LTNode* head)
{assert(head);assert(head-next ! head);LTNode* Next head-next;head-next Next-next;Next-prev head;free(Next);Next NULL;}
头删就是一定要断言head和head的下一个如果只有一个哨兵位也无法进行删除。
然后剩下的就是把哨兵位的下一个变成第二个节点第二个节点的上一个变成哨兵位最后将原本的第一个节点释放掉置为NULL。
1.6尾删
/尾删
void LTPopBack(LTNode* head)
{assert(head);assert(head-next ! head);LTNode* cur head-prev;head-prev cur-prev;head-prev-next head;free(cur);cur NULL;
}
依然是对head和他的下一个进行断言。然后思路与前面的头删大致相同。只是是对哨兵位的上一个进行操作。
1.7任意插入
//任意插入
void LTInsert(LTNode* pos, ListDataType x)
{assert(pos);LTNode* newhead BuyNode(x);LTNode* posPrev pos-prev;newhead-prev posPrev;posPrev-next newhead;pos-prev newhead;newhead-next pos;}这里的任意插入我们需要事先找到我们要插入的数的位置然后在这个位置的后面进行插入。这就需要一个find函数这个我们后面会讲到暂时不用去管我们先弄清楚任意插入的思路就是将创建一个新的节点然后将pos的下一个变成它后面的节点的前一个变成他。
1.8任意位置删除
//pos删除
void LTErase(LTNode* pos)
{//pos理论上不能为phead但是没有参数phead无法增加校验assert(pos);pos-next-prev pos-prev;pos-prev-next pos-next;free(pos);pos NULL;这个依然要用到Find函数还是先不用去管我们先看一下这个的思路思路也是很简单就是将pos前面的节点指向pos后面pos后面的节点指向pos前面。
1.9寻找
LTNode* LTFind(LTNode* head, ListDataType x)
{assert(head);assert(head-next ! NULL);LTNode* cur head-next;while (cur ! head){if (cur-data x){return cur;}cur cur-next;}printf(找不到\n);return NULL;
}
这里就是我们find函数的代码了我们首先要对head和head-next进行断言防止其是NULL然后创建一个cur进行while循环条件依旧是cur!head然后找到的话就返回这个节点找不到就返回空指针。
1.10链表的销毁
最后我们来说一下链表的销毁这里我们要对每一个节点都要销毁。
//链表的销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur phead-next;while (pcur ! phead){LTNode* next pcur-next;free(pcur);pcur next;}free(phead);phead NULL;
}
这个就要相对简单一些了就是令pcur等于head-next,然后遍历最后对phead进行销毁。
全部代码
List.h:
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.htypedef int ListDataType;struct ListNode
{ListDataType data;struct ListNode* next;struct ListNode* prev;
}ListNode;typedef struct ListNode LTNode;//初始化
LTNode* InitNode();//创建新节点
LTNode* BuyNode(ListDataType x);//打印
void ListNodeprint(LTNode* head);//后插
void LTNPushBack(LTNode* phead, ListDataType x);//前插
void LTPushFront(LTNode* phead, ListDataType x);//头删
void LTPopFront(LTNode* head);//尾删
void LTPopBack(LTNode* head);//任意点插入
void LTInsert(LTNode* pos, ListDataType x);//任意点删除
void LTErase(LTNode* pos);//查找
LTNode* LTFind(LTNode* head, ListDataType x);//链表的销毁
void LTDestroy(LTNode* phead);
List.c:
#includeList.h//创建新节点
LTNode* BuyNode(ListDataType x)
{LTNode* newhead (LTNode*)malloc(sizeof(LTNode));if (newhead NULL){perror(malloc fail !!!);}newhead-next newhead-prev NULL;newhead-data x;return newhead;
}//初始化
LTNode* InitNode()
{LTNode* phead BuyNode(-1);phead-next phead;phead-prev phead;return phead;
}//打印
void ListNodeprint(LTNode* head)
{assert(head);LTNode* cur head-next;while (cur ! head){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}//后插
void LTNPushBack(LTNode* phead, ListDataType x)
{assert(phead);LTNode* newhead BuyNode(x);LTNode* Tail phead-prev;Tail-next newhead;newhead-prev Tail;newhead-next phead;phead-prev newhead;}//前插
void LTPushFront(LTNode* phead, ListDataType x)
{assert(phead);LTNode* newhead BuyNode(x);LTNode* Tail phead-next;newhead-next Tail;Tail-prev phead;phead-next newhead;newhead-prev phead;}//头删
void LTPopFront(LTNode* head)
{assert(head);assert(head-next ! head);LTNode* Next head-next;head-next Next-next;Next-prev head;free(Next);Next NULL;}//尾删
void LTPopBack(LTNode* head)
{assert(head);assert(head-next ! head);LTNode* cur head-prev;head-prev cur-prev;head-prev-next head;free(cur);cur NULL;
}//任意插入
void LTInsert(LTNode* pos, ListDataType x)
{assert(pos);LTNode* newhead BuyNode(x);LTNode* posPrev pos-prev;newhead-prev posPrev;posPrev-next newhead;pos-prev newhead;newhead-next pos;}//pos删除
void LTErase(LTNode* pos)
{//pos理论上不能为phead但是没有参数phead无法增加校验assert(pos);pos-next-prev pos-prev;pos-prev-next pos-next;free(pos);pos NULL;}LTNode* LTFind(LTNode* head, ListDataType x)
{assert(head);assert(head-next ! NULL);LTNode* cur head-next;while (cur ! head){if (cur-data x){return cur;}cur cur-next;}printf(找不到\n);return NULL;
}//链表的销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur phead-next;while (pcur ! phead){LTNode* next pcur-next;free(pcur);pcur next;}free(phead);phead NULL;
} test.c:
#includeList.hint main()
{LTNode* head InitNode();LTNPushBack(head, 1);LTNPushBack(head, 2);LTNPushBack(head, 3);LTNPushBack(head, 4);LTNode* find LTFind(head, 1);LTErase(find);find NULL;//打印ListNodeprint(head);//销毁LTDestroy(head);
}
总结
双链表是一种常见的数据结构与单链表相比每个节点不仅保存了指向下一个节点的指针还保存了指向前一个节点的指针。这种结构的引入增加了链表的灵活性和功能性。
首先双链表支持双向遍历。由于每个节点都有指向前一个节点的指针可以从任一节点开始向前或向后遍历链表这对于某些操作如逆序遍历或者在特定节点前后插入节点非常方便。
其次双链表更便于节点的删除和插入。在单链表中要删除或插入一个节点需要找到其前一个节点而在双链表中只需要修改节点本身的指针即可无需额外的查找操作从而提高了操作效率。
然而双链表相比单链表需要额外的空间来存储前一个节点的指针因此会占用更多的内存。在某些情况下如果对内存占用有限制可能需要权衡选择是否使用双链表。
总的来说双链表是一种功能强大的数据结构适用于需要频繁进行节点插入、删除和双向遍历的场景但在内存占用上需要谨慎权衡。
