79 lines
2 KiB
Markdown
79 lines
2 KiB
Markdown
# 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)$. |