// linked array implementation of list

import java.lang.StringBuilder;

public class ArrayLinkedList2<E> {

    private E[] data;
	private int[] next;
	private int first, last, firstFree, n;

	public static final int EOL = -1;

    @SuppressWarnings({"unchecked"})
	public ArrayLinkedList2(int size) {
        data = (E[]) (new Object[size]);
		next = new int[size];
		for (int i = 0; i < size-1; i++)
			next[i] = i+1;
		next[size-1] = EOL;
		first = EOL;
		last = EOL;
		firstFree = 0;
		n = 0;
	}


	public void insert(int p, E x) {
		if (p >= data.length || p < -1)
			throw new ListException("Invalid position:" + p);

		if (firstFree == -1)
			throw new ListException("List full");

		// new space to use
		int i = firstFree;
		firstFree = next[firstFree];
		n++;

		if (p != EOL) {
            // to inset in fron of given position, move previous
            // element in p elsewhere
			data[i] = data[p];
			// follower of old element 
			next[i] = next[p];
			// now elemen in plave
			data[p] = x;
			// follower of new element points to the position where
            // old element was moved
			next[p] = i;

		} else {
			// inset to end
			data[i] = x;
			next[i] = EOL;
			if (first == EOL)	// in empty also as first
				first = i;
			else
				next[last] = i;	// follwer of the previous last
			last = i;
		}
				
	}


	public E remove(int p) {
		if (p > data.length || p < 0)
            throw new ListException("Invalid position");

		E x = data[p];
		n--;
		if (p == last) {
			// if we remove last element, we need to find second to last
			int q = first;
			while (getNext(q) != last)
				q = getNext(q);
			last = q;
            next[last] = EOL;
			next[p] = firstFree;
			firstFree = p;
		} else {
			// otherwise, move next element in place of removed element
			int q = next[p];
			if (last == q)
				last = p;
			data[p] = data[q];
			next[p] = next[q];
			next[q] = firstFree;
            data[q] = null;
			firstFree = q;
		}
		return x;
	}

	public int first() {
		return first;
	}


	public int last() {
		return last;
	}


	public E getElement(int p) {
		return data[p];
	}

	public int getNext(int p) {
		if (p >= data.length || p < 0)
			throw new ListException("Invalid position");

		return next[p];
	}

	public int size() {
		return n;
	}


}