// listan linkitetty taulukkototeutus

import java.util.Vector;

public class ArrayLinkedList<E> {

    // hieman tehokkaampaa (pienellä vakiokertoimella)
    // olisi käyttää suoraan taulukkoa eikä Vectoria

	private Vector<E> data;
	private Vector<Integer> next;
	private int first, last, firstFree, n;

	public static final int EOL = -1;

	public ArrayLinkedList(int size) {
		data = new Vector<E>(size);
		next = new Vector<Integer>(size);
		data.setSize(size);
		next.setSize(size);
		for (int i = 0; i < size-1; i++)
			next.set(i, i+1);
		next.set(size-1, EOL);
		first = EOL;
		last = EOL;
		firstFree = 0;
		n = 0;
	}


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

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

		// tilanvaraus
		int i = firstFree;
		firstFree = next.get(firstFree);
		n++;

		if (p != EOL) {
			// jotta lisäys tulisi annetun aseman eteen, siirretään
			// entinen pois
			data.set(i, data.get(p));
			// vanhan alkion seuraaja entisellään
			next.set(i, next.get(p));
			// uusi alkio paikalleen
			data.set(p, x);
			// uuden seuraajaksi aiemmin p:ssä olleen uusi osoite
			next.set(p, i);

		} else {
			// lisäys listan loppuun
			data.set(i, x);
			next.set(i, EOL);
			if (first == EOL)	// tyhjään listaan myös ensimmäiseksi
				first = i;
			else
				next.set(last, i);	// viimeisen seuraajaksi
			last = i;
		}
				
	}


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

		E x = data.get(p);
		n--;
		if (p == last) {
			// viimeistä alkiota poistettaessa joudutaan lista läpikäymään
			int q = first;
			while (getNext(q) != last)
				q = getNext(q);
			last = q;
			next.set(p, firstFree);
			firstFree = p;
		} else {
			// muuten siirretään seuraava tämän paikalle
			int q = next.get(p);
			if (last == q)
				last = p;
			data.set(p, data.get(q));
			next.set(p, next.get(q));
			next.set(q, firstFree);
			firstFree = q;
		}
		return x;
	}

	public int first() {
		return first;
	}


	public int last() {
		return last;
	}


	public E getElement(int p) {
		return data.get(p);
	}

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

		return next.get(p);
	}

	public int size() {
		return n;
	}

	// sisällön tulostus debuggaustarkoituksiin
	/*
	public String toString() {
		return data + "\n" + next + "\nf" + first + " l" + last + " ff" + firstFree + "\n";
	}
	*/


}