Question

Java

Here are the class definitions of Node and List that implement a linked list. class Node {private Node next; private int key; Node (Node nxt, int keyValue);//constructor Node getNext(); int getKey(); void putNext(Node nxt);} class List {//assume the class does not use a dummy Node private Node head; List ();//constructor boolean exists (int ky);//returns true if v 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();//Returns -1 if the list is empty void delete(int ky);//delete the element or do nothing if v doesn't exist int removesmallest();//removes the Node containing the smallest key//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();//calls the private version int length();//calls the private version private int maxElement (Node x); private int sum (Node x); private int length Node x);}

Write the function void insertAtTail (int v). Don’t add any class variables to the List class.

Answer 1

I have added function definitions of Node class to understand the things easiy. So, the code that is asked in the question is:

Code:

class Node
{
private Node next;
  
private int key;
  
Node(Node nxt, int keyValue)
{
next = nxt;
key = keyValue;
}
  
Node getNext()
{
return next;
}
  
void putNext(Node nxt)
{
next = nxt;
}
  
int getKey()
{
return key;
}
}

public class List
{
private Node head;
  
void insertAtTail(int v)
{
if(head == null)
{
head = new Node(null, v);
}
  
else
{
Node n = new Node(null, v);

Node tmp = head;
  
while(tmp.getNext()!=null)
tmp = tmp.getNext();
  
tmp.putNext(n);
  
return;
}
}
}

Working:

First, it checks whether the list has a headd node i.e. the list is initialized or not. So, if the head is not initialized, it sets new node as head. So,, as there is only 1 node in the list, I set null to its next while writing the constructor and v is the value that will be set in the 'key' variable.

Now, in the else part. This means the list has at least 1 node. So, the new node will not be the head node but it will be inserted at last. From its constructor it is clear that the new node is supposed to be inserted at last, so its next will contain .... null and the value v is set as key.

Now, I created a node tmp which points to head initially. The purpose of this is to traverse the list till I get last node. So, the loop goes on until it reaches to the last node which is having null as its next. And for that, the newly created node is inserted in its next. So, the newly created node is added at last position.

If there is any confusion regarding this, please comment. I'll clear it for sure. Thank you. :)