We zullen onze eigen versie van zo’n gegevensstructuur implementeren: de gegevensstructuur List. Een List is een datastructuur waar elementen van hetzelfde type kunnen worden toegevoegd of verwijderd.
De List in Java is geïmplementeerd als een Interface [1]. Dit betekent dat er veel verschillende manieren kunnen zijn om hetzelfde gedrag te implementeren.
Java heeft twee algemene List-implementaties, de ArrayList en de LinkedList. We gaan gaan onze eigen implementatie van beide maken. We doen dit in kleine stappen.
Hier is een interface voor een eenvoudige Lijst-gegevensstructuur:
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()})
*/
boolean 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();
}
Er zijn meerdere manieren waarop je de List kunt implementeren. Eén zo’n manier is door een array te gebruiken om de gegevens op te slaan. Daarom wordt het een ArrayList genoemd.
Je opdracht is om een List te implementeren met behulp van eenaArray.
Hieronder staat een mogelijke implementatie:
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 boolean remove(int index) {
return false;
}
@Override
public boolean remove(String element) {
return false;
}
@Override
public String set(int index, String element) {
return null;
}
@Override
public int size() {
return 0;
}
}
Deze implementatie doet echter niets. Het is jouw taak om het zijn gedrag te geven.
We gaan dit op een Test Driven manier doen door te beginnen met het definiëren van de test voor de methoden in onze datastructuur.
Om je in de juiste richting te helpen, is hier een eerste test die je als uitgangspunt kunt gebruiken:
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 testAddElementAtIndex() {
assertEquals(3,list.size());
list.add(1, "Insert");
assertEquals( 4,list.size());
assertEquals( "Insert",list.get(1));
}
}
Op een iteratieve manier ga je dan de volgende stappen doorlopen:
Tips