Question

1- Use LinkList. Write removeLast(n). Delete the last occurrence of an item from a linked list. So if the item is 7 and the list is [1,3,7,4,7,3,7,2], the result is [1,3,7,4,7,3,2]

2- Use LinkList. Write removeAll(int n). Deletes all occurrences of an item n from a linked list. So if the item is 7 and the list1 is [1,3,7,4,7,3,2] , then list1.removeAll(7) then list1 becomes [1,3,4,3,2].

Demonstrate by displaying the list contents before and after calling the above methods. Eg:

lst1
[1,3,7,4,7,3,7,2]
lst1.removelast(7)
[1,3,7,4,7,3,2]

lst1.removeall(7)
[1,3,4,3,2]

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

// linkList.java
// demonstrates linked list
// to run this program: C>java LinkListApp
////////////////////////////////////////////////////////////////
class Link
{
public int iData; // data item
public double dData; // data item
public Link next; // next link in list
// -------------------------------------------------------------
public Link(int id, double dd) // constructor
{
iData = id; // initialize data
dData = dd; // ('next' is automatically
} // set to null)
// -------------------------------------------------------------
public void displayLink() // display ourself
{
System.out.print("{" + iData + ", " + dData + "} ");
}
} // end class Link
////////////////////////////////////////////////////////////////
class LinkList
{
private Link first; // ref to first link on list

// -------------------------------------------------------------
public LinkList() // constructor
{
first = null; // no links on list yet
}
// -------------------------------------------------------------
public boolean isEmpty() // true if list is empty
{
return (first==null);
}
// -------------------------------------------------------------
// insert at start of list
public void insertFirst(int id, double dd)
{ // make new link
Link newLink = new Link(id, 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()
{
System.out.print("List (first-->last): ");
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
////////////////////////////////////////////////////////////////

class LinkListApp
{
public static void main(String[] args)
{
LinkList theList = new LinkList(); // make new list

theList.insertFirst(22, 2.99); // insert four items
theList.insertFirst(44, 4.99);
theList.insertFirst(66, 6.99);
theList.insertFirst(88, 8.99);

theList.displayList(); // display list

while( !theList.isEmpty() ) // until it's empty,
{
Link aLink = theList.deleteFirst(); // delete link
System.out.print("Deleted "); // display it
aLink.displayLink();
System.out.println("");
}
theList.displayList(); // display list
} // end main()
} // end class LinkListApp
////////////////////////////////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

Class LinkListAppTest.Java is just for testing. Please do not edit.
class LinkListAppTest
   {
   public static void main(String[] args)                      //  NEW MAIN
      {
      LinkList lst1 = new LinkList();                          //  Since the available add method is a pre-add to the first we go in reverse order
      lst1.insertFirst(8,2);                                   // last digit
      lst1.insertFirst(7,7);                                   // entering next to last
      lst1.insertFirst(6,3);                                   // until we get to the the beginning
      lst1.insertFirst(5,7);
      lst1.insertFirst(4,4);
      lst1.insertFirst(3,7);
      lst1.insertFirst(2,3);
      lst1.insertFirst(1,1);

      System.out.println("lst1");                              //  list the name of the linked-list
      lst1.displayList();                                      //  pre-print the entered list unaltered
      System.out.println("lst1.removeLast(7)");                //  list the action to be taken
      lst1.removeLast(7);                                      //  complete the action to remove the last dData == 7;
      lst1.displayList();                                      //  print list post removal of the last dData == 7;
      System.out.println("1st1.removeAll(7)");                 //  list the action to be taken
      lst1.removeAll(7);                                       //  complete the action to remove all remaining dData == 7;
      lst1.displayList();                                      //  print list post removal of all remaining dData == 7;

      }  // end main()

   }  // end class 

Answer 1

class Link
{
public int iData; // data item
public double dData; // data item
public Link next; // next link in list
// -------------------------------------------------------------
public Link(int id, double dd) // constructor
{
iData = id; // initialize data
dData = dd; // ('next' is automatically
} // set to null)
// -------------------------------------------------------------
public void displayLink() // display ourself
{
System.out.print("{" + iData + ", " + dData + "} ");
}
} // end class Link
////////////////////////////////////////////////////////////////
class LinkList
{
private Link first; // ref to first link on list

// -------------------------------------------------------------
public LinkList() // constructor
{
first = null; // no links on list yet
}
// -------------------------------------------------------------
public boolean isEmpty() // true if list is empty
{
return (first==null);
}
// -------------------------------------------------------------
// insert at start of list
public void insertFirst(int id, double dd)
{ // make new link
Link newLink = new Link(id, 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
}
void removeAll(int key)  
    {  
        // Store head node  
        Link temp = first, prev = null;  
      
        // If head node itself holds the key  
        // or multiple occurrences of key  
        while (temp != null && temp.dData == key)  
        {  
            first = temp.next; // Changed head  
            temp = first;         // Change Temp  
        }  
      
        // Delete occurrences other than head  
        while (temp != null)  
        {  
            // Search for the key to be deleted,  
            // keep track of the previous node  
            // as we need to change 'prev->next'  
            while (temp != null && temp.dData != 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;  
      
            //Update Temp for next iteration of outer loop  
            temp = prev.next;  
        }  
    }  
    
void  removeLast( int key)  
{  
    // Initialize previous of Node to be deleted  
    Link x = null;  
  
    // Start from head and find the Node to be  
    // deleted  
    Link temp = first;  
    while (temp != null)  
    {  
        // If we found the key, update xv  
        if (temp.dData == key)  
            x = temp;  
  
        temp = temp.next;  
    }  
  
    // key occurs at-least once  
    if (x != null)  
    {  
  
        // Copy key of next Node to x  
        x.dData = x.next.dData;  
  
        // Store and unlink next  
        temp = x.next;  
        x.next = x.next.next;  
  
        // Free memory for next  
    }  
  
}     
    
// -------------------------------------------------------------
public void displayList()
{
System.out.print("List (first-->last): ");
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
////////////////////////////////////////////////////////////////

 class LinkListApp
{
public static void main(String[] args)
{
LinkList theList = new LinkList(); // make new list

theList.insertFirst(22, 2.99); // insert four items
theList.insertFirst(44, 4.99);
theList.insertFirst(66, 6.99);
theList.insertFirst(88, 8.99);

theList.displayList(); // display list // display list
} // end main()
} // end class LinkListApp
////////////////////////////////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

public class LinkListAppTest
   {
   public static void main(String[] args)                      //  NEW MAIN
      {
      LinkList lst1 = new LinkList();                          //  Since the available add method is a pre-add to the first we go in reverse order
      lst1.insertFirst(8,2);                                   // last digit
      lst1.insertFirst(7,7);                                   // entering next to last
      lst1.insertFirst(6,3);                                   // until we get to the the beginning
      lst1.insertFirst(5,7);
      lst1.insertFirst(4,4);
      lst1.insertFirst(3,7);
      lst1.insertFirst(2,3);
      lst1.insertFirst(1,1);

      System.out.println("lst1");                              //  list the name of the linked-list
      lst1.displayList();                                      //  pre-print the entered list unaltered
     System.out.println("lst1.removeLast(7)");                //  list the action to be taken
      lst1.removeLast(7);                                      //  complete the action to remove the last dData == 7;
      lst1.displayList();                                      //  print list post removal of the last dData == 7;
      System.out.println("1st1.removeAll(7)");                 //  list the action to be taken
      lst1.removeAll(7);                                       //  complete the action to remove all remaining dData == 7;
      lst1.displayList();                                      //  print list post removal of all remaining dData == 7;

      }  // end main()

   }