Provide pseudocode to find the last occurrence of a target element in a singly linked list and compare it to the pseudocode given for this method for a doubly linked list.
What will be an ideal response?
Pseudocode: finding the last occurrence of an element in a singly linked list
1. set cursor to head’s successor
2. create a new pointer, temp //this references an element which matches the
target element.
3. while the cursor is not at the tail node
4. if the element field of the cursor node matches the target element
5. let temp point to this node
6. else move cursor to its successor
// loop postcondition: temp references the last occurrence of target element
7. return temp
The cost is ?(n) for the singly linked list implementation because we have to look at all n nodes. For the doubly linked implementation, we would start at the end of the list and work backwards. The first occurrence we find in a backward traversal must be the last. This has a cost of O(n).
You might also like to view...
By creating lookup fields you can help improve the efficiency of the data entry process
Indicate whether the statement is true or false
Which of the following is TRUE about embedding fonts in a presentation?
A) Embedding fonts is a new feature of PowerPoint 2013. B) Embedding fonts ensures that your entire font set on your computer will be installed on another computer. C) Embedding fonts increases the file size of a presentation. D) Embedding fonts in a presentation compresses the file.
Which of the following tools is best suited for comparing the effects of two variables on a formula?
A) Goal Seek B) One-variable data table C) Two-variable data table D) Solver
The DAEMONS array and daemons directory are used to reference and show Linux startup services
Indicate whether the statement is true or false