4. Datastructuren in Java Flashcards
Waaruit bestaat het Collections Framework?
Dit framework bestaat uit drie delen:
- interfaces
- implementaties (= de concrete klassen)
- algoritmes (=de methoden)
Wat is een interface?
Een interface stelt een abstract datatype voor.
Dit betekent dat voor de klassen die erven van de interface “contracten” worden afgesloten waaraan die klassen moeten voldoen.
Wat zijn polymorfe collectionklassen?
Polymorfe collectionklassen maken het mogelijk elementen te verzamelen ongeacht het soort elementen dat we erin willen stoppen (bv. Student of Inschrijving).
Dit wordt bereikt door Object te kiezen als het type van de elementen.
—
ArrayList lijst = new ArrayList();
lijst.add(“hallo”);
Student k = new Student(“Katrien Deleu”);
lijst.add(k);
System.out.println(“lijst” + lijst);
> lijst[hallo, Katrien Deleu]
Wat is het nadeel van polymorfe collectionklassen?
Het nadeel van deze aanpak is dat ze niet type-safe is. Er is dus een cast nodig om het object in z’n juiste type terug te krijgen.
Wat zijn generische collectionklassen?
Generische collectionklassen laten toe elementen van een zelfde type te verzamelen.
Dit wordt bereikt door de klassedefinitie te parametriseren met het type van de elementen.
—
ArrayList lijst = new ArrayList();
//lijst.add(“hallo”); –> compileert niet
Student k = new Student(“Katrien Deleu”);
lijst.add(k);
System.out.println(“lijst” + lijst);
> lijst[Katrien Deleu]
Wat is het voordeel van generische collectionklassen?
Deze aanpak is type-safe, de type informatie van de elementen blijft behouden en er moet niet gecast worden.
In welke package is het Java Collections Framework ondergebracht?
java.util
Som de interfaces op van het Java Collections Framework.
- Iterable
- Collection
- List
- ListIterator
- Queue
- Deque
- Set
- SortedSet
- Map
- SortedMap
Wat is een iterator?
Een iterator laat toe om elementen in een collectionklasse één voor één te overlopen.
---
Collection list = ...
Iterator it = list.iterator();
while (it.hasNext()) {
Student s = it.next();
...
}Wat is het voordeel van een iterator?
Deze laat toe om de collection te wijzigen (bv. elementen verwijderen).
---
Iterator it = list.iterator();
while (it.hasNext()){
Student s = it.next();
System.out.println(s);
it.remove(); // toegelaten
}Wat is een list?
Een sequentiële datastructuur; dit betekent dat de volgorde zoals de elementen opgeslagen zitten in de datastructuur van belang is.
Wat is een queue?
Een queue is abstract datatype en stelt een wachtrij (FIFO) voor.
De elementen worden altijd achteraan toegevoegd en vooraan verwijderd.
Wat is een stack?
Een stack is een datastructuur die een stapel voorstelt (LIFO).
De elementen worden altijd vooraan toegevoegd en vooraan verwijderd.
Wat is een deque?
Een deque (uitgesproken als dek) is een queue waar we aan beide uiteinden elementen kunnen toevoegen en verwijderen. De naam deque staat voor ‘Double-ended queue’. De Deque-interface omvat dus zowel de functionaliteiten van een queue als van een stack.
Wat is een set?
Een set is een verzameling van unieke elementen.
Dit betekent dat er geen twee gelijke elementen in een set aanwezig kunnen zijn.
Een set is in principe ongeordend, wat betekent dat wanneer we een set twee keer overlopen, de elementen niet noodzakelijk in de zelfde volgorde zullen weergegeven worden.
Wat is een map?
Een map laat toe om elementen zo op te slaan dat ze eenvoudig aan de hand van een sleutel kunnen teruggevonden worden.
Elk gegeven wordt dus gekoppeld aan een sleutel.
Een map kan geen dubbele sleutels bevatten en elke sleutel komt overeen met exact één element.
Hoe gebeurt de ordening van een SortedSet/SortedMap?
De ordening gebeurt via de natuurlijke ordening van de elementen/sleutels of op basis van een Comparator die bij creatie van de SortedSet/SortedMap wordt meegegeven.
Wat zijn de opties om de ordening te regelen van collections waar elementen opgeslagen worden volgens een bepaalde ordening, zoals bij SortedSet en SortedMap?
De implementatie van deze interfaces moeten een methode voorzien die deze ordening regelt.
Dit kan de compareTo()-methode zijn van de Comparable-interface of de compare()-methode van de Comparator-interface.
Wat is het verschil tussen de Comparable en Comparator interface?
De Comparator-interface laat toe om een ordening te definiëren in een aparte klasse.
Er kan dan een object van die klasse meegegeven worden aan bijvoorbeeld de sort()-methode om de manier van ordenen te bepalen.
Dit laat toe om meerdere manieren van sorteren te definiëren voor eenzelfde soort objecten.
Wat is een arraylist?
Een arraylist is een sequentiële datastructuur en implementeert bijgevolg de List-interface.
In een arraylist is het belangrijk dat het opvragen van een element snel kan aan de hand van een index.
Deze structuur lijkt dus veel weg te hebben van een array, maar anders dan een array heeft een arraylist geen vaste grootte.
Wat zijn de belangrijkste methodes van een ArrayList?
- add(e): element e achteraan toevoegen > O(1)
- add(i,e): element e op index i toevoegen > O(n)
- remove(i): element op index i verwijderen > O(n)
- get(i): waarde van element op index i opvragen > O(1)
- set(i,e): waarde van element op index i wijzigen in e > O(1)
Een array heeft een vaste grootte, hoe lost een ArrayList dit probleem op?
Het idee is om wanneer de array vol is, een nieuwe array te creëren die dubbel zo groot is en alle elementen over te zetten naar de nieuwe array.
Dit lijkt een trage oplossing te zijn, want het uitbreiden en alle elementen overzetten duurt O(n). Maar merk op dat wanneer de array uitgebreid is, er weer n elementen bij kunnen, vooraleer de uitbreiding nog eens plaats vindt.
Wat is een LinkedList?
De LinkedList-class is een implementatie van een dubbel gelinkte lijst.
Wat zijn de belangrijkste methodes van een LinkedList?
Methoden overgeërfd van de Queue en Deque-interface:
- addFirst(e): element e vooraan toevoegen > O(1)
- addLast(e): element e achteraan toevoegen > O(1)
- removeFirst(): eerste element verwijderen > O(1)
- removeLast(): laatste element verwijderen > O(1)
- getFirst(): waarde van eerste element opvragen > O(1)
- getLast(): waarde van laatste element opvragen > O(1)
Methoden overgeërfd van de List-interface
- add(e): element e achteraan toevoegen > O(1)
- add(i,e): element e op index i toevoegen > O(n)
- remove(): eerste element verwijderen > O(1)
- remove(i): element op index i verwijderen > O(n)
- get(i): waarde van element op index i opvragen > O(n)
- set(i,e): waarde van element op index i wijzigen in e > O(n)
