摘要:让我们来研究一下单链表的时间复杂度相比于数组,单链表在插入删除节点的时候,不需要移动大量的元素,只需要改变指针的指向,所以我们往往看到好多文章说它的时间复杂度是。所以这种情况下,时间复杂度为。
让我们来研究一下单链表的时间复杂度
相比于数组,单链表在插入删除节点的时候,不需要移动大量的元素,只需要改变指针的指向,所以我们往往看到好多文章说它的时间复杂度是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,且告诉你该结点的地址nodenewNode=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
阅读 3352·2023-04-26 00:39
阅读 3868·2021-09-22 10:02
阅读 2454·2021-08-09 13:46
阅读 1061·2019-08-29 18:40
阅读 1417·2019-08-29 18:33
阅读 721·2019-08-29 17:14
阅读 1474·2019-08-29 12:40
阅读 2917·2019-08-28 18:07