说实话这个题把我整蒙了。。。
题目中的选项提到了前驱这样的称呼,一般是在双向链表结构中会使用前驱和后继这样的叫法,但是答案解释中却出现了数组下标,所以这个链表到底是顺序存储还是链表存储有点搞不懂了,因为只有当链表是顺序存储结构时,A选项的直接访问节点的复杂度才是1。
目前看来只能认为它所说的前驱指的只是前一个元素的意思?然后这个顺序表是一个顺序存储结构,这样A选项才合理。
但是插入节点的时间复杂度是怎么达到n方的,这个确实没想明白,如果是顺序存储,需要元素串位,如果是链表结构,需要先定位元素,无论哪一种都只要O(n) - 单循环结构就可以了。
然后回答一下题主的问题,删除第i个结点的复杂度为O(n)。
如果是顺序结构,需要保证整体连续,删除一个元素之后,后面的元素需要向前串。
如果是链式结构,需要先定位到需要删除的元素,然后改变前驱后继指向。
回答只为再问一下,这个题目有没有大前提,是在什么情况下讨论的,还有就是为什么是n的平方,希望有回复,谢谢~