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

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

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

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

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

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

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

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

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

首先需要從頭開始向后遍歷，直到找到第index-1個結(jié)點，這需要O(n)時間；找到以后，創(chuàng)建新節(jié)點，改變指針的指向，這需要O(1)的時間。所以這種情況下，時間復(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;