Question

在具有n个结点的有序单链表中插入一个新结点并保持有序的运算的时间复杂度为（ ）。

A.O(1)
B.O(logn)
C.O(n)
D.O(n2)

Answer 1

【答案】：C
本题考查数据结构基础知识。
在具有n个结点的有序单链表中插入一个新结点时，插入操作本身仅需要修改两个指针，时间主要消耗在顺序地比对需插入的元素与表中元素的大小，从而确定其插入位置。若要插入的元素小于表中的最小元素，则插入该元素时与表中的一个元素进行比较，若要插入的元素大于表中的最大元素，则需要与表中的n个元素全部比较一遍。
因此，单链表中参与比较的元素个数平均为(1+2+…+n+n)/(n+1)，即该操作的时间复杂度为O(n)。