Konverzija liste u i iz niza, lista koja se deli na dve

diff --git a/kodovi/liste/ListeKonverzija.java b/kodovi/liste/ListeKonverzija.java
new file mode 100644 (file)
index 0000000..a353cbd
--- /dev/null
+++ b/kodovi/liste/ListeKonverzija.java
@@ -0,0 +1,167 @@
+/**
+ * Primer pravljanja liste koja moze da se napravi od niza istog tipa elemenata
+ * i koja moze da napravi niz od svog sadrzaja.
+ *
+ */
+public class ListeKonverzija {
+
+       public static void main(String[] args) {
+               // demonstracija kako izgleda stampajniz
+               String[] ptice = new String[]{"golub", "vrana", "vrabac"};
+               System.out.println("niz:" + ptice); //toString od niza
+               stampajNiz(ptice);
+               
+               System.out.println();
+               
+               // pravimo novu listu od postojeceg niza
+               ListaN listaP = new ListaN();
+               listaP.dodajSve(ptice);
+               System.out.println(listaP);
+               listaP.dodaj("sova");
+               System.out.println(listaP);
+
+               System.out.println();
+
+               // ako nam je bitan redosled, onda koristimo drugi metod
+               ListaN druga = new ListaN();
+               druga.dodajSveUIstomRedosledu(ptice);
+               System.out.println(druga);
+
+               // mozemo dodavati i elemente druge liste
+               druga.dodajSve(listaP);
+               System.out.println(druga);
+               
+               System.out.println();
+               
+               // mozemo direktno u konstruktor da prosledimo niz
+               ListaN treca = new ListaN(ptice);
+               System.out.println(treca);
+               
+               System.out.println();
+               
+               // pravimo listu koju cemo pretvarati u niz
+               ListaN lista = new ListaN();
+
+               lista.dodaj("vrabac");
+               lista.dodaj("vrana");
+               lista.dodaj("golub");
+               lista.dodaj("albatros");
+
+               System.out.println(lista);
+
+               String[] niz = lista.napraviNiz();
+               System.out.println("niz:" + niz); //toString od niza
+               stampajNiz(niz);
+
+               String[] niz2 = lista.napraviNiz();
+               System.out.println("niz:" + niz2); //toString od niza
+               stampajNiz(niz2);
+               System.out.println("nizovi su jednaki:"+niz.equals(niz2));
+               
+               System.out.println();                           
+       }
+
+       public static void stampajNiz(String[] niz) {
+               System.out.print("sadzaj niza:");
+               for (String s : niz) {
+                       System.out.print('"' + s + '"' + ' ');
+               }
+               System.out.println();
+       }
+
+}
+
+/**
+ * Lista strigova koja omogucava da njen sadrzaj pretvori u niz, kao i da se
+ * lista napravi od niza, ili da se dodaju svi elementi iz nekog niza.
+ */
+class ListaN {
+
+       class Element {
+               String info;
+               Element veza;
+
+               public Element(String s) {
+                       info = s;
+                       veza = null;
+               }
+       }
+
+       // pokazivac na prvi element liste
+       Element prvi;
+
+       // interni brojac koji pomaze kod nekih operacija
+       int brojElemenata;
+
+       /** Kreira praznu listu. */
+       public ListaN() {
+               this.prvi = null;
+               this.brojElemenata = 0;
+       }
+
+       /** Kreira listu u kojoj je pocetni sadrzaj iskopiran iz prosledjenog niza */
+       public ListaN(String[] stringovi) {
+               this.dodajSveUIstomRedosledu(stringovi);
+       }
+
+       public String toString() {
+               String rez = "ListaN: [ ";
+               Element tekuci = prvi;
+               while (tekuci != null) {
+                       rez += '"' + tekuci.info + "\" ";
+                       tekuci = tekuci.veza;
+               }
+               rez += "]";
+               return rez;
+       }
+
+       /** vraca broj elemenata u listi */
+       public int velicina() {
+               return brojElemenata;
+       }
+
+       /** Vraca da li je lista prazna */
+       public boolean jePrazna() {
+               return prvi == null;
+       }
+
+       public void dodaj(String str) {
+               Element novi = new Element(str);
+               novi.veza = prvi;
+               prvi = novi;
+               brojElemenata++;
+       }
+
+       public void dodajSve(String[] stringovi) {
+               for (String s : stringovi) {
+                       dodaj(s);
+               }
+       }
+
+       public void dodajSveUIstomRedosledu(String[] stringovi) {
+               for (int i = stringovi.length - 1; i >= 0; i--) {
+                       dodaj(stringovi[i]);
+               }
+       }
+
+       public String[] napraviNiz() {
+               String[] niz = new String[brojElemenata];
+               Element tekuci = prvi;
+               int br = 0;
+               while (tekuci != null) {
+                       niz[br] = tekuci.info;
+                       br++;
+                       tekuci = tekuci.veza;
+               }
+               return niz;
+       }
+       
+       public void dodajSve(ListaN lista) {
+               Element tekuci = lista.prvi;
+               while (tekuci != null) {
+                       dodaj(tekuci.info);
+                       tekuci = tekuci.veza;
+               }
+       }
+
+}
\ No newline at end of file

diff --git a/kodovi/liste/ListePodela.java b/kodovi/liste/ListePodela.java
new file mode 100644 (file)
index 0000000..fa71786
--- /dev/null
+++ b/kodovi/liste/ListePodela.java
@@ -0,0 +1,339 @@
+/**\r
+ * Progam predstavlja primere podele liste na dve, samo premestanje pokazivaca,\r
+ * odnosno bez zauzimanja memorije za nove elemente.\r
+ */\r
+public class ListePodela {\r
+\r
+       static void testNaizmenicnoPrviParan() {\r
+               DeljivaLista l = new DeljivaLista();\r
+               int n = 5;\r
+               for (int i = 0; i < n; i++) {\r
+                       l.dodaj(i);\r
+               }\r
+               System.out.println("originalna lista:");\r
+               System.out.println(l);\r
+\r
+               System.out.println("nove liste:");\r
+               DeljivaLista l2 = l.izdvojParne();\r
+               System.out.println(l);\r
+               System.out.println(l2);\r
+       }\r
+\r
+       static void testNaizmenicnoPrviNeParan() {\r
+               DeljivaLista l = new DeljivaLista();\r
+               int n = 5;\r
+               for (int i = 0; i < n; i++) {\r
+                       l.dodaj(i + 1);\r
+               }\r
+               System.out.println("originalna lista:");\r
+               System.out.println(l);\r
+\r
+               System.out.println("nove liste:");\r
+               DeljivaLista l2 = l.izdvojParne();\r
+               System.out.println(l);\r
+               System.out.println(l2);\r
+       }\r
+\r
+       static void testSviParni() {\r
+               DeljivaLista l = new DeljivaLista();\r
+               int n = 5;\r
+               for (int i = 0; i < n; i++) {\r
+                       l.dodaj(i * 2);\r
+               }\r
+               System.out.println("originalna lista:");\r
+               System.out.println(l);\r
+\r
+               System.out.println("nove liste:");\r
+               DeljivaLista l2 = l.izdvojParne();\r
+               System.out.println(l);\r
+               System.out.println(l2);\r
+       }\r
+\r
+       static void testSviNeparni() {\r
+               DeljivaLista l = new DeljivaLista();\r
+               int n = 5;\r
+               for (int i = 0; i < n; i++) {\r
+                       l.dodaj(i * 2 + 1);\r
+               }\r
+               System.out.println("originalna lista:");\r
+               System.out.println(l);\r
+\r
+               System.out.println("nove liste:");\r
+               DeljivaLista l2 = l.izdvojParne();\r
+               System.out.println(l);\r
+               System.out.println(l2);\r
+       }\r
+\r
+       static void testUzastopniParni() {\r
+               DeljivaLista l = new DeljivaLista();\r
+               l.dodaj(7);\r
+               int n = 3;\r
+               for (int i = 0; i < n; i++) {\r
+                       l.dodaj(i * 2);\r
+               }\r
+               l.dodaj(5);\r
+               l.dodaj(8);\r
+               l.dodaj(5);\r
+\r
+               System.out.println("originalna lista:");\r
+               System.out.println(l);\r
+\r
+               System.out.println("nove liste:");\r
+               DeljivaLista l2 = l.izdvojParne();\r
+               System.out.println(l);\r
+               System.out.println(l2);\r
+       }\r
+\r
+       static void testPrvihN1() {\r
+               DeljivaLista l = new DeljivaLista();\r
+               int n = 5;\r
+               for (int i = 0; i < n; i++) {\r
+                       l.dodaj(i);\r
+               }\r
+\r
+               System.out.println("originalna lista:");\r
+               System.out.println(l);\r
+\r
+               System.out.println("nove liste:");\r
+               DeljivaLista l2 = l.izdvojPrvihN(1);\r
+               System.out.println(l);\r
+               System.out.println(l2);\r
+       }\r
+       \r
+       static void testPrvihN0() {\r
+               DeljivaLista l = new DeljivaLista();\r
+               int n = 5;\r
+               for (int i = 0; i < n; i++) {\r
+                       l.dodaj(i);\r
+               }\r
+\r
+               System.out.println("originalna lista:");\r
+               System.out.println(l);\r
+\r
+               System.out.println("nove liste:");\r
+               DeljivaLista l2 = l.izdvojPrvihN(0);\r
+               System.out.println(l);\r
+               System.out.println(l2);\r
+       }\r
+       \r
+       static void testPrvihN3() {\r
+               DeljivaLista l = new DeljivaLista();\r
+               int n = 5;\r
+               for (int i = 0; i < n; i++) {\r
+                       l.dodaj(i);\r
+               }\r
+\r
+               System.out.println("originalna lista:");\r
+               System.out.println(l);\r
+\r
+               System.out.println("nove liste:");\r
+               DeljivaLista l2 = l.izdvojPrvihN(3);\r
+               System.out.println(l);\r
+               System.out.println(l2);\r
+       }\r
+       \r
+       static void testPrvihNN() {\r
+               DeljivaLista l = new DeljivaLista();\r
+               int n = 5;\r
+               for (int i = 0; i < n; i++) {\r
+                       l.dodaj(i);\r
+               }\r
+\r
+               System.out.println("originalna lista:");\r
+               System.out.println(l);\r
+\r
+               System.out.println("nove liste:");\r
+               DeljivaLista l2 = l.izdvojPrvihN(n);\r
+               System.out.println(l);\r
+               System.out.println(l2);\r
+       }\r
+       \r
+       static void testPrvihNN1() {\r
+               DeljivaLista l = new DeljivaLista();\r
+               int n = 5;\r
+               for (int i = 0; i < n; i++) {\r
+                       l.dodaj(i);\r
+               }\r
+\r
+               System.out.println("originalna lista:");\r
+               System.out.println(l);\r
+\r
+               System.out.println("nove liste:");\r
+               DeljivaLista l2 = l.izdvojPrvihN(n+1);\r
+               System.out.println(l);\r
+               System.out.println(l2);\r
+       }\r
+       \r
+       static void testPrvihN2N() {\r
+               DeljivaLista l = new DeljivaLista();\r
+               int n = 5;\r
+               for (int i = 0; i < n; i++) {\r
+                       l.dodaj(i);\r
+               }\r
+\r
+               System.out.println("originalna lista:");\r
+               System.out.println(l);\r
+\r
+               System.out.println("nove liste:");\r
+               DeljivaLista l2 = l.izdvojPrvihN(2*n);\r
+               System.out.println(l);\r
+               System.out.println(l2);\r
+       }\r
+       \r
+       public static void main(String[] args) {\r
+               testNaizmenicnoPrviParan();\r
+               System.out.println();\r
+               testNaizmenicnoPrviNeParan();\r
+               System.out.println();\r
+               testSviParni();\r
+               System.out.println();\r
+               testSviNeparni();\r
+               System.out.println();\r
+               testUzastopniParni();\r
+               System.out.println();\r
+               System.out.println("Izdvajanje prvih 0:");\r
+               testPrvihN0();\r
+               System.out.println("Izdvajanje prvih 1:");\r
+               testPrvihN1();\r
+               System.out.println("Izdvajanje prvih 3:");\r
+               testPrvihN3();\r
+               System.out.println("Izdvajanje prvih N:");\r
+               testPrvihNN();\r
+               System.out.println("Izdvajanje prvih N+1:");\r
+               testPrvihNN1();\r
+               System.out.println("Izdvajanje prvih 2*N:");\r
+               testPrvihN2N();\r
+       }\r
+\r
+}\r
+\r
+/**\r
+ * Lista brojeva koja omogucava da se iz nje izdvoji nova lista u kojoj se\r
+ * nalaze samo parni brojevi.\r
+ */\r
+class DeljivaLista {\r
+\r
+       class Element {\r
+               int info;\r
+               Element veza;\r
+\r
+               public Element(int br) {\r
+                       info = br;\r
+                       veza = null;\r
+               }\r
+\r
+               public String toString() {\r
+                       return info + "";\r
+               }\r
+\r
+       }\r
+\r
+       Element prvi;\r
+\r
+       public DeljivaLista() {\r
+               prvi = null;\r
+       }\r
+\r
+       public void dodaj(int br) {\r
+               Element novi = new Element(br);\r
+               novi.veza = prvi;\r
+               prvi = novi;\r
+       }\r
+\r
+       public String toString() {\r
+               String rez = "DeljivaLista: [ ";\r
+               Element tekuci = prvi;\r
+               while (tekuci != null) {\r
+                       rez += tekuci.info + " ";\r
+                       tekuci = tekuci.veza;\r
+               }\r
+               rez += "]";\r
+               return rez;\r
+       }\r
+\r
+       /**\r
+        * Metod pravi novu listu koja se sastoji od izdvojenih parnih elemenata ove\r
+        * liste, pri cemu se ne zauzima nova memorija. Nakon poziva ovog metoda\r
+        * lista na kojoj je pozvan se sastoji samo od neparnih elemenata.\r
+        * \r
+        * @return lista parnih elemenata ove liste\r
+        */\r
+       public DeljivaLista izdvojParne() {\r
+               // buduci rezultat operacije\r
+               DeljivaLista parni = new DeljivaLista();\r
+\r
+               // da bi dodavali na kraj mozemo imati lokalnu\r
+               // promenljivu koja pamti gde je kraj\r
+               Element parniKraj = null;\r
+\r
+               Element tek, pret;\r
+\r
+               while (prvi != null && prvi.info % 2 == 0) {\r
+                       tek = prvi;\r
+                       prvi = prvi.veza;\r
+                       if (parni.prvi == null) {\r
+                               parni.prvi = tek;\r
+                               parniKraj = tek;\r
+                               tek.veza = null;\r
+                       } else {\r
+                               parniKraj.veza = tek;\r
+                               tek.veza = null;\r
+                               parniKraj = tek;\r
+                       }\r
+               }\r
+\r
+               if (prvi != null) {\r
+                       tek = prvi;\r
+                       while (tek.veza != null) {\r
+                               pret = tek;\r
+                               tek = tek.veza;\r
+                               if (tek.info % 2 == 0) {\r
+                                       pret.veza = tek.veza;\r
+                                       if (parni.prvi == null) {\r
+                                               parni.prvi = tek;\r
+                                               tek.veza = null;\r
+                                               parniKraj = tek;\r
+                                       } else {\r
+                                               parniKraj.veza = tek;\r
+                                               tek.veza = null;\r
+                                               parniKraj = tek;\r
+                                       }\r
+                                       tek = pret;\r
+                               }\r
+                       }\r
+               }\r
+\r
+               return parni;\r
+       }\r
+\r
+       /**\r
+         * Vraca novu listu koja se sastoji od prvih `n` elemenata\r
+         * ove liste, a ova lista se nakon poziva sastoji od ostatka.\r
+         * U slucaju da je `n` nepozitivan broj bice vracena prazna lista,\r
+         * a u slucaju da je `n` vece ili jednako broju elemenata u listi\r
+         * nova lista ce se sastojati od cele ove liste, a ova ce ostati\r
+         * prazna.\r
+         */\r
+       public DeljivaLista izdvojPrvihN(int n) {\r
+               DeljivaLista rezultat = new DeljivaLista();\r
+               if (n <= 0) {\r
+                       return rezultat;\r
+               }\r
+               \r
+               rezultat.prvi = prvi;\r
+\r
+               int brojac = 0;\r
+               Element poslednji = prvi;\r
+               while (poslednji != null && brojac < n - 1) {\r
+                       poslednji = poslednji.veza;\r
+                       brojac++;\r
+               }\r
+               if (poslednji != null) {\r
+                       prvi = poslednji.veza;\r
+                       poslednji.veza = null;\r
+               } else {\r
+                       prvi = null;\r
+               }\r
+               return rezultat;\r
+       }\r
+}\r