A list is an ordered collection, with duplicates allowed. In class we implemente

Question

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 [wel, 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 [l trying to remove item at index 0 index outside of list!

Explanation / Answer

Given below is the completed code. Output shown. Please do rate the answer if it helped. Thank you.

To indent code in eclipse, select code by pressing Ctrl+A and then Ctrl+i

/*
* 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
checkForNull(item);
int index = indexOf(item);
if(index == -1)
return false;
else
{
remove(index);
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)
{
checkIndex(index);
T val = collection[index];
shiftLeft(index + 1); //move all elemtns from index + 1 1 position left
size--;
return val;
}
/*
* 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; i++)
{
collection[i-1] = collection[i];
}
}
}

/*
* 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
checkForNull(item);
Node current = head, previous = null;
while(current != null)
{
if(current.data.equals(item))
break;
previous = current;
current = current.next;
}
  
if(current == null)
return false;
else
{
if(current == head)//removing head node
{
head = head.next;
if(head == null) ///now list is empty
tail = null;
}
else
{
previous.next = current.next;
if(current == tail)
tail = previous;
}
  
size--;
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
checkIndex(index);
Node current = head, previous = null;
for (int i = 0; i < index; i++)
{
previous = current;
current = current.next;
}
  
if(current == head)//removing head node
{
head = head.next;
if(head == null) ///now list is empty
tail = null;
}
else
{
previous.next = current.next;
if(current == tail)
tail = previous;

}
  
size--;
return current.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;
}
}

output

adding 'hello' to the list
[hello]

adding 'world' to the list
[hello, world]

adding 'there' at position 1
[hello, there, world]

adding 'well' at position 0
[well, hello, there, world]

replacing item at position 1 with 'hi'
replaced: hello
[well, hi, there, world]

getting item at position 3
world

does the list contain 'hello'?
no
what is its index?
-1

does the list contain 'hi'?
yes
what is its index?
1

--> 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 out of range!

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.