摘要：讓我們來(lái)研究一下單鏈表的時(shí)間復(fù)雜度相比于數(shù)組，單鏈表在插入刪除節(jié)點(diǎn)的時(shí)候，不需要移動(dòng)大量的元素，只需要改變指針的指向，所以我們往往看到好多文章說(shuō)它的時(shí)間復(fù)雜度是。所以這種情況下，時(shí)間復(fù)雜度為。

讓我們來(lái)研究一下單鏈表的時(shí)間復(fù)雜度

相比于數(shù)組，單鏈表在插入刪除節(jié)點(diǎn)的時(shí)候，不需要移動(dòng)大量的元素，只需要改變指針的指向，所以我們往往看到好多文章說(shuō)它的時(shí)間復(fù)雜度是O(1)。但是，這種說(shuō)法是不對(duì)的，應(yīng)該根據(jù)情況而定。

由于這是單鏈表，我們無(wú)法獲取node前一個(gè)節(jié)點(diǎn)的地址，看上去貌似不能刪除這個(gè)結(jié)點(diǎn)。但是，是否刪除這個(gè)節(jié)點(diǎn)只是看這個(gè)節(jié)點(diǎn)的data值是否還存在于鏈表中，因此，我們可以讓鏈表看起來(lái)刪除了node，實(shí)則刪除了結(jié)點(diǎn)node.next.

newNode=node.next;  
node.data=newNode.data;//移交元素  
node.next=newNode.next;//移交指針  
free(newNode);//釋放目標(biāo)刪除結(jié)點(diǎn)后一個(gè)節(jié)點(diǎn)的內(nèi)存  
newNode=NULL;//置空指針 

這樣，看起來(lái)刪除了node結(jié)點(diǎn)，實(shí)際上node.next成了真正的犧牲品。上述操作在O(1)內(nèi)完成。

newNode=NULL;  
newNode.data=newdata;  
newNode.next=node.next;  
node.next=newNode;

首先需要從頭開始向后遍歷，直到找到第index-1個(gè)結(jié)點(diǎn)，這需要O(n)時(shí)間；找到以后，改變指針的指向，這需要O(1)的時(shí)間。所以這種情況下，時(shí)間復(fù)雜度為O(n)。

let i=0; 
let p = head; 
while(head&&i<=index-2)//找到第index-1個(gè)結(jié)點(diǎn)退出  
{  
    p=p.next;  
    i++;  
}  
let q=p.next;//q是第index個(gè)節(jié)點(diǎn)，即要?jiǎng)h除的節(jié)點(diǎn)  
p.next=q.next;//轉(zhuǎn)移指針  
free(q);//釋放內(nèi)存
newNode=NULL;  
newNode.data=newdata;  
newNode.next=node.next;  
node.next=newNode;

首先需要從頭開始向后遍歷，直到找到第index-1個(gè)結(jié)點(diǎn)，這需要O(n)時(shí)間；找到以后，創(chuàng)建新節(jié)點(diǎn)，改變指針的指向，這需要O(1)的時(shí)間。所以這種情況下，時(shí)間復(fù)雜度為O(n)。

let p=head;  
int i=0;  
while(p&&i<=index-2)  
{  
   p=p.next;  
    i++;  
}  
let newNode=NULL;  
newNode.data=newdata;  
newNode.next=p.next;  
p.next=newNode;