kodovi/liste/ListePodela.java

   1 /**
   2  * Progam predstavlja primere podele liste na dve, samo premestanje pokazivaca,
   3  * odnosno bez zauzimanja memorije za nove elemente.
   4  */
   5 public class ListePodela {
   6
   7         static void testNaizmenicnoPrviParan() {
   8                 DeljivaLista l = new DeljivaLista();
   9                 int n = 5;
  10                 for (int i = 0; i < n; i++) {
  11                         l.dodaj(i);
  12                 }
  13                 System.out.println("originalna lista:");
  14                 System.out.println(l);
  15
  16                 System.out.println("nove liste:");
  17                 DeljivaLista l2 = l.izdvojParne();
  18                 System.out.println(l);
  19                 System.out.println(l2);
  20         }
  21
  22         static void testNaizmenicnoPrviNeParan() {
  23                 DeljivaLista l = new DeljivaLista();
  24                 int n = 5;
  25                 for (int i = 0; i < n; i++) {
  26                         l.dodaj(i + 1);
  27                 }
  28                 System.out.println("originalna lista:");
  29                 System.out.println(l);
  30
  31                 System.out.println("nove liste:");
  32                 DeljivaLista l2 = l.izdvojParne();
  33                 System.out.println(l);
  34                 System.out.println(l2);
  35         }
  36
  37         static void testSviParni() {
  38                 DeljivaLista l = new DeljivaLista();
  39                 int n = 5;
  40                 for (int i = 0; i < n; i++) {
  41                         l.dodaj(i * 2);
  42                 }
  43                 System.out.println("originalna lista:");
  44                 System.out.println(l);
  45
  46                 System.out.println("nove liste:");
  47                 DeljivaLista l2 = l.izdvojParne();
  48                 System.out.println(l);
  49                 System.out.println(l2);
  50         }
  51
  52         static void testSviNeparni() {
  53                 DeljivaLista l = new DeljivaLista();
  54                 int n = 5;
  55                 for (int i = 0; i < n; i++) {
  56                         l.dodaj(i * 2 + 1);
  57                 }
  58                 System.out.println("originalna lista:");
  59                 System.out.println(l);
  60
  61                 System.out.println("nove liste:");
  62                 DeljivaLista l2 = l.izdvojParne();
  63                 System.out.println(l);
  64                 System.out.println(l2);
  65         }
  66
  67         static void testUzastopniParni() {
  68                 DeljivaLista l = new DeljivaLista();
  69                 l.dodaj(7);
  70                 int n = 3;
  71                 for (int i = 0; i < n; i++) {
  72                         l.dodaj(i * 2);
  73                 }
  74                 l.dodaj(5);
  75                 l.dodaj(8);
  76                 l.dodaj(5);
  77
  78                 System.out.println("originalna lista:");
  79                 System.out.println(l);
  80
  81                 System.out.println("nove liste:");
  82                 DeljivaLista l2 = l.izdvojParne();
  83                 System.out.println(l);
  84                 System.out.println(l2);
  85         }
  86
  87         static void testPrvihN1() {
  88                 DeljivaLista l = new DeljivaLista();
  89                 int n = 5;
  90                 for (int i = 0; i < n; i++) {
  91                         l.dodaj(i);
  92                 }
  93
  94                 System.out.println("originalna lista:");
  95                 System.out.println(l);
  96
  97                 System.out.println("nove liste:");
  98                 DeljivaLista l2 = l.izdvojPrvihN(1);
  99                 System.out.println(l);
 100                 System.out.println(l2);
 101         }
 102
 103         static void testPrvihN0() {
 104                 DeljivaLista l = new DeljivaLista();
 105                 int n = 5;
 106                 for (int i = 0; i < n; i++) {
 107                         l.dodaj(i);
 108                 }
 109
 110                 System.out.println("originalna lista:");
 111                 System.out.println(l);
 112
 113                 System.out.println("nove liste:");
 114                 DeljivaLista l2 = l.izdvojPrvihN(0);
 115                 System.out.println(l);
 116                 System.out.println(l2);
 117         }
 118
 119         static void testPrvihN3() {
 120                 DeljivaLista l = new DeljivaLista();
 121                 int n = 5;
 122                 for (int i = 0; i < n; i++) {
 123                         l.dodaj(i);
 124                 }
 125
 126                 System.out.println("originalna lista:");
 127                 System.out.println(l);
 128
 129                 System.out.println("nove liste:");
 130                 DeljivaLista l2 = l.izdvojPrvihN(3);
 131                 System.out.println(l);
 132                 System.out.println(l2);
 133         }
 134
 135         static void testPrvihNN() {
 136                 DeljivaLista l = new DeljivaLista();
 137                 int n = 5;
 138                 for (int i = 0; i < n; i++) {
 139                         l.dodaj(i);
 140                 }
 141
 142                 System.out.println("originalna lista:");
 143                 System.out.println(l);
 144
 145                 System.out.println("nove liste:");
 146                 DeljivaLista l2 = l.izdvojPrvihN(n);
 147                 System.out.println(l);
 148                 System.out.println(l2);
 149         }
 150
 151         static void testPrvihNN1() {
 152                 DeljivaLista l = new DeljivaLista();
 153                 int n = 5;
 154                 for (int i = 0; i < n; i++) {
 155                         l.dodaj(i);
 156                 }
 157
 158                 System.out.println("originalna lista:");
 159                 System.out.println(l);
 160
 161                 System.out.println("nove liste:");
 162                 DeljivaLista l2 = l.izdvojPrvihN(n+1);
 163                 System.out.println(l);
 164                 System.out.println(l2);
 165         }
 166
 167         static void testPrvihN2N() {
 168                 DeljivaLista l = new DeljivaLista();
 169                 int n = 5;
 170                 for (int i = 0; i < n; i++) {
 171                         l.dodaj(i);
 172                 }
 173
 174                 System.out.println("originalna lista:");
 175                 System.out.println(l);
 176
 177                 System.out.println("nove liste:");
 178                 DeljivaLista l2 = l.izdvojPrvihN(2*n);
 179                 System.out.println(l);
 180                 System.out.println(l2);
 181         }
 182
 183         public static void main(String[] args) {
 184                 testNaizmenicnoPrviParan();
 185                 System.out.println();
 186                 testNaizmenicnoPrviNeParan();
 187                 System.out.println();
 188                 testSviParni();
 189                 System.out.println();
 190                 testSviNeparni();
 191                 System.out.println();
 192                 testUzastopniParni();
 193                 System.out.println();
 194                 System.out.println("Izdvajanje prvih 0:");
 195                 testPrvihN0();
 196                 System.out.println("Izdvajanje prvih 1:");
 197                 testPrvihN1();
 198                 System.out.println("Izdvajanje prvih 3:");
 199                 testPrvihN3();
 200                 System.out.println("Izdvajanje prvih N:");
 201                 testPrvihNN();
 202                 System.out.println("Izdvajanje prvih N+1:");
 203                 testPrvihNN1();
 204                 System.out.println("Izdvajanje prvih 2*N:");
 205                 testPrvihN2N();
 206         }
 207
 208 }
 209
 210 /**
 211  * Lista brojeva koja omogucava da se iz nje izdvoji nova lista u kojoj se
 212  * nalaze samo parni brojevi.
 213  */
 214 class DeljivaLista {
 215
 216         class Element {
 217                 int info;
 218                 Element veza;
 219
 220                 public Element(int br) {
 221                         info = br;
 222                         veza = null;
 223                 }
 224
 225                 public String toString() {
 226                         return info + "";
 227                 }
 228
 229         }
 230
 231         Element prvi;
 232
 233         public DeljivaLista() {
 234                 prvi = null;
 235         }
 236
 237         public void dodaj(int br) {
 238                 Element novi = new Element(br);
 239                 novi.veza = prvi;
 240                 prvi = novi;
 241         }
 242
 243         public String toString() {
 244                 String rez = "DeljivaLista: [ ";
 245                 Element tekuci = prvi;
 246                 while (tekuci != null) {
 247                         rez += tekuci.info + " ";
 248                         tekuci = tekuci.veza;
 249                 }
 250                 rez += "]";
 251                 return rez;
 252         }
 253
 254         /**
 255          * Metod pravi novu listu koja se sastoji od izdvojenih parnih elemenata ove
 256          * liste, pri cemu se ne zauzima nova memorija. Nakon poziva ovog metoda
 257          * lista na kojoj je pozvan se sastoji samo od neparnih elemenata.
 258          *
 259          * @return lista parnih elemenata ove liste
 260          */
 261         public DeljivaLista izdvojParne() {
 262                 // buduci rezultat operacije
 263                 DeljivaLista parni = new DeljivaLista();
 264
 265                 // da bi dodavali na kraj mozemo imati lokalnu
 266                 // promenljivu koja pamti gde je kraj
 267                 Element parniKraj = null;
 268
 269                 Element tek, pret;
 270
 271                 while (prvi != null && prvi.info % 2 == 0) {
 272                         tek = prvi;
 273                         prvi = prvi.veza;
 274                         if (parni.prvi == null) {
 275                                 parni.prvi = tek;
 276                                 parniKraj = tek;
 277                                 tek.veza = null;
 278                         } else {
 279                                 parniKraj.veza = tek;
 280                                 tek.veza = null;
 281                                 parniKraj = tek;
 282                         }
 283                 }
 284
 285                 if (prvi != null) {
 286                         tek = prvi;
 287                         while (tek.veza != null) {
 288                                 pret = tek;
 289                                 tek = tek.veza;
 290                                 if (tek.info % 2 == 0) {
 291                                         pret.veza = tek.veza;
 292                                         if (parni.prvi == null) {
 293                                                 parni.prvi = tek;
 294                                                 tek.veza = null;
 295                                                 parniKraj = tek;
 296                                         } else {
 297                                                 parniKraj.veza = tek;
 298                                                 tek.veza = null;
 299                                                 parniKraj = tek;
 300                                         }
 301                                         tek = pret;
 302                                 }
 303                         }
 304                 }
 305
 306                 return parni;
 307         }
 308
 309         /**
 310           * Vraca novu listu koja se sastoji od prvih `n` elemenata
 311           * ove liste, a ova lista se nakon poziva sastoji od ostatka.
 312           * U slucaju da je `n` nepozitivan broj bice vracena prazna lista,
 313           * a u slucaju da je `n` vece ili jednako broju elemenata u listi
 314           * nova lista ce se sastojati od cele ove liste, a ova ce ostati
 315           * prazna.
 316           */
 317         public DeljivaLista izdvojPrvihN(int n) {
 318                 DeljivaLista rezultat = new DeljivaLista();
 319                 if (n <= 0) {
 320                         return rezultat;
 321                 }
 322
 323                 rezultat.prvi = prvi;
 324
 325                 int brojac = 0;
 326                 Element poslednji = prvi;
 327                 while (poslednji != null && brojac < n - 1) {
 328                         poslednji = poslednji.veza;
 329                         brojac++;
 330                 }
 331                 if (poslednji != null) {
 332                         prvi = poslednji.veza;
 333                         poslednji.veza = null;
 334                 } else {
 335                         prvi = null;
 336                 }
 337                 return rezultat;
 338         }
 339 }