Add the following methods to your ArrayList and LinkedList implementations: publ
ID: 3607264 • Letter: A
Question
Add the following methods to your ArrayList and LinkedList implementations:
public int lastIndexOf (T item);
public boolean removeAll (T item);
public void removeRange (int start, int end);
For removeAll(), the method should return true if the item was in the data structure, false otherwise.
For reoveRange (int start, int end), make the indices both inclusive.
public class Methods
{
public static void main (String [] args)
{
ArrayList<Character> letters = new ArrayList< >();
//LinkedList<Character> letters = new LinkedList< >();
letters.add('J');
letters.add('a');
letters.add('v');
letters.add('a');
letters.add('&');
letters.add('C');
letters.add('+');
letters.add('+');
letters.add('a');
System.out.println("Here are the characters in the data structure:");
System.out.println(letters);
System.out.println("Removing items from indices 4 to 6");
letters.removeRange(4,6);
System.out.println(letters);
}
}
/*
* interface for a list
*
* ordered collection with duplicates allowed
*/
public interface List<T>
{
void add(T item);
boolean remove (T item);
boolean contains(T item);
int size();
String toString();
// list-specific methods
void add (int index, T item);
T get (int index);
T remove (int index);
T set(int index, T item);
int indexOf(T item);
}
/*
* ArrayList
*
* array-based implementation of a list
*
* ordered collection with duplicates allowed
*/
public class ArrayList<T> implements List<T>
{
public static final int DEFAULT_CAPACITY = 10;
private T [] collection;
private int size;
/*
* no-argument constructor
*
* size set to default value
*/
public ArrayList()
{
this(DEFAULT_CAPACITY);
}
/*
* argument constructor
*
* size specified by user
*/
@SuppressWarnings("unchecked")
public ArrayList(int capacity)
{
collection = (T[]) new Object[capacity];
size = 0;
}
/*
* adds item to list
*/
public void add (T item)
{
checkForNull(item);
ensureSpace();
collection[size] = item;
size++;
}
/*
* removes item from list
*
* returns true if item found in list
*/
public boolean remove (T item)
{
checkForNull(item);
for (int i = 0; i < size; i++)
{
if (collection[i].equals(item))
{
shiftLeft(i);
size--;
return true;
}
}
return false;
}
/*
* returns true if item is in list
*/
public boolean contains (T item)
{
for (int i = 0; i < size; i++)
{
if (collection[i].equals(item))
{
return true;
}
}
return false;
}
/*
* returns size of list
*/
public int size()
{
return size;
}
/*
* returns string representation of list
*/
public String toString()
{
if (size == 0)
{
return "[]";
}
String s = "[";
for (int i = 0; i < size; i++)
{
s+= collection[i];
if (i!= size-1)
{
s+= ", ";
}
}
return s + "]";
}
/* list-specific methods */
/*
* adds item at specified index
*/
public void add (int index, T item)
{
checkForNull(item);
checkIndex(index);
ensureSpace();
shiftRight(index);
collection[index] = item;
size++;
}
/*
* replaces item at specified index with new value
*
* returns original value
*/
public T set (int index, T item)
{
checkForNull(item);
checkIndex(index);
T removed = collection[index];
collection[index] = item;
return removed;
}
/*
* removes item at specified index
*
* returns removed item
*/
public T remove (int index)
{
checkIndex(index);
T removed = collection[index];
shiftLeft(index);
size--;
return removed;
}
/*
* returns item at specified index
*/
public T get (int index)
{
if (size == 0)
{
return null;
}
checkIndex(index);
return collection[index];
}
/*
* returns index of specified item
*
* returns -1 if item not in list
*/
public int indexOf (T item)
{
for (int i = 0; i < size; i++)
{
if (item.equals(collection[i]))
{
return i;
}
}
return -1;
}
// Added Method
public void removeRange (int start, int end){
checkIndex(start);
checkIndex(end);
int x = start;
int y = 0;
while(x <= end){
shiftLeft(x);
x++;
}
y = end - start;
size = size - y;
}
/* helper methods */
/*
* doubles size of array if full
*/
private void ensureSpace()
{
if (size == collection.length)
{
@SuppressWarnings("unchecked")
T [] larger = (T[]) new Object[size*2];
for (int i = 0; i < size; i++)
{
larger[i] = collection[i];
}
collection = larger;
}
}
/*
* checks to make sure item isn't null
*/
private void checkForNull (T item)
{
if (item == null)
{
throw new IllegalArgumentException("null not a possible value!");
}
}
/*
* checks to make sure index falls within list
*/
private void checkIndex (int index)
{
if (index < 0 || index >= size)
{
throw new IndexOutOfBoundsException("index outside of list!");
}
}
/*
* shifts items one to right starting at specified index
*/
private void shiftRight (int index)
{
for (int i = size; i > index; i--)
{
collection[i] = collection[i-1];
}
}
/*
* shifts items one to left starting at specified index
*/
private void shiftLeft (int index)
{
for (int i = index; i < size-1; i++)
{
collection[i] = collection[i+1];
}
}
}
/*
* LinkedList
*
* linked implementation of a list
*
* ordered collection with duplicates allowed
*/
public class LinkedList<T> implements List<T>
{
private class Node
{
private T data;
private Node next;
public Node(T item)
{
data = item;
next = null;
}
}
private Node head;
private Node tail;
private int size;
public LinkedList()
{
head = null;
tail = null;
size = 0;
}
/*
* adds item to list
*/
public void add (T item)
{
checkForNull(item);
Node newest = new Node (item);
if (size == 0)
{
head = newest;
}
else
{
tail.next = newest;
}
tail = newest;
size++;
}
/*
* removes item from list
*
* returns true if item found in list
*/
public boolean remove (T item)
{
Node previous = null;
Node current = head;
while (current != null)
{
if(current.data.equals(item)){
current = current.next;
if (previous == null)
previous = current;
else previous.next = current;
size--;
return true;
} else {
previous = current;
current = current.next;
}
}
return false;
}
/*
* returns true if item is in list
*/
public boolean contains (T item)
{
Node current = head;
for (int i = 0; i < size; i++)
{
if (current.data.equals(item))
{
return true;
}
current = current.next;
}
return false;
}
/*
* returns size of list
*/
public int size()
{
return size;
}
/*
* returns string representation of list
*/
public String toString()
{
if (size == 0)
{
return "[ ]";
}
String s = "[";
Node current = head;
while (current.next != null)
{
s+= current.data + ", ";
current = current.next;
}
return s + current.data + "]";
}
/* list-specific methods */
/*
* adds item at specified index
*/
public void add (int index, T item)
{
checkForNull(item);
checkIndex(index);
Node newest = new Node (item);
if (index == 0)
{
newest.next = head;
head = newest;
}
else
{
Node current = getNode(index-1);
newest.next = current.next;
current.next = newest;
}
size++;
}
/*
* replaces item at specified index with new value
*
* returns original value
*/
public T set (int index, T item)
{
checkForNull(item);
checkIndex(index);
Node current = getNode(index);
T removed = current.data;
current.data = item;
return removed;
}
/*
* removes item at specified index
*
* returns removed item
*/
public T remove (int index)
{
checkIndex(index);
if(index == 0) {
Node current = head;
head = head.next;
return current.data;
}
Node current = head;
int i=0;
while(i < index-1){
i++;
current = current.next;
}
Node nextNode = current.next;
current.next = current.next.next;
return nextNode.data;
}
/*
* returns item at specified index
*/
public T get (int index)
{
checkIndex(index);
return getNode(index).data;
}
/*
* returns index of specified item
*
* returns -1 if item not in list
*/
public int indexOf (T item)
{
Node current = head;
for (int i = 0; i < size; i++)
{
if (current.data.equals(item))
{
return i;
}
current = current.next;
}
return -1;
}
/* helper methods */
/*
* checks to make sure item isn't null
*/
private void checkForNull (T item)
{
if (item == null)
{
throw new IllegalArgumentException ("null not a possible value!");
}
}
/*
* checks to make sure index falls within list
*/
private void checkIndex (int index)
{
if (index < 0 || index >= size)
{
throw new IndexOutOfBoundsException("index out of range!");
}
}
/*
* returns pointer to node at specified index
*/
private Node getNode (int index)
{
Node current = head;
for (int i = 0; i < index; i++)
{
current = current.next;
}
return current;
}
}
Explanation / Answer
Hi, I had answered this query earlier. This code contains the implementation of required methods.
Please rate this answer if it helps.
Note: To indent code in Eclipse IDE, you can select the code in each of the java file press "Ctrl + A" and then "Ctrl + i".
The output is as follows
Here are the characters in the data structure:
[J, a, v, a, &, C, +, +, a]
Removing items from indices 4 to 6
[J, a, v, a, +, a]
// ================================== Code ============================================
//======================== List.java ================
/*
* interface for a list
*
* ordered collection with duplicates allowed
*/
public interface List<T>
{
void add(T item);
boolean remove (T item);
boolean contains(T item);
int size();
String toString();
// list-specific methods
void add (int index, T item);
T get (int index);
T remove (int index);
T set(int index, T item);
int indexOf(T item);
//Additions
public int lastIndexOf (T item);
public boolean removeAll (T item);
public void removeRange (int start, int end);
}
//========================= ArrayList.java ===============
/*
* ArrayList
*
* array-based implementation of a list
*
* ordered collection with duplicates allowed
*/
public class ArrayList<T> implements List<T>
{
public static final int DEFAULT_CAPACITY = 10;
private T [] collection;
private int size;
/*
* no-argument constructor
*
* size set to default value
*/
public ArrayList()
{
this(DEFAULT_CAPACITY);
}
/*
* argument constructor
*
* size specified by user
*/
@SuppressWarnings("unchecked")
public ArrayList(int capacity)
{
collection = (T[]) new Object[capacity];
size = 0;
}
/*
* adds item to list
*/
public void add (T item)
{
checkForNull(item);
ensureSpace();
collection[size] = item;
size++;
}
/*
* removes item from list
*
* returns true if item found in list
*/
public boolean remove (T item)
{
// to be implemented
if(size == 0)
return false;
int i = 0;
while(i < size && (!collection[i].equals(item)))
i++;
if(i == size)
return false;
// last element to remove
if(i == size-1) {
collection[i] = null;
size--;
return true;
}
for(int j = i; j<size-1; j++) {
collection[j] = collection[j+1];
}
collection[size-1] = null;
size--;
return true;
}
/*
* returns true if item is in list
*/
public boolean contains (T item)
{
for (int i = 0; i < size; i++)
{
if (collection[i].equals(item))
{
return true;
}
}
return false;
}
/*
* returns size of list
*/
public int size()
{
return size;
}
/*
* returns string representation of list
*/
public String toString()
{
if (size == 0)
{
return "[]";
}
String s = "[";
for (int i = 0; i < size; i++)
{
s+= collection[i];
if (i!= size-1)
{
s+= ", ";
}
}
return s + "]";
}
/* list-specific methods */
/*
* adds item at specified index
*/
public void add (int index, T item)
{
checkForNull(item);
checkIndex(index);
ensureSpace();
shiftRight(index);
collection[index] = item;
size++;
}
/*
* replaces item at specified index with new value
*
* returns original value
*/
public T set (int index, T item)
{
checkForNull(item);
checkIndex(index);
T removed = collection[index];
collection[index] = item;
return removed;
}
/*
* removes item at specified index
*
* returns removed item
*/
public T remove (int index)
{
// to be implemented
if(size == 0 || index < 0 || index >= size())
return null;
T item = collection[index];
for(int i=index; i<size()-1; i++)
collection[i] = collection[i+1];
collection[size()-1] = null;
size--;
return item;
}
/*
* returns item at specified index
*/
public T get (int index)
{
if (size == 0)
{
return null;
}
checkIndex(index);
return collection[index];
}
/*
* returns index of specified item
*
* returns -1 if item not in list
*/
public int indexOf (T item)
{
for (int i = 0; i < size; i++)
{
if (item.equals(collection[i]))
{
return i;
}
}
return -1;
}
/* helper methods */
/*
* doubles size of array if full
*/
private void ensureSpace()
{
if (size == collection.length)
{
@SuppressWarnings("unchecked")
T [] larger = (T[]) new Object[size*2];
for (int i = 0; i < size; i++)
{
larger[i] = collection[i];
}
collection = larger;
}
}
/*
* checks to make sure item isn't null
*/
private void checkForNull (T item)
{
if (item == null)
{
throw new IllegalArgumentException("null not a possible value!");
}
}
/*
* checks to make sure index falls within list
*/
private void checkIndex (int index)
{
if (index < 0 || index >= size)
{
throw new IndexOutOfBoundsException("index outside of list!");
}
}
/*
* shifts items one to right starting at specified index
*/
private void shiftRight (int index)
{
for (int i = size; i > index; i--)
{
collection[i] = collection[i-1];
}
}
/*
* shifts items one to left starting at specified index
*/
private void shiftLeft (int index)
{
for (int i = index; i < size-1; i++)
{
collection[i] = collection[i+1];
}
}
/**
* Returns the index of the specific item from the end of the list
* If the specific item is not found, -1 is returned
*/
public int lastIndexOf (T item) {
int lastIndex = -1;
for (int i = 0; i < size; i++)
{
if (item.equals(collection[i]))
{
lastIndex = i;
}
}
return lastIndex;
}
/**
* Deletes all instances of the specific item in the list.
* Returns True/False when the item is deleted or otherwise
*/
public boolean removeAll (T item) {
boolean retElementDeleted = false;
while (true) {
int index = indexOf(item);
if(index == -1) break;
T deletedElement = remove(index);
if(deletedElement != null) {
retElementDeleted = true;
}
}
return retElementDeleted;
}
/**
* Deletes all the item in the list between the specific range
*/
public void removeRange (int start, int end) {
checkIndex(start);
checkIndex(end);
if(start > end) {
throw new IllegalArgumentException ("Error: Start is greater than end");
}
for(int index = start; index <= end; index++) {
//When the item is deleted, as the nodes shift left, we repeatedly delete the "start" node
remove(start);
}
}
}
//==============LinkedList.java ========================
/*
* LinkedList
*
* linked implementation of a list
*
* ordered collection with duplicates allowed
*/
public class LinkedList<T> implements List<T>
{
private class Node
{
private T data;
private Node next;
public Node(T item)
{
data = item;
next = null;
}
}
private Node head;
private Node tail;
private int size;
public LinkedList()
{
head = null;
tail = null;
size = 0;
}
/*
* adds item to list
*/
public void add (T item)
{
checkForNull(item);
Node newest = new Node (item);
if (size == 0)
{
head = newest;
}
else
{
tail.next = newest;
}
tail = newest;
size++;
}
/*
* removes item from list
*
* returns true if item found in list
*/
public boolean remove (T item)
{
// to be implemented
if(size == 0)
return false;
if(head.data.equals(item)) {
head = head.next;
return true;
}
Node curr = head;
while(curr.next != null && (!curr.next.data.equals(item)))
curr = curr.next;
if(curr.next == null)
return false;
curr.next = curr.next.next;
return true;
}
/*
* returns true if item is in list
*/
public boolean contains (T item)
{
Node current = head;
for (int i = 0; i < size; i++)
{
if (current.data.equals(item))
{
return true;
}
current = current.next;
}
return false;
}
/*
* returns size of list
*/
public int size()
{
return size;
}
/*
* returns string representation of list
*/
public String toString()
{
if (size == 0)
{
return "[ ]";
}
String s = "[";
Node current = head;
while (current.next != null)
{
s+= current.data + ", ";
current = current.next;
}
return s + current.data + "]";
}
/* list-specific methods */
/*
* adds item at specified index
*/
public void add (int index, T item)
{
checkForNull(item);
checkIndex(index);
Node newest = new Node (item);
if (index == 0)
{
newest.next = head;
head = newest;
}
else
{
Node current = getNode(index-1);
newest.next = current.next;
current.next = newest;
}
size++;
}
/*
* replaces item at specified index with new value
*
* returns original value
*/
public T set (int index, T item)
{
checkForNull(item);
checkIndex(index);
Node current = getNode(index);
T removed = current.data;
current.data = item;
return removed;
}
/*
* removes item at specified index
*
* returns removed item
*/
public T remove (int index)
{
// to be implemented
if(size == 0 || index < 0 || index>=size)
return null;
if(index == 0) {
Node t = head;
head = head.next;
return t.data;
}
int i=0;
Node curr = head;
while(i < index-1){
i++;
curr = curr.next;
}
Node t = curr.next;
curr.next = curr.next.next;
return t.data;
}
/*
* returns item at specified index
*/
public T get (int index)
{
checkIndex(index);
return getNode(index).data;
}
/*
* returns index of specified item
*
* returns -1 if item not in list
*/
public int indexOf (T item)
{
Node current = head;
for (int i = 0; i < size; i++)
{
if (current.data.equals(item))
{
return i;
}
current = current.next;
}
return -1;
}
/* helper methods */
/*
* checks to make sure item isn't null
*/
private void checkForNull (T item)
{
if (item == null)
{
throw new IllegalArgumentException ("null not a possible value!");
}
}
/*
* checks to make sure index falls within list
*/
private void checkIndex (int index)
{
if (index < 0 || index >= size)
{
throw new IndexOutOfBoundsException("index out of range!");
}
}
/*
* returns pointer to node at specified index
*/
private Node getNode (int index)
{
Node current = head;
for (int i = 0; i < index; i++)
{
current = current.next;
}
return current;
}
/**
* Returns the index of the specific item from the end of the list
* If the specific item is not found, -1 is returned
*/
public int lastIndexOf (T item) {
Node current = head;
int lastIndex = -1;
for (int i = 0; i < size; i++)
{
if (current.data.equals(item))
{
lastIndex = i;
}
current = current.next;
}
return lastIndex;
}
/**
* Deletes all instances of the specific item in the list.
* Returns True/False when the item is deleted or otherwise
*/
public boolean removeAll (T item) {
boolean retElementDeleted = false;
while (true) {
int index = indexOf(item);
if(index == -1) break;
T deletedElement = remove(index);
if(deletedElement != null) {
retElementDeleted = true;
}
}
return retElementDeleted;
}
/**
* Deletes all the item in the list between the specific range
*/
public void removeRange (int start, int end) {
checkIndex(start);
checkIndex(end);
if(start > end) {
throw new IllegalArgumentException ("Error: Start is greater than end");
}
for(int index = start; index <= end; index++) {
//When the item is deleted, as the nodes shift left, we repeatedly delete the "start" node
remove(start);
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.