我要招人

去企业版

首页 > 试题广场 >

若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删

[单选题]

若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用( )存储方式最节省运算时间。

```
单链表
```
```
仅有头指针的单循环链表
```
```
双链表
```
```
仅有尾指针的单循环链表
```

查看答案及解析

北辰星（心斋）

1,单链表只能单向遍历，即只能由链表头向链表尾遍历。

2，单循环链表也只能单向遍历：链表头->链表尾->链表头；

对于A,B，C要想在尾端插入结点，需要遍历整个链表。对于D，要插入结点，只要改变一下指针即可，要删除头结点，只要将指针移动到头结点即可。

发表于 2017-07-26 19:56:06 回复(0)

HelloWorld

基本同意观点：

1,单链表只能单向遍历，即只能由链表头向链表尾遍历。

2，单循环链表也只能单向遍历：链表头->链表尾->链表头；

对于A,B，C要想在尾端插入结点，需要遍历整个链表。

对于D，要插入结点，只要改变一下指针即可，要删除头结点，只要删除指针.next的元素即可。

编辑于 2017-09-29 10:28:31 回复(2)

striveyang

选项A、单链表插入最后一个元素需要遍历链表到最后一个元素。

选项B、仅有头指针，删除第一个元素方便，但是末尾插入一个元素同选项A。

选项C、双链表，方便来回遍历但是末尾插入一个元素依旧需要遍历整个链表。

选项D、有尾指针的循环单链表，可以在末尾插入元素后，尾指针移动一次至首结点删除第一个结点。

故D选项最节约运算时间。

发表于 2021-06-26 18:32:10 回复(0)

山风啦

单链表只能单向遍历，所以最好是有尾指针的循环链表，可以从尾指针加一到链表头部（头指针不能减一到尾部，因为是单向遍历）

发表于 2019-11-30 22:45:09 回复(0)

倒霉熊不倒霉

单循环链表不单链表的差异在于循环判断上。循环链表对于单链表的优势在于不需要死板的每次从头结点开始遍历。但是要获取尾节点，任然需要O(n)的时间，只有加了尾指针，才能以O(1)的时间访问到尾部

发表于 2019-10-31 21:42:06 回复(0)

道可道非常道嘤

为什么是D而不是B

因为是循环单链表，

如果只要知道尾指针p，则通过计算一次p->next就能获得头指针；插入和删除算法复杂度O(1)+O(1)

而如果只知道头指针，则需要遍历整个链表来获得尾指针的位置;插入和删除算法复杂度O(1)+O(N)

所以D.仅有尾指针的单循环链表存储方式最节省运算时间

发表于 2019-10-18 22:27:25 回复(0)

fightcindy

A只有头指针，在尾部插入元素，需要找到最后一个元素，删除也要找个某一个元素，时间复杂度O（n）。

B增加尾指针，只能提升插入的效率，不用遍历到尾部。但不能提升删除的效率。

C．D有头指针和尾指针，插入操作为O（1），删除操作为O（n）。

发表于 2019-09-18 11:21:11 回复(0)

大大大🍍

双链表（双向循环链表）
插入删除可以说都是O(1)

只有尾指针的单循环链表删除位O（N）,除非他循环的就是他的前驱指针

发表于 2022-09-16 09:36:13 回复(0)

牛客104329435号

我的第一反应是队列

发表于 2022-07-23 23:58:49 回复(0)

Andrew9646

应该从业务需求考虑，无论那种方式存储元素，首先要找到目标位置，那么首先应该考虑如何找到地址最节省时间，遍历则需要ON，如果有尾指针，则直接读取尾指针对应的位置进行添加，如果是循环链表，那么头节点就在尾节点的下一个，所以只需要两步就能完成数据元素的存储。

发表于 2021-08-28 10:14:06 回复(0)

提交观点

问题信息

链表

上传者：星辰大海的碎片

难度：

10条回答 367收藏 20329浏览

若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删

问题信息

热门推荐

相关试题