Seznam/UrskaBerce
Iz MaFiRaWiki
![]() | Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili. |
Vsebina |
Verižni seznam
Verižni seznam je zaporedje vozlov. Vsak vozel vsebuje vrednost (podatek) in povezavo (referenco) do drugega vozla. Referenca v zadnjem vozlu v seznamu je null. Vozlov naslednik je naslednji vozel v zaporedju. Zadnji vozel nima naslednika. Vozlov predhodnik je predhodni vozel v zaporedju. Prvi vozel nima predhodnika. Velikost seznama je število elementov v njem. Seznam pa je lahko tudi prazen.
Podatkovno strukturo lahko vpeljemo rekurzivno, npr. tako, da je linearni seznam bodisi prazen seznam, bodisi struktura, ki vsebuje en element in verižni seznam. Elementi seznama so lahko cela števila, poljubni objekti ali pa je to par dveh seznamov (glava in preostanek seznama). Glavni vozel je dodaten vozel vpeljan v posameznem seznamu. Uporaba tega so običajno enostavnejši programi, tako se lahko pogosto izognemo vprašanju o praznem seznamu kot posebnem primeru. Ko je glavni vozel uporabljen, vsak seznam (tudi prazen) vsebuje najmanj en vozel.
Verižni seznam je množica elementov, kjer vsak element vsebuje tudi kazalec (povezavo, referenco) na element.
Elementi verižnega seznama so vozli. Vozel je objekt.
Komponente
- Prostor za podatke
- Referenca na naslednjega
Razred Verižni seznam je dinamična podatkovna struktura. Od statične tabele se razlikuje po tem, da moramo velikost in obliko tabele določiti vnaprej, pomankljivost pa je še zahtevno vstavljanje ali brisanje elementov v sredini tabele. Vse to rešuje povezan oz verižni seznam (LinkedList), kjer so podatki shranjeni v vozlišča. Vsako vozlišče vsebuje poleg podatka tudi kazalec (povezavo, referenco), ki kaže na vozlišče z naslednjim podatkom.
Vrste seznamov
- enojno povezani seznami
- dvojno povezani seznami
- krožno povezani seznami
Enojno povezan seznam: (poznamo le kazalec na prvi element).
Dvojno povezan seznam: Dvojno povezan seznam je seznam, katerega vsak vozel vsebuje vrednost in dve referenci, eno na naslednji vozel, eno na predhodni vozel. To dopušča da program deluje v obeh smereh od danega vozla. Glavni vozel (glava) pokaže na prvi vozel v seznamu in na zadnji vozel v seznamu ( ali pa vsebuje ničelno povezavo če je seznam prazen)
Prednosti dvojno povezanega seznama:
- lahko je prečkan v obeh smereh
- nekatere operacije, kot so brisanje in vstavljanje pred vozel, postanejo lažje.
Slabost dvojno povezanega seznama:
- zahteva več prostora
- operacije v seznamu so počasnejše ( ker mora biti več povezav spremenjenih )
Krožno povezan seznam: Krožno povezan verižni seznam je povezan seznam, katerega vsak vozel ima naslednika ( referenca znotraj zadnjega vozla pokaže na prvi vozel) Krožno povezan seznam v resnici nima začetka ali konca. Vendar mi še vedno potrebujemo zunanjo referenco na enega od vozlov v seznamu. Razred LinkedList vsebuje cel kup uporabnih metod za delo s seznami (vstavljanje, brisanje, prikaza števila elementov seznama, ...). Osnovne operacije, ki jih lahko izvedemo na linearnem seznamu so:
- Vstavljanje
- S to operacijo lahko vstavimo nov element na začetek, konec ali pa nekje znotaj seznama.
- Brisanje
- S to operacijo izbrišemo element na začetku, koncu ali nekje znotraj seznama.
- Iskanje
- S to operacijo poiščemo neko vrednost znotraj seznama.
Konstruktorji
- LinkedList(): Ustvari prazen povezan seznam.
LinkedList list= new LinkedList();
LinkedList(Collection< ? extends E> c)
Ustvari seznam, ki vsebuje elemente zbiralnika (Collection) c, v istem vrstnem redu kot je c. c je zbirka, katere elemente želimo vstaviti v seznam. Če je c enak null, nam metoda vrže izjemo tipa NullPointerException.
for(int i=1; i<=10; i++){ //vpišemo v seznam števila od 1-10 list.add(""+i); }
Zgled
- Neciklični verižni seznam
- Ciklični verižni seznam
Pomembnejše objektne metode
public E getFirst() Vrne prvi element iz seznama. V kolikor je seznam prazen nam metoda vrne napako.
list.add(a); list.add(c);
public E getLast() Vrne zadnji element iz seznama. V kolikor je seznam prazen nam metoda vrne napako.
list.add(a); list.add(c);
public E removeFirst() Metoda nam vrne in izbriše prvi element iz seznama. V kolikor je seznam prazen nam metoda vrne napako.
list.add(a); list.add(c); System.out.println("Prvi element iz seznama, ki ga bomo izbrisali je: "+ list.removeFirst()); //vrne a
public E removeLast() Metoda nam vrne in izbriše zadnji element iz seznama. V kolikor je seznam prazen nam metoda vrne napako.
list.add(a); list.add(c); System.out.println("Zadnji element iz seznama, ki ga bomo izbrisali je: "+ list.removeLast()); //vrne c
public void addFirst(E o) Metoda ničesar ne vrača. Vstavi dani element o na začetek povezanega seznama.
list.addFirst(c); //vpisemo na zacetek seznama c list.addFirst(a); //vpisemo na zacetek seznama a
public void addLast(E o) Metoda ničesar ne vrača. Vstavi dani element o na konec povezanega seznama. <javaLinkedList list = new LinkedList(); list.addLast(c); //vpisemo na konec seznama c list.addLast(a); //vpisemo na konec seznama a System.out.println("Listi v povezanem seznamu so: "+ list); //vrne c a</java>
public void add(int index, E element)
Doda določen element(element) na določeno mesto(index) seznama.
list.add(c); //vpisemo na konec seznama c list.add(a); //vpisemo na konec seznama a list.add(b, ""+20); // dodamo na b indeks vrednost 20
public int size() Metoda vrne število elementov v seznamu.
public void clear() Metoda ničesar ne vrača. Odstrani vse elemente iz seznama.
list.add(c); list.add(a); list.clear(); // Odstranimo vse elemente
Prednosti verižnega seznama
Dobra lastnost povezanega seznama je, da nam pri vstavljanju ali brisanju ni potrebno izvajati nobenega premikanja elementov, kot je to potrebno pri tabeli. Bistvena prednost povezanega seznama je tudi, da zavzema ravno toliko pomnilnika kot ga potrebuje ter, da ga lahko brez težav razširimo na ves razpoložljiv pomnilnik. Povezan seznam se v praksi zelo pogosto uporablja (za implementacijo različnih seznamov,sklada,vrste,...).Vstavljanje na začetek linearnega (povezanega) seznama oz. brisanje začetnega vozlišča je zelo hitro. Saj je potrebno zamenjati samo eno ali dve referenci. Pri iskanju, brisanju ali vstavljanju vozlišč nekje vmes, pa je potrebno preiskati seznam.
Primer
Napiši statično metodo ki vrne nov seznam z obrnjenimi elementi našega seznama!
public static LinSez obrni(LinSez s){ LinSez s1 = new LinSez(); Vozel p =s.vrniPrviVozel(); while(p! = null){ Vozel n =new Vozel(p.vrniPodatek()); s1.vstaviPrvega(n); p=p.vrniNasled(); } return s1; }