Here are the class definitions of Node and List that implement a linked list. cl
ID: 3880489 • Letter: H
Question
Here are the class definitions of Node and List that implement a linked list. class Node 1 private Node next; private int key: Node (Node nxt, int keyValue); // constructor Node getNext); int getKey) void putNext (Node nxt); class List 1 // 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 ); // 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); / calls the private version, doesn't delete the Node int sum(); int length // calls the private version // calls the private version private int maxElement (Node x); private int sum (Node x); private int length (Node x); 1. Write the function void insertAtTail(int ky). Don't add any class variables to the List class. 2. Write the private iterative function void delete(int ky) using only ONE reference variable that marches along the list (my notes use two reference variables, ref and prev) 3. Write the private recursive function int maxElement (Node x) 4. Write the private recursive function int sum (Node x) to find the sum of the keys stored in a List.Explanation / Answer
1.
void insertAtTail(int ky)
{
// create a new node
Node newnode = new Node(null, ky);
// if the list is empty
if(head == null)
{
// make new_node the new head of te list
head = new_node;
return;
}
// point head to the head of the list
Node trav = head;
// move to the last node
while(trav.getNext() != null)
trav= trav.getNext();
trav.putNext(new_node);
}
2.
// assuming the value of the node is positive
void delete(int ky)
{
// if the list is empty
if(head == null)
return;
// if the node to be deleted is the head node
if(head.getKey() == ky)
// move head to one node right
head = head.next;
else
{
// point trav to the head of the node
Node trav = head;
// traverse through the list
while(trav.getNext() != null)
{
// if the node to be deleted is the next node
if(trav.getNext().getKey() == ky)
trav.putNext(trav.getNext().getNext());
// omve to next node
trav = trav.getNext();
}
}
}
3.
// assuming the value of the node is positive
int maxElement(Node x)
{
// if the current node is empty
if(x == null)
return 0;
else
{
// recursively call the function on the next node
// and get the value of the maximum element in the sub
// list from the next node to the end
int a = maxElement(x.getNext());
// if the current node is smaller than the max element
// in the sub list from the next node to the end
if(a > x.getKey())
return a;
// if the current node is larger than the max element
// in the sub list from the next node to the end
return x.getKey();
}
}
4.
// assuming the value of the node is positive
int sum(Node x)
{
// if the current node is empty
if(x == null)
return 0;
else
{
// recursively call the function to get the sum in the sublist
// from the next node to the end of the list
return x.getKey() + sum(x.getNext());
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.