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

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

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

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

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

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

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

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

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

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