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).
01./**02. * Rozhrani, jez definuje operace, ktere musi splnit kazda implementace seznamu03. * @author Pavel Micka04. */05.public interface ListIface {06. 07. /**08. * Vlozi na konec seznamu prvek09. * @param i prvek k vlozeni10. */11. public void add(int i);12. 13. /**14. * Vrati prvek na indexu i15. * @param i index prvku16. * @return prvek na indexu i17. */18. public int get(int i);19. 20. /**21. * Smaze prvek na indexu i22. * @param i index mazaneho prvku23. */24. public void remove(int i);25. 26. /**27. * Dotaz na delku seznamu28. * @return delka seznamu29. */30. public int size();31.}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
01./**02. * Jednosmerne zretezeny spojovy seznam03. * @author Pavel Micka04. */05.public class MyLinkedList implements ListIface {06. 07. private Node first;08. private Node last;09. private int size;10. 11. /**12. * Konstruktor spojoveho seznamu13. */14. public MyLinkedList() {15. this.size = 0;16. }17. 18. /**19. * Vnitrni trida reprezentujici jeden uzel spojoveho seznamu20. */21. private class Node {22. 23. private int value;24. private Node next;25. 26. private Node(int value) {27. this.value = value;28. }29. }30.}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
01./**02. * Vlozi na konec seznamu prvek03. * @param i prvek k vlozeni04. */05.public void add(int i) {06. Node n = new Node(i);07. if (size == 0) {08. this.first = n;09. this.last = n;10. } else {11. this.last.next = n;12. this.last = n;13. }14. size++;15.}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
01./**02. * Vrati prvek na indexu i03. * @param i index prvku04. * @throws IndexOutOfBoundsException pokud je i vyssi nebo rovna delce seznamu05. * @throws IllegalArgumentException pokud je i zaporne06. * @return prvek na indexu i07. */08.public int get(int i) {09. if (i >= size) {10. throw new IndexOutOfBoundsException("Mimo meze index:" + i + ", size:" + this.size);11. }12. if (i < 0) {13. throw new IllegalArgumentException("Index mensi nez 0");14. }15. Node curr = first;16. for (int j = 0; j < i; j++) {17. curr = curr.next;18. }19. return curr.value;20.}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
01./**02. * Smaze prvek na indexu i03. * @param i index mazaneho prvku04. * @throws IndexOutOfBoundsException pokud je i vyssi nebo rovna delce seznamu05. * @throws IllegalArgumentException pokud je i zaporne06. */07.public void remove(int i) {08. if (i >= size) {09. throw new IndexOutOfBoundsException("Mimo meze index:" + i + ", size:" + this.size);10. }11. if (i < 0) {12. throw new IllegalArgumentException("Index mensi nez 0");13. }14. if (i == 0) {15. first = first.next;16. } else {17. Node curr = first;18. for (int j = 0; j < i - 1; j++) { //najdeme predchozi19. curr = curr.next;20. }21. curr.next = curr.next.next; //a mazany prvek vynechame22. if (i == size - 1) { //pokud mazeme posledni23. last = curr;24. }25. }26. size--;27.}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
1./**2. * Dotaz na delku seznamu3. * @return delka seznamu4. */5.public int size() {6. return this.size;7.}Metoda size pouze vrátí předpočítanou délku seznamu.
Metoda toString
01./**02. * Klasicka toString metoda, vraci textovou reprezentaci objektu03. * @return textova reprezentace objektu04. */05.@Override06.public String toString() {07. StringBuilder builder = new StringBuilder();08. Node curr = first;09. for (int i = 0; i < this.size; i++) {10. builder.append(curr.value);11. builder.append(" ");12. curr = curr.next;13. }14. return builder.toString();15.}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:
001./**002. * Jednosmerne zretezeny spojovy seznam003. * @author Pavel Micka004. */005.public class MyLinkedList implements ListIface {006. 007. private Node first;008. private Node last;009. private int size;010. 011. /**012. * Konstruktor spojoveho seznamu013. */014. public MyLinkedList() {015. this.size = 0;016. }017. 018. /**019. * Vlozi na konec seznamu prvek020. * @param i prvek k vlozeni021. */022. public void add(int i) {023. Node n = new Node(i);024. if (size == 0) {025. this.first = n;026. this.last = n;027. } else {028. this.last.next = n;029. this.last = n;030. }031. size++;032. }033. 034. /**035. * Vrati prvek na indexu i036. * @param i index prvku037. * @throws IndexOutOfBoundsException pokud je i vyssi nebo rovna delce seznamu038. * @throws IllegalArgumentException pokud je i zaporne039. * @return prvek na indexu i040. */041. public int get(int i) {042. if (i >= size) {043. throw new IndexOutOfBoundsException("Mimo meze index:" + i + ", size:" + this.size);044. }045. if (i < 0) {046. throw new IllegalArgumentException("Index mensi nez 0");047. }048. Node curr = first;049. for (int j = 0; j < i; j++) {050. curr = curr.next;051. }052. return curr.value;053. }054. 055. /**056. * Smaze prvek na indexu i057. * @param i index mazaneho prvku058. * @throws IndexOutOfBoundsException pokud je i vyssi nebo rovna delce seznamu059. * @throws IllegalArgumentException pokud je i zaporne060. */061. public void remove(int i) {062. if (i >= size) {063. throw new IndexOutOfBoundsException("Mimo meze index:" + i + ", size:" + this.size);064. }065. if (i < 0) {066. throw new IllegalArgumentException("Index mensi nez 0");067. }068. if (i == 0) {069. first = first.next;070. } else {071. Node curr = first;072. for (int j = 0; j < i - 1; j++) { //najdeme predchozi073. curr = curr.next;074. }075. curr.next = curr.next.next; //a mazany prvek vynechame076. if (i == size - 1) { //pokud mazeme posledni077. last = curr;078. }079. }080. size--;081. }082. 083. /**084. * Dotaz na delku seznamu085. * @return delka seznamu086. */087. public int size() {088. return this.size;089. }090. 091. /**092. * Klasicka toString metoda, vraci textovou reprezentaci objektu093. * @return textova reprezentace objektu094. */095. @Override096. public String toString() {097. StringBuilder builder = new StringBuilder();098. Node curr = first;099. for (int i = 0; i < this.size; i++) {100. builder.append(curr.value);101. builder.append(" ");102. curr = curr.next;103. }104. return builder.toString();105. }106. 107. 108. /**109. * Vnitrni trida reprezentujici jeden uzel spojoveho seznamu110. */111. private class Node {112. 113. private int value;114. private Node next;115. 116. private Node(int value) {117. this.value = value;118. }119. }120.}Volání
01./**02. * @param args the command line arguments03. */04.public static void main(String[] args) {05. ListIface l = new MyLinkedList();06. 07. l.add(0);08. l.add(10);09. l.add(20);10. l.add(30);11. l.add(40);12. 13. //vypiseme spojovy seznam pomoci toString metody14. System.out.println(l);15. System.out.println(l.get(2)); //2016. 17. 18. l.remove(1); //odstranime prvek na prvnim indexu19. System.out.println(l.get(2)); //3020. 21. l.remove(0);22. System.out.println(l);23. System.out.println(l.size()); //324.}1.0 10 20 30 40 2.203.304.20 30 40 5.3V 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.