在链表中,如果要在已知结点后插入一个新结点,其时间复杂度为多少?
答案解析
核心考点是链表的插入操作时间复杂度。在链表中,如果已知插入位置的前驱结点,插入操作的时间复杂度为O(1),因为只需要修改几个指针即可完成插入。解题思路是直接根据链表插入操作的特点来判断。选项A正确,因为插入操作不需要移动元素,仅需修改指针。选项B、C、D错误,因为它们分别表示线性、对数和平方时间复杂度,不符合链表插入操作的实际时间复杂度。易错点提醒:注意区分在已知结点后插入和在未知位置插入的时间复杂度差异。
正确答案:A