FAV-ZCU/KIV PPA2/11. Kolekce v Javě.md

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).