C/C++編程筆記：鏈接列表（鏈表）丨插入節(jié)點(diǎn)的三種方法
在上一篇文章中，我們介紹了鏈接列表。我們還創(chuàng)建了一個(gè)具有3個(gè)節(jié)點(diǎn)的簡(jiǎn)單鏈表，并討論了鏈表遍歷。
本文討論的所有程序均考慮以下鏈表的表示形式。?
C ++
C
在這篇文章中，討論了在鏈表中插入新節(jié)點(diǎn)的方法?？梢酝ㄟ^三種方式添加節(jié)點(diǎn)：?
1）在鏈表的最前面?
2）在給定節(jié)點(diǎn)之后。?
3）在鏈接列表的末尾。
在前面添加一個(gè)節(jié)點(diǎn)：（4個(gè)步驟）
將新節(jié)點(diǎn)始終添加到給定鏈接列表的開頭之前。新添加的節(jié)點(diǎn)成為鏈接列表的新頭。例如，如果給定的鏈接列表為10-> 15-> 20-> 25，并且我們?cè)谇懊嫣砑恿隧?xiàng)目5，則鏈接列表將變?yōu)?-> 10-> 15-> 20-> 25。讓我們將添加到列表最前面的函數(shù)稱為push（）。push（）必須接受一個(gè)指向頭指針，因?yàn)楸仨毻祁^指針改為指向新的節(jié)點(diǎn)。
以下是在最前面添加節(jié)點(diǎn)的4個(gè)步驟。
C++
C
push（）的時(shí)間復(fù)雜度為O（1），因?yàn)樗龅墓ぷ髁渴呛愣ǖ摹?/p>
在給定節(jié)點(diǎn)之后添加一個(gè)節(jié)點(diǎn)：（5個(gè)步驟）?
給我們一個(gè)指向節(jié)點(diǎn)的指針，并將新節(jié)點(diǎn)插入到給定節(jié)點(diǎn)之后。
C ++
C
insertAfter（）的時(shí)間復(fù)雜度為O（1），因?yàn)樗墓ぷ髁渴呛愣ǖ摹?/p>
在最后添加一個(gè)節(jié)點(diǎn)：（6個(gè)步驟）?
將新節(jié)點(diǎn)始終添加到給定鏈接列表的最后一個(gè)節(jié)點(diǎn)之后。例如，如果給定的鏈接列表為5-> 10-> 15-> 20-> 25，并且我們?cè)谀┪蔡砑恿隧?xiàng)目30，則鏈接列表將變?yōu)?-> 10-> 15-> 20-> 25- > 30。?
由于鏈接列表通常由其頭部表示，因此我們必須遍歷該列表直至結(jié)束，然后將最后一個(gè)節(jié)點(diǎn)的下一個(gè)更改為新節(jié)點(diǎn)。
以下是最后添加節(jié)點(diǎn)的6個(gè)步驟。
C
append的時(shí)間復(fù)雜度為O（n），其中n是鏈表中節(jié)點(diǎn)的數(shù)量。由于從頭到尾都有一個(gè)循環(huán)，因此該函數(shù)可以執(zhí)行O（n）。?
還可以通過保留指向鏈表尾部的額外指針，將該方法優(yōu)化為在O（1）中工作。
以下是使用上述所有方法創(chuàng)建鏈表的完整程序。
C ++
#include <bits/stdc++.h>
usingnamespacestd;
classNode?
{?
????public:
????intdata;?
????Node *next;?
};?
voidpush(Node** head_ref, intnew_data)?
{?
????Node* new_node = newNode();
????new_node->data = new_data;?
????new_node->next = (*head_ref);?
????(*head_ref) = new_node;?
}?
voidinsertAfter(Node* prev_node, intnew_data)?
{?
????if(prev_node == NULL)?
????{?
????????cout<<"the given previous node cannot be NULL";?
????????return;?
????}?
????Node* new_node = newNode();
????new_node->data = new_data;?
????new_node->next = prev_node->next;?
????prev_node->next = new_node;?
}?
voidappend(Node** head_ref, intnew_data)?
{?
????Node* new_node = newNode();
????Node *last = *head_ref; /* used in step 5*/
????new_node->data = new_data;?
????new_node->next = NULL;?
????then make the new node as head */
????if(*head_ref == NULL)?
????{?
????????*head_ref = new_node;?
????????return;?
????}?
????while(last->next != NULL)?
????????last = last->next;?
????last->next = new_node;?
????return;?
}?
voidprintList(Node *node)?
{?
????while(node != NULL)?
????{?
????????cout<<" "<<node->data;?
????????node = node->next;?
????}?
}?
int main()?
{?
????Node* head = NULL;?
????append(&head, 6);?
????push(&head, 7);?
????push(&head, 1);?
????append(&head, 4);?
????insertAfter(head->next, 8);?
????cout<<"Created Linked list is: ";?
????printList(head);?
????return 0;?
}
C語言
#include <stdio.h>
#include <stdlib.h>
structNode
{
??intdata;
??structNode *next;
};
voidpush(structNode** head_ref, intnew_data)
{
????structNode* new_node = (structNode*) malloc(sizeof(structNode));
????new_node->data? = new_data;
????new_node->next = (*head_ref);
????(*head_ref)??? = new_node;
}
voidinsertAfter(structNode* prev_node, intnew_data)
{
????/*1. check if the given prev_node is NULL */
????if(prev_node == NULL)
????{
??????printf("the given previous node cannot be NULL");
??????return;
????}
????structNode* new_node =(structNode*) malloc(sizeof(structNode));
????new_node->data? = new_data;
????new_node->next = prev_node->next;
????prev_node->next = new_node;
}
voidappend(structNode** head_ref, intnew_data)
{
????structNode* new_node = (structNode*) malloc(sizeof(structNode));
????structNode *last = *head_ref;? /* used in step 5*/
????new_node->data? = new_data;
??????????it as NULL*/
????new_node->next = NULL;
????if(*head_ref == NULL)
????{
???????*head_ref = new_node;
???????return;
????}
????while(last->next != NULL)
????????last = last->next;
????last->next = new_node;
????return;
}
voidprintList(structNode *node)
{
??while(node != NULL)
??{
?????printf(" %d ", node->data);
?????node = node->next;
??}
}
intmain()
{
??structNode* head = NULL;
??append(&head, 6);
??push(&head, 7);
??push(&head, 1);
??append(&head, 4);
??insertAfter(head->next, 8);
??printf("\n Created Linked list is: ");
??printList(head);
??return0;
}
輸出：
創(chuàng)建的鏈接列表為：1 7 8 6 4
希望本篇文章對(duì)你有幫助~
另外如果你想更好的提升你的編程能力，學(xué)好C語言C++編程！彎道超車，快人一步！筆者這里或許可以幫到你~
UP在主頁(yè)上傳了一些學(xué)習(xí)C/C++編程的視頻教程，有興趣或者正在學(xué)習(xí)的小伙伴一定要去看一看哦！會(huì)對(duì)你有幫助的~
分享（源碼、項(xiàng)目實(shí)戰(zhàn)視頻、項(xiàng)目筆記，基礎(chǔ)入門教程）
歡迎轉(zhuǎn)行和學(xué)習(xí)編程的伙伴，利用更多的資料學(xué)習(xí)成長(zhǎng)比自己琢磨更快哦！
編程學(xué)習(xí)書籍分享：
編程學(xué)習(xí)視頻分享：
