Please answer correctly. show code and output of compiled code Linked Lists Reca
ID: 3869561 • Letter: P
Question
Please answer correctly. show code and output of compiled code
Linked Lists
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.
Download the Node and LList classes. You task is to complete the LList class.
implement the set(int k, String s) method: sets x_k to be s.
implement the swap(int p1, int p2) method: swaps 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. Two 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
Add a few lines to the TestLL program to test the find method.
LLIST.JAVA
NODE.JAVA
}
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){ // add a new node with data d at given position // return null if method fails if( position < 0 || position > size){ return null; } 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<size-1; i=i+1){ out += current.getData() + "]->["; current = current.getNext(); } return out+current.getData() +"]"; }NODE.JAVA
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; } }}
Explanation / Answer
TestLL.java class was not provided, so I've written my own tester class.
PROGRAM CODE:
LList.java
package list;
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
if( position < 0 || position > size-1)
return false;
else
{
Node current = head;
int count = 0;
while(count < position){
current = current.getNext();
count += 1;
}
current.setData(d);
return true;
}
}
/* swap method */
public boolean swap(int p1, int p2)
{
if( p1 < 0 || p1 > size-1 || size < 2 || p2 < 0 || p2 > size-1){
return false;
}
else
{
String data1 = get(p1);
String data2 = get(p2);
set(p1, data2);
set(p2, data1);
return true;
}
}
/* 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){
return null;
}
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)
String data = head.getData();
head = head.getNext();
size--;
return data;
}
public String remove(int position){
// remove x_position (return data of x_position)
if(position < 0 || position > size-1)
return null;
size--;
if(position == 0)
return removeFront();
else
{
Node current = head;
int count = 0;
while(count < position-1){
current = current.getNext();
count += 1;
}
String data = current.getNext().getData();
if(current.getNext().getNext() != null)
current.setNext(current.getNext().getNext());
else current.setNext(null);
return data;
}
}
/* 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 current = head;
int count = 0;
while(count < size){
if(current.getData().equals(d))
return count;
current = current.getNext();
count += 1;
}
return -1;
}
@Override
public int compareTo(LList o){
return size - o.size;
}
public static boolean same(LList a, LList b)
{
if(a.compareTo(b) == 0)
{
int count = 0;
int size = a.getSize();
while(count < size)
{
if(!a.get(count).equals(b.get(count)))
return false;
count++;
}
return true;
}
else return false;
}
@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.java
package list;
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;
}
}
TestLL.java
package list;
public class TestLL {
public static void main(String[] args) {
LList list = new LList();
list.addBack("Apple");
list.addFront("Banana");
list.addBack("Orange");
list.addBack("Peach");
System.out.println("List 1: ");
System.out.println(list);
list.set(2, "Grapes");
list.set(0, "Strawberry");
list.add(4, "Pomegranate");
System.out.println(list);
System.out.println("Removing position 2: " + list.remove(2));
System.out.println("Position of Apple: " + list.find("Apple"));
LList list2 = new LList();
list2.addBack("Strawberry");
list2.addBack("Apple");
list2.addBack("Grapes");
list2.addBack("Pomegranate");
list2.addBack("Peach");
System.out.println(" List 2: ");
System.out.println(list2);
list2.swap(3, 4);
System.out.println(list2);
System.out.println("Removing position 2: " + list2.remove(2));
System.out.println(" Size of list 1: " + list.getSize());
System.out.println("Size of list 2: " + list2.getSize());
System.out.println(" Are the two lists same? " + LList.same(list, list2));
}
}
OUTPUT:
List 1:
[Banana]->[Apple]->[Orange]->[Peach]
[Strawberry]->[Apple]->[Grapes]->[Peach]->[Pomegranate]
Removing position 2: Grapes
Position of Apple: 1
List 2:
[Strawberry]->[Apple]->[Grapes]->[Pomegranate]->[Peach]
[Strawberry]->[Apple]->[Grapes]->[Peach]->[Pomegranate]
Removing position 2: Grapes
Size of list 1: 4
Size of list 2: 4
Are the two lists same? true