From the 3 variations of linked lists(1.Circular 2. With header and trailer node

Question

From the 3 variations of linked lists(1.Circular 2. With header and trailer nodes, and 3. doubly linked) which would be most appropriate for the following applications?

A. You must search a list for a key and return the keys of the 2 elements that come before it and the keys of the 2 elements that come after it.

B. A text file contains integer elements, one per line, sorted from smallest to largest. You must read the values from the file and create a sorted linked list containing the values.

C. You need a list that is short and frequently becomes empty. You want the optimal implementation for adding an element into the empty list and removing the last element from the list.

Explanation / Answer

a.) Because you want to first find an item, and then return items both before and after the one that was searched for, using a doubly linked list will give you the simplest implementation.

b.) In this case, the data is already sorted, so you only need to insert it into the list, and not re-sort it. In this situation, all three list types would work fine, but a circular linked list will have the smallest memory usage.

c.) In this case you definitely want to use a list with trailer and header nodes, as it will give you the best performance on emptying and adding the first item into a list. This is because it doesn't need to check for empty list conditions, but can use the same code on an empty and partially filled list.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.