一路选择题
一道选择题
If the frequent-used operation done to a link list to access a random selected item with specified index and insert or delete item from the rest,then which of the following is the most suitable structure to save time?
A.Sequential list
B.Double linked list
C.Double linked list with header pointer
D.Linked list
书上答案选A,为啥?
顺序表的查找是常数复杂度,但插入和删除就要移动了,要线性复杂度,而且,如果块很大,这将非常费时
双向链表的查找是线性复杂度,插入删除常数复杂度
链表查找是线性的,插入和删除也是常数复杂度
这题咋比较出来的
我就不明白了,为啥选A
------解决方案--------------------
因为题目说 insert or delete item from the rest。经常是从后面插入和删除,所以移动量小。
If the frequent-used operation done to a link list to access a random selected item with specified index and insert or delete item from the rest,then which of the following is the most suitable structure to save time?
A.Sequential list
B.Double linked list
C.Double linked list with header pointer
D.Linked list
书上答案选A,为啥?
顺序表的查找是常数复杂度,但插入和删除就要移动了,要线性复杂度,而且,如果块很大,这将非常费时
双向链表的查找是线性复杂度,插入删除常数复杂度
链表查找是线性的,插入和删除也是常数复杂度
这题咋比较出来的
我就不明白了,为啥选A
------解决方案--------------------
因为题目说 insert or delete item from the rest。经常是从后面插入和删除,所以移动量小。