作者前言
?? ??????????????????????
??? 作者介紹： ????
?? ?????????????? ??
??作者id：老秦包你會， ??
簡單介紹：??????????????????????????????
喜歡學習C語言和python等編程語言，是一位愛分享的博主，有興趣的小可愛可以來互討 ????????????????
??個人主頁::小小頁面??
??gitee頁面:秦大大??
????????????????
?? 一個愛分享的小博主 歡迎小可愛們前來借鑒??
鏈表的差別
- 無頭單向非循環(huán)鏈表：結構簡單，一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結
構的子結構，如哈希桶、圖的鄰接表等等。另外這種結構在筆試面試中出現(xiàn)很多。 - 帶頭雙向循環(huán)鏈表：結構最復雜，一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結構，都
是帶頭雙向循環(huán)鏈表。另外這個結構雖然結構復雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結構會帶
來很多優(yōu)勢，實現(xiàn)反而簡單了，后面我們代碼實現(xiàn)了就知道了。
帶頭雙向循環(huán)鏈表的實現(xiàn)
我們需要的當這種鏈表為空時，
這個小知識一定要記住
鏈表初始化
DLists* plist = (DLists*)malloc(sizeof(DLists));
plist->next = plist;
plist->prev = plist;
一個節(jié)點要包含三部分分別是值，兩個指針
節(jié)點創(chuàng)建
//創(chuàng)建節(jié)點
DLists* CreateNode(DLDataType elemest)
{
DLists* newnode = (DLists*)malloc(sizeof(DLists));
newnode->next = newnode;
newnode->prev = newnode;
newnode->val = elemest;
return newnode;
}
鏈表的尾插
void DLPushBack(DLists* plist, DLDataType elelmest)
{
assert(plist);
//創(chuàng)建節(jié)點
DLists* newnode = CreateNode(elelmest);
DLists* n = plist->prev;
newnode->next = plist;
newnode->prev = n;
n->next = newnode;
plist->prev = newnode;
}
這里我們只需要更改四個指針指向就可以，分別是哨兵位的 、prev 和新節(jié)點的prev 、next和舊節(jié)點的next
鏈表尾刪
void DLPopBack(DLists* plist)
{
assert(plist->next != plist && plist);
//保存最后一個節(jié)點的地址
DLists* p = plist->prev;
plist->prev = p->prev;
DLists* p1 = p->prev;
p1->next = plist;
free(p);
}
這樣寫可以防止只有一個節(jié)點的時候報錯
我們可以創(chuàng)建兩個指針，一個指向要free的節(jié)點，一個是要和哨兵位關聯(lián)的節(jié)點也就是d2
打印鏈表
我們可以從d1這個節(jié)點開始打印，遇見頭節(jié)點就結束
//打印
void DLPrint(DLists* plist)
{
assert(plist);
printf("哨兵位");
DLists* tail = plist->next;
while (tail != plist)
{
printf("<=>%d", tail->val);
tail = tail->next;
}
printf("<=>哨兵位\n");
}
鏈表頭插
我們可以創(chuàng)建一個指針用于存儲d1的地址，然后把節(jié)點插入，這樣可以簡單快捷
//頭插
void DLPushFront(DLists* plist, DLDataType elemest)
{
assert(plist);
DLists* n1 = plist->next;
//創(chuàng)建節(jié)點
DLists* newnode = CreateNode(elemest);
plist->next = newnode;
newnode->prev = plist;
n1->prev = newnode;
newnode->next = n1;
}
鏈表頭刪
當我們刪除到哨兵位就不要刪除了
//頭刪
void DLPopFront(DLists* plist)
{
assert(plist->next != plist && plist);
// 保存下一個節(jié)點
DLists *nextnode = plist->next;
DLists* nexnode_next = nextnode->next;
plist->next = nexnode_next;
nexnode_next->prev = plist;
free(nextnode);
}
判斷鏈表是否為空
// 判斷鏈表是否為空
bool Empty(DLists* plist)
{
assert(plist);
return plist->next == plist;
}
鏈表pos前插入
//在pos前面插入
DLists* DLPushbefore(DLists* plist, DLists* pos, DLDataType elemest)
{
assert(plist);
//創(chuàng)建節(jié)點
DLists* newnode = CreateNode(elemest);
//pos的前一個節(jié)點
DLists* node = pos->prev;
pos->prev = newnode;
newnode->next = pos;
newnode->prev = node;
node->next = newnode;
}
計算鏈表長度
// 長度
int DLSize(DLists* plist)
{
assert(plist);
DLists* tail = plist->next;
int size = 0;
while (tail != plist)
{
size++;
tail = tail->next;
}
return size;
}
鏈表刪除pos前一個節(jié)點
//刪除pos前一個節(jié)點
DLists* DLPopbefore(DLists* plist, DLists* pos)
{
assert(plist && pos);
assert(pos->prev != plist);
//前一個節(jié)點
DLists* n2 = pos->prev;
//前前一個節(jié)點
DLists* n1 = n2->prev;
n1->next = pos;
pos->prev = n1;
free(n2);
}
刪除pos節(jié)點
// 刪除 pos節(jié)點
DLists* DLPop(DLists* plist, DLists* pos)
{
assert(plist && pos);
assert(pos!= plist);
//pos前一個節(jié)點
DLists* n2 = pos->prev;
//pos后一個節(jié)點
DLists* n1 = pos->next;
n2->next = n1;
n1->prev = n2;
free(pos);
}
釋放鏈表
從d1開釋放,遇見head停止
//釋放鏈表
void DLDestroy(DLists** plist)
{
assert(*plist && plist);
DLists* tail = (*plist)->next;
while (tail != *plist)
{
DLists* node = tail;
tail = tail->next;
free(node);
}
free(*plist);
*plist = NULL;
}
順序表和鏈表的差異
鏈表的優(yōu)勢
- 任意位置插入和刪除都是O(1),前提是知道位置
- 按需申請和釋放
缺點問題
3. 下標隨機訪問不方便,物理空間不連續(xù),O(n)
4. 鏈表不好排序
順序表的問題
5. 頭部插入或者中間插入刪除效率低下,要移動數(shù)據(jù)
6. 空間不夠要擴容,擴容會有一定消耗且可能存在一定的空間浪費.
7. 只適合尾插尾刪
優(yōu)勢
支持下標的隨機訪問文章來源：http://www.zghlxwxcb.cn/news/detail-754052.html
?文章來源地址http://www.zghlxwxcb.cn/news/detail-754052.html
到了這里，關于數(shù)據(jù)結構第三課 -----線性表之雙向鏈表的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
