3. De basis datastructuren Flashcards
Wat is een array?
Een array is een containerobject dat een vast aantal waarden kan vasthouden.
String[] woorden = new String[3];
woorden[0] = "hallo";
...
OF
String[] woorden = {"hallo","oe","ist"};
Wanneer wordt de lengte van een array vastgelegd?
Op het moment dat de array wordt gecreëerd.
In welke klasse zitten er belangrijke ingebouwde methoden voor een array te sorteren, kopiëren, vergelijken,…
java.util.Arrays
Dit zijn statische methoden.
Wat is het nadeel van arrays?
Arrays zijn niet aanpasbaar aangezien ze een vaste grootte hebben.
Wat is een gelinkte lijst?
Een verzameling van knopen die sequentieel geordend zijn.
Elke knoop is een object dat een referentie bewaart naar een element en een referentie naar een andere volgende knoop. Deze laatste referentie noemen we een “next”.
Wat is een “next”-referentie?
De “next”-referentie in de knoop kan gezien worden als een verwijzing of pointer naar een volgende knoop.
Dit betekent dat om naar een volgende knoop te gaan in de lijst, we de “next”-referentie moeten volgen.
Hoe worden de eerste en laatste knoop van een gelinkte lijst genoemd?
Het hoofd en de staart van de lijst.
Welke “next”-referentie heeft de staart?
Null
Wat zijn de verschillen tussen een array en een gelinkte lijst?
Het grote verschil met een array is dat er bij een gelinkte lijst geen beperking staat op de grootte van de lijst en dat er maar zoveel knopen in de lijst zijn als de gegevens die bij gehouden worden.
Een tweede groot verschil met een array is dat een gelinkte lijst geen indexen bijhoudt die aantonen om het hoeveelste element (of knoop) het gaat.
Wat is een gelijkenis tussen een array en een gelinkte lijst?
Net zoals een array, houdt een gelinkte lijst zijn gegevens in een bepaalde orde bij.
Hoe wordt de orde van de gegevens in een gelinkte lijst bepaalt?
Deze orde wordt bepaald door de ketting van “next” koppelingen die toelaten om van een knoop naar zijn volgende knoop te gaan.
Wat is een nadeel van een enkel gelinkte lijst?
Het verwijderen van het element aan de staart van een enkel gelinkte lijst is niet zo eenvoudig.
Het is heel tijdrovend om een element dat niet aan het hoofdt van de lijst staat te verwijderen, aangezien we geen snelle toegang hebben tot het element dat net voor het te verwijderen element staat.
Wat is een dubbel gelinkte lijst?
Een dubbel gelinkte lijst is een lijst waar we in twee richtingen, voorwaarts en achterwaarts, kunnen bewegen.
Een knoop in een dubbel gelinkte lijst heeft twee referenties: één naar de volgende knoop (next), en één naar de vorige knoop (previous) in de lijst.
Wat is het voordeel van een dubbel gelinkte lijst?
Zo’n lijst laat toe om manipulaties, zoals toevoegen en verwijderen, veel sneller uit te voeren.
Wat is het grote voordeel van een array?
De toegang is “random”.
Wanneer we de index van een gegeven kennen, kunnen we het gegeven teruggeven met een algoritme van O(1).
In een gelinkte lijst kunnen we dit niet. Daar moeten we alle knopen overlopen totdat we de gewenste knoop tegenkomen en hebben we dus een algoritme nodig van O(n).
Wat is het grote voordeel van een gelinkte lijst?
Naast de efficiëntie in tijd, is ook de efficiëntie in ruimte belangrijk.
Hier winnen de gelinkte lijsten, aangezien ze niet vat zijn in grootte en dus steeds evenveel geheugen reserveren als het aantal gegevens die effectief in de lijst zitten.
Wat zijn de meest eenvoudige datastructuren die in een programmeertaal voorkomen?
- array
- gelinkte lijst
Geef een voorbeeld van een implementatie van een enkel gelinkte lijst.
public class Knoop {
private String element;
private Knoop next;
public Knoop(String e, Knoop n) {
element = e;
next = n;
}
...
getters & setters
}
public class EnkelGelinkteLijst {
private Knoop hoofd;
public EnkelGelinkteLijst() {
hoofd = null;
}
// elementen vooraan toevoegen
public void addFirst(Knoop k) {
k.setNext(hoofd);
hoofd = k;
}
// elementen achteraan toevoegen
public void addLast(Knoop k) {
k.setNext(null);
if(hoofd == null) {
hoofd = k;
} else {
Knoop temp = hoofd;
while(temp.getNext() != null) {
temp = temp.getNext();
}
temp.setNext(k);
}
// elementen vooraan verwijderen
public Knoop removeFirst() {
if(hoofd == null) {
return null;
} else {
Knoop temp = hoofd;
hoofd = hoofd.getNext();
temp.setNext(null);
return temp;
}
}
// elementen achteraan verwijderen
public Knoop removeLast() {
if(hoofd == null) {
return null;
} else {
Knoop temp = hoofd;
Knoop voorTemp = hoofd;
while(temp.getNext() != null) {
voorTemp = temp;
temp = temp.getNext();
}
if(temp == voorTemp) {
hoofd = null;
} else {
voorTemp.setNext(null);
}
return temp; } }
Waarom is het toevoegen van elementen achteraan een enkel gelinkte lijst lastig?
Omdat we iedere keer op zoek moeten gaan het laatste element. Als de lijst lang is, is dit heel tijdrovend.
Dit probleem kan opgelost worden door ook de staart bij te houden.
Waarom is het verwijderen van elementen achteraan een enkel gelinkte lijst lastig?
We moeten de volledige lijst overlopen om het laatste, te verwijderen element, te kennen.
Meer nog, we moeten ook het voorlaatste element kennen, anders kunnen we de verwijzing van de voorlaatste knoop naar de laatste knoop niet op null zetten.
Met welke uitzonderingsgevallen moet er rekening gehouden worden bij het verwijderen van de laatste knoop in een enkel gelinkte lijst?
- Een lijst kan leeg zijn, en dan kan het laatste element niet verwijderd worden.
- Een lijst kan slechts één element bevatten. Dan is het laatste element ook het eerste element en zijn voorTemp en temp in het algoritme gelijk.
