Here are the class definitions of Node and List that implement a linked list. cl

Question

Here are the class definitions of Node and List that implement a linked list. class Node f private Node next; private int key; Value // constructor Node(Node nxt, int key Node getNext ); int getKey) void putNext (Node nxt); class List t // assume the class does not use a dummy Node private Node head; List); boolean exists(int ky); // returns true if ky is in the list void insertAtHead(int ky); // inserts at the beginning of the list void insertAtTail(int ky); // inserts at the end of the list int removeFromHead ); void delete(int ky); // delete the element or do nothing if ky doesn't exist int removeSmallest ); I/ removes the Node containing the smallest key // constructor // Returns -1 if the list is empty // and returns that key. Returns -1 if the list is empty // Could be duplicate entries, so remove the first int removeLargest; // removes the Node containing the largest key // and returns that key. Returns -1 if the list is empty // Could be duplicate entries, so remove the first int maxElement ) int sum(O; int length // calls the private version, doesn't delete the Node // calls the private version // calls the private version private int maxElement (Node x); private int sum (Node x); private int length (Node x);

Explanation / Answer

If you post more than 1 question, as per chegg guidleines I have to slve only 1 question.

9.

(a) In an arbitrarily ordered inked list, we have to simply traverse through each element of the list to search for a specific node as we do not know where the node is placed.

So, Time Complexity = O(n)

(b) Even if the linked list is sorted, we can not find the element in less time by applying ninary search algorithm as each time we have to go to the middle element, we have to traverse the list from the head node only.

So, time complexity would be reaching O(n) only.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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