资讯专栏INFORMATION COLUMN

单链表的时间复杂度

gself / 3176人阅读

摘要:让我们来研究一下单链表的时间复杂度相比于数组,单链表在插入删除节点的时候,不需要移动大量的元素,只需要改变指针的指向,所以我们往往看到好多文章说它的时间复杂度是。所以这种情况下,时间复杂度为。

让我们来研究一下单链表的时间复杂度

相比于数组,单链表在插入删除节点的时候,不需要移动大量的元素,只需要改变指针的指向,所以我们往往看到好多文章说它的时间复杂度是O(1)。但是,这种说法是不对的,应该根据情况而定。

O(1)的情况 一个已知头结点的链表,删除某结点,且告诉你该元素的地址node

由于这是单链表,我们无法获取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)内完成。

一个已知头结点的链表,在某结点后面插入新节点,大小为newdata,且告诉你该结点的地址node
newNode=NULL;  
newNode.data=newdata;  
newNode.next=node.next;  
node.next=newNode;
O(n)的情况 一个已知头结点的链表,删除第index个元素

首先需要从头开始向后遍历,直到找到第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个元素前插入一个元素

首先需要从头开始向后遍历,直到找到第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;

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/94412.html

相关文章

发表评论

0条评论

gself

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<