Matematickým modelem ADT seznam je posloupnost. Jde opět o dynamickou množinu prvků, kde můžeme prvky vkládat a vyjímat na libovolné pozici v posloupnosti.
Příkladem ADT seznam je řádek znaků na obrazovce. Pozici v řádku, místo vložení nebo vyjmutí, tj. vymazání znaku, určuje poloha kurzoru. Pomocí šipek vlevo a vpravo můžeme polohu kurzoru změnit na předcházející nebo následující znak, stisknutím klávesy se znakem vložíme znak, pomocí funkční klávesy Del vyjmeme znak, pomocí funkční klávesy Home přesuneme kurzor na začátek řádku, atd.
Pokud na ADT zásobník a fronta nahlížíme jako na posloupnosti vložených prvků, v případě zásobníku se vkládání a vyjímání prvků uskutečňuje na jednom konci posloupnosti a v případě fronty se prvky vkládají na jednom konci a vybírají na druhém konci. ADT seznam je tedy ve srovnání s ADT zásobník a fronta, daleko flexibilnější.
ADT seznam reprezentujeme posloupností nula nebo více prvků daného typu a zapisujeme v závorkách
( ) (e1) (e1, e2 ) (e1,e2,..., en)
kde n >= 0 je délka seznamu. Je-li n >= 1 je e1 první prvek seznamu a en poslední prvek. Je-li n = 0 máme prázdný seznam.
Důležitou vlastností seznamu je seřazení jeho prvků. Seřazení je definováno relací následování na množině prvků seznamu
ei následuje ei-1, i = 2,3, ..., n
nebo ekvivalentně relací předcházení
ei předchází ei+1, i = 1,2, ..., n-1.
Horní index i reprezentuje pozici prvku v posloupnosti ve smyslu pořadí prvku v posloupnosti, tj. první, druhý, ..., i-tý, ..., poslední.
Uvažujme seznam (a, b, c, d). Vložením prvku x na a pozici i=3 vznikne seznam (a, b, x, c, d), dalším vložením prvku y na stejnou pozici vznikne seznam (a, b, y, x, c, d). Zrušením prvku na pozici i=3 v tomto seznamu dostaneme seznam (a, b, x, c, d).
Pro definici rozhraní ADT seznam zůstává určit signatury metod. Na to musíme rozhodnout o reprezentaci pozice v seznamu. V uvedeném přikladu jsme tak činili explicitně pomocí pořadí prvku v seznamu. Na druhé straně v případě řádku na obrazovce se operace vkládání a mazání znaku vykonávají na implicitní pozici určované okamžitou polohou kurzoru, stručně budeme mluvit o okamžité pozici. V tomto případě pozice nebude parametrem metod implementujících operace ADT seznam, protože je uchovávána spolu se seznamem, a proto její typ nebude vystupovat v signaturách metod.
Rozhraní ADT seznam pro seznam prvků s klíčem typu int je definováno na obr..
Poskytuje-li toto rozhraní seznam s , potom odstranění všech výskytů prvku x, můžeme napsat jako fragment klientského programu
if(!s.jePrazdny()) {
s.naZacatek();
boolean konec=false;
while (!konec) {
konec = s.jePosledni();
if(s.ctiKlic() == x)
s.vyber();
else
s.naDalsiPrvek();
}
}
Implementace seznamu pomocí pole tak, že prvky seznamu jsou ukládány do prvků pole, vede při operaci vložení na posun všech prvků vpravo od místa vložení tak, aby vzniklo volné místo pro vkládaný prvek. Obdobně při výběru prvku, na to, aby v prvcích pole byly za sebou prvky seznamu, musíme všechny prvky za vybraným prvkem posunout o jedno místo doleva. Operace vložení a výběru by tedy byly O(n).
Toto nenastane, při vkládání a výběru prvku, když implementujeme seznam pomocí spojových struktur. Prvek seznamu bude obsahovat kromě hodnoty klíče člen dalsi, což bude odkaz na následující prvek seznamu.
class Prvek {
... klic;
Prvek dalsi;
}
Seznam bude reprezentován referenční proměnnou prvni třídy Prvek obsahující odkaz na první prvek seznamu nebo hodnotu null, je-li seznam prázdný.
Vytvoření prázdného seznamu, inicializace, má implementaci
inicializace:
prvni = null;
a imlementace testu je-li seznam prázdný je
test je-li prázdný:
if (prvni == null)
Okamžitou pozici v seznamu pro operace nad seznamem budeme reprezentovat referenční proměnnou nynejsi (pozice) typu Prvek. Potom operaci nastavení okamžité pozice na začátek seznamu implementuje příkaz
nastaveni na začátek:
nynejsi = prvni;
test je-li okamžitá pozice na posledním prvku implementuje příkaz
test poslední pozice:
if (nynejsi.dalsi == null)
Vložení nového prvku, na který odkazuje proměnná novy, za prvek na okamžité pozici, potom musí rozlišovat vkládáme-li do prázdného seznamu první prvek nebo za prvek na okamžité pozici. V prvním případě má proměnná nynejsi hodnotu null, kdežto ve druhém případě odkazuje na objekt třídy Prvek.
vlož prvek za nynejsi:
if (prvni == null) {
prvni = novy;
prvni.dalsi = null;
}
else {
novy.dalsi = nynejsi.dalsi;
nynejsi.dalsi = novy;
}
nynejsi = novy;
Pro vytisknutí všech prvků seznamu nebo nalezení prvku s určitou hodnotou klíče musíme seznam procházet. Průchod seznamem implementuje následující cyklus.
procházení seznamem:
for (nynejsi = prvni; nynejsi != null;
nynejsi = nynejsi.dalsi);
Při použití procházení seznamu, nalezení prvku s určitou hodnotou zjistíme příkazem
if (nynejsi.klic = hodnota)
Chceme-li takto nalezený prvek se seznamu odstranit, je vhodné, aby operace vyber, odstranila se seznamu prvek na okamžité pozici. Na implementaci této operace ovšem musíme znát odkaz na předcházející prvek.
Alternativně by jsme mohli operaci vyber specifikovat jako odstranění prvku na pozici následující za okamžitou pozicí, kdy odkaz na předcházející prvek znát nemusíme.
Udržujeme tedy při operacích nad seznamem v proměnné predch odkaz na prvek předcházející okamžité pozici. Je-li okamžitou pozicí první prvek má proměnná predch hodnotu null. Operaci vyber potom můžeme implementovat následovně
vyber nynejsi:
if (predch == null) {
prvni = nynejsi.dalsi;
nynejsi = prvni;
}
else {
predch.dalsi = nynejsi.dalsi;
if (nynejsi.dalsi == null) { //byl poslední
nynejsi = prvni;
predch = null;
}
else
nynejsi = nynejsi.dalsi;
kde v případě, že jsme odstranili poslední prvek, nastavíme okamžitou pozici v seznamu na první prvek, jinak se okamžitou pozicí stane pozice za odstraněným prvkem.
Poznamenejme, že uvedená implementace operace pro vložení prvku neumožňuje vložit do neprázdného seznamu prvek na první místo, protože prvek vkládáme za okamžitou pozici. S pomocí proměnné predch však můžeme napsat implementaci další perace vložpřed, která vloží prvek před okamžitou pozici.
Uvedené programové fragmenty nám umožňují napsat třídu seznam s požadovaným rozhraním. V této třídě by byly pro implementaci operací ADT seznam použity členské proměnné prvni, nynejsi, predch.
Pro práci s polem můžeme používat několik indexů reprezentujících pozici v poli. Uvedená implementace ADT seznam by umožňovala operace nad seznamem jenom na jedné pozici. Na to, abychom mohli pracovat se seznamem obdobně jako s polem, musíme oddělit reprezentaci objektu implementujícího ADT seznam, proměnná prvni, a práci s ním, proměnné nynejsi a predch.
Objekty, které pracují s datovými strukturami a obsahují odkazy na jejich prvky se nazývají iterátory.
ADT seznam tedy bude implementována třídami Seznam a IteratorSeznamu, obr..
Třída Seznam obsahuje metodu getIterator( ), která vrací reference na iterátory seznamu voláním konstruktoru pro iterátor seznamu s parametrem this, tedy pro sebe. Konstruktor třídy IteratorSeznamu pro seznam potom vytvoří iterátor s členskými proměnnými nynejsi a predch. Metoda getIterator( ) umožňuje klientovi pro objekt třídy Seznam vyvářet iterátory, které nad ním můžou pracovat, přičemž každý iterátor spravuje vlastní okamžitou pozici v tomto objektu, jak je uvedeno v metodě main( ) na obr..
Rozhraní třídy Seznam bude dále obsahovat metody implementující operace rozhraní ADT seznam, které pracují s proměnnou prvni a metody pro její nastavení a čtení využívané metodami třídy IteratorSeznamu, obr..
Rozhraní třídy IteratorSeznamu pak obsahuje metody implementující ostatní operace ADT seznam, obr.. Pro prvky třídy Prvek na obr.
je implementace rozhraní třídy Seznam na obr.
a implementace rozhraní třídy IteratorSeznamu na obr.
a
.
V softwarovém inženýrství standardní řešení obecných problémů v návrhu programů se nazývají návrhové vzory. Algoritmy nejsou návrhové vzory, protože řeší problémy samotné a ne problémy návrhu. Typicky návrhový vzor zahrnuje těsnou interakci několika třída a objektů. Iterátor je typický příklad návrhového vzoru pro sekvenční přístup k objektům.
Pro uvedenou reprezentaci dat ADT seznam jsme v implementaci některých operací museli rozlišovat je-li okamžitá pozice první prvek nebo ne. Řešením je neuložit odkaz na první prvek seznamu do proměnné odkazující na objekt třídy prvek, ale také do objektu třídy Prvek, totiž do jeho položky dalsi a položku pro uchovávání hodnoty prvku nevyužijeme. Tento prvek nazýváme hlavička a budeme ho reprezentovat proměnnou hlavicka.
Implementace operací ve třídě Seznam bude mít nyní tvar
inicializace:
hlavicka = new Prvek();
test je-li prázdný:
if (hlavicka.dalsi == null)
a metoda getHlavicka() bude vracet referenci na hlavicku seznamu.
Operace ve třídě IteratorSeznamu budou iplementovány následovně
nastavení na začátek:
if(s.jePrazdny()) {
nynejsi = s.getHlavicka();
predch = null;
}
else {
nynejsi = s.getHlavicka().dalsi;
predch = s.getHlavicka();
}
vlož prvek za nynejsi:
novy.dalsi = nynejsi.dalsi;
nynejsi.dalsi = novy;
nynejsi = novy;
naDalsiPrvek();
vyber nynejsi:
predch.dalsi = nynejsi.dalsi;
if (jePosledni())
naZacatek();
else
nynejsi = nynejsi.dalsi;
Při implementaci ADT seznam lineárním spojovým seznamem máme přístup pomocí položky dalsi jenom k prvkům od okamžité pozice do konce seznamu. K prvkům před okamžitou pozicí v seznamu můžeme přistupovat jenom začneme-li explicitně prvním prvkem nastavením okamžité pozice na začátek.
Řešením, které toto nepožaduje je v položce dalsi posledního prvku namísto hodnoty null uchovávat odkaz na první prvek.
Při implementaci ADT seznam pomocí lineárního spojového seznamu jsme pro operace vložení prvku před okamžitou pozici a výběr prvku na okamžité pozici potřebovali znalost odkazu na předcházející prvek. Tuto informaci jsme uchovávali v členské proměnné predch instancí třídy IteratorSeznamu .
Jinou možností je uchovávat tuto informaci v samotném objektu třídy Prvek, která potom bude
class Prvek {
...
Prvek dalsi;
Prvek predch;
}
Uvedené techniky implementace je možné různě variovat. Příkladem může být zavedení reprezentace konce seznamu objektem třídy Prvek, kterého položka dalsi odkazuje na sebe.
inicializace:
hlavicka = new Prvek();
z = new Prvek();
hlavicka.dalsi = z;
z.dalsi = z;
Jiným příkladem může být obousměrný kruhový seznam, umožňující procházení seznamu oběma směry.
Připomeňme, že v úvodu jsme řekli, že pole není vhodné na implementaci ADT seznam a ADT seznam jsme implementovali pomocí různých variací spojového seznamu. Na druhé straně spojové seznamy můžeme implementovat pomocí polí.
Pro jednoduchost uvažujme lineární spojový seznam. Na implementaci jeho prvků s položkami klic a dalsi použijeme dvě stejnojmenná pole a prvek seznamu bude reprezentován dvojicí jejich prvků se stejným indexem. Je-li typ klice char, tyto pole budou
char[ ] klic = new char[max];
int[ ] dalsi = new int[max];
V prvcích pole dalsi je ukazatel na následující prvek seznamu, tj. index prvků polí klic a dalsi , ve kterých je uložen. Je-li prvek seznamu poslední bude dalsi obsahovat hodnotu -1. Uložíme-li například jméno PAVEL ve tvaru seznamu jednotlivých písmen, podobně jako v případě implementace spojovým seznamem, bude seznam reprezentován indexem prvku, kde je jeho první prvek. V našem příkladě je tento index na proměnné jmeno.
int jmeno = 3;
klic[3] = ‘P’; dalsi[3] = [4];
klic[4] = ‘A’; dalsi[4] = [7];
klic[7] = ‘V’; dalsi[7] = [2];
klic[2] = ‘E’; dalsi[2] = [6];
klic[6] = ‘L’; dalsi[6] = [-1];
V polích klic a dalsi může být uloženo několik seznamů.
int jinejmeno = 9;
klic[9] = ‘D’; dalsi[9] = ... ;
Implementace jednotlivých operací je podobná jako při implementaci spojového seznamu pomocí referencí.
Na vložení prvku seznamu musíme znát index, kam můžeme nový prvek seznamu vložit. Na to udržujeme pomocí prvků pole dalsi zásobník všech volných prvků a jeho začátek v proměnné volne.
int volne;
Přidělení indexu pro další prvek seznamu potom implementuje metoda
int pridelIndex() {
if (volne == -1)
“neni volny index”
else {
int i = volny;
volny = dalsi[i];
return i;
}
Je-li prvek seznamu odstraněn, vrácení jeho indexu i mezi volné implementuje metoda
void uvolniIndex(i) {
dalsi[i] = volne;
volne = i;
}
Uvedené algoritmy přidělení volného prvku pole a uvolnění prvku pole jsou základem procesu přidělování paměti pro vytvářený objekt operátorem new a její uvolnění není-li objekt více referencován (garbage collection). Stačí si uvědomit, že paměť je pole bytů a jejich indexy jsou adresy. V případě objektů nutno navíc vzít v úvahu, že mají obecně různou velikost, zatímco v našem případě měli všechny prvky velikost klíče.