Linked list class public class LList implements Comparable<LList>{ protected Nod
ID: 3919637 • Letter: L
Question
Linked list class
public class LList implements Comparable<LList>{ 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) throws OutOfBoundsException{ // add a new node with data d at given position if( position < 0 ){ throw new OutOfBoundsException("Cannot add a list item with negative index."); }else if( position > 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 < 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 0; } @Override public String toString(){ if( size == 0 || head == null){ return null; } String out = "["; Node current = head; for(int i=0; i<size-1; i=i+1){ out += current.getData() + "]->["; 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<0, tries to remove/modify an element X_m for any m>=n or m<0, or tries to add an element X_m for any m>n or m<0 */ public class OutOfBoundsException extends Exception{ public OutOfBoundsException(String message){ super(message); } }
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<Integer> list = new ArrayList<Integer>(); HashSet<Integer> set = new HashSet<Integer>(); int size = 100; System.out.print("making collections... "); for(int i=0; i<size; i+=1){ list.add(i); set.add(i); } System.out.println("done!"); long start_time = System.nanoTime(); for(int i=0; i<2*size; i+=1){ set.contains(i); } long set_time = System.nanoTime()-start_time; System.out.println("set time = " + (set_time*1e-9)); start_time = System.nanoTime(); for(int i=0; i<2*size; i+=1){ list.contains(i); } long list_time = System.nanoTime()-start_time; System.out.println("list time = " + (list_time*1e-9)); HashSet<Integer> s = new HashSet<Integer>(); for(int i=0; i<10; i+=1){ s.add(i); } System.out.println(s); java.util.Collections.sort(s); System.out.println(s); } }
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.
Explanation / Answer
Node.java 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;
}
}
---------------------------------------------------------------------------
LLsit.java class:-
public class LList implements Comparable<LList> {
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) throws OutOfBoundsException {
// set data of element at given position to d
// returns true if successful and false otherwise
// if index position is outofbound then throws exception.
if (position < 0) {
throw new OutOfBoundsException("Cannot set a list item at negative index.");
} else if (head == null) {
throw new OutOfBoundsException("List is empty");
} else if (position > size - 1) {
throw new OutOfBoundsException(
"Cannot set an element at index " + position + "into a list of size " + size);
}
int count = 0;
Node node = head;
while (count < position) {
node = node.getNext();
count += 1;
}
if (node != null) {
node.setData(d);
return true;
}
return false;
}
/**
* Swap data at index p1 with the data at index p2. If successfully swapped
* return true else return false And of given indexes are irrelevant then
* throws OutOfBoundsExceptionen.
*
* @param p1
* @param p2
* @return
* @throws OutOfBoundsException
*/
public boolean swap(int p1, int p2) throws OutOfBoundsException {
if (p1 < 0 || p2 < 0) {
throw new OutOfBoundsException("Cannot swap a list item at negative index.");
} else if (head == null) {
throw new OutOfBoundsException("List is empty");
} else if (p1 > size - 1 || p2 > size - 1) {
throw new OutOfBoundsException(
"Cannot swap elements at index " + p1 + " or " + p2 + "into a list of size " + size);
}
int count1 = 0;
Node node1 = head;
while (count1 < p1) {
node1 = node1.getNext();
count1 += 1;
}
int count2 = 0;
Node node2 = head;
while (count2 < p1) {
node2 = node1.getNext();
count2 += 1;
}
if (node1 != null && node2 != null) {
// Swapping of node data using temp variable
String temp = node1.getData();
node1.setData(node2.getData());
node2.setData(temp);
return true;
}
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) throws OutOfBoundsException {
// add a new node with data d at given position
if (position < 0) {
throw new OutOfBoundsException("Cannot add a list item with negative index.");
} else if (position > 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 < 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() throws OutOfBoundsException {
// remove x_0 (return data of x_0)
if (head == null) {
String frontData = head.getData();
head = head.getNext();
size--;
return frontData;
} else {
throw new OutOfBoundsException("List is Empty. So can't remove");
}
}
public String remove(int position) throws OutOfBoundsException {
// remove x_position (return data of x_position)
if (position < 0) {
throw new OutOfBoundsException("Cannot remove a list item at negative index.");
} else if (head == null) {
throw new OutOfBoundsException("List is empty. So can't remove");
} else if (position > size - 1) {
throw new OutOfBoundsException(
"Cannot remove an element at index " + position + "into a list of size " + size);
}
if (position == 0)
return removeFront();
int count = 1;
Node prevNode = head;
Node currentNode = head.getNext();
while (count < position) {
prevNode = currentNode;
currentNode = currentNode.getNext();
count += 1;
}
prevNode.setNext(currentNode.getNext());
size --;
return currentNode.getData();
}
/* 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
Node node = head;
int index = 0;
while (node != null) {
if (node.getData().equals(d))
return index;
node = node.getNext();
index++;
}
return -1;
}
@Override
public int compareTo(LList o) {
// If both list are same sixe then return 0;
// If current list size is greater than given list then return 1
// else -1
return this.size == o.size ? 0 : this.size > o.size ? 1 : -1;
}
public static boolean same(LList a, LList b) {
// Return false any of list is null orr their size are not same.
// Otherwise check all position values are same or not in lists
if (a == null || b == null)
return false;
if (a.size != b.size)
return false;
Node aNode = a.head;
Node bNode = b.head;
while (aNode != null && bNode != null) {
if (!aNode.getData().equals(bNode.getData()))
return false;
aNode = aNode.getNext();
bNode = bNode.getNext();
}
return true;
}
@Override
public String toString() {
if (size == 0 || head == null) {
return null;
}
String out = "[";
Node current = head;
for (int i = 0; i < size - 1; i = i + 1) {
out += current.getData() + "]->[";
current = current.getNext();
}
return out + current.getData() + "]";
}
}
---------------------------------------------------------------------------------------------
OutOfBoundsException.java class
public class OutOfBoundsException extends Exception{
public OutOfBoundsException(String message){
super(message);
}
}
------------------------------------------------------------------------------
TestLL.java 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
try {
list.removeFront();
} catch (OutOfBoundsException e1) {
System.out.println(e1);
}
try {
list.removeFront();
} catch (OutOfBoundsException e1) {
System.out.println(e1);
}
System.out.println("removes : " + list);
// removes
try {
list.remove(3);
} catch (OutOfBoundsException e1) {
System.out.println(e1);
}
try {
list.remove(list.getSize() - 1);
} catch (OutOfBoundsException e1) {
System.out.println(1);
}
System.out.println("removes : " + list);
// remove front add to back
System.out.println("before : " + list);
System.out.println("move front to back ");
try {
list.addBack(list.removeFront());
} catch (OutOfBoundsException e1) {
System.out.println(e1);
}
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) = " + LList.same(l1,l2)) ;
System.out.println("Finding 'c' in list l1 " + l1.find("c"));
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.