Spojové seznamy v Javě - LinkedList

Teorie

Spojový seznam je kontejner objektů a je to jedna z nejefektivnějších struktur, pokud budeme často zapisovat na začátek nebo na konec seznamu. Jednotlivé prvky zde nemají žádné indexy, ale jednoduše na sebe po sobě jdoucí prvky odkazují. Tyto spojové seznamy slouží převážně k ukládání dat předem neznámé délky. Základem těchto seznamů je uzel neboli Node, který odkazuje na další prvek v seznamu.

Výhody a nevýhody spojového seznamu

Největší výhodou spojového seznamu je rychlé a efektivní přidávání prvku na konec nebo začátek seznamu. Stejně tak to platí i pro mazání prvků.

Jedna z největších nevýhod spojového seznamu je, že nemůžeme efektivně přistoupit k prvku uprostřed řady, ale musíme seznam prohledávat postupně celý, něž nalezne náš n-tý prvek.

Dělení

Jednosměrný spojový seznam

Anglicky (Single Linked List) – Je to jedna ze základních a nejjednodušších spojových datových struktur, kdy každý jednotlivý datový uzel (node) obsahuje svá data a odkaz na další položku seznamu. Poslední položka neobsahuje žádný odkaz ale pouze hodnotu null. Proto také jednosměrný

Obousměrný spojový seznam

Anglicky (Double Linked List) - Je to efektivnější a používanější varianta spojového seznamu. Jednotlivé prvky obsahují kromě svých dat také odkaz na předešlý a následující prvek.

Linked List

V Javě je obousměrný spojový seznam reprezentován třídou LinkedList. Umožňuje například přidávat položky na poslední pozici seznamu, nebo na začátek seznamu s tím, že všechny ostatní prvky se posunou o jednu pozici dál. Pokud byste z nějakého důvodu po dokončení operací vkládání/mazání dále nechtěli pracovat se seznamem a chtěli by jste raději použít pole, tak nezoufejte. Jednoduše můžete ze seznamu udělat pole pomocí metody toArray() a dále již s jednotlivými prvky můžete pracovat tak, jak jste zvyklí. Všechny operace fungují jako u dvojitého spojového seznamu. Pokud uvedeme u nějaké funkce index (get, set), bude se procházet seznam od začátku nebo od konce, podle toho, co je blíže k určenému indexu.

Konstruktory

• new LinkedList(); - bezparametrický konstruktor
• new LinkedList(Co­llection c); - vytvoří nový spojový seznam a naplní jej položkami z dané kolekce

Metody

1. add() - přidá položku na další pozici
2. addFirts(param) - přidá položku na začátek seznamu
3. addLast(param) - přidá položku na konec seznamu
4. addAll(Colection) – přidá do seznamu celou kolekci (všechny položky, které obsahuje původní seznam)
5. removeFirst() - odstraní první položku v seznamu
6. removeLast() - odstraní poslední položku v seznamu
7. get(index) – vrátí prvek na dané pozici
8. getFirst() - vrátí první položku v seznamu
9. getLast() - vrátí poslední položku v seznamu
10. set(index, param) – přepíše původní položku na daném indexu.
11. contains(param) – vrátí hodnotu true, pokud se v seznamu nachází daná položka. V opačném případě vrácí hodnotu false
12. size() - metoda vrací počet položek seznamu
13. toArray() - vrátí pole naplněné položkami spojového seznamu

Pro představu jak tato kolekce funguje přikládám okomentovaný kód jednoduché aplikace:

package javalinkedlist;

import java.util.LinkedList;

public class JavaLinkedList {

    public static void main(String[] args) {
       //vytvoření seznamu
       LinkedList seznam = new LinkedList();
       //naplnění hodnotami
       seznam.add(1);
       seznam.add(2);
       seznam.add(3);
       seznam.add(4);
       seznam.add(5);
       seznam.add(6);
       seznam.add(7);
       // odstranění a přidání prvku na poslední pozici
       seznam.removeLast();
       seznam.addLast(8);
       //odstraňení a přidání prvku na první pozici
       seznam.removeFirst();
       seznam.addFirst(0);

       //vypsání seznamu
       System.out.println(seznam);

       //vložení 2 hodnot doprostřed seznamu
       seznam.add(Math.round(seznam.size()/2),13);
       seznam.add(Math.round(seznam.size()/2),15);
       //přepsání hodnot
       seznam.set(1, 20);

       //vypsání seznamu
       System.out.println(seznam);

       //pokud se číslo vyskytuje v seznamu vypíše ho, v opačném případě jej do seznamu zapíše a vypíše jeho pozici
       int cislo = 18;
       if(seznam.contains(cislo)){
           System.out.println(cislo);
       }
       else{
           seznam.addLast(cislo);
           System.out.printf("Index čísla %s je %s \n", cislo, seznam.indexOf(cislo));
       }

       //získání první a podlední hodnoty v seznamu
       int prvni = (int) seznam.getFirst();
       int posledni = (int) seznam.getLast();
    }
}

Nakonec jen doplním, že seznam se indexuje od 0, stejně jako pole. Tak a o dvousměrném spojovém seznamu již máte určitou představu. Umíte jej používat a to je pro vás nejdůležitější. Možná se mezi čtenáři najde i část lidí, kteří by chtěli vědět jak to funguje "pod pokličkou". Pro tyto lidi mám připravený další díl, ve kterém se těmito věcmi budeme zabývat více do hloubky a ve kterém si společně vytvoříme jednoduchý SingleLinkedList a ukážeme si jak to vše vlastně funguje.

Pro dnešek jste se naučili používat obousměrný spojový seznam v podobě třídy LinkedList, kterou má java již v základu v balíčku java.util. Jednosměrný spojový seznam Java neobsahuje a proto si ukážeme jak si ho vytvořit a po přečtení dalšího tutoriálu budete vědět jak to celé vlastně funguje. Pod článkem jsou jako vždy přiložené zdrojové kódy, takže kdyby Vám cokoliv nešlo a nemohli jste najít chybu tak si je stáhněte a hledejte řádek po řádku