78 lines
2.6 KiB
Markdown
78 lines
2.6 KiB
Markdown
# 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` |