鏈表基礎(chǔ)操作
鏈表基礎(chǔ)知識
在數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)過程中，我們知道線性表【一種數(shù)據(jù)組織、在內(nèi)存中存儲的形式】是線性結(jié)構(gòu)的，其中線性表包括順序表和鏈表。數(shù)組就是順序表，其各個(gè)元素在內(nèi)存中是連續(xù)存儲的。
鏈表則是由數(shù)據(jù)域和指針域組成的結(jié)構(gòu)體構(gòu)成的，數(shù)據(jù)域是一個(gè)節(jié)點(diǎn)的數(shù)據(jù)，指針域存儲下一個(gè)節(jié)點(diǎn)的地址，下一個(gè)節(jié)點(diǎn)依靠上一個(gè)節(jié)點(diǎn)的指針域?qū)ぶ?。給出整個(gè)鏈表的頭節(jié)點(diǎn)地址（指針）head后，就能依次訪問鏈表的每個(gè)節(jié)點(diǎn)。
鏈表定義：
鏈表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，它或者為空（null），或者是指向一個(gè)結(jié)點(diǎn)（node）的引用，該節(jié)點(diǎn)還有一個(gè)元素和一個(gè)指向另一條鏈表的引用。
根據(jù)鏈表間節(jié)點(diǎn)的指向，鏈表可以分為以下三種：
- 單向鏈表：指針域中只有指向下一個(gè)節(jié)點(diǎn)的地址；只能單向遍歷鏈表；
- 雙向鏈表：指針域中有兩個(gè)指針，一個(gè)指向前一個(gè)節(jié)點(diǎn)，一個(gè)指向下一個(gè)節(jié)點(diǎn)；可以雙向遍歷鏈表；
- 循環(huán)鏈表：鏈表形成環(huán)，最后一個(gè)節(jié)點(diǎn)的指針域不賦值為null，而是指向頭節(jié)點(diǎn)head；
定義一個(gè)鏈表節(jié)點(diǎn)，是單向的鏈表：
//定義一個(gè)結(jié)構(gòu)體ListNode表示鏈表節(jié)點(diǎn)
struct ListNode {
int val; //數(shù)據(jù)域，這里用的int，根據(jù)實(shí)際情況選擇type，比如char、float等
ListNode *next; //指針域，存下一個(gè)節(jié)點(diǎn)的地址，所以是指針類型，并且下一個(gè)節(jié)點(diǎn)也是該結(jié)構(gòu)體，所以是ListNode*
//自定義構(gòu)造函數(shù)，給數(shù)據(jù)域和指針域賦值
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
鏈表中頭節(jié)點(diǎn)直接用head指針訪問，其他節(jié)點(diǎn)用currentNode->next的指針訪問，可見鏈表的頭節(jié)點(diǎn)是特殊的。在插入、刪除操作中，針對頭節(jié)點(diǎn)都需要做特殊的處理，會(huì)較麻煩，因此在頭節(jié)點(diǎn)前增加一個(gè)虛擬頭節(jié)點(diǎn)【也叫附加頭節(jié)點(diǎn)、哨兵節(jié)點(diǎn)等】dummy_head，虛擬頭節(jié)點(diǎn)的指針域存head，即dummy_head->next = head；數(shù)據(jù)域無效，因?yàn)楹罄m(xù)不會(huì)用到。給定dummy_head后，其他節(jié)點(diǎn)都用當(dāng)前節(jié)點(diǎn)的next指針訪問，即currentNode->next：
接下來介紹對鏈表進(jìn)行的一些操作【穿針引線法】：
插入節(jié)點(diǎn)
在鏈表中的一個(gè)位置插入節(jié)點(diǎn)，需要先斷開插入位置前后兩個(gè)節(jié)點(diǎn)的鏈接，再和這兩個(gè)節(jié)點(diǎn)建立新的鏈接：先cur->next = pre->next；再pre->next = cur； 如果先pre->next = cur，就會(huì)丟失sur這個(gè)節(jié)點(diǎn)的地址。
上面是普通的情況，那么針對頭節(jié)點(diǎn)，尾節(jié)點(diǎn)的特殊情況呢？ 末尾節(jié)點(diǎn)其實(shí)也沒有什么特殊的，只是suc是NULL，也就是pre->next為NULL，按照上述的兩步操作也是ok的。問題是在頭節(jié)點(diǎn)前插入：
- 如果是普通鏈表，頭節(jié)點(diǎn)前什么都沒有，pre是NULL的。只進(jìn)行①：cur->next = head，head = cur【頭節(jié)點(diǎn)是新插入的節(jié)點(diǎn)】；
- 如果前面有虛擬頭節(jié)點(diǎn)，那么pre就是dummy_head，頭節(jié)點(diǎn)和其他節(jié)點(diǎn)是一樣的操作；
刪除節(jié)點(diǎn)
從鏈表中刪除節(jié)點(diǎn)，可以是刪除指定位置的，比如刪除第三個(gè)節(jié)點(diǎn)；也可以是根據(jù)節(jié)點(diǎn)值刪除的，比如刪除值等于target的節(jié)點(diǎn)。刪除節(jié)點(diǎn)時(shí)，將被刪除節(jié)點(diǎn)的前面節(jié)點(diǎn)和后面節(jié)點(diǎn)連接起來的同時(shí)，斷開被刪除節(jié)點(diǎn)和其前面一個(gè)、后面一個(gè)節(jié)點(diǎn)的連接，并且要釋放掉被刪除節(jié)點(diǎn)的空間：pre->next = cur->next；delete cur。
針對頭節(jié)點(diǎn)和尾節(jié)點(diǎn)的特殊情況呢？ 將尾節(jié)點(diǎn)看作是下一個(gè)節(jié)點(diǎn)是null的節(jié)點(diǎn)，處理和其他節(jié)點(diǎn)一樣。問題同樣是頭節(jié)點(diǎn)，刪除頭節(jié)點(diǎn)的話：
- 普通鏈表，直接tmp = head->next，delete head，head = tmp；
- 添加了虛擬頭節(jié)點(diǎn)的鏈表，刪除頭節(jié)點(diǎn)，其pre = dummy_head，cur = head；直接按照正常節(jié)點(diǎn)刪除即可。
從刪除頭節(jié)點(diǎn)和在頭節(jié)點(diǎn)前插入節(jié)點(diǎn)的分析就可以知道，添加了虛擬頭節(jié)點(diǎn)dummy_head后，對頭節(jié)點(diǎn)的操作不需要單獨(dú)討論，所有節(jié)點(diǎn)操作一致。
查找節(jié)點(diǎn)
比如按位置查找某個(gè)節(jié)點(diǎn)，返回其節(jié)點(diǎn)值；比如按值查找鏈表中是否存在值等于target的節(jié)點(diǎn)。因?yàn)殒湵硎峭ㄟ^節(jié)點(diǎn)的指針域而將各個(gè)節(jié)點(diǎn)連接起來的，它不能像數(shù)組一樣直接按下標(biāo)查找【數(shù)組各元素在內(nèi)存空間是連續(xù)存儲的，通過下標(biāo)就能夠定位到內(nèi)存空間】。要查找鏈表中某個(gè)節(jié)點(diǎn)，需要遍歷鏈表，需要O(n)的時(shí)間復(fù)雜度。
707. 設(shè)計(jì)鏈表
題目鏈接：707.設(shè)計(jì)鏈表
題目內(nèi)容：
理解題意：實(shí)際上就是實(shí)現(xiàn)一個(gè)鏈表類，可以單向也可以雙向，其中要涉及到插入節(jié)點(diǎn)：在頭部插入、在尾部插入、根據(jù)下標(biāo)index在指定位置插入；刪除節(jié)點(diǎn)；根據(jù)下標(biāo)index獲取節(jié)點(diǎn)值。
實(shí)現(xiàn)：單向鏈表：
以下代碼實(shí)現(xiàn)的是有虛擬頭節(jié)點(diǎn)的單向鏈表，并且在類中定義一個(gè)_size變量存儲鏈表中節(jié)點(diǎn)數(shù)量，以便根據(jù)下標(biāo)index刪除、添加節(jié)點(diǎn)時(shí)，判斷下標(biāo)是否合理。 另外在節(jié)點(diǎn)末尾處添加節(jié)點(diǎn)，可認(rèn)為是index = _size時(shí)，在index處插入節(jié)點(diǎn)：文章來源：http://www.zghlxwxcb.cn/news/detail-664740.html
class MyLinkedList {
private:
//定義類的私有變量
int _size; //鏈表中節(jié)點(diǎn)數(shù)量，不包括虛擬頭節(jié)點(diǎn)
//定義鏈表節(jié)點(diǎn)結(jié)構(gòu)體
struct ListNode {
int val; //數(shù)據(jù)域
ListNode *next; //指針域
//構(gòu)造函數(shù)
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
//鏈表附加頭節(jié)點(diǎn)，整個(gè)鏈表的開始
ListNode* _dummyhead;
public:
//自定義類的構(gòu)造函數(shù)
MyLinkedList() {
_dummyhead = new ListNode(0); //新建虛擬頭節(jié)點(diǎn)
_size = 0; //初始化鏈表中有效節(jié)點(diǎn)數(shù)量為0
}
//根據(jù)下標(biāo)返回節(jié)點(diǎn)value
int get(int index) {
//下標(biāo)無效
if(index >= _size)
return -1;
ListNode* currNode = _dummyhead; //從虛擬頭節(jié)點(diǎn)開始訪問
//遍歷到下標(biāo)為index的節(jié)點(diǎn)
for(int i = 0; i <= index; i++){
currNode = currNode->next;
}
return currNode->val; //返回value
}
//在頭部添加節(jié)點(diǎn)
void addAtHead(int val) {
ListNode * newNode = new ListNode(val); //先構(gòu)造一個(gè)新節(jié)點(diǎn)
newNode->next = _dummyhead->next; //直接在虛擬頭節(jié)點(diǎn)后插入
_dummyhead->next = newNode;
_size++; //插入節(jié)點(diǎn)后，鏈表節(jié)點(diǎn)數(shù)量+1
}
//在尾部添加節(jié)點(diǎn)
//實(shí)際上就是在index為_size的地方添加節(jié)點(diǎn)
void addAtTail(int val) {
addAtIndex(_size,val);
}
//在指定下標(biāo)index位置處插入節(jié)點(diǎn)
void addAtIndex(int index, int val) {
if(index > _size) return ; //下標(biāo)不合理
ListNode* newNode = new ListNode(val); //構(gòu)造一個(gè)新節(jié)點(diǎn)
ListNode* prevNode = _dummyhead;
//找到需要插入的地方
while(index) {
prevNode = prevNode->next;
index--;
}
//插入節(jié)點(diǎn)
newNode->next = prevNode->next;
prevNode->next = newNode;
_size++; //節(jié)點(diǎn)數(shù)量++
}
//刪除指定位置的節(jié)點(diǎn)
void deleteAtIndex(int index) {
if(index >= _size) return; //下標(biāo)不合理
ListNode* prevNode = _dummyhead;
//找到要?jiǎng)h除的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
while(index){
prevNode = prevNode->next;
index--;
}
//tmp為要?jiǎng)h除的節(jié)點(diǎn)
ListNode* tmp = prevNode->next;
//要?jiǎng)h除節(jié)點(diǎn)前后兩個(gè)節(jié)點(diǎn)建立新連接
prevNode->next = tmp->next;
//刪除tmp節(jié)點(diǎn)，釋放空間
delete tmp;
_size--; //鏈表中節(jié)點(diǎn)數(shù)量-1；
}
};
實(shí)現(xiàn)：雙向鏈表
雙向鏈表就是每個(gè)節(jié)點(diǎn)有兩個(gè)指針，一個(gè)指向前驅(qū)節(jié)點(diǎn)（preNode），一個(gè)指向后驅(qū)節(jié)點(diǎn)（succNode），插入、刪除節(jié)點(diǎn)時(shí)，需要對兩個(gè)指針的指向都處理：文章來源地址http://www.zghlxwxcb.cn/news/detail-664740.html
- 插入一個(gè)節(jié)點(diǎn)時(shí)，preNode->next = newNode； newNode->next = succNode； succNode->prior = newNode； newNode->prior = preNode；
- 刪除一個(gè)節(jié)點(diǎn)時(shí)：preNode->next = succNode；succNode->prior = preNode；
這里需要注意的是，succNode實(shí)際上是currNode->next，如果是刪除最后一個(gè)節(jié)點(diǎn)或者在最后一個(gè)節(jié)點(diǎn)后追加一個(gè)節(jié)點(diǎn)，succNode=NULL，為了和其他節(jié)點(diǎn)統(tǒng)一操作，同樣在末尾增加一個(gè)虛擬尾節(jié)點(diǎn)。
雙向鏈表可以雙向遍歷，在index位置插入、刪除、查詢節(jié)點(diǎn)值時(shí)，可以先判斷index是在鏈表前半段還是后半段，確定是從前往后遍歷更快，還是從后往前遍歷更快。 代碼如下（C++）：
class MyLinkedList {
private:
int _size; //鏈表中有效節(jié)點(diǎn)數(shù)量，不包括虛擬頭節(jié)點(diǎn)、虛擬尾節(jié)點(diǎn)
struct ListNode { //定義鏈表節(jié)點(diǎn)結(jié)構(gòu)體
int val;
ListNode *next, *prior; //雙向鏈表需要有兩個(gè)指針
ListNode() : val(0), next(nullptr), prior(nullptr) {}
ListNode(int x) : val(x), next(nullptr), prior(nullptr) {}
ListNode(int x, ListNode *next, ListNode *prior) : val(x), next(next), prior(prior) {}
};
ListNode *_dummyhead, *_dummytail; //虛擬頭節(jié)點(diǎn)和虛擬尾節(jié)點(diǎn)
public:
MyLinkedList() {
_dummyhead = new ListNode(0); //虛擬頭節(jié)點(diǎn)
_dummytail = new ListNode(0); //虛擬尾節(jié)點(diǎn)
//建立虛擬頭節(jié)點(diǎn)和虛擬尾節(jié)點(diǎn)之間的連接
_dummyhead->next = _dummytail;
_dummytail->prior = _dummyhead;
_size = 0; //鏈表中有效節(jié)點(diǎn)數(shù)量
}
int get(int index) {
//下標(biāo)無效
if(index >= _size)
return -1;
ListNode *currNode;
//判斷index在前半段
if(index < _size/2){
currNode = _dummyhead;
//從前往后遍歷更快
for(int i = 0; i <= index; i++){
currNode = currNode->next;
}
}
else{ //index在后半段
currNode = _dummytail;
//從后往前遍歷更快
for(int i = _size-1; i >= index ;i--){
currNode = currNode->prior;
}
}
return currNode->val;
}
//在頭部添加節(jié)點(diǎn)，即在虛擬頭節(jié)點(diǎn)后插入
void addAtHead(int val) {
ListNode *newNode = new ListNode(val);
//建立四條新的連接
_dummyhead->next->prior = newNode;
newNode->next = _dummyhead->next;
_dummyhead->next = newNode;
newNode->prior = _dummyhead;
_size++;
}
//在尾部插入節(jié)點(diǎn)，等于在index = _size的位置插入節(jié)點(diǎn)
void addAtTail(int val) {
addAtIndex(_size,val);
}
//在指定index處插入
void addAtIndex(int index, int val) {
if(index > _size) return ;
ListNode* newNode = new ListNode(val);
ListNode *prevNode = _dummyhead, *succNode = _dummytail;
if(index < _size/2){ //從前往后更快定位到index前的節(jié)點(diǎn)
for(int i = 0; i < index; i++){
prevNode = prevNode->next;
}
succNode = prevNode->next;
}
else{ //從后往前更快定位到index前的節(jié)點(diǎn)
for(int i = _size - 1; i >= index; i--){
succNode = succNode->prior;
}
prevNode = succNode->prior;
}
//插入一個(gè)節(jié)點(diǎn)后，新增四條連接
succNode->prior = newNode;
newNode->next = succNode;
prevNode->next = newNode;
newNode->prior = prevNode;
_size++;
}
//刪除index處的節(jié)點(diǎn)
void deleteAtIndex(int index) {
if(index >= _size) return;
ListNode *prevNode = _dummyhead, *succNode = _dummytail;
//根據(jù)index和_size的關(guān)系，決定從前往后遍歷還是從后往前遍歷
if(index < _size/2){
for(int i = 0; i < index; i++){
prevNode = prevNode->next;
}
succNode = prevNode->next->next;
}
else{
for(int i = _size - 1; i > index; i--){
succNode = succNode->prior;
}
prevNode = succNode->prior->prior;
}
ListNode* tmp = prevNode->next;
//preNode和succNode之間建立雙向連接
prevNode->next = succNode;
succNode->prior = prevNode;
delete tmp;
_size--;
}
};
到了這里，關(guān)于【leetcode 力扣刷題】鏈表基礎(chǔ)知識 基礎(chǔ)操作的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
