Při implementaci seznamu pomocí pole můžeme podobně jako v případě zásobníku využít statického pole, jehož velikost je dána předem, případně dynamického pole, jehož velikost se upravuje podle potřeby. V případě statického pole musíme předem rozhodnout, jaký nejvyšší počet prvků může být v seznamu současně uložen. Pokud tento počet známe již při implementaci aplikace, může být řešení využívající statického pole velmi efektivní. Je možné také na začátku činnosti aplikace zjistit požadovanou velikost (např. z konfiguračních údajů nebo parametrů spuštění programu), pole o této velikosti vytvořit a dále s ním pracovat již podobně jako se statickým polem.
Z hlediska časové složitosti jsou kritickými operacemi vkládání a rušení prvku uvnitř seznamu. Pro přidání nebo zrušení prvku na konci seznamu totiž stačí pouze aktualizovat informaci o délce seznamu, zatímco na ostatních pozicích je třeba všechny následující prvky přesunout a vytvořit tak místo pro nový prvek, případně naopak zaplnit mezeru po odstraněném prvku. Tento přesun má obecně lineární časovou složitost. Naopak velmi efektivní je v případě reprezentace seznamu polem operace čtení prvku z libovolné pozice vzhledem k tomu, že konkrétní umístění prvku jsme schopni ze znalosti jeho pozice rovnou vypočítat.
Operaci indexOf() zajišťující vyhledání prvku v seznamu můžeme realizovat nejjednodušší metodou lineárního vyhledávání, kdy postupně projdeme všechny prvky v seznamu a porovnáváme je s hledaným klíčem. Složitost této operace je lineární, v nejhorším případě musíme provést tolik kroků porovnání, jaká je délka seznamu. Základní operaci contains() převzatou z rozhraní Collection pak můžeme jednoduše vyjádřit pomocí testování výsledku operace indexOf().
 | Příklad 3.6. Řešený příklad |
Implementujte seznam objektů pomocí statického pole. Velikost statického pole bude parametrem konstruktoru pole a v případě, že bude tato velikost překročena, dojde ke generování výjimky. Při vkládání a rušení prvků dochází vždy k přesunu zbývajících prvků.
public class ArrayList implements List {
public ArrayList(int size) {
_data = new Object[size];
}
public void add(Object obj) {
assert _size<_data.length : "Přetečení seznamu";
_data[_size++] = obj;
}
public void add(int pos, Object obj)
{
assert pos>=0 && pos<=_size : "Pozice mimo rozsah";
assert _size<_data.length : "Přetečení seznamu";
for(int i = _size; i > pos; i--) {
_data[i] = _data[i-1];
}
_data[pos] = obj;
_size++;
}
public void remove(int pos)
{
assert pos>=0 && pos<_size : "Pozice mimo rozsah";
for(int i = pos; i < _size; i++)
_data[i] = _data[i+1];
_size--;
}
public boolean remove(Object elem)
{
int pos = indexOf(elem);
if( pos < 0 ) return false;
remove(pos);
return true;
}
public Object get(int pos)
{
assert pos>=0 && pos<_size : "Pozice mimo rozsah";
return _data[pos];
}
public int indexOf(Object obj)
{
for(int i = 0; i < _size; i++) {
if( obj.equals(_data[i]) ) return i;
}
return -1;
}
public boolean contains(Object obj) {
return indexOf(obj) >= 0;
}
public int size()
{
return _size;
}
protected Object _data[];
protected int _size = 0;
}
|