Question

对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为O（1），在给定值为x的结...

对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为O（1），在给定值为x的结点后插入一个新结点的时间复杂度为？

Answer 1

在给定值为x的结点后插入一个新结点的时间复杂度为O（n）。

链表中的数据是以结点来表示的，每个结点的构成：元素（数据元素的映象） +指针（指示后继元素存储位置），元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

以“结点的序列”表示线性表称作线性链表（单链表），单链表是链式存取的结构。

扩展资料：

LinkList和ListNode是不同名字的同一个指针类型（命名的不同是为了概念上更明确）；*LinkList类型的指针变量head表示它是单链表的头指针；ListNode类型的指针变量p表示它是指向某一结点的指针。

typedef char DataType; //假设结点的数据域类型为字符

typedef struct node{ //结点类型定义

DataType data; //结点的数据域

struct node *next;//结点的指针域

}ListNode;

typedef ListNode *LinkList;

ListNode *p;

LinkList head;

Answer 2

O(n),因为需要遍历找x