Question

求解两道数据结构关于 线性表的问题

1，如果对线性表的运算只有两种，即删除第一个元素，在最后一个元素的后面插入一个新元素，则最好使用____.
A,只有表头指针没有表尾指针的循环单链表
B,只有表尾指针没有表头指针的循环单链表
C,非循环双链表
D,循环双链表
（书上答案选的是B，A，C我能理解书上解释的时间复杂度为O（n）。但是它解释D因为没有特殊的指针指示头结点或尾结点，故从某一结点向固定的方向顺序依次搜索插入和删除的位置，时间复杂度也为O（n）。 这我就不很明白了 循环双链表头结点有指向尾结点的指针啊 不是一下就能找到尾结点的位置吗？还有C选项 如果有指向表尾的尾指针 就一下能找到对吗？）

2，设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用____最省时间。
A,带头结点的循环双链表 B.循环单链表 C.带尾指针的循环单链表 D.单链表
答案是A 这个题为什么就不能选C呢 是不是因为有删除尾结点的操作 需要知道尾结点的前驱 所以不能呢？

两道题感觉差不多 但是两个答案不同 主要想知道为什么答案不能互换呢？
谢谢好心人 初学者真心求助

Answer 1

第一题：
C：如果有指向表尾的尾指针，但是删除第一个元素还得从最后一个元素遍历到第一个元素。
D：循环双链表不一定有头尾指针，所以要插入删除一个元素只能把表遍历一遍。
第二题：
C：删除尾节点后要把尾节点指针指向前一个元素当新表的尾节点，而要找到这个节点没有直接的前驱指针（循环单链表） 你的考虑是正确的。

追问

没有头指针是不是就不知道那一个结点是头结点了？所以会从任意一个结点出发去找 所以要遍历整个链表？但是没有头指针 该怎么知道找到了要找元素的位置呢？

追答

其实头指针主要是为了方便编程（当然也是数据结构的需要），没有头指针一样可以建链表，把第一个节点当头结点，但是添加删除首节点会变得比较麻烦，判断一个元素是不是你要找的结点靠的主要还是结点本身的属性（比如数值）而不是位置，但是我们常常需要在链表头尾进行操作，所以有头尾结点会很方便。