Of the three variations of linked lists (circular, with header and trailer nodes
ID: 3688812 • Letter: O
Question
Of the three variations of linked lists (circular, with header and trailer nodes, and doubly linked), which would be most appropriate for each of the following applications and why in detail?
Do NOT use others, please use your own words.
1. You want to search a list for a key and return the keys of the two elements that come before it and the keys of the two elements that come after it.
2. A text file contains integer elements, one per line, sorted from smallest to larges. You must read the values from the file and create a sorted linked list containing the values.
3. A list is short and frequently becomes empty. You want a list that is optimal for inserting an element into the empty list and deleting the last element from the list.
Explanation / Answer
1. You want to search a list for a key and return the keys of the two elements that come before it and the keys of the two elements that come after it. For this doubly linked list is most appropriate. The reason is, first you'll start from the beginning and keep searching for the key, by moving forward. Once the key is found, you're supposed to return the keys of 2 elements that come before it, and ofcourse two more elements that come after it. Especially, when you want to visit the 2 elements that come before, unless its a doubly linked list, it will be a real hard task to visit the previous nodes. Therefore, doubly linked list is most appropriate, for this case.
2. A text file contains integer elements, one per line, sorted from smallest to larges. You must read the values from the file and create a sorted linked list containing the values. For this a singly linked list is an appropriate choice, the one with a header and a tailer. The given list is readily sorted in a file. So, all you have to do, is read one element at a time, and simply insert at the end of the list. For this you need to update the tail pointer everytime you read an element from the file, and add it to the list. You don't have to make the things complex by using either a circular linked list or doubly linked list. So, singly linked list with a header and tailer nodes is most appropriate in this case.
3. A list is short and frequently becomes empty. You want a list that is optimal for inserting an element into the empty list and deleting the last element from the list. A circular linked list, with a tail pointer will maintain a pointer to the last node. So, when you want to frequently delete last element from the list, its ideal to go with a circular list. Actually, you can also go with a singly linked list with a header and a tailer in this case. The advantage is that, you're not making it circular. And ofcourse, it is also not a bad idea going with a doubly linked list for this, as you want to delete the last element everytime, and when deleting the last element, you need an access for the previous element, that is where you're unlinking to delete the last element. But sometimes, this will be space inefficient. So, the ideal one in this case, is circular linked list.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.