在长度为n(n≥1)的双链表L中,在p结点之前插入一个新结点s的时间复杂度为______。
A. O(1)
B. O(n)
C. O(n2)
D. O(nlog2n)
单向链表要删除某一节点时,必须要先通过遍历的方式找到前驱节点(通过待删除节点序号或按值查找)。若仅仅知道待删除节点,是不能知道前驱节点的,故单链表的增删操作复杂度为O(n)。
双链表(双向链表)知道要删除某一节点p时,获取其前驱节点q的方式为 q = p->prior,不必再进行遍历。故时间复杂度为O(1)。而若只知道待删除节点的序号,则依然要按序查找,时间复杂度仍为O(n)。
单、双链表的插入操作,若给定前驱节点,则时间复杂度均为O(1)。否则只能按序或按值查找前驱节点,时间复杂度为O(n)。
至于查找,二者的时间复杂度均为O(n)。 对于最基本的CRUD操作,双链表优势在于删除给定节点。但其劣势在于浪费存储空间(若从工程角度考量,则其维护性和可读性都更低)。
双链表本身的结构优势在于,可以O(1)地找到前驱节点,若算法需要对待操作节点的前驱节点做处理,则双链表相比单链表有更加便捷的优势。
A
用户登录可进行刷题及查看答案
登录后提交答案