kodovi/liste/ObrtanjeListe.java

   1 /**
   2  * Primer obrtanja liste unazad u jednom prolazu. Ovo može biti vrlo pogodno
   3  * ukoliko nam je bitno da lista na kraju unosa bude u onom redosledu u kome su
   4  * unošeni elementi, a ne želimo da imamo dodatni pokazivač na poslednji
   5  * element.
   6  */
   7 public class ObrtanjeListe {
   8
   9         public static void main(String[] args) {
  10                 ListaStringovaOb lista = new ListaStringovaOb();
  11
  12                 lista.dodaj("prvi");
  13                 lista.dodaj("neki el");
  14                 lista.dodaj("svasta");
  15                 lista.dodaj("nista");
  16                 lista.dodaj("poslednji");
  17
  18                 System.out.println(lista);
  19
  20                 lista.obrniListu();
  21
  22                 System.out.println(lista);
  23         }
  24
  25 }
  26
  27 /**
  28  * Lista stringova sa dodatnom operacijom obrtanja liste unazad.
  29  */
  30 class ListaStringovaOb {
  31         class Element {
  32                 String info;
  33                 Element veza;
  34
  35                 public Element(String s) {
  36                         this.info = s;
  37                         this.veza = null;
  38                 }
  39
  40                 public String toString() {
  41                         return info + "";
  42                 }
  43         }
  44
  45         // pokazivac na prvi element liste
  46         Element prvi = null;
  47
  48         public String toString() {
  49                 String rez = "Lista: [ ";
  50                 Element tekuci = prvi;
  51                 while (tekuci != null) {
  52                         rez += '"' + tekuci.info + "\" ";
  53                         tekuci = tekuci.veza;
  54                 }
  55                 rez += "]";
  56                 return rez;
  57         }
  58
  59         public void dodaj(String s) {
  60                 Element novi = new Element(s);
  61                 novi.veza = prvi;
  62                 prvi = novi;
  63         }
  64
  65         /**
  66          * Obrće elemente liste tako da prvi postane poslednji, a poslednji prvi.
  67          * Operacija se obavlja u samo jednom prolasku kroz listu.
  68          */
  69         public void obrniListu() {
  70                 if (prvi == null || prvi.veza == null) {
  71                         // znaci da nemamo sta da radimo
  72                         return;
  73                 }
  74
  75                 // postoje bar 2 elementa
  76                 Element preth = null;
  77                 Element tek = prvi;
  78
  79                 while (tek != null) {
  80                         /**
  81                          * prevezujemo da element tek pokazuje na element preth; potrebno je
  82                          * da zapamtimo sledeci jer cemo izgubiti vezu na njega inace
  83                          */
  84                         Element sled = tek.veza;
  85
  86                         tek.veza = preth;
  87
  88                         // pomeramo se na sledeca dva
  89                         preth = tek;
  90                         tek = sled;
  91                 }
  92
  93                 prvi = preth;
  94         }
  95 }