We will implement our own version of such a data structure: the List data structure. A List
data structure is a random access variable size data structures that allow elements of the
same type to be added or removed.
The List in Java is implemented as an interface. This means that there can be many
different ways to implement the same behavior.
Java has two general-purpose List implementation the ArrayList and the LinkedList. We are
going to create our own implementation of both. We are going to do this in small steps.
Here is an interface to a simple List data structure:
package nl.saxion.sdp.list;
/**
* Simple List interface
* defining just a few of the operations available in the
* java.util.List interface
*/
public interface List {
/**
* Appends the specified element to the end of this list
*
*
* @param element element to be appended to this list
* @return {@code true}
* @throws NullPointerException if the specified element is null
*/
boolean add(String element);
/**
* Inserts the specified element at the specified position in this list
* Shifts the element currently at that position (if any) and any
* subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws NullPointerException if the specified element is null
* @throws IndexOutOfBoundsException if the index is out of range
* ({@code index < 0 || index > size()})
*/
void add(int index,String element) ;
/**
* Removes all of the elements from this list (optional operation).
* The list will be empty after this call returns.
*/
void clear();
/**
* Returns {@code true} if this list contains the specified element.
*
* @param element element whose presence in this list is to be tested
* @return {@code true} if this list contains the specified element
* @throws NullPointerException if the specified element is null
*/
boolean contains(String element);
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException if the index is out of range
* ({@code index < 0 || index >= size()})
*/
String get(int index) ;
int indexOf(String element);
/**
* Returns {@code true} if this list contains no elements.
*
* @return {@code true} if this list contains no elements
*/
boolean isEmpty();
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one
* from their indices). Returns the element that was removed from the
* list.
*
* @param index the index of the element to be removed
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException if the index is out of range
* ({@code index < 0 || index >= size()})
*/
String remove(int index);
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If this list does not contain
* the element, it is unchanged. Returns {@code true} if this list
* contained the specified element.
*
* @param element element to be removed from this list, if present
* @return {@code true} if this list contained the specified element
* @throws NullPointerException if the specified element is null
*/
boolean remove(String element);
/**
* Replaces the element at the specified position in this list with the
* specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws NullPointerException if the specified element is null
* @throws IndexOutOfBoundsException if the index is out of range
* ({@code index < 0 || index >= size()})
*/
String set(int index, String element);
/**
* Returns the number of elements in this list. If this list contains
* more than {@code Integer.MAX_VALUE} elements, returns
* {@code Integer.MAX_VALUE}.
*
* @return the number of elements in this list
*/
int size();
}
There are multiple ways you can implement a List data structure. One such way is by using
an Java native array to store the data. That is why it is called an ArrayList.
Your assignment is to implement the List in a class using a Java native array to store the elements.
Below is a possible implementation:
package nl.saxion.sdp.list;
public class ArrayList implements List{
@Override
public boolean add(String element) {
return false;
}
@Override
public void add(int index, String element) {
}
@Override
public void clear() {
}
@Override
public boolean contains(String element) {
return false;
}
@Override
public String get(int index) {
return null;
}
@Override
public int indexOf(String element) {
return 0;
}
@Override
public boolean isEmpty() {
return false;
}
@Override
public String remove(int index) {
return "";
}
@Override
public boolean remove(String element) {
return false;
}
@Override
public String set(int index, String element) {
return null;
}
@Override
public int size() {
return 0;
}
}
This implementation does not do anything though. It is your job to give it its behavior.
We are going to this in a Test Drive Way by starting with defining the test cases for the methods in our data structure.
Here is a first test that you can use as a starting point:
package nl.saxion.sdp.list;
import nl.saxion.sdp.list.ArrayList;
import nl.saxion.sdp.list.List;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;
class ArrayListTest {
List list = new ArrayList();
@BeforeEach
public void setup() {
for (int i = 0; i < 3; i++)
list.add("" + i);
}
@Test
public void listOfSize3WhenAddingAnElementAtIndex1ResultsInListOfSize4() {
assertEquals(3,list.size()); // Better to use assumeTrue(list.size() == 3)
list.add(1, "Insert");
assertEquals(4, list.size());
}
}
List interfaceIn an iterative way write:
ArrayList classArrayList class so that the test no longer failsHints:
array as the underlying structure to store the contents of the List