🔑🔑博客主頁:阿客不是客
🍓🍓系列專欄:漸入佳境之數據結構與算法
歡迎來到泊舟小課堂
😘博客制作不易歡迎各位👍點贊+?收藏+?關注
??
前言
前面我們學習了單鏈表,它解決了順序表中插入刪除需要挪動大量數據的缺點,使單鏈表解決順序表缺陷時,我們發現作為另一種形態出現的單鏈表似乎也有明顯的缺陷。
- 在部分功能實現時因為頭結點的改變需要引進二級指針(或者采用返回等更為復雜的方法)導致代碼更加復雜。
- 尋找某個節點的前一個節點,對于單鏈表而言只能遍歷,這樣就可能造成大量時間的浪費。
- 尾部以及指定位置插入、刪除數據的時間復雜度為O(N)?,效率低下。
為了解決這個問題,我們就要學習今天的主角——雙向鏈表。
一、帶頭雙向循環鏈表的介紹
實際中鏈表的結構非常多樣,以下情況組合起來就有8種鏈表結構,雖然有這么多的鏈表的結構,但是我們實際中最常用還是兩種結構:無頭單向不循環鏈表,帶頭雙向循環鏈表。
對比單鏈表來了解,帶頭雙向循環鏈表:結構復雜,一般單獨存儲數據。憑著其復雜的結構我們可以做到快速管理數據,實現對數據的操作。
?
帶頭雙向循環鏈表具有以下特點:
- 頭節點:帶頭雙向循環鏈表包含一個頭節點,它位于鏈表的起始位置,并且不存儲實際數據。頭節點的前指針指向尾節點,頭節點的后指針指向第一個實際數據節點。
- 循環連接:尾節點的后指針指向頭節點,而頭節點的前指針指向尾節點,將鏈表形成一個循環連接的閉環。這樣可以使鏈表在遍歷時可以無限循環,方便實現循環操作。
- 雙向連接:每個節點都有一個前指針和一個后指針,使得節點可以向前和向后遍歷。前驅指針指向前一個節點,后繼指針指向后一個節點。
總結:帶頭雙向循環鏈表可以支持在鏈表的任意位置進行插入和刪除操作,并且可以實現正向和反向的循環遍歷。通過循環連接的特性,鏈表可以在連續的循環中遍歷所有節點,使得鏈表的操作更加靈活和高效。
二、帶頭雙向循環雙鏈表的實現
2.1 創建鏈表
雙向鏈表的定義結構體需要包含三個成員,一個成員存儲數值,一個成員存儲前一個節點的地址,最后一個成員存儲下一個節點的地址。
typedef int LTDataType;
typedef struct ListNode
{LTDataType val;struct ListNode* next;struct ListNode* prev;
}LTN;
2.2 初始化鏈表
在初始化雙向鏈表時,我們需要創建一個頭節點,也就是我們常說的哨兵位頭節點。
這里需要注意一下:創建頭結點的時候,因為鏈表中沒有其它的數據,我們在初始化的時候讓guard的next和prev都要指向自己,這樣才是一個循環鏈表(如下圖所示 ↓↓↓ )
?
LTN* LTinit()
{LTN* phead = CreateLTNode(-1);phead->next = phead;phead->prev = phead;return phead;
}
2.3 創建新結點
跟之前的一樣就不過多介紹了
LTN* CreateLTNode(LTDataType x)
{LTN* newnode = (LTN*)malloc(sizeof(LTN));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->val = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}
2.4?打印鏈表
這個鏈表中的結點是沒有NULL的,因此在判斷循環是否要結束的條件應該是判斷tail是否等于phead
void LTprint(LTN* phead)
{assert(phead);printf("哨兵位 <--> ");LTN* tail = phead->next;while (tail != phead){printf("%d <--> ",tail->val);tail = tail->next;}printf("哨兵位\n");
}
2.5?雙向鏈表的查找
和單鏈表一樣,我們也可以對雙向鏈表進行查找。如果找到就返回該節點的地址,否則返回NULL。
LTN* LTFind(LTN* phead, LTDataType x)
{assert(phead);LTN* cur = phead->next;while (cur != phead){if (cur->val == x){return cur;}else{cur = cur->next;}}return NULL;
}
2.6?雙向鏈表的插入
2.5.1 尾插
單鏈表尾插結點需要遍歷全鏈表,當指針走到鏈表最后一個結點的時候,判斷tail->next是否為NULL,若為NULL,則跳出遍歷的循環,尾插新結點。然而帶頭雙向循環鏈表不需要遍歷鏈表,只需要對哨兵位的頭節點的prev域解引用,直接找到帶頭雙向循環鏈表的尾節點,尾插新節點。
?
頭指針的區別:帶頭雙向循環鏈表不需要判斷頭指針是否指向NULL,因為哨兵位的頭節點也是有它的地址的,添加新節點時只需要直接在尾節點尾插。然而單鏈表卻需要判斷頭指針是否指向NULL,而且需要用到二級指針,比較棘手。
??
void LTpushback(LTN* phead, LTDataType x)
{assert(phead);//帶哨兵位頭結點,只改變了結構體成員,不需要二級指針LTN* tail = phead->prev;LTN* newnode = CreateLTNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}
2.5.2 頭插
void LTpushfront(LTN* phead, LTDataType x)
{assert(phead);LTN* tail = phead->next;LTN* newnode = CreateLTNode(x);tail->prev = newnode;newnode->next = tail;newnode->prev = phead;phead->next = newnode;
}
2.5.3 任意位置插入
void LTInsert(LTN* pos, LTDataType x)
{assert(pos);LTN* newnode = CreateLTNode(x);LTN* tail = pos->prev;pos->prev = newnode;newnode->next = pos;newnode->prev = tail;tail->next = newnode;
}
和單鏈表不同,雙向鏈表頭尾操作完全可以用任意位置操作替代。?
LTInsert實現尾插:
LTInsert(phead, x);
LTInsert實現頭插:
LTInsert(phead->next, x);
2.7?雙向鏈表的刪除
2.6.1 尾刪
?當鏈表只有一個節點(哨兵位不算)時:
若鏈表為NULL(只剩哨兵位就是鏈表為NULL)時,再尾刪就被assert會出錯:
void LTpopback(LTN* phead)
{assert(phead);assert(phead->next != phead);LTN* tail = phead->prev;LTN* tailprev = tail->prev;tailprev->next = phead;phead->prev = tailprev;free(tail);tail = NULL;
}
2.6.2 頭刪
鏈表不止一個結點時:
鏈表為一個結點時:
代碼示例如下:?
void LTpopfront(LTN* phead)
{assert(phead);assert(phead->next != phead);LTN* tail = phead->next;LTN* tailnext = tail->next;tailnext->prev = phead;phead->next = tailnext;free(tail);tail = NULL;
}
2.6.3 任意位置刪除
void LTErase(LTN* pos)
{assert(pos);LTN* tailnext = pos->next;LTN* tailprev = pos->prev;tailnext->prev = tailprev;tailprev->next = tailnext;free(pos);pos = NULL;
}
LTErase實現尾刪:
LTErase(phead->prev);
?LTErase實現頭刪:
LTErase(phead->next);
2.8?銷毀鏈表
void LTDestroy(LTN* phead)
{assert(phead);LTN* cur = phead->next;while (cur != phead){LTN* next = cur->next;free(cur);cur = next;}free(phead);
}
三、完整代碼
3.1 LTN.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDataType;
typedef struct ListNode
{LTDataType val;struct ListNode* next;struct ListNode* prev;
}LTN;LTN* LTinit();//初始化鏈表void LTprint(LTN* phead);void LTpushback(LTN* phead, LTDataType x);
void LTpushfront(LTN* phead, LTDataType x);
void LTpopback(LTN* phead);
void LTpopfront(LTN* phead);LTN* LTFind(LTN* phead, LTDataType x);void LTInsert(LTN* pos, LTDataType x);
void LTErase(LTN* pos);
3.2 LTN.c
#include"SLTN.h"LTN* CreateLTNode(LTDataType x)
{LTN* newnode = (LTN*)malloc(sizeof(LTN));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->val = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}LTN* LTinit()
{LTN* phead = CreateLTNode(-1);phead->next = phead;phead->prev = phead;return phead;
}void LTprint(LTN* phead)
{assert(phead);printf("哨兵位 <--> ");LTN* tail = phead->next;while (tail != phead){printf("%d <--> ",tail->val);tail = tail->next;}printf("哨兵位\n");
}void LTpushback(LTN* phead, LTDataType x)
{assert(phead);//帶哨兵位頭結點,只改變了結構體成員,不需要二級指針LTN* tail = phead->prev;LTN* newnode = CreateLTNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;//LTInsert(phead->prev, x);
}void LTpushfront(LTN* phead, LTDataType x)
{assert(phead);LTN* tail = phead->next;LTN* newnode = CreateLTNode(x);tail->prev = newnode;newnode->next = tail;newnode->prev = phead;phead->next = newnode;//LTInsert(phead->next, x);
}void LTpopback(LTN* phead)
{assert(phead);assert(phead->next != phead);LTN* tail = phead->prev;LTN* tailprev = tail->prev;tailprev->next = phead;phead->prev = tailprev;free(tail);tail = NULL;//LTErase(phead->prev);
}void LTpopfront(LTN* phead)
{assert(phead);assert(phead->next != phead);LTN* tail = phead->next;LTN* tailnext = tail->next;tailnext->prev = phead;phead->next = tailnext;free(tail);tail = NULL;//LTErase(phead->next);
}LTN* LTFind(LTN* phead, LTDataType x)
{assert(phead);LTN* cur = phead->next;while (cur != phead){if (cur->val == x){return cur;}else{cur = cur->next;}}return NULL;
}void LTInsert(LTN* pos, LTDataType x)
{assert(pos);LTN* newnode = CreateLTNode(x);LTN* tail = pos->prev;pos->prev = newnode;newnode->next = pos;newnode->prev = tail;tail->next = newnode;
}void LTErase(LTN* pos)
{assert(pos);LTN* tailnext = pos->next;LTN* tailprev = pos->prev;tailnext->prev = tailprev;tailprev->next = tailnext;free(pos);pos = NULL;
}
四、順序表與鏈表優缺點分析
- 鏈表(雙向)優勢:
- 任意位置插入刪除都是O(1)
- 按需申請釋放,合理利用空間,不存在浪費
- 問題:
- 下標隨機訪問不方便
- 順序表問題:
- 頭部或中間插入刪除效率低,要挪動數據O(N)
- 空間不夠要擴容,擴容有一定消耗,且可能存在一定的空間浪費
- 只適合尾插尾刪
- 優勢:?
- 支持下標隨機訪問O(1),可以進行排序操作。