Feladatok‎ > ‎

Csináljunk listát!

Leírás

Ha sok hasonló adatot tároltunk, akkor mindig a tömböket hívtuk segítségül. Akárhány ugyanolyan elemet tudtunk tárolni bennük, akármilyen típusúak is voltak.

Viszont a tömböknek vannak korlátai, a lista ezeket a korlátokat hivatott feloldani. Amikor létrehozunk egy tömböt, megadjuk a méretét. Ez egy fix szám, később ezt az értéket nem lehet módosítani. Pedig előállhat olyan helyzet, hogy előre nem látható, hogy hány értéket szeretnénk tárolni benne.

Ezért készítsünk egy lista adatstruktúrát (adattípust), amibe akárhány elemet bele tudunk szúrni akár tetszőleges helyre, illetve később el tudjuk őket távolítani onnan.

Működés

Ahhoz, hogy sok elemet eltárolhassunk, megint csak a tömbökhöz kell nyúlnunk. De vajon hogyan tudjuk a tömbök méretét menet közben megnövelni?

Sehogy. Új tömböt kell létrehozni, ami nagyobb/kisebb, és a régi tömb elemeit bele kell másolni. De mekkora tömbökkel operáljunk?

Ötlet 1

Mindig egy pont akkora tömböt vegyünk fel, mint ahány elemet akarunk tárolni. Ha új elem érkezik, akkor vegyünk fel egy eggyel nagyobb tömböt, másoljuk be a régi elemeket, majd a végére az újonnan érkező elemet. Eltávolításkor hasonlóan egy eggyel kisebb tömböt használunk, és minden elemet átmásolunk, leszámítva azt, amit le szeretnénk törölni.

Ötlet 2

Először vegyünk fel mondjuk egy 10 hosszú tömböt, pakolgassunk bele elemeket, majd amikor megtelik, akkor másoljuk át az egészet egy 10-zel hosszabb tömbbe. Ha a 20-as telik be, akkor 30-as tömböt veszünk fel, és így tovább. Elemkivételkor ugyanígy. (Vaagy érdemes másképp?)

Ötlet 3

Induljunk megint csak egy fix hosszú tömbből (legyen 8 a kezdeti hossz). Amikor betelt, akkor duplázzuk meg a tömb hosszát, így 16-os, 32-es, 64-es, 128-as, … tömböket fogunk használni. Hogyan érdemes törölni?

Elemezzük az ötleteket!

  • Mennyi memóriát használunk N adat eltárolásához?
  • Hányszor történik másolás, miközben sorban hozzáadogatok a végére N elemet?
  • Egy másolás alkalmával hány elemet kell átmásolni?
  • Egy új elemet a végére beszúrva várhatóan hány másolás fog történni?
  • Hova a "legdrágább" beszúrni/honnan a "legdrágább" törölni?

Megvalósítás

Hozzunk létre egy új osztályt Lista néven (az osztálynevek, metódusnevek tetszőlegesen megválaszthatók)! Ezzel az osztállyal int-eket fogunk tudni tetszőleges számban eltárolni.

Generikus osztály (csak haladóknak): Ne csak int-eket, hanem tetszőleges objektumokat lehessen eltárolni. Segítség: Google

Akármelyik ötletet is választod, a listának ugyanazokat kell tudnia, miszerint

  • Hozzáadás (hova, mit)
  • Törlés (honnan)
  • Olvas (honnan) – visszatér a megfelelő elemmel
  • Méret – hány elemet tárol jelenleg a lista?
  • … – lehetnek ezentúl tetszőleges függvények (pl segédfüggvény tömbök másolgatására, egyszerre több érték hozzáadása, …)
Készíts egy main metódust, és próbáld ki, jól működik-e a listád!

Ha kész