3. De basis datastructuren

Question 1

Wat is een array?

Answer 1

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"};

Question 2

Wanneer wordt de lengte van een array vastgelegd?

Answer 2

Op het moment dat de array wordt gecreëerd.

Question 3

In welke klasse zitten er belangrijke ingebouwde methoden voor een array te sorteren, kopiëren, vergelijken,…

Answer 3

java.util.Arrays

Dit zijn statische methoden.

Question 4

Wat is het nadeel van arrays?

Answer 4

Arrays zijn niet aanpasbaar aangezien ze een vaste grootte hebben.

Question 5

Wat is een gelinkte lijst?

Answer 5

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

Question 6

Wat is een “next”-referentie?

Answer 6

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.

Question 7

Hoe worden de eerste en laatste knoop van een gelinkte lijst genoemd?

Answer 7

Het hoofd en de staart van de lijst.

Question 8

Welke “next”-referentie heeft de staart?

Answer 8

Null

Question 9

Wat zijn de verschillen tussen een array en een gelinkte lijst?

Answer 9

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.

Question 10

Wat is een gelijkenis tussen een array en een gelinkte lijst?

Answer 10

Net zoals een array, houdt een gelinkte lijst zijn gegevens in een bepaalde orde bij.

Question 11

Hoe wordt de orde van de gegevens in een gelinkte lijst bepaalt?

Answer 11

Deze orde wordt bepaald door de ketting van “next” koppelingen die toelaten om van een knoop naar zijn volgende knoop te gaan.

Question 12

Wat is een nadeel van een enkel gelinkte lijst?

Answer 12

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.

Question 13

Wat is een dubbel gelinkte lijst?

Answer 13

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.

Question 14

Wat is het voordeel van een dubbel gelinkte lijst?

Answer 14

Zo’n lijst laat toe om manipulaties, zoals toevoegen en verwijderen, veel sneller uit te voeren.

Question 15

Wat is het grote voordeel van een array?

Answer 15

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

Question 16

Wat is het grote voordeel van een gelinkte lijst?

Answer 16

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.

Question 17

Wat zijn de meest eenvoudige datastructuren die in een programmeertaal voorkomen?

Answer 17

• array

- gelinkte lijst

Question 18

Geef een voorbeeld van een implementatie van een enkel gelinkte lijst.

Answer 18

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;   } }

Question 19

Waarom is het toevoegen van elementen achteraan een enkel gelinkte lijst lastig?

Answer 19

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.

Question 20

Waarom is het verwijderen van elementen achteraan een enkel gelinkte lijst lastig?

Answer 20

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.

Question 21

Met welke uitzonderingsgevallen moet er rekening gehouden worden bij het verwijderen van de laatste knoop in een enkel gelinkte lijst?

Answer 21

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