Question
In: Computer Science
Create a concrete LinkedList class that extends the provided ALinkedList class. You will need to override...
Create a concrete LinkedList class that extends the provided ALinkedList class. You will need to override the extract()method in your class. You can use your main() method for testing your method (although you do not need to provide a main method).
Recall that a list is an ordered collection of data
X_0, X_1, X_2, ..., X_n-1
The extract(int start, int end) method removes all elements
X_start, X_start_1, ..., X_end-1
from the list. It also returns all removed elements as a new list (LinkedList) that retains the same ordering.
For example, if the initial list called animals was
cat, dog, eel, cow, owl, pig, pip
then animals.extract(1,5) would return the new list
dog, eel, cow, owl
and animals would now be the list
cat, pig, pip
The AlinkedList class also has a sort() method that currently does nothing. Complete this method so that it sorts the current linked list (alphabetically).
For example, if there was a list called kids that consisted of
puppy, kitten, cub, leveret, kit, cygnet
then after calling kids.sort(), the list would now be
cub, cygnet, kit, kitten, leveret, puppy
This is the code:
public abstract class ALinkedList{
public Node head;
public Node tail;
public int size;
/** removes and returns the sublist
* [x_start, x_start+1, ..., x_end-1] from the current list
*
* @param start is the starting position of the list to remove.
* You can assume that 0 <= start <= length of list -1.
* @param end is position after the last element to be removed.
* You can assume that start <= end <= length of list.
*/
public abstract ALinkedList extract(int start, int end);
/** Sorts this list
<p>
This method sorts this list lexicographically (alphabetically).
Use the built-in compareTo() in the String class to compare individual
strings in the list.
<p>
You are NOT allowed to use any sort method provided in java.util.Arrays
or java.util.Collections.
*/
public void sort(){}
/* -----------------------------------------
provided code
----------------------------------------- */
/** returns the size of the list
*
* @return the size of the list
*/
public final int size(){ return size; }
public final 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.get();
}
/** add a string to the back of the list
*
* @param s is a string to add to the back of the list
* @return the current list
*/
public final ALinkedList add(String s){
if( size == 0 ){
head = tail = new Node(s, null);
}else{
Node tmp = new Node(s, null);
tail.setNext(tmp);
tail = tmp;
}
size += 1;
return this;
}
public final ALinkedList 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 add(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 from the back */
public final String remove(){
if( tail == null || size == 0 ){ return null; }
String s = tail.get();
if( size == 1){
head = tail = null;
}else{
Node tmp = head;
for(int i=0; i<size-2; i+=1){
tmp = tmp.getNext();
} // at end of loop tmp.getNext() == tail is true
tail = tmp;
tail.setNext(null);
}
size -= 1;
return s;
}
/* remove first string in list */
public final String removeFront(){
if(head == null || size == 0){return null;}
String s = head.get();
if(size == 1){
head = tail = null;
}else{
Node tmp = head;
head = tmp.getNext();
tmp.setNext(null);
}
size -= 1;
return s;
}
/* add string to front of list */
public final ALinkedList addFront(String s){
if(size == 0){
head = tail = new Node(s, null);
}else{
head = new Node(s, head);
}
size += 1;
return this;
}
/* string representation of list */
@Override
public final String toString(){
String s = "[";
Node tmp = head;
for(int i=0; i<size-1; i++){
s += tmp.get() + ", ";
tmp = tmp.getNext();
}
if(size > 0){
s += tmp.get();
}
s += "]";
return s;
}
}
Solutions
Expert Solution
Hi. I have answered this question before. Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks
// LinkedList.java implementing extract method
public class LinkedList extends ALinkedList {
@Override
public ALinkedList extract(int start, int end) {
// validating indices
if (start >= 0 && start < size() && end >= 0 && end <= size()
&& start < end) {
// getting reference to head node
Node temp = head; // current node under process
Node prev = null; // previous of current node
// creating a new list to hold extracted values
LinkedList newList = new LinkedList();
// looping until node at index start is found
for (int i = 0; i < start; i++) {
// storing temp in prev
prev = temp;
// updating temp
temp = temp.getNext();
}
// now looping until the node at end-1 index
for (int i = start; i < end; i++) {
// adding current value to newList
newList.add(temp.get());
// advancing to next node
temp = temp.getNext();
}
// now we have extracted values to new list, just need to adjust the
// links.
if (prev == null) {
// head node has been moved to temp
head = temp;
} else {
// nodes between prev and temp and removed
prev.setNext(temp);
}
// if temp is null, adjusting tail to be prev
if (temp == null) {
tail = prev;
}
// if head became null, setting tail to be null
if (head == null) {
tail = null;
}
// subtracting end-start from size to get the new size
size -= (end - start);
// returning new list
return newList;
}
// invalid indices
return null;
}
}
// ALinkedList.java (modified to implement sort method, also corrected toString() method)
public abstract class ALinkedList {
public Node head;
public Node tail;
public int size;
/**
* removes and returns the sublist [x_start, x_start+1, ..., x_end-1] from
* the current list
*
* @param start
* is the starting position of the list to remove. You can assume
* that 0 <= start <= length of list -1.
* @param end
* is position after the last element to be removed. You can
* assume that start <= end <= length of list.
*/
public abstract ALinkedList extract(int start, int end);
/**
* Sorts this list
*
*
*
* This method sorts this list lexicographically (alphabetically). Use the
* built-in compareTo() in the String class to compare individual strings in
* the list.
*
*
*
* You are NOT allowed to use any sort method provided in java.util.Arrays
* or java.util.Collections.
*/
public void sort() {
// using bubble sort algorithm to sort
boolean sorted = false;
while (!sorted) {
//initially assuming list is sorted
sorted = true;
//taking reference to head
Node temp = head;
for (int i = 0; i < size - 1; i++) {
if (temp.get().compareTo(temp.getNext().get()) > 0) {
// swapping elements at temp and temp.getNext()
String data = temp.get();
temp.set(temp.getNext().get());
temp.getNext().set(data);
// will run the next loop to see if all elements are in
// sorted order
sorted = false;
}
//moving to next node
temp=temp.getNext();
}
}
}
/*
* ----------------------------------------- provided code
* -----------------------------------------
*/
/**
* returns the size of the list
*
* @return the size of the list
*/
public final int size() {
return size;
}
public final 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.get();
}
/**
* add a string to the back of the list
*
* @param s
* is a string to add to the back of the list
* @return the current list
*/
public final ALinkedList add(String s) {
if (size == 0) {
head = tail = new Node(s, null);
} else {
Node tmp = new Node(s, null);
tail.setNext(tmp);
tail = tmp;
}
size += 1;
return this;
}
public final ALinkedList 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 add(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 from the back */
public final String remove() {
if (tail == null || size == 0) {
return null;
}
String s = tail.get();
if (size == 1) {
head = tail = null;
} else {
Node tmp = head;
for (int i = 0; i < size; i++) {
tmp = tmp.getNext();
} // at end of loop tmp.getNext() == tail is true
tail = tmp;
tail.setNext(null);
}
size -= 1;
return s;
}
/* remove first string in list */
public final String removeFront() {
if (head == null || size == 0) {
return null;
}
String s = head.get();
if (size == 1) {
head = tail = null;
} else {
Node tmp = head;
head = tmp.getNext();
tmp.setNext(null);
}
size -= 1;
return s;
}
/* add string to front of list */
public final ALinkedList addFront(String s) {
if (size == 0) {
head = tail = new Node(s, null);
} else {
head = new Node(s, head);
}
size += 1;
return this;
}
/* string representation of list */
@Override
public final String toString() {
String s = "[";
Node tmp = head;
for (int i = 0; i < size-1; i++) {
s += tmp.get() + ", ";
tmp = tmp.getNext();
}
if (size > 0) {
s += tmp.get();
}
s += "]";
return s;
}
}
venereology answered 10 months agoRelated Solutions
Create an ArrayListReview class with one data field of ArrayList and one with LinkedList with the...
Create two child classes, UnderGraduateStudent and GraduateStudent that will extend from the Student class. Override the...
In java Create a class named CellPhoneCase that extends your Case class – it inherits all...
Create 2 derived classes from Clothing class: Pants class Write only necessary constructors Override the wash()...
Consider the following definition of a doubly linked-list: class LinkedList{ public: LinkedList():head(0), tail(0){} ~LinkedList(); void reverse();...
In Java, using the code provided for Class Candle, create a child class that meets the...
i just need the Polygon class Shapes In this lab you will create an interface, and...
Define empty methods in Queue class using LinkedList class in Java ------------------------------------------------------------------------------- //Queue class public class...
Define empty methods in Stack class using LinkedList class in Java ------------------------------------------------------------------------------- //Stack class public class...
This LinkedListUtil class tests various usages of the LinkedList class. The single param is an array...
- During the year, Hepworth Company earned a net income of $59,225. Beginning and ending balances for...
- For python! You walk into a fast food restaurant and order fries, a burger, and a...
- A football is kicked straight up into the air; it hits the ground 3.6 s later....
- Did you view conflict as a negative factor in a relationship? Were you surprised to discover...
- for tax purposes, interest on corporate dept is:
- In elementary school, how might you support the development of media literacy in your classes?
- Problem 6 Exchange rate is currently $1.85 US per 1 British pound. Interest rate is 4%...