Java Question

Complete the LList class and build up the TestLL class

a. implement the set(int k, String s) method: sets x_k to be s. b. implement the swap(int p1, int p2) method: swaps the data in x_p1 and x_p2 c. implement the removeFront() method: removes x_0, the list adjusts itself to be length n-1. 3. d. implement the remove(int k) method: removes x_k, the list adjusts itself to be length n-1 e. implement the find(String s) method: returns first k such that s_k = s, return -1 if s is not in the list implement the compareTo method: lists are compared by their lengths. A longer list is greater than a shorter list. Two lists are equal if their lengths are the same. f. implement a static same(LList, a, LList b) method that returns true if both lists are the same (and false otherwise). The notion of same is the intuitive notion of two lists being the same (not the == sense). g. Add a few lines to the TestLL program to test the find method.

h. ArrayList :

Open up a web browser and see what methods the ArrayList class provides. In particular, look at add(E e), add(int index, E e), get(int index), remove(int index), set(int index, E e), and size(). Note, E is the type you specify when creating the ArrayList (as follows):

import java.util.ArrayList; ... /* empty string list (E is String here) * ArrayList slist = new ArrayList();

/* empty integer list (E is Integer here) */ ArrayList ilist = new ArrayList()

1.Modify your TestLL program so that for each linked list in the program you have a mirror list that is an ArrayList. Use the same operations (when applicable) to create the ArrayLists. 2. Overload the same method to take an LList and an ArrayList that checks if two lists are the same.

......................................................................................................................................................................................................................

public class Node{ protected String data; protected Node next; public Node(String d){ this(d, null);} public Node(String d, Node n){ this.data = d; this.next = n; } public String getData(){ return data; } public Node getNext(){ return next; } public void setData(String d){ data = d; } public void setNext(Node n){ next = n;} @Override public String toString(){ return data; } } 

................................................................................................................................................................................................

public class LList implements Comparable{ protected Node head; protected Node tail; protected int size; /* constructors */ public LList(){ head = tail = null; size = 0; } public LList(Node n){ head = tail = n; size = 1; } /* simple getters */ public int getSize(){ return size; } public String get(int position){ // returns data of element at index position // returns null otherwise if( position < 0 || position > size -1 || head == null){ return null; } int count = 0; Node current = head; while(count < position){ current = current.getNext(); count += 1; } return current.getData(); } /* setter */ public boolean set(int position, String d){ // set data of element at given position to d // returns true if successful and false otherwise return false; } /* add elements to the list */ public LList addBack(String d){ // add to back of list Node n = new Node(d); if( size == 0 ){ head = tail = n; }else{ tail.setNext(n); tail = n; } size += 1; return this; } public LList addFront(String d){ // add to front of list Node n = new Node(d, head); head = n; if(size == 0){ tail = n; } size += 1; return this; } public LList add(int position, String d){ // add a new node with data d at given position // return null if method fails if( position < 0 || position > size){ // position is invalid return null; } // check for adding to front or back if( position == 0){ return addFront(d); }else if( position == size ){ return addBack(d); } // find node at index position-1 Node prev = head; int count = 0; while( count < position-1 ){ count += 1; prev = prev.getNext(); } // prev will point to node before Node n = new Node(d, prev.getNext() ); prev.setNext(n); size += 1; return this; } /* remove elements from the list */ public String removeFront(){ // remove x_0 (return data of x_0) return null; } public String remove(int position){ // remove x_position (return data of x_position) return null; } /* find element in list */ public int find(String d){ // return the first index k such that x_k == d // return -1 if d is not in the list return -2; } @Override public int compareTo(LList o){ return size - o.size; } @Override public String toString(){ if( size == 0 || head == null){ return null; } String out = "["; Node current = head; for(int i=0; i 

...........................................................................................................................................................

public class TestLL{ public static void main(String[] args){ // create an empty linked list LList list = new LList(); System.out.print("empty list : "); System.out.println(list); // create a list with one element // list = [cat] list = new LList(new Node("cat")); System.out.print("singleton : "); System.out.println(list); // add some elements to the back and front list.addBack("dog"); list.addFront("owl"); list.addBack("bat"); System.out.print("some adds : "); System.out.println(list); // abritrary adds list.add(1, "crow"); list.add(1, "goat"); list.add(2, "eel"); System.out.print("more adds : "); System.out.println(list); // some gets System.out.println("x0 = " + list.get(0)); System.out.println("x1 = " + list.get(1)); System.out.println("x5 = " + list.get(5)); System.out.println("xn = " + list.get(list.getSize()-1)); // removes list.removeFront(); list.removeFront(); System.out.println("removes : " + list); // removes list.remove(3); list.remove(list.getSize()-1); System.out.println("removes : " + list); // remove front add to back System.out.println("before : " + list); System.out.println("move front to back "); list.addBack( list.removeFront() ); System.out.println("after : " + list); LList l1 = new LList(new Node("a")); l1.addFront("b").addBack("c").add(1,"d"); LList l2 = new LList(new Node("a")); l1.addFront("b").addBack("c").add(1,"eeee"); System.out.println( "l1.compareTo(l2) = " + l1.compareTo(l2)); // uncomment this next line // System.out.println( "same(l1,l2) = " + same(l1,l2)) ; } }