Java Lists A list is an ordered collection, with duplicates allowed. In class we
ID: 3594539 • Letter: J
Question
Java Lists
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
Explanation / Answer
Please find my implementation.
Please let me know in case of any issue.
/*
* 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;
}
}
/*
* 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];
}
}
}
/*
* 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);
}
/*
* test program for lists
*
* can be run with ArrayList or LinkedList
*/
public class Lists
{
public static void main (String [] args)
{
try
{
List<String> words = new ArrayList<String>();
//List<String> words = new LinkedList<String>();
// adding items
System.out.println(" adding 'hello' to the list");
words.add("hello");
System.out.println(words);
System.out.println(" adding 'world' to the list");
words.add("world");
System.out.println(words);
// adding at a specific position
System.out.println(" adding 'there' at position 1");
words.add(1, "there");
System.out.println(words);
System.out.println(" adding 'well' at position 0");
words.add(0, "well");
System.out.println(words);
// replacing
System.out.println(" replacing item at position 1 with 'hi'");
System.out.println("replaced: " + words.set(1, "hi"));
System.out.println(words);
// retrieving
System.out.println(" getting item at position 3");
System.out.println(words.get(3));
// contains and indexOf
System.out.println(" does the list contain 'hello'?");
System.out.println(words.contains("hello") ? "yes" : "no");
System.out.println("what is its index?");
System.out.println(words.indexOf("hello"));
System.out.println(" does the list contain 'hi'?");
System.out.println(words.contains("hi") ? "yes" : "no");
System.out.println("what is its index?");
System.out.println(words.indexOf("hi"));
// removing item
System.out.println(" --> testing remove methods");
System.out.println(words);
System.out.println("removing 'hi'");
words.remove("hi");
System.out.println(words);
// removing at specified index
System.out.println(" removing item at index 1");
System.out.println("removed: " + words.remove(1));
System.out.println(words);
System.out.println(" removing item at index 0");
System.out.println("removed: " + words.remove(0));
System.out.println(words);
// item not in list
System.out.println(" trying to remove 'hello'");
System.out.println("was it removed? " +
((words.remove("hello"))? "yes" : "no"));
System.out.println(words);
System.out.println(" trying to remove 'world'");
System.out.println("was it removed? " +
((words.remove("world"))? "yes" : "no"));
System.out.println(words);
// index out of range
System.out.println(" trying to remove item at index 0");
words.remove(0);
}
catch (IndexOutOfBoundsException e)
{
System.out.println(e.getMessage());
}
}
}
/*
Sample run:
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
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.