# Kolekce v Javě

Java poskytuje knihovní třídy pro základní implementaci kolekcí

### Třída `LinkedList<T>`

- spojová datová struktura

**Operace**
- operace v $\mathcal O(1)$
	- `void addFirst(T)`, `void addLast(T)`
	- `T getFirst()`, `T getLast()`
	- `void removeFirst()`, `void removeLast()`
- operace v $\Omega(n)$
	- `void add(int, T)` - vložení na daný index
	- `T get(int)` - získání z indexu
	- `void remove(int)` - smazání z indexu
- `Iterator<T> iterator()`
- `ListIterator<T> listIterator()` - lepší iterátor

### Třída `ArrayList<T>`

- dynamické pole

**Operace**
- operace v $\mathcal O(1)$
	- `void add(T)`
	- `T get(int)`
- operace v $\Omega(n)$
	- `void remove(int)`
- operace pro získání iterátorů - ale s **vyšší složitostí**!

### Třída `Iterator<T>`

**Operace**
- `T next()` - vrátí přeskočený prvek a posune se dopředu
	- na konci vyhodí výjimku
- `boolean hasNext()` - existence dalšího prvku
- `void remove()` - odstraní poslední prvek vrácený metodou `next()`
	- před dalším odstraněním potřeba zavolat `next()`
- chybí:
	- návrat na začátek (stačí si vyžádat nový iterátor)
	- metoda pro vložení prvku

**Vylepšený `ListIterator<T>`**
- má navíc:
	- `T previous()` - vrátí hodnotu předchozího prvku a posune iterátor zpět
		- na začátku vyhodí výjimku
	- `void add(T)` - vloží prvek na pozici iterátoru

### Rozhraní `Queue<T>`

- rozhraní fronty
- `LinkedList<T>` toto rozhraní implementuje

**Operace**
- `void add()`
- `T element()`
- `T remove()`

### Třída `Stack<T>`

implementace zásobníku dynamickým polem - `ArrayList`
- stejné metody poskytuje i `LinkedList`

**Operace**
- `void push(T)`
- `T pop()`
- `T peek()`

### Obecná zásada

Kolekce v čase $\mathcal O(1)$ umí buď
1) vybrat prvek na specifickém indexu, anebo
2) vyjmout/vložit prvek na pozici iterátoru,

ale nikdy ne obojí současně!

Najít i-tý prvek ve spojovém seznamu zabere vždy $\Omega(n)$.