FAV-ZCU/KIV PPA2/10. ADT Seznam.md

Seznam

• abstraktní datová struktura
• umožňuje vložení i odebrání prvku z jakékoliv pozice

Jak specifikovat pozici?

• indexem
• aktuální pozice

Ukazovátko

• ukazuje na aktuální pozici v seznamu
• posun dopředu i na začátek
• operace v \Theta(1)
• možné interpretace:
  • ukazuje na prvek
    • některé operace problematické (např. vložení - před nebo za prvek?)
  • ukazuje mezi prvky
    • jednoznačné vkládání: sem
    • vybírání/odebírání dohodou - třeba prvek napravo

Implementace spojovou strukturou

• opět spojovací dílek - data a následující prvek
• reference na první (first) a aktuální prvek (current)
• ukazovátko míří na current a current.next
• je-li current = null, míří se před první prvek seznamu
• pohyb ukazovátka:
  • moveToFirst - na začátek
  • next - na další prvek
    • potřeba myslet na posun z null a neexistující další prvek
• přidávání mezi dva prvky:
  • přepíše se odkaz current.next na vložený prvek
  • vloženému prvku se nastaví původní current.next
• mazání prvku
  • vyřešení speciálních případů (na začátku, na konci)
  • current.next = current.next.next, prvek se přeskočí
• vybrání prvku na zadané pozici
  • projdeme seznam od začátku
  • \Omega(n) složitost!

Iterátor

• seznam neumožňuje prácí na více místech
• vznik odděleného ukazovátka od dat - iterátoru (návrhový vzor)
• třída, která má aktuální index current a referenci list
• stejná implementace jako u seznamu (místo first se použije list.first)`

Operace

• vybrání dat napravo (get())
• posunutí doprava (next())
• vrácení na začátek (moveToFirst())
• přidání prvku na pozici (insert(...))
• odstranění prvku napravo (remove())
• vytvoření klonu (clone()), který ukazuje na stejný prvek

Problémy

• iterátory o sobě nevědí
  • jeden smaže prvek, na který odkazuje jiný iterátor
  • řešení
    • používat více iterátorů pouze pro čtení
    • při editaci zajistit, aby nebyl zasažen jiný iterátor
• pohyb pouze dopředu
  • řešení: obousměrně zřetězený seznam
  • spojovací prvek s next i previous
  • v iterátoru nová metoda previous()
  • složitější konzistence struktury
  • 2x více režijní paměti

Implementace paralelními poli

• jen dopředné zřetězení
• dvě stejně dlouhá pole
  • pro data
  • pro index následovníka (next) - prázdného či obsazeného prvku
• index začátku first
• index volného pole empty
• index aktuálního prvku current