Question
Add the following methods to ArrayList and LinkedList implementations (code for the ArrayList and LinkedList are below as well as a driver method and interface):
Add the following methods to ArrayList and LinkedList implementations (code for the ArrayList and LinkedList are below as well as a driver method and interface):
public int lastIndexOf (T item);
public boolean removeAll (T item);
public void removeRange (int start, int end);
//Details for methods
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.
Java Lists Lab (This code is complete only needs the 3 methods above)
A list is an ordered collection, with duplicates allowed. In class we implemented methods for adding, replacing, and retrieving an item from a given position, as well as for getting the index of an item. Add methods to remove a specific item and to remove an item at a given index to both ArrayList and LinkedList:
boolean remove (T item);
T remove (int index);
Then compile and run Lists.java. The output that tests the two remove methods should look like this:
--> testing remove methods
[well, hi, there, world]
removing hi
[well, there, world]
removing item at index 1
removed: there
[well, world]
removing item at index 0
removed: well
[world]
trying to remove hello
was it removed? no
[world]
trying to remove world
was it removed? yes
[ ]
trying to remove item at index 0
index outside of list!
//Driver Program
public class Method {
public static void main(String[] args) {
ArrayList
// 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);
System.out.println("The last index of 'a' is " + letters.lastIndexOf('a'));
System.out.println("Let's remove an 'a'");
letters.remove(new Character('a'));
System.out.println(letters);
System.out.println("Let's remove all the 'a's");
letters.removeAll('a');
System.out.println(letters);
System.out.println("The last index of 'a' is " + letters.lastIndexOf('a'));
System.out.println("Let's remove all the 'a's");
letters.removeAll('a');
System.out.println(letters);
System.out.println("Removing items from indices 4 to 6");
}
}
/* * interface for a list * * ordered collection with duplicates allowed */ public interface List{ 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); }
/*
* LinkedList
*
* linked implementation of a list
*
* ordered collection with duplicates allowed
*/
public class LinkedList
{
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;
}
}
/*
* ArrayList
*
* array-based implementation of a list
*
* ordered collection with duplicates allowed
*/
public class ArrayList
{
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 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 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]; } } }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started
