public class TestLL { public static void main(String[] args) { // create an empt
ID: 3919302 • Letter: P
Question
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"));
}
}
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() + "]";
}
}
Generics All of the classes in the Java Colections Framework (JCF) use generics. As we saw w ith the cosparable interface, one purpose of this is that it lats us specify w hich type of objects we are deaing w ith (we can think of the class as having a parameter that spec?ies a type inside it). Note that w hen using generics we can only use reference data types. Java does not alow us to use primitive data types w ith generics (and this is one very good reason we have the primitive w rapper classes). We w ill cover generics in more detail in class later ArrayList The arraylist is a commorly used class in the the JCF It implements the list abstract data type (ADT) https:docs.oracle.comjavase/8idocs/apijavali ArrayList.hm Open up a web brow ser and see what methods the ArrayList class provides. In particular, look at add(E eadint index, E e) get(int index), renove(int index), set(int index, E e?, and size(). Note, E is the type you specify when creating the ArrayList (as follow s) isport java.uts.Arraylist eapty string 1ist ( is String here) ArrayListeString slist new ArraylisteStrin0 eapty integer list (E is Integer here)* ArrayListeinteger ilist new ArrayListeinteger> Modiy your TesELL 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 applcable) to create the ArrayLists. 2. Overload the sase method to take an LList and an ArraylisteString> that checks if tw o lists are the same.Explanation / Answer
here is your answer : ------------------->>>>>>>>>>
LList.java : -----------
import java.util.ArrayList;
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;
}
public static boolean same(LList a, ArrayList<String> 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;
int i = 0;
while (aNode != null && i < b.size()) {
if (!aNode.getData().equals(b.get(i)))
return false;
aNode = aNode.getNext();
i++;
}
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() + "]";
}
}
TestLL.java : ------------------------------
import java.util.ArrayList;
public class TestLL {
public static void main(String[] args) {
// create an empty linked list
LList list = new LList();
ArrayList<String> aList = new ArrayList<>();
System.out.print("empty list : ");
System.out.println(list);
System.out.print("empty ArrayList : ");
System.out.println(aList);
// create a list with one element
// list = [cat]
list = new LList(new Node("cat"));
aList.add("cat");
System.out.print("singleton : ");
System.out.println(list);
System.out.print("singleton ArrayList : ");
System.out.println(aList);
// add some elements to the back and front
list.addBack("dog");
aList.add("dog");
list.addFront("owl");
aList.add(0,"owl");
list.addBack("bat");
aList.add("bat");
System.out.print("some adds : ");
System.out.println(list);
System.out.print("some adds in ArrayList : ");
System.out.println(aList);
// abritrary adds
try {
list.add(1, "crow");
aList.add(1,"crow");
} catch (OutOfBoundsException e) {
System.out.println(e);
}
try {
list.add(1, "goat");
aList.add(1,"goat");
} catch (OutOfBoundsException e) {
System.out.println(e);
}
try {
list.add(2, "eel");
aList.add(2,"eel");
} catch (OutOfBoundsException e) {
System.out.println(e);
}
System.out.print("more adds : ");
System.out.println(list);
System.out.print("more adds in ArrayList : ");
System.out.println(aList);
// 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));
System.out.println("ArrayList x0 = " + aList.get(0));
System.out.println("ArrayList x1 = " + aList.get(1));
System.out.println("ArrayList x5 = " + aList.get(5));
System.out.println("ArrayList xn = " + aList.get(aList.size() - 1));
// removes
try {
list.removeFront();
aList.remove(0);
} catch (OutOfBoundsException e1) {
System.out.println(e1);
}
try {
list.removeFront();
aList.remove(0);
} catch (OutOfBoundsException e1) {
System.out.println(e1);
}
System.out.println("removes : " + list);
System.out.println("removes in ArrayList : " + aList);
// removes
try {
list.remove(3);
aList.remove(3);
} catch (OutOfBoundsException e1) {
System.out.println(e1);
}
try {
list.remove(list.getSize() - 1);
aList.remove(aList.size() - 1);
} catch (OutOfBoundsException e1) {
System.out.println(1);
}
System.out.println("removes : " + list);
System.out.println("removes in ArrayList : " + aList);
// remove front add to back
System.out.println("before : " + list);
System.out.println("before ArrayList : " + aList);
System.out.println("move front to back ");
try {
list.addBack(list.removeFront());
aList.add(aList.remove(0));
} catch (OutOfBoundsException e1) {
System.out.println(e1);
}
System.out.println("after : " + list);
System.out.println("after ArrayList : " + aList);
LList l1 = new LList(new Node("a"));
ArrayList<String> al1 = new ArrayList<>();
al1.add("a");
LList l2 = new LList(new Node("a"));
ArrayList<String> al2 = new ArrayList<>();
al2.add("a");
try {
l1.addFront("b").addBack("c").add(1, "d");
al1.add(0,"b");al1.add("c");al1.add(1,"d");
l2.addFront("b").addBack("c").add(1, "eeee");
al2.add(0,"b");al2.add("c");al2.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( "same(l1,ArrayList l2) = " + LList.same(l1,al2));
System.out.println("Finding 'c' in list l1 " + l1.find("c"));
System.out.println("Finding 'c' in ArrayList al1 " + al1.indexOf("c"));
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.