Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili. Kaj pomeni to opozorilo?

Vsebina 1 Verižni seznam 1.1 Vrste seznamov 1.2 Konstruktorji 1.3 Zgled 1.4 Pomembnejše objektne metode 1.5 Prednosti verižnega seznama 1.6 Primer 1.7 Glej tudi

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.

LinkedList list= new LinkedList();
for(int i=1; i<=10; i++){    //vpišemo v seznam števila od 1-10
list.add(""+i);
}
LinkedList list1= new LinkedList(list);  //Ustvarimo list1 in vanj kopiramo vse elemnte list-a. 

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.

LinkedList list = new LinkedList();
list.add(a);
list.add(c);
System.out.println("Prvi element v povezanem seznamu je: " + list.getFirst()); //vrne a 

public E getLast() Vrne zadnji element iz seznama. V kolikor je seznam prazen nam metoda vrne napako.

LinkedList list = new LinkedList();
list.add(a);
list.add(c);
System.out.println("Zadnji element v povezanem seznamu je: " + list.getLast()); //vrne c 

public E removeFirst() Metoda nam vrne in izbriše prvi element iz seznama. V kolikor je seznam prazen nam metoda vrne napako.

LinkedList list = new LinkedList();
list.add(a);
list.add(c);
System.out.println("Prvi element iz seznama, ki ga bomo izbrisali je: "+ list.removeFirst()); //vrne a
System.out.println("Listi v povezanem seznamu so: "+ list); //vrne c 

public E removeLast() Metoda nam vrne in izbriše zadnji element iz seznama. V kolikor je seznam prazen nam metoda vrne napako.

LinkedList list = new LinkedList();
list.add(a);
list.add(c);
System.out.println("Zadnji element iz seznama, ki ga bomo izbrisali je: "+ list.removeLast()); //vrne c
System.out.println("Listi v povezanem seznamu so: "+ list); //vrne a 

public void addFirst(E o) Metoda ničesar ne vrača. Vstavi dani element o na začetek povezanega seznama.

LinkedList list = new LinkedList();
list.addFirst(c);   //vpisemo na zacetek seznama c
list.addFirst(a);   //vpisemo na zacetek seznama a
System.out.println("Listi v povezanem seznamu so: "+ list); //vrne a c 

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.

LinkedList list = new LinkedList();
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
System.out.println("Listi v povezanem seznamu so: "+ list); //vrne c a 20 

public int size() Metoda vrne število elementov v seznamu.

LinkedList list = new LinkedList();
System.out.println("Velikost seznama je: "+list.size()); 

public void clear() Metoda ničesar ne vrača. Odstrani vse elemente iz seznama.

LinkedList list = new LinkedList();
list.add(c);
list.add(a);
list.clear();  // Odstranimo vse elemente
System.out.println("Listi v povezanem seznamu so: "+ list); //vrne 

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;
} 

Glej tudi

• Vrsta