Question

Purpose

Purpose is to implement some single linked list methods.

Add methods to the List class

In the ‘Implementation of linked lists’ lecture, review the ‘Dynamic implementation of single linked list’ section. You will be adding new methods to the List class.

Eight new methods are required:

1. new constructor – creates a new single linked list from an array of integers

• e.g.

        int a[] = {1, 2, 3, 4};
        List list = new List(a);

2. toString() – returns a string representing a list, nicely formatted

• e.g.

        System.out.println(list.toString());

• gives a string of comma-separated values, with no comma after the last value. g. for the list above, output would be:

        1, 2, 3, 4

• hint: use the StringBuilder library class for efficiency, as you build the string from the list
• returns the null string “” for an empty list

3. findLast() – returns a reference to the last item in a list, or null if the list is empty

• e.g.

        Item r = list.findLast();

4. insertLast() – creates a new item and inserts it at the end of a list

• e.g.

        list.insertLast(5);

• must work with an empty list

5. removeLast() – removes the last item from a list and returns its info

• e.g.

        int x = list.removeLast();

• report an error and exit if the list is empty
• hint: you can use two references:
• lead – advance this first. Start at the beginning of the list
• lag – follows one item behind lead
• stop when lead references the last item in the list, lag references the item before this one
• be careful to handle the special case of only one item in the list

6. copy() – makes a copy of a list and returns a reference to the new list

• e.g.

        List result = list.copy();

• must not change the list being copied

7. join() – creates a new list that is the result of joining one list to the end of another

• e.g.

        List result = list1.join(list2);

• here, the new result list is the result of joining list2 to the end of list1
• must not change list1 or list2

8. intersect() – creates a new list that is the intersection of one list with another

• e.g.

        List result = list1.intersect(list2);

• here, the new result list is the result of finding every item in list1 that occurs in list2
• hint: assume for simplicity that each list does not contain duplicate items
• must not change list1 or list2

Many classes are given to you

You must write this code in the List class, that implements the single linked list. Other than List, the code provided must not be altered in any way.

Hints

No Java library classes other than StringBuilder are allowed. However you are encouraged to use the List methods as you write your new code, just like in real life.

Your methods should manipulate lists directly. For example, do not convert list to string, use string library methods, then convert string back to list(!)

Run the program to test your completed List class. When correct, save the output as an output.txt text file

Required

Your program must be correct, simple and clear:

• clear, consistent layout and indentation
• you must Javadoc comment every class, method and anything that is not simple and clear.
• clear, meaningful variable and method names

Code Given:

=================================================================================

Tester

public class Tester
{
public static void main()
{
int a[] = {1, 2, 3, 4};
List list1 = new List(a);

int b[] = {6, 5, 4, 3};
List list2 = new List(b);

list1.insertLast(5);
System.out.println("insertLast() gives: " + list1.toString());

list2.removeLast();
System.out.println("removeLast() gives: " + list2.toString());

List result = list2.copy();
System.out.println("copy() gives: " + result.toString());

result = result.join(list2);
System.out.println("join() gives: " + result.toString());

result = list1.intersect(list2);
System.out.println("intersect() gives: " + result.toString());
}
}

=========================================================================================

List

public class List
{
private Item list;

public List()
{
list = null;
}

public void insertFirst(int i)
{
Item r = new Item(i);
r.next = list;
list = r;
}

public int removeFirst()
{
if (isEmpty()) {
System.out.println("Error in removeFirst(): list is empty");
System.err.println("Error in removeFirst(): list is empty");
System.exit(1);
}
Item r = list;
int x = r.info;
list = r.next;
return x;
}

public Boolean isEmpty()
{
return list == null;
}

public int count()
{
int count = 0;
Item r = list;
while (r != null) {
++count;
r = r.next;
}
return count;
}

public void insertAfter(Item p, int i)
{
if (isEmpty() || p == null) {
System.out.println("Error in insertAfter(): list is empty or p not set");
System.err.println("Error in insertAfter(): list is empty or p not set");
System.exit(2);
}
Item r = new Item(i);
r.next = p.next;
p.next = r;
}

public int deleteAfter(Item p)
{
if (p.next == null || p == null) {
System.out.println("Error in deleteAfter(): p not set or is last item");
System.err.println("Error in deleteAfter(): p not set or is last item");
System.exit(3);
}
Item r = p.next;
int x = r.info;
p.next = r.next;
return x;
}

//returns reference to first occurrence of i in list
//returns null if not found
public Item find(int i)
{
if (isEmpty()) {
System.out.println("Error in find(): list is empty");
System.err.println("Error in find(): list is empty");
System.exit(4);
}
Item r = list;
while (r != null && r.info != i)
r = r.next;
return r;
}
}

===========================================================================

Item

public class Item
{
protected int info;
protected Item next;

public Item()
{
info = 0;
next = null;
}

public Item(int i)
{
info = i;
next = null;
}
}

===========================================================================

Also Note that NO JAVA CLASSES OTHER THAN STRINGBUILDER ARE ALLOWED. But, List Methods are allowed.

Answer 1

// Item.java
public class Item
{
   protected int info;
   protected Item next;

   public Item()
   {
       info = 0;
       next = null;
   }

   public Item(int i)
   {
       info = i;
       next = null;
   }
}

//end of Item.java

// List.java

public class List
{
   private Item list;

   public List()
   {
       list = null;
   }
  
   // creates a new single linked list from an array of integers
   public List(int[] a)
   {
       list = null; // set list to null
       Item curr = list; // set curr to list
      
       // loop over the array
       for(int i=0;i<a.length;i++)
       {
           if(curr == null) // list is empty, make a[i] the first element
           {
               list = new Item(a[i]);
               curr = list;
           }else // insert a[i] after curr
           {
               curr.next = new Item(a[i]);
               curr = curr.next;
           }
       }
   }
  

   public void insertFirst(int i)
   {
       Item r = new Item(i);
       r.next = list;
       list = r;
   }

   public int removeFirst()
   {
       if (isEmpty()) {
       System.out.println("Error in removeFirst(): list is empty");
       System.err.println("Error in removeFirst(): list is empty");
       System.exit(1);
       }
       Item r = list;
       int x = r.info;
       list = r.next;
       return x;
   }

   public Boolean isEmpty()
   {
       return list == null;
   }

   public int count()
   {
       int count = 0;
       Item r = list;
       while (r != null) {
       ++count;
       r = r.next;
       }
       return count;
   }

   public void insertAfter(Item p, int i)
   {
       if (isEmpty() || p == null) {
       System.out.println("Error in insertAfter(): list is empty or p not set");
       System.err.println("Error in insertAfter(): list is empty or p not set");
       System.exit(2);
       }
       Item r = new Item(i);
       r.next = p.next;
       p.next = r;
   }

   public int deleteAfter(Item p)
   {
       if (p.next == null || p == null) {
       System.out.println("Error in deleteAfter(): p not set or is last item");
       System.err.println("Error in deleteAfter(): p not set or is last item");
       System.exit(3);
       }
       Item r = p.next;
       int x = r.info;
       p.next = r.next;
       return x;
   }

   //returns reference to first occurrence of i in list
   //returns null if not found
   public Item find(int i)
   {
       if (isEmpty()) {
       //System.out.println("Error in find(): list is empty");
       //System.err.println("Error in find(): list is empty");
       //System.exit(4);
           return null; // empty list i.e i not found, return null
       }
       Item r = list;
       while (r != null && r.info != i)
           r = r.next;
       return r;
   }
  
   // returns a string representing a list, nicely formatted
   public String toString()
   {
       // create a new StringBuilder object
       StringBuilder sb = new StringBuilder();
       Item curr = list; // set curr to list
      
       // loop over list appending curr's info to sb
       while(curr != null)
       {
           sb.append(curr.info);
           if(curr.next != null) // curr is not the last node append comma and a space to sb
               sb.append(", ");
          
           curr = curr.next;
       }
      
       return sb.toString();
   }
  
   // returns a reference to the last item in a list, or null if the list is empty
   public Item findLast()
   {
       if(isEmpty()) // empty list, return null
           return null;
       Item curr = list;
       // loop to get the last element of list
       while(curr.next != null)
           curr = curr.next;
       return curr; // return the last element
   }
  
   // creates a new item and inserts it at the end of a list
   public void insertLast(int val)
   {
       if(isEmpty()) // empty list, make val the first element of list
           insertFirst(val);
       else
       {
           Item last = findLast(); // get the last node of list
           last.next = new Item(val); // create a new node to store val and set it to the next of last node to insert it at the end
       }
   }
  
   // removes the last item from a list and returns its info
   // report an error and exit if the list is empty
   public int removeLast()
   {
       if (isEmpty()) // empty list
       {
           System.out.println("Error in removeLast(): list is empty");
           System.err.println("Error in removeLast(): list is empty");
           System.exit(1);
       }
      
       Item curr = list; // set curr to list
       Item pre = null; // pre is node previous to curr
      
       // loop to get the last node in curr and second last node in pre
       while(curr.next != null)
       {
           pre = curr;
           curr = curr.next;
       }
      
       int x = curr.info; // get the last node's data
       if(pre != null) // list contains more than 1 element
           pre.next = null;
       else // list contains 1 element
           list = null;
       return x;
   }
  
   // makes a copy of a list and returns a reference to the new list
   // must not change the list being copied
   public List copy()
   {
       List result = new List(); // create a new empty List
       // set curr to first node
       Item curr = list;
      
       // loop over the list, inserting curr's data at the end of result
       while(curr != null)
       {
           result.insertLast(curr.info);
           curr = curr.next;
       }
      
       return result;
   }
  
   // creates a new list that is the result of joining one list to the end of another
   // must not change list1 or list2
   public List join(List other)
   {
       List result = new List(); // create a new empty List
      
       // set curr to first node
       Item curr = list;
      
       // loop over the list, inserting curr's data at the end of result
       while(curr != null)
       {
           result.insertLast(curr.info);
           curr = curr.next;
       }
      
       curr = other.list; // set curr to first node of other list
      
       // loop over the other list, inserting curr's data at the end of result
       while(curr != null)
       {
           result.insertLast(curr.info);
           curr = curr.next;
       }
      
       return result;
   }
  
   // creates a new list that is the intersection of one list with another
   // assume for simplicity that each list does not contain duplicate items
   // must not change list1 or list2
   public List intersect(List other)
   {
       List result = new List(); //create an empty List
       Item curr = list; // set curr to first node of list
      
       // loop over the list
       while(curr != null)
       {
           if(other.find(curr.info) != null) // curr's data is present in other, insert curr's data at the end of result
               result.insertLast(curr.info);
          
           curr = curr.next;
       }
      
       return result;
   }
  
  
}
//end of List.java

// Tester.java

public class Tester {
  
   public static void main(String[] args) {

       int a[] = {1, 2, 3, 4};
       List list1 = new List(a);

       int b[] = {6, 5, 4, 3};
       List list2 = new List(b);

       list1.insertLast(5);
       System.out.println("insertLast() gives: " + list1.toString());

       list2.removeLast();
       System.out.println("removeLast() gives: " + list2.toString());

       List result = list2.copy();
       System.out.println("copy() gives: " + result.toString());

       result = result.join(list2);
       System.out.println("join() gives: " + result.toString());

       result = list1.intersect(list2);
       System.out.println("intersect() gives: " + result.toString());
   }

}

//end of Tester.java

Output: