Java

Linked list class

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  size -1 || head == null){ return null; } int count = 0; Node current = head; while(count  size){ throw new OutOfBoundsException("Cannot add an element with index " + position + "into a list of size " + size); } 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 ["; current = current.getNext(); } return out+current.getData() +"]"; } } 

Node class

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; } } 

OutOfBoundsClass

/** This exception should be thrown whenever a linked list with n elements tries to access an element X_m for any m>=n or m=n or mn or m 
 
 
TestLL class
 
 
 
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 try{ list.add(1, "crow"); }catch(OutOfBoundsException e){ System.out.println(e); } try{ list.add(1, "goat"); }catch(OutOfBoundsException e){ System.out.println(e); } try{ list.add(2, "eel"); }catch(OutOfBoundsException e){ System.out.println(e); } 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")); LList l2 = new LList(new Node("a")); try{ l1.addFront("b").addBack("c").add(1,"d"); l1.addFront("b").addBack("c").add(1,"eeee"); }catch(OutOfBoundsException e){ System.out.println(e); } System.out.println( "l1.compareTo(l2) = " + l1.compareTo(l2)); // uncomment this next line // System.out.println( "same(l1,l2) = " + same(l1,l2)) ; } } 
 
 
 
SetOrList class
 
 
 
 
 
import java.util.HashSet; import java.util.ArrayList; public class SetORList{ public static void main(String[] args){ ArrayList list = new ArrayList(); HashSet set = new HashSet(); int size = 100; System.out.print("making collections... "); for(int i=0; i 
 

Linked Lists and Exceptions Recal that a list is a collection of ordered data x 0. x_1, x 2..... x n-1. Here, the length of the ist is n Dow nload task is to complete tho L OutofBoundsException w henever appropriate. the Node. LList and outofBoundstxception classes. Notice how the ads method in wist throws an exception Your methods as List class by completing the follow ing methods as descrbed below and throw ing an 1. implement the set(int k, String s) method: sets x_k to be s. 2. implement the swap(int pl, int pa) method: sw aps the data in xipt and xp2 3. implement the renoveFront the renoveF ront() method: removes x 0, the list adjusts eself to be length n-1 4. implement the renove(int k) method: removes x_k the list adjusts itself to be length n-1 5. implerment the findtstring s) method: returns first k such that s k s. return-1 if s is not in the list implement the conparete method: ists are compared by their lengths. A longer ist is greater than a shorter ist. Two ists are equal if their lengths are the same. 7. implement a static sane(LLust, , ist b) method that returns true ir both lats are the sare. That is, both lists are the same Dow nload and modify the TestLL program so that it compiles and runs. Add some tests for the find method. Generics All of the classes in the Java Collections Framew ork (JCF) use generics. As we saw w ith the Comparable interface, one purpose of this is that it lets us specify w hich type of objects we are dealing with (we can think of the class as having a parameter that specifies a type inside i). Note that when using generics we can only use reference data types. Java does not allow us to use primtive data types w ith generics (and this is one very good reason we have the primitive w rapper classes). We w? cover generics in more detal in class later