ArrayListTest

ArrayList.java

public class ArrayList<T> extends List<KeyItem<T>> {
	private int N;

	/**
	 * constructor
	 * 
	 * @param N
	 *            the array size of the items within the array list
	 */
	public ArrayList(int N) {
		super();
		this.N = N;
	}

	/**
	 * Adds an item to the end of the list
	 * 
	 * @param item
	 *            the item that should be added
	 */
	public void addItem(T item) {
		if (this.first == null)
			this.first = new ListItem<KeyItem<T>>(new KeyItem<T>(N), null);
		ListItem<KeyItem<T>> p = this.first;
		while (!p.key.addItem(item)) {
			if (p.next == null)
				p.next = new ListItem<KeyItem<T>>(new KeyItem<T>(N), null);
			p = p.next;
		}
	}

	/**
	 * Removes the item at a specific index
	 * 
	 * @param index
	 *            the index of the item that should be removed
	 */
	public void removeItem(int index) {
		int rem = index;
		ListItem<KeyItem<T>> p = this.first;
		while (p != null) {
			if (rem < p.key.n) {
				for (int j = rem; j < p.key.array.length; j++)
					if (j + 1 == p.key.array.length)
						p.key.array[j] = null;
					else
						p.key.array[j] = p.key.array[j + 1];
				p.key.n--;
				return;
			} else
				rem -= p.key.n;
			p = p.next;
		}
	}

	/**
	 * Compresses the array list to the minimum needed list items
	 */
	public void compress() {
		// ...
	}
}

ArrayListTest.java

import static org.junit.Assert.*;

import org.junit.Before;
import org.junit.Test;


public class ArrayListTest {
	private ArrayList<String> list;
	
	@Before
	public void setUp() throws Exception {
		this.list = new ArrayList<String>(3);
	}

	@Test
	public void testCompress() {
		for (int i = 1; i <= 8; i++)
			this.list.addItem("Test" + i);
		this.list.removeItem(2);
		this.list.removeItem(4);
		assertEquals("{Test1, Test2, null | 2}, {Test4, Test5, null | 2}, {Test7, Test8, null | 2}", list.toString());
		this.list.compress();
		assertEquals("{Test1, Test2, Test4 | 3}, {Test5, Test7, Test8 | 3}", list.toString());
	}

	@Test
	public void testCompress2() {
		for (int i = 1; i <= 12; i++)
			this.list.addItem("Test" + i);
		this.list.removeItem(2);
		this.list.removeItem(3);
		this.list.removeItem(3);
		this.list.removeItem(4);
		assertEquals("{Test1, Test2, null | 2}, {Test4, null, null | 1}, {Test7, Test9, null | 2}, {Test10, Test11, Test12 | 3}", list.toString());
		this.list.compress();
		assertEquals("{Test1, Test2, Test4 | 3}, {Test7, Test9, Test10 | 3}, {Test11, Test12, null | 2}", list.toString());
	}
	
	@Test
	public void testCompress3() {
		for (int i = 1; i <= 12; i++)
			this.list.addItem("Test" + i);
		this.list.removeItem(6);
		this.list.removeItem(6);
		this.list.removeItem(2);
		this.list.removeItem(2);
		assertEquals("{Test1, Test2, null | 2}, {Test5, Test6, null | 2}, {Test9, null, null | 1}, {Test10, Test11, Test12 | 3}", list.toString());
		this.list.compress();
		assertEquals("{Test1, Test2, Test5 | 3}, {Test6, Test9, Test10 | 3}, {Test11, Test12, null | 2}", list.toString());
	}
	
	@Test
	public void testCompress4() {
		this.list.addItem("Test1");
		this.list.addItem("Test2");
		assertEquals("{Test1, Test2, null | 2}", list.toString());
		this.list.compress();
		assertEquals("{Test1, Test2, null | 2}", list.toString());
		this.list.addItem("Test3");
		assertEquals("{Test1, Test2, Test3 | 3}", list.toString());
		this.list.compress();
		assertEquals("{Test1, Test2, Test3 | 3}", list.toString());
	}
	
	@Test
	public void testCompress5() {
		this.list = new ArrayList<String>(4);
		for (int i = 1; i <= 12; i++)
			this.list.addItem("Test" + i);
		this.list.removeItem(6);
		this.list.removeItem(6);
		this.list.removeItem(2);
		this.list.removeItem(2);
		assertEquals("{Test1, Test2, null, null | 2}, {Test5, Test6, null, null | 2}, {Test9, Test10, Test11, Test12 | 4}", list.toString());
		this.list.compress();
		assertEquals("{Test1, Test2, Test5, Test6 | 4}, {Test9, Test10, Test11, Test12 | 4}", list.toString());
	}
	
	@Test
	public void testCompress6() {
		for (int i = 1; i <= 12; i++)
			this.list.addItem("Test" + i);
		this.list.removeItem(1);
		this.list.removeItem(1);
		this.list.removeItem(2);
		this.list.removeItem(2);
		this.list.removeItem(3);
		this.list.removeItem(3);
		assertEquals("{Test1, null, null | 1}, {Test4, null, null | 1}, {Test7, null, null | 1}, {Test10, Test11, Test12 | 3}", list.toString());
		this.list.compress();
		assertEquals("{Test1, Test4, Test7 | 3}, {Test10, Test11, Test12 | 3}", list.toString());
	}
}

KeyItem.java

public class KeyItem<T> {
	public Object[] array;
	public int n;

	/**
	 * constructor
	 * 
	 * @param N
	 *            the size of the array in the element
	 */
	public KeyItem(int N) {
		this.array = new Object[N];
		this.n = 0;
	}

	/**
	 * Tries to add an element to the key item
	 * 
	 * @param item
	 *            the item that should be added
	 * @return true if it was added, false if it wasn't
	 */
	public boolean addItem(T item) {
		if (this.n < this.array.length) {
			this.array[this.n] = item;
			this.n++;
			return true;
		}
		return false;
	}

	/**
	 * @see java.lang.Object#toString()
	 */
	public String toString() {
		StringBuilder result = new StringBuilder();
		result.append("{");
		for (int i = 0; i < this.array.length; i++) {
			if (this.array[i] != null)
				result.append(this.array[i].toString());
			else
				result.append("null");
			if (i < this.array.length - 1)
				result.append(", ");
		}
		result.append(" | " + this.n + "}");
		return result.toString();
	}
}

List.java

public class List<T> {
	public ListItem<T> first;

	/**
	 * constructor
	 */
	public List() {
		this.first = null;
	}

	/**
	 * Adds an element to the end of the list
	 * 
	 * @param key
	 *            The element that should be inserted
	 */
	protected void add(T key) {
		if (this.first == null)
			this.first = new ListItem<T>(key, null);
		else {
			ListItem<T> p = this.first;
			while (p.next != null)
				p = p.next;
			p.next = new ListItem<T>(key, null);
		}
	}

	/**
	 * @see java.lang.Object#toString()
	 */
	public String toString() {
		ListItem<T> p = this.first;
		StringBuilder result = new StringBuilder();
		while (p != null) {
			result.append(p.key.toString());
			if (p.next != null)
				result.append(", ");
			p = p.next;
		}
		return result.toString();
	}
}

ListItem.java

public class ListItem<T> {
	public T key;
	public ListItem<T> next;

	/**
	 * constructor
	 * 
	 * @param key
	 *            key of the current element
	 * @param next
	 *            next element of the list
	 */
	public ListItem(T key, ListItem<T> next) {
		this.key = key;
		this.next = next;
	}
}