Question

class LinkListTest
{
    public static void main(String[] args)
    {
        LinkList theList = new LinkList();
        theList.insertFirst(7);
        theList.insertFirst(6);
        theList.insertFirst(5);
        theList.insertFirst(4);
        theList.insertFirst(3);
        theList.insertFirst(2);
        theList.insertFirst(1);

        theList.displayList();
        System.out.println("delete(4)");
        theList.delete(4);

        System.out.println("delete(16)");
        theList.delete(16);

        theList.displayList(); 

        System.out.println("insertAfter(2, 12)");
        theList.insertAfter(2, 12);

        System.out.println("insertAfter(4, 14)");
        theList.insertAfter(4, 14);

        System.out.println("insertAfter(7, 17)");
        theList.insertAfter(7, 17);

        theList.displayList();

        System.out.println("insertLast(20)");
        theList.insertLast(20);

        theList.displayList();

    } 
} 

class Link
{
    public int iData;              // data item
    public Link next;              // next link in list
    // -------------------------------------------------------------
    public Link(int id)             // constructor
    {
        iData = id;                 // initialize data
        next = null;
    }                           
    // -------------------------------------------------------------
    public void displayLink()      // display ourself
    {
        System.out.print(iData +" ");
    }
}  // end class Link
public class LinkList
{
    private Link first;            // ref to first item on list
    // -------------------------------------------------------------
    public LinkList()              // constructor
    { 
        first = null; 
    }           // no items on list yet
    // -------------------------------------------------------------
    public boolean isEmpty()       // true if list is empty
    { 
        return (first==null); 
    }
    // -------------------------------------------------------------
    public void insertFirst(int dd) // insert at start of list
    {                           // make new link
        Link newLink = new Link(dd);
        newLink.next = first;       // newLink --> old first
        first = newLink;            // first --> newLink
    }
    // -------------------------------------------------------------
    public Link deleteFirst()      // delete first item
    {                           // (assumes list not empty)
        Link temp = first;          // save reference to link
        first = first.next;         // delete it: first-->old next
        return temp;          // return deleted link
    }
    // -------------------------------------------------------------
    public void displayList()
    {
        Link current = first;       // start at beginning of list
        while(current != null)      // until end of list,
        {
            current.displayLink();   // print data
            current = current.next;  // move to next link
        }
        System.out.println("");
    }
    // -------------------------------------------------------------
}  // end class LinkList

For methods find and delete the return type is Link not key. The method returns a Link object.

Add these methods to the provided LinkList class:

1-     Key find(int key) returns the link with the specified key or null if not found.

2-     void insertAfter(int afterKey, int newKey) inserts a new link with key newKey after the node with key afterKey. If the afterKey node does not exist, the method just returns. Must call method find(int key).

3-     Key delete(int key) removes and returns the Link with the specified key if the node exists, returns null otherwise.

4-     Link getLast() returns a reference to the last link in the list.

5-     void insertLast(int key) adds a new node with the specified key to the end of the list. Must call method getLAst().

Use LinkListTest.java to test your code.

Answer 1

class Main 
{ 
    Node head;  // head of list 
  
    /* Linked list Node*/
    class Node 
    { 
        int data; 
        Node next; 
        Node(int d) {data = d; next = null; } 
    } 
  
    /* This function is in LinkedList class. Inserts a 
   new Node at front of the list. This method is  
   defined inside LinkedList class shown above */
    public void insertFirst(int new_data) 
    { 
        /* 1 & 2: Allocate the Node & 
                  Put in the data*/
        Node new_node = new Node(new_data); 
      
        /* 3. Make next of new Node as head */
        new_node.next = head; 
      
        /* 4. Move the head to point to new Node */
        head = new_node; 
    } 
  
    /* Inserts a new node after the given prev_node. */
    public void insertAfterUtil(Node prev_node, int new_data) 
    { 
        /* 1. Check if the given Node is null */
        if (prev_node == null) 
        { 
            System.out.println("The given previous node cannot be null"); 
            return; 
        } 
  
        /* 2 & 3: Allocate the Node & 
                  Put in the data*/
        Node new_node = new Node(new_data); 
  
        /* 4. Make next of new Node as next of prev_node */
        new_node.next = prev_node.next; 
  
        /* 5. make next of prev_node as new_node */
        prev_node.next = new_node; 
    } 
    
    public void insertAfter(int afterKey,int newKey){
        Node node = head;
        Node prevNode = null;
        while( node != null ){
            if( node.data == afterKey ){
                prevNode = node;   
            } 
            node = node.next;
        }
        if( prevNode == null ){
            return;
        }
        insertAfterUtil(prevNode,newKey);
    }
     
    /* Appends a new node at the end.  This method is  
       defined inside LinkedList class shown above */
    public void insertLast(int new_data) 
    { 
        /* 1. Allocate the Node & 
           2. Put in the data 
           3. Set next as null */
        Node new_node = new Node(new_data); 
  
        /* 4. If the Linked List is empty, then make the 
              new node as head */
        if (head == null) 
        { 
            head = new Node(new_data); 
            return; 
        } 
  
        /* 4. This new node is going to be the last node, so 
              make next of it as null */
        new_node.next = null; 
  
        /* 5. Else traverse till the last node */
        Node last = head;  
        while (last.next != null) 
            last = last.next; 
  
        /* 6. Change the next of last node */
        last.next = new_node; 
        return; 
    } 
  
    /* This function prints contents of linked list starting from 
        the given node */
    public void displayList() 
    { 
        Node tnode = head; 
        while (tnode != null) 
        { 
            System.out.print(tnode.data+" "); 
            tnode = tnode.next; 
        } 
    } 
    
    /* Given a key, deletes the first occurrence of key in linked list */
    void delete(int key)
    {
        // Store head node
        Node temp = head, prev = null;
 
        // If head node itself holds the key to be deleted
        if (temp != null && temp.data == key)
        {
            head = temp.next; // Changed head
            return;
        }
 
        // Search for the key to be deleted, keep track of the
        // previous node as we need to change temp.next
        while (temp != null && temp.data != key)
        {
            prev = temp;
            temp = temp.next;
        }    
 
        // If key was not present in linked list
        if (temp == null) return;
 
        // Unlink the node from linked list
        prev.next = temp.next;
    }
  
    /* Driver program to test above functions. Ideally this function 
       should be in a separate user class.  It is kept here to keep 
       code compact */
    public static void main(String[] args) 
    { 
        /* Start with the empty list */
        Main llist = new Main(); 
        llist.insertFirst(7); 
        llist.insertFirst(6); 
        llist.insertFirst(5); 
        llist.insertFirst(4); 
        llist.insertFirst(3); 
        llist.insertFirst(2); 
        llist.insertFirst(1);
        llist.displayList(); 
        
        llist.insertAfter(7, 8); 
        System.out.println("\ndelete(4) "); 
        llist.delete(4);
        System.out.println("\ndelete(16) "); 
        llist.delete(16);
        llist.displayList(); 

        System.out.println("\ninsertAfter(2, 12)");
        llist.insertAfter(2, 12);

        System.out.println("insertAfter(4, 14)");
        llist.insertAfter(4, 14);

        System.out.println("insertAfter(7, 17)");
        llist.insertAfter(7, 17);

        llist.displayList();

        System.out.println("\ninsertLast(20)");
        llist.insertLast(20);

        llist.displayList();
    } 
} 

Output: