Dvostruko povezana lista, primer palindrom

diff --git a/kodovi/liste/Palindrom.java b/kodovi/liste/Palindrom.java
new file mode 100644 (file)
index 0000000..5b0a350
--- /dev/null
+++ b/kodovi/liste/Palindrom.java
@@ -0,0 +1,151 @@
+/**
+ * Demonstracija upotrebe dvostruko povezane liste za odredjivanje svih
+ * palindroma u listi znakova.
+ *
+ */
+public class Palindrom {
+
+       static void interaktivniTest() {
+               DPLista lista = new DPLista();
+               System.out.println("Unesite rec znak po znak, zavrsite unos tackom:");
+               char ulaz = Svetovid.in.readChar();
+               while (ulaz != '.') {
+                       lista.ubaciNaKraj(ulaz);
+                       ulaz = Svetovid.in.readChar();
+               }
+               System.out.println("Uneta rec je:" + lista);
+       }
+
+       static void testRec(String rec) {
+               System.out.println("= Rec:");
+               System.out.println(rec);
+               DPLista lista = new DPLista();
+               lista.ubaciString(rec);
+               System.out.println("= Palindromi:");
+               lista.stampajSvePalindrome();
+       }
+
+       public static void main(String[] args) {
+               // interaktivniTest();
+               testRec("abakus");
+               testRec("anavolimilovana");
+               testRec("nekoliko brodskih kapaka");
+               testRec("");
+               testRec(" ");
+       }
+
+}
+
+/**
+ * Dvostruko povezana lista znakova koja omogucava provere palindroma 
+ * u okviru liste. Lista ima pokazivace na prvi i poslednji element.
+ */
+class DPLista {
+
+       /**
+        * Klasa predstavlja jedan element dvostruko povezane liste sa pokazivacima
+        * na prethodni i sledeci, kao i poljem info koje sadrzi znak.
+        */
+       class Znak {
+               char info;
+               Znak sledeci;
+               Znak prethodni;
+
+               public Znak(char c) {
+                       this.info = c;
+                       this.sledeci = null;
+                       this.prethodni = null;
+               }
+
+               public String toString() {
+                       return info + "";
+               }
+       }
+
+       Znak prvi;
+       Znak poslednji;
+
+       /** Kreira novu praznu dvostruko povezanu listu znakova */
+       public DPLista() {
+               prvi = null;
+               poslednji = null;
+       }
+
+       public String toString() {
+               String rez = "";
+               Znak tekuci = prvi;
+               while (tekuci != null) {
+                       rez += tekuci.info;
+                       tekuci = tekuci.sledeci;
+               }
+               return rez;
+       }
+
+       public void ubaciNaKraj(char c) {
+               Znak novi = new Znak(c);
+               if (poslednji == null) {
+                       prvi = novi;
+                       poslednji = novi;
+               } else {
+                       novi.prethodni = poslednji;
+                       poslednji.sledeci = novi;
+                       poslednji = novi;
+               }
+       }
+
+       public void ubaciString(String rec) {
+               for (int i = 0; i < rec.length(); i++) {
+                       ubaciNaKraj(rec.charAt(i));
+               }
+       }
+
+       /**
+        * pomocni metod za nalazenje podreci oznacene sa dva pokazivaca. ne vrsi
+        * nikakve provere o validnosti datih argumenata.
+        */
+       public String podRec(Znak pocetak, Znak kraj) {
+               String rez = "";
+               Znak tekuci = pocetak;
+               while (tekuci != kraj) {
+                       rez += tekuci.info;
+                       tekuci = tekuci.sledeci;
+               }
+               rez += tekuci.info;
+               return rez;
+       }
+
+       /**
+        * Proverava da li je rec koja pocinje od pokazivaca pocetak do pokazivaca
+        * kraj predstavlja palindrom. Ne vrsi se nikakva provera validnosti prosledjenih
+        * pokazivaca, tako da metod moze da baci izuzetak u slucaju null pointera, kao i
+        * da radi beskonacno dugo u nekim slucajevima. 
+        */
+       public boolean jePalindrom(Znak pocetak, Znak kraj) {
+               while ((pocetak != kraj) && (pocetak.sledeci != kraj)) {
+                       if (pocetak.info != kraj.info) {
+                               return false;
+                       } else {
+                               pocetak = pocetak.sledeci;
+                               kraj = kraj.prethodni;
+                       }
+               }
+               return pocetak.info == kraj.info;
+       }
+
+       /**
+        * Stampa sve podreci ove reci koje su palindromi na ekran.
+        */
+       public void stampajSvePalindrome() {
+               Znak pocetak = prvi;
+               while (pocetak != null) {
+                       Znak kraj = poslednji;
+                       while (kraj != pocetak) {
+                               if (jePalindrom(pocetak, kraj)) {
+                                       System.out.println(podRec(pocetak, kraj));
+                               }
+                               kraj = kraj.prethodni;
+                       }
+                       pocetak = pocetak.sledeci;
+               }
+       }
+}
\ No newline at end of file