UNC-CH COMP 410

List ADT (Implemented with Linked Cells)



Overview

You are going to build in Java a general List ADT (LIST) using linked cells to do it. This means do not use arrays to contain the elements stored in the List. It also means do not use any of the code from the Java Collections library to get your work done.

The LIST you will implement will be very similar to the ADT shown in your text. It will have an operation to put an element into the list, to take an element out, and to retrieve an element (without altering the data structure). It will have an operation telling how many elements are stored in the list, and a boolean to tell if it is empty or not. It has an operation to make a fresh, empty list. We have left out the operations shown in the text that search for elements by value.

The class Node below shows how we do linked cells in Java. A linked cell is an object (class instance) that has one (or more) references to other objects of the same class. So a list cell refers to another list cell (the next one in the linked chain).

Note also that our implementation given in outline form below always has at least one node (cell) in it. We are using a single cell as a header; when a brand new list is created and there are no elements stored, there is the one header cell in the list structure; the data value in that node doesnt matter, as the header node is not really data. It serves as an item that will always be there. This approach helps eliminate a lot of null pointer errors. In essence an empty list is not a "null", but a single cell with no next and no prev cells.

We ask that you use the boilerplate code provided and work out of it. You should copy and paste in the boilerplate below and structure it as we described.

Project,package,zip names matter!! It's how we grade your code! A good reference if you get stuck is your text book (pg 75-82).


What to Hand-in

Hand in via Sakai, your eclipse project entitled Assignment0 (see below about zipping instructions and name of zip). Your program must be within a package entitled LinkedListA0 See the ListLinksInterface below for instructions on submitting as an Eclipse project.

PLEASE REMOVE THE ALLTESTS.java, 410LocalChecks.jar, and REMOVE THE JAR FROM BUILD PATH BEFORE ZIPPING!!!(see powerpoint for details)


Interfaces

For uniformity, to aid grading, you must write your program with these specific structures.

Interface LIST_Interface

/**
 * COMP 410
 *
 * Make your class and its methods public!
 * Don't modify this file!
 * Before zipping: PLEASE REMOVE THE ALLTESTS.java, 410LocalChecks.jar, 
 *  and REMOVE THE JAR FROM BUILD PATH BEFORE ZIPPING!!! 
 * (see powerpoint for instructions)
 *
 * Submission directions: Zip your eclipse project folder 
 * (e.g. Assignment0) for this assignment and upload it to Sakai.
 * Please name your zip file youronyen_assignment0.zip 
 * That folder should contain src and bin folders with 
 * your code/classes.
 * Your LinkedList implementation will implement this interface.
 *
*/

package LinkedListA0;
/*
  Interface: The LIST will provide this collection of operations:

  clear:
    in: nothing
    return: void
    effect: list is left with size 0, no elements in it,
            consists of just the original root Node
  size:
    in: nothing
    return: number of elements stored in the list
    effect: no change to list state
  isEmpty:
    in: nothing
    return: boolean, true if the list has no elements in it, true is size is 0
    effect: no change to list state
  insert
    in: a Node element, and an int index
    return: boolean, return true in insert is successful, false otherwise
    effect: the list state will be altered so that the Node element is located at the
            specified index; the list has size bigger by one; all elements that were
            at the specified index or after have been moved down one slot
    error: is index is beyond list size range return false
  remove
    in: an int, the index of the element to take out of the list
    return: boolean.. return true if the remove is successful, false otherwise
    effect: list state is altered in that the Node at the specified index is decoupled
            list size decreases by one
    errors: what if specified index is not in the list? return false
  get
    in: an int, the index of the element item to return
    return: Node, the element stored at index, or null
    effect: no change in state of the list
    error: what if index is not in the list? return null
*/

// ADT operations

public interface LIST_Interface {
    public boolean insert(Node n, int index);
    public boolean remove(int index);
    public Node get(int index);
    public int size();
    public boolean isEmpty();
    public void clear();
}

Class LinkedListImpl

/**
 * COMP 410
 *See inline comment descriptions for methods not described in interface.
 *
*/
package LinkedListA0;

public class LinkedListImpl implements LIST_Interface {
  Node root;//this will be the entry point to your linked list (the head)
  
  public LinkedListImpl(){//this constructor is needed for testing purposes. Please don't modify!
    root=new Node(0); //Note that the root's data is not a true part of your data set!
  }
  
  //implement all methods in interface, and include the getRoot method we made for testing purposes. Feel free to implement private helper methods!
  
  public Node getRoot(){ //leave this method as is, used by the grader to grab your linkedList easily.
    return root;
  }
}


Class Node

/**
 * COMP 410
 * Don't modify this file!
*/

package LinkedListA0;

public class Node { //this is your Node object, these are the Objects in your list
  public double data;
  public Node next; //links this node to the next Node in the List
  public Node prev; //links this node to the preceeding Node in the List (ie this Node is the prev Node's next node)
            //NOTE: use of prev is optional!! You could do this with only using the next Node!
            //See Notes in assignment prompt for details.
  public Node(double data){
    this.data=data;
    this.next=null;
    this.prev=null;
  }
  public String toString(){
    return "data: "+data+"\thasNext: "+(next!=null)+"\t\thasPrev: "+(prev!=null);
  }
  
