# 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`