对于长度为n的线性表，建立其对应的单链表的时间复杂度为（）。_

推荐

横竖都是一

本题答案为C。

[解析] 本题主要考查的知识点是单链表的建立。

[要点透析] 无论采用什么方式建立单链表，都需要扫描这n个元素，边扫描边创建单链表中的结点并链接起来，其时间复杂度为O(n)。

编辑于 2019-02-25 14:18:22 回复(0)

clear_rain

选C

我们使用头插式或尾插式创建链表都只需要一次循环遍历就可实现，所以时间复杂度为O(n)。

链表创建参考博客：https://blog.csdn.net/aabb7012086/article/details/80595191

线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储），但是把最后一个数据元素的尾指针指向了首位结点）。

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，链表比较方便插入和删除操作

编辑于 2019-02-22 15:23:11 回复(0)

__sgf__

无论采用什么方式建立单链表，都需要扫描这n个元素，边扫描边创建单链表中的结点并链接起来，其时间复杂度为O(n)。

发表于 2022-01-25 14:49:16 回复(0)

相信光变成光

链接：https://www.nowcoder.com/questionTerminal/357fb0073b6044c2b68c99ff6c05724c?toCommentId=2565680
来源：牛客网

选C

我们使用头插式或尾插式创建链表都只需要一次循环遍历就可实现，所以时间复杂度为O(n)。

链表创建参考博客：https://blog.csdn.net/aabb7012086/article/details/80595191

线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储），但是把最后一个数据元素的尾指针指向了首位结点）。

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，链表比较方便插入和删除操作

编辑于 2019-02-22 18:39:12 回复(0)