  /*  Below are "getters" for our testing purposes (don't worry we don't 
      call prev if you don't use it). Please do not modify.  I would advise 
      just referencing the fields of your Nodes since they are public
  */
  public boolean isNode(){ //testing purposes please do not touch!
    return true;
  }
  public double getData(){ //testing purposes please do not touch!
    return data;
  }
  public Node getNext(){ //testing purposes please do not touch
    return next;
  }
  public Node getPrev(){ //testing purposes please do not touch
    return prev;
  }
}

Class LinkedListPlayground

package LinkedListA0;

public class LinkedListPlayground {

  public static void main(String[] args) { 
    /*
     here you can instantiate your LinkedList and play around with it to check
     correctness. We've graciously also provided you a bit of extra test data for debugging.
     It doesn't matter what you have in here. We will not grade it. This is for your use in testing your implementation.
      */
    test1();
    test2();

  }
  
  public static void test1(){
        LinkedListImpl L= new LinkedListImpl();
    System.out.println(L.isEmpty());
    printList(L);
    L.clear();
    System.out.println(L.isEmpty());
    printList(L);
    System.out.println(L.root.toString());
    L.insert(new Node(3.3),0);
    System.out.println(L.isEmpty());
    printList(L);
    System.out.println(L.root.next.toString());
    L.insert(new Node(3.4),0);
    L.insert(new Node(3.5),0);
    L.insert(new Node(3.67),1);
    L.insert(new Node(3.357),0);
    L.insert(new Node(3.333),4);
    System.out.println(L.size());
    printList(L);
    L.remove(3);
    System.out.println(L.size());
    printList(L);
    L.clear();
    L.insert(new Node(3.4),0);
    L.insert(new Node(3.5),0);
    L.insert(new Node(3.67),1);
    L.insert(new Node(3.357),0);
    L.insert(new Node(3.333),3);
    L.remove(0);
    System.out.println(L.size());
    printList(L);
  }
  public static void test2(){
    LinkedListImpl L= new LinkedListImpl();
    L.insert(new Node(3.4),0);
    L.insert(new Node(3.5),1);
    L.insert(new Node(3.67),2);
    L.remove(0);
    System.out.println(L.size());
    printList(L);
  }
  
  public static void printList(LinkedListImpl L){ //note that this is a good example of how to iterate through your linked list
    Node curr=L.root;
    for(int i=-1; i<L.size(); i++) { //-1 b/c the 0th node in list is the one after root. Root is just the entry point!
      System.out.print(curr.data+" --> ");
      curr=curr.next;
    }
    System.out.println();
  }
}

Class RunTests

/**
 * COMP 410
 * Don't modify this file!
 * This file is optional and is only needed to run the Oracle if
 * it is in your build path and the jar is in your project.
*/

package LinkedListA0;
import gradingTools.comp410f16.assignment0.testcases.Assignment0Suite;

public class RunTests {
  public static void main(String[] args){
    Assignment0Suite.main(args);
  }
}


Notes on Operations and Objects

Node

Please note that the use of Node.prev is optional. You could implement this List ADT with linked cells without linking nodes to their predecessor. Some people like to do this for easier iterating and insertion, but to each their own. We only test the resulting structures after calling methods listed in the LIST_Interface we provided. However, don't change the Node class. If you want to forgoe the use of prev, just don't use it but keep the Node object as we handed it to you. Thanks!

size

The size operation simply returns the count of how many elements are in the list. It should be 0 if the list is empty, and always return a 0 or greater. Note the isEmpty() is synonymous with size()==0 .

insert and remove

Note that we wish for you to look out for the edge case of inserting or removing in an index that is not reachable (ie <0 or > size of list) We ask that you return false in these cases. Also when inserting and removing be careful to connect your nodes to the next (and prev if you choose to use) nodes inside the list. You don't want to get a null pointer when iterating, inserting, and removing. See Node object notes above for info on the optional use of prev.




Testing and Output

For testing, use your own test cases in LinkedListPlayground class. We also encourage using the Oracle program for incremental development. Instructions on using the Oracle will be in the form of the ppt presented in class (and posted online). PLEASE REMOVE THE ALLTESTS.java, 410LocalChecks.jar, and REMOVE THE JAR FROM BUILD PATH BEFORE ZIPPING!!! (see powerpoint for instructions)

There is no specific output or runnable class required for this assignment. We assume you will use the "print" capability provided that will assist you in seeing how your code is working.

For grading, we will be using a grading program that will instantiate your objects and perform the LIST ADT operations on it. We will then observe if the functionality of the data structure is as we requested. If you get a "100" on the Oracle. You should be good to go (so long as you are not spamming for this one test set). The order in which ADT operations are performed and what data is entering your list will be different in the official grading script.

Zip Instructions

For COMP 410, you will need to submit every assignment as an archive of your eclipse project in a file named youronyen_assignmentX.zip In Eclipse, after you have completed your program and tested it, do the following: PLEASE REMOVE THE ALLTESTS.java, 410LocalChecks.jar, and REMOVE THE JAR FROM BUILD PATH BEFORE ZIPPING!!!(see powerpoint for details) After that, select the project you wish to export in the Package Explorer (usually on the left-hand side in Eclipse). Right click that project in Package Explorer -> Export... Under the General folder, select Archive File Click "Next" Make sure that your project, and all of it's sub-folders (.settings, bin, and src) are selected in the window on the left, and that .classpath and .project are selected in the right window. Next to "To archive file" click the Browse button to choose where to save your zipped project and what to name it. Double check that "save in zip format" is selected Click Finish, and you are done!