Linked Lists and Exceptions Recall that a list is a collection of ordered data x
ID: 3919282 • Letter: L
Question
Linked Lists and Exceptions
Recall that a list is a collection of ordered data x_0, x_1, x_2, ..., x_n-1. Here, the length of the list is n.
Dow nload the Node , LList and OutOfBoundsException classes. Notice how the add method in LList throws an exception. Your task is to complete the LList class by completing the follow ing methods as described below and throw ing an
OutOfBoundsException whenever appropriate.
-implement the set(int k, String s) method: sets x_k to be s.
-implement the swap(int p1, int p2) method: sw aps the data in x_p1 and x_p2
-implement the removeFront() method: removes x_0, the list adjusts itself to be length n-1.
-implement the remove(int k) method: removes x_k, the list adjusts itself to be length n-1
-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. Tw o lists are
equal if their lengths are the same.
-implement a static same(LList, a, LList b) method that returns true if both lists are the same. That is, both lists are the same
and a_0 = b_0, a_1 = b_1, ..., a_n = b_n
Dow nload and modify the TestLL program so that it compiles and runs. Add some tests for the find method.
ArrayList
The ArrayList is a commonly used class in the the JCF. It implements the list abstract data type (ADT).
https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html
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 follow s):
import java.util.ArrayList; ...
/* empty string list (E is String here) */ ArrayList<String> slist = new ArrayList<String>();
/* empty integer list (E is Integer here) */ ArrayList<Integer> ilist = new ArrayList<Integer>();
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 (w hen applicable) to create the ArrayLists.
2. Overload the same method to take an LList and an ArrayList<String> that checks if two lists are the same.
CLASSES:
LList.java
Node.java
OutofBoundsExeption.java
TestLL.java
THANK YOU.
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;
}
}
------------------------------------------------------------------------------------------------------
LList.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
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)) ;
//Find test
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.