For doubly linked lists, there are two variants of the move-to-front and transpose methods (Matthews, Rotem, & Bretholz 1980). A move-to-end method moves an element being accessed to the end from which the search started. For instance, if the doubly linked list is a list of items A B C D and the search starts from the right end to access node C, then the reorganized list is A B D C. If the search for C started from the left end, the resulting list is C A B D. The swapping technique transposes a node with this predecessor also with respect to the end from which the search started (Ng & Oommen 1989). Assuming that only elements of the list are in the data, what is the worst case for a move-to-end doubly linked list when the search is made alternately from the left and from the right? For a swapping list?

Group of answer choices

Since the optimal search requires building the list afterwards, the list has the same length during the search for any letter, and hence the combined length is 14 3 = 42.

Since the optimal search requires building the list beforehand, the list has the same length during the search for any letter, and hence the combined length is 14 8 = 112.

Since the optimal search requires building the list beforehand, the list has the same length during the search for any letter, and hence the combined length is 14 5 = 70.

Since the optimal search requires building the list afterwards, the list has the same length during the search for any letter, and hence the combined length is 14 4 = 56.

Flag this Question

Question 42 pts

The shortest linked list has zero nodes while the longest linked list has only 100,000 nodes

Group of answer choices

True

False

Flag this Question

Question 52 pts

A linked list does not have to be implemented with pointers, it can be implemented with arrays of objects and amusing files.

Group of answer choices

True

False