Zbirke ali kolekcije so objekti, ki vsebujejo druge objekte (tiste, ki jih v take zbirke shranjujemo) in metode za delo z objekti, ki jih kolekcije vsebujejo. Objekti, vsebovani oz. shranjeni v kolekciji so lahko istega ali pa različnih tipov.
Prvotne inačice Jave niso vsebovale zbirk, zato jih boste tam zaman iskali. Vendar se je uporaba in koristnost prvih implementacij izkazala za tako koristno, da je različnih namenskih realizacij čedalje več. Tako je inačica Java2 1.4 vsebovala 6 različnih tipov zbirk, inačica iste platforme s številko 1.5 že devet, ...
Zastavlja se vprašanje, za kaj so zbirke uporabne ? Tipično večjo količino objektov shranjujemo v 'klasične zbirke', kot so tabele, datoteke. Vendar s temi nastopajo problemi, kot so : omejenost velikost tabele, počasnost procesiranja podatkov na zananjem mediju (datoteka). Probleme so programerji reševali z dinamičnimi podatkovnimi strukturami (seznami, drevesi, ...), vendar je bilo potrebno tako strukturo najprej programsko zgraditi in nato še spisati vse mehanizme za delo s posameznimi elementi.
Ideja zbirk je zato v naslednjem : dajmo programerjem že izdelane mehanizme za izgradnjo take strukture, hkrati pa tudi vse potrebne mehanizme za delo z elementi strukture. S tem programerjem prihranimo čas za gradnjo strukture in mehanizmov, pa še končni mehanizmi ne bodo podvrženi neoptimalni realizaciji (pomnite: javanska realizacija razedov gre skozi proces certifikacije !)
V tem poglavju se ne bomo ukvarjali s tem, kdaj izbrati katero iz zbirk, temveč bomo eno izmed njih uporabili.LinkedList je ena izmed zbirk, ki se uporablja predvsem za realizacijo struktur, kot sta npr.: vrsta in sklad. Tipično se taka struktura uporablja kot tipizirana oz. homogena struktura; se pravi, da so vsi elementi v njen istega tipa.
Za naš primer si bomo pogledali strukturo, ki bo vsebovala objekte tipa String.
LinkedList<String> zbirkaBesed = new LinkedList<string>();
pravi, da bomo kreirali nov objekt (zbirko), ki bo vrste LinkedList. Tako zbirko lahko uporabimo za elemente poljubnih tipov, zato tipu v ostrih oklepajih ( < > ) sledi tip elementa, ki ga bomo shranjevali v tej zbirki. V našem primeru so elementi nizo znakov (String).
naša zbirka ima definirane družine metod naslednjih vrst:
add/addFirst/addLast/addAll
zbirkaBesed.add("da");
zbirkaBesed.add("se");
zbirkaBesed.add("mi");
zbirkaBesed.add("kidat");
zbirkaBesed.add("sneg");
v zbirko zaporedno doda pet objektov tipa String; najprej "da" in na koncu "sneg".
get/getFirst/getLast
System.out.println(""+zbirkaBesed.getFirst() ); // da
System.out.println(""+zbirkaBesed.getLast() ); // sneg
System.out.println(""+zbirkaBesed.get(3) ); // kidat
so primeri doseganja do posameznih elementov; najprej do prvega, nato do zadnjega in na koncu do tistega, ki ima indeks 3
remove/removeFirst/removeLast
zbirkaBesed.removeFirst(); // odstrani prvega (z najmanjšim indeksom) zbirkaBesed.removeLast(); // odstrani zadnjega zbirkaBesed.remove(2); // odstrani element z indeksom 2
se pravi, da odstrani besedi da, sneg in nato še besedico kidat, ki ima po brisanju prvih dveh indeks 2
Naštetih je nekaj, za podrobnejši opis in spisek vseh metod, si poglejte dokumentacij za uporabljen razred
clear(), size(), peek(), poll(),indexOf(),lastIndexOf(), ...
od teh instantno pride prav le clear(), ki vam sprazni kolekcijo, če to potrebujete, size(), ki vrne število elementov v kolekciji.
import java.util.*;
public class LnkListTest{
public static void main(String[] arg){
LinkedList<String> zbirkaBesed = new LinkedList<String>();
zbirkaBesed.add("da");zbirkaBesed.add("se");zbirkaBesed.add("mi");
zbirkaBesed.add("sneg");zbirkaBesed.add("kidat");
for (String s: zbirkaBesed)
System.out.print(s+" ");
System.out.println();
System.out.println("prvi el. je: "+zbirkaBesed.getFirst());
System.out.println("zadnji el. je: "+zbirkaBesed.getLast());
System.out.println("cetrti el. je: "+zbirkaBesed.get(3));
zbirkaBesed.removeFirst();
zbirkaBesed.removeLast();
zbirkaBesed.removeFirst(3);
zbirkaBesed.remove("mi");
System.out.println("odstranjeni : prvi, zadnji, novi cetrti, \"m\" ..");
for (String s: zbirkaBesed)
System.out.print(s+" ");
System.out.println();
zbirkaBesed.add(1,"novi");
for (String s: zbirkaBesed)
System.out.print(s+" ");
System.out.println();
System.out.println("stevilo elementov: "+zbirkaBesed.size());
zbirkaBesed.clear();
System.out.println("stevilo elementov po clear(): "+zbirkaBesed.size());
}
}
Program izvaja simulacijo dodajanja in odvzemanja elementov iz zbirke.Izpis, ki ga povzroči, je naslednji:
da se mi sneg kidat prvi el. je: da zadnji el. je: kidat cetrti el. je: sneg odstranjeni : prvi, zadnji, novi drugi, "mi" .. se sneg se novi sneg stevilo elementov: 3 stevilo elementov po clear(): 0
Poglejmo si primer programa, ki je namenjen razvrščanju elementov tabele v nepadajočem vrstnem redu. Postopek, uporabljen v primeru je t.i. hitro razvrščanje /Quick sort/:
public class QuickSort {
// zamenja a[i] in a[j]
private static void zamenjaj(double[] a, int i, int j) {
double swap = a[i];
a[i] = a[j];
a[j] = swap;
}
private static int part(double[] a, int left, int right) {
int i = left - 1;
int j = right;
while (true) {
while (a[++i] < a[right]);
while ( a[right] < a[--j]))
if (j == left)
break;
if (i >= j) break;
zamenjaj(a, i, j);
}
zamenjaj(a, i, right);
return i;
}
public static void quicksort(double[] a) {
quicksort(a, 0, a.length - 1);
}
public static void quicksort(double[] a, int left, int right) {
if (right <= left)
return;
int i = part(a, left, right);
quicksort(a, left, i-1);
quicksort(a, i+1, right);
}
public static void main(String[] args) {
int N = 50;
double[] a = new double[N];
for (int i = 0; i < N; i++)
a[i] = Math.random();
quicksort(a);
}
}
če malo bolje pogledamo, lahko ugotovimo, da postopek ni najenostavnejši. Pisanje tega postopka bi avtorju vzelo kar nekaj časa, poleg tega, pa je dani postopek spisan tako, da zna razvrščati elemente le v tabeli necelih števil.
Nad zbirkami je možno izvesti iskanje želenega elementa, razvrščanje, ne da bi poznali mehanizme iskanja oz. razvrščanja. V principu nas ti postopki ne zanimajo, dovolj je da se zavedamo, da obstajajo. S takim pristopom do zbirk se Java približuje deklarativnim programskim jezikom.
Primer :
izvedimo najprej dodaten test nad zbirko vrste LinkedList:
import java.util.*;
public class LnkListTest2{
public static void main(String[] arg){
LinkedList<String> zbirkaBesed = new LinkedList<String>();
zbirkaBesed.add("da"); zbirkaBesed.add("se");
zbirkaBesed.add("mi"); zbirkaBesed.add("sneg");
zbirkaBesed.add("kidat");
System.out.print("original :");
System.out.println(zbirkaBesed);
System.out.print("razvrsceno :");
Collection.sort(zbirkaBesed);
System.out.println(zbirkaBesed);
System.out.println("\"kidat\" se nahaja na poziciji: "+
Collections.binarySearch(zbirkaBesed,"kidat"));
}
}
izpis iz izvedenega programa govori sam zase:
original :[da, se, mi, sneg, kidat] razvrsceno :[da, kidat, mi, se, sneg] "kidat" se nahaja na poziciji: 1
To pa še ni vse :
celotno kodo razreda QuickSort lahko nadomestimo preprosto z naslednjim :
class QSortA{
public static void main(String[] args) {
int N = 50;
double[] a = new double[N];
for (int i = 0; i < N; i++)
a[i] = Math.random();
Arrays.sort(a);
for (double d : a)
System.out.println(d);
}
}
na enak način bi za iskanje elementa v tabeli lahko uporabili binarno iskanje :
int kjeJe = Arrays.binarySearch(tabela,iskaniKljuc);
Naloga 1
Realizirajte vrsto celoštevilskih vrednosti. Osnovni operaciji realizirajte kot metodi razreda:
Implementacija razreda naj vsebuje tudi oba kazalca, glavo in rep , ki označujeta začetek in konec podatkovne strukture:
Realizacija naj preprečuje dodajanje elementa v primereu, da je vrsta polna in odvzemanje elementa v primeru, da je vrsta prazna. 'Podatkovna struktura' za realizacijo naj bo tabela 20-tih celoštevilskih vrednosti:
static int vrsta[];
Naloga 2
Podobno kot v prvi nalogi vrsto, realizirajte sklad. Pri skladu se od vrste razlikuje zgolj mehanizem delovanja. Sklad naj bo podobno kot v predhodni nalogi realiziran s tabelo celoštevilskih vrednosti velikost 20 elementov.
Naloga 3
Realizirajte obe podatkovni strukturi z uporabo zbirk, konkretno: uporabite LinkedList. Ker ste pri velikosti zbirke objektov omejeni zgolj s pomnilnikov, upoštevajte, da je največja možna velikost strukture 20 elementov. Dodajanje 21-tega elementa naj povzroči prekoračitev obsega !