V desátém dílu jsme si ukázali první kolekci – dynamické pole (ArrayList). Dnes si vytvoříme další kontejner – spojový seznam (LinkedList). Spojový seznam je jedna z nejvděčnějších datových struktur. Přestože je implementačně poměrně jednoduchý, je zároveň velmi použitelný – je základem mnoha implementací zásobníku, fronty, grafu a dalších datových struktur.
Dnes vytvoříme implementaci, jež nám zajistí základní funkcionalitu. Příště si ukážeme, jak seznam zobecnit pro ukládání objektů libovolného typu a jak zefektivnit jeho procházení pomocí for-each cyklu.
Co je to spojový seznam?
Spojový seznam je datový kontejner, který se skládá z mnoha lineárně provázaných uzlů. Každý uzel obsahuje část obsahující uloženou entitu a z ukazatel na další prvek (jednosměrně zřetězený seznam), případně i z ukazatel na prvek předchozí (obousměrně zřetězený seznam).
Rozhraní (spojového) seznamu
Nejprve si specifikujme operace, které musí splňovat každý seznam. Tato abstrakce nám v případě potřeby umožní nahradit spojový seznam jinou implementací (například již zmíněným dynamickým polem).
/**
* Rozhrani, jez definuje operace, ktere musi splnit kazda implementace seznamu
* @author Pavel Micka
*/
public interface ListIface {
/**
* Vlozi na konec seznamu prvek
* @param i prvek k vlozeni
*/
public void add(int i);
/**
* Vrati prvek na indexu i
* @param i index prvku
* @return prvek na indexu i
*/
public int get(int i);
/**
* Smaze prvek na indexu i
* @param i index mazaneho prvku
*/
public void remove(int i);
/**
* Dotaz na delku seznamu
* @return delka seznamu
*/
public int size();
}
Implementace
Samotný spojový seznam budeme implementovat jako jednosměrně zřetězený s ukazateli na první a poslední prvek. Ukládané hodnoty budou primitivního typu int.
Třídní proměnné, konstruktory a vnitřní třída Node
/**
* Jednosmerne zretezeny spojovy seznam
* @author Pavel Micka
*/
public class MyLinkedList implements ListIface {
private Node first;
private Node last;
private int size;
/**
* Konstruktor spojoveho seznamu
*/
public MyLinkedList() {
this.size = 0;
}
/**
* Vnitrni trida reprezentujici jeden uzel spojoveho seznamu
*/
private class Node {
private int value;
private Node next;
private Node(int value) {
this.value = value;
}
}
}
Třídu spojového seznamu pojmenujeme MyLinkedList, aby nedocházelo ke kolizi jmen s již předpřipravenou třídou java.util.LinkedList (dokumentace). Třída bude implementovat operace, které jsme si definovali v rozhraní ListIface.
Objekt spojového seznamu bude obsahovat ukazatel na první uzel first, ukazatel na poslední uzel last a hodnotu size obsahující počet prvků uložených v seznamu.
Reference na první uzel použijeme pro průchod skrz seznam (je jednosměrný). Reference na poslední prvek zjednoduší operaci ukládání nové hodnoty, protože nebudeme muset napřed proiterovat celý seznam (vkládáme nakonec). Obdobným způsobem proměnná size zjednodušší dotaz na délku seznamu.
Konstruktor obsahuje pouze jedinou operaci – inicializaci proměnné size na hodnotu 0.
Třída Node
Základem spojového seznamu je soukromá vnitřní třída Node. Tuto třídu jsme vytvořili jako vnitřní a soukromou, protože ji takto v duchu zásad zapouzdření (encapsulation) dokonale skryjeme před okolním světem.
Node obsahuje uloženou hodnotu value a referenci na další prvek next (nullový v případě, že se jedná o poslední uzel). Gettery a settery jednotlivých proměnných nejsou nevyhnutelně nutné, jelikož má k typu Node přístup pouze třída MyLinkedList (a ta může použít přímý přístup).
Metoda add
/**
* Vlozi na konec seznamu prvek
* @param i prvek k vlozeni
*/
public void add(int i) {
Node n = new Node(i);
if (size == 0) {
this.first = n;
this.last = n;
} else {
this.last.next = n;
this.last = n;
}
size++;
}
Metoda add přidá zadanou hodnotu na konec seznamu. Jako první musíme vytvořit nový uzel seznamu pro předávanou hodnotu. Pokud je seznam prázdný, tak se nově přidávaný uzel stane prvním (first) a posledním (last) prvkem seznamu. Pokud není seznam prázdný, tak vybereme pomocí reference last poslední prvek seznamu a do jeho proměnné next vložíme referenci na nově přidávaný uzel. Jako poslední krok v každém případě inkrementujeme proměnnou size.
Metoda get
/**
* Vrati prvek na indexu i
* @param i index prvku
* @throws IndexOutOfBoundsException pokud je i vyssi nebo rovna delce seznamu
* @throws IllegalArgumentException pokud je i zaporne
* @return prvek na indexu i
*/
public int get(int i) {
if (i >= size) {
throw new IndexOutOfBoundsException("Mimo meze index:" + i + ", size:" + this.size);
}
if (i < 0) {
throw new IllegalArgumentException("Index mensi nez 0");
}
Node curr = first;
for (int j = 0; j < i; j++) {
curr = curr.next;
}
return curr.value;
}
Metoda get vrátí prvek na zadaném indexu seznamu. Nejprve ošetříme chyby, které mohou nastat – předání buď příliš vysokého nebo příliš nízkého (záporného) indexu. Na obě chyby zareagujeme adekvátní nekontrolovanou výjimkou (jedná se o chybu programátora).
Nyní proiterujeme celý seznam až na daný index a vrátíme hodnotu uschovanou v daném uzlu.
Metoda remove
/**
* Smaze prvek na indexu i
* @param i index mazaneho prvku
* @throws IndexOutOfBoundsException pokud je i vyssi nebo rovna delce seznamu
* @throws IllegalArgumentException pokud je i zaporne
*/
public void remove(int i) {
if (i >= size) {
throw new IndexOutOfBoundsException("Mimo meze index:" + i + ", size:" + this.size);
}
if (i < 0) {
throw new IllegalArgumentException("Index mensi nez 0");
}
if (i == 0) {
first = first.next;
} else {
Node curr = first;
for (int j = 0; j < i - 1; j++) { //najdeme predchozi
curr = curr.next;
}
curr.next = curr.next.next; //a mazany prvek vynechame
if (i == size - 1) { //pokud mazeme posledni
last = curr;
}
}
size--;
}
Při odstraňování prvku opět nejprve zkontrolujeme platnost zadaného indexu. Pokud mažeme první prvek, tak nám stačí změnit ukazatel na první prvek seznamu (first) na prvek následující. V ostatních případech nalezneme prvek, který je v seznamu před mazaným prvkem (označíme jej curr) a změníme jeho ukazatel na next na prvek, který je za mazaným prvkem (mazaný prvek vynecháme). Pokud jsme mazali poslední prvek, pak je nyní posledním prvkem curr. Na závěr dekrementujeme proměnnou size.
Pro úplnost si připomeňme, že poté, co na daný uzel zmizí poslední reference, bude odstraněn pomocí garbage collectoru.
Metoda size
/**
* Dotaz na delku seznamu
* @return delka seznamu
*/
public int size() {
return this.size;
}
Metoda size pouze vrátí předpočítanou délku seznamu.
Metoda toString
/**
* Klasicka toString metoda, vraci textovou reprezentaci objektu
* @return textova reprezentace objektu
*/
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
Node curr = first;
for (int i = 0; i < this.size; i++) {
builder.append(curr.value);
builder.append(" ");
curr = curr.next;
}
return builder.toString();
}
Nakonec ještě překryjeme metodu toString zděděnou z Object. Tato metoda vrací textovou reprezentaci daného objektu.
V této metodě využíváme StringBuilder (dokumentace), což je obdoba ArrayListu pro znaky. Kdybychom používali pouze operátor zřetězení +, tak bychom každým jeho použitím vytvořili nový řetězec, který bychom v zápětí zahodili (jakožto vstup nového zřetězení). Tento postup by byl velmi nehospodárný.
Kód
Takto zatím vypadá kompletní kód naší implementace spojového seznamu:
/**
* Jednosmerne zretezeny spojovy seznam
* @author Pavel Micka
*/
public class MyLinkedList implements ListIface {
private Node first;
private Node last;
private int size;
/**
* Konstruktor spojoveho seznamu
*/
public MyLinkedList() {
this.size = 0;
}
/**
* Vlozi na konec seznamu prvek
* @param i prvek k vlozeni
*/
public void add(int i) {
Node n = new Node(i);
if (size == 0) {
this.first = n;
this.last = n;
} else {
this.last.next = n;
this.last = n;
}
size++;
}
/**
* Vrati prvek na indexu i
* @param i index prvku
* @throws IndexOutOfBoundsException pokud je i vyssi nebo rovna delce seznamu
* @throws IllegalArgumentException pokud je i zaporne
* @return prvek na indexu i
*/
public int get(int i) {
if (i >= size) {
throw new IndexOutOfBoundsException("Mimo meze index:" + i + ", size:" + this.size);
}
if (i < 0) {
throw new IllegalArgumentException("Index mensi nez 0");
}
Node curr = first;
for (int j = 0; j < i; j++) {
curr = curr.next;
}
return curr.value;
}
/**
* Smaze prvek na indexu i
* @param i index mazaneho prvku
* @throws IndexOutOfBoundsException pokud je i vyssi nebo rovna delce seznamu
* @throws IllegalArgumentException pokud je i zaporne
*/
public void remove(int i) {
if (i >= size) {
throw new IndexOutOfBoundsException("Mimo meze index:" + i + ", size:" + this.size);
}
if (i < 0) {
throw new IllegalArgumentException("Index mensi nez 0");
}
if (i == 0) {
first = first.next;
} else {
Node curr = first;
for (int j = 0; j < i - 1; j++) { //najdeme predchozi
curr = curr.next;
}
curr.next = curr.next.next; //a mazany prvek vynechame
if (i == size - 1) { //pokud mazeme posledni
last = curr;
}
}
size--;
}
/**
* Dotaz na delku seznamu
* @return delka seznamu
*/
public int size() {
return this.size;
}
/**
* Klasicka toString metoda, vraci textovou reprezentaci objektu
* @return textova reprezentace objektu
*/
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
Node curr = first;
for (int i = 0; i < this.size; i++) {
builder.append(curr.value);
builder.append(" ");
curr = curr.next;
}
return builder.toString();
}
/**
* Vnitrni trida reprezentujici jeden uzel spojoveho seznamu
*/
private class Node {
private int value;
private Node next;
private Node(int value) {
this.value = value;
}
}
}
Volání
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
ListIface l = new MyLinkedList();
l.add(0);
l.add(10);
l.add(20);
l.add(30);
l.add(40);
//vypiseme spojovy seznam pomoci toString metody
System.out.println(l);
System.out.println(l.get(2)); //20
l.remove(1); //odstranime prvek na prvnim indexu
System.out.println(l.get(2)); //30
l.remove(0);
System.out.println(l);
System.out.println(l.size()); //3
}
0 10 20 30 40 20 30 20 30 40 3
V kódu volání používáme na levé straně přiřazení rozhraní ListIface. Stejně tak bychom postupovali v libovolném jiném případě, kdy by vytvářená entita měla vyhovující interface.
Tomuto postupu se říká programování proti rozhraní. Výhody jsou poměrně jasné – pokud se rozhodneme změnit implementační třídu, tak ji vyměníme na jediném místě (tam kde vytváříme instanci) a zbytek programu může zůstat totožný. Kdybychom programovali proti implementaci – implementační třída by se objevovala na levých stranách přiřazení, v hlavičkách metod a podobně – tak bychom v případě výměny této třídy museli přepsat skoro celý program.
Reference vs. ukazatel
Poznámka: Bylo mi vytknuto zaměňování termínů reference a ukazatel (které nejsou v C++ totožné). Jak je nám známo, tak Java má pouze reference a nemá ukazatele. Názvoslovný problém je v tom, že javovská reference výrazně více odpovídá C++ ukazateli (oproti C++ referenci).
Pokud tedy budu mluvit v tom seriálu a ukazatelích a referencích, tak tím budu mít vždy na mysli Java referenci.