1. Een singly linked list
Het nadeel van een array is dat je van tevoren moet bepalen hoeveel elementen erin moeten worden geplaatst. Bovendien kost het verwijderen of het invoegen van een element veel tijd omdat alle andere elementen moeten worden opgeschoven. Er is daarom ook een andere structuur bedacht: een singly linked list.
Een singly linked list is een lijst van nodes die aan elkaar zijn gekoppeld. De eerste node noemen we de head en de laatste node noemen we de tail. De tail kunnen we herkennen aan het feit dat deze altijd naar een null-element is gekoppeld.
Hoe gaat dit in de praktijk? We zullen beginnen met het maken van een Node class.
public class Node {
private int data;
private Node nextNode;
public Node(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNextNode() {
return nextNode;
}
public void setNextNode(Node nextNode) {
this.nextNode = nextNode;
}
@Override
public String toString() {
return "Data: " + this.data;
}
}
Hier is iets vreemds aan de hand. De class-variabele Node nextNode verwijst naar de eigen class. Verder zien we een methode toString(). Dit is om de data te kunnen printen.
De verwijzing naar de volgende Node in de class Node is de basisstructuur van een Linked list.
We zullen nu de met behulp van de class Node de linkedlist maken inclusief een methode toString om de lijst te kunnen printen.
public class LinkedList {
private Node head;
public void insertAtHead(int data) {
//eerst wordt een nieuwe node aangemaakt met de meegegeven data
Node newNode = new Node(data);
//deze nieuwe node laat de head (het eerste element van de Linked list verwijzen naar de volgende Node.
newNode.setNextNode(this.head);
//nu wordt de head de nieuwe node
this.head = newNode;
}
@Override
public String toString() {
String result = "{";
Node current = this.head;
while (current != null) {
result += current.toString() + ", ";
current = current.getNextNode();
}
result += "}";
return result;
}
}
Kijk goed naar het commentaar boven de code. We zullen dat nog eens uitleggen aan de hand van een afbeelding:
2. Verwijder de head
De lijst die we in de opdracht van de vorige les hebben gemaakt en geprint is een linked list die er als volgt uitziet:
{Data: 10 (head) ⇒ Data: 9 ⇒ Data: 7 ⇒ Data: 8 ⇒ Data: 5 ⇒ Data: 10 ⇒ Data: 12 ⇒ Data: 19 ⇒ Data: 20 ⇒ null}
Merk op dat het laatste element naar null verwijst. Daar herken je een linkedlist aan.
We willen nu het eerste element, de head, verwijderen. Dat gaat als volgt:
Eerst maken we een Node current
Node current = this.head;
Vervolgens laten we de head naar de volgende node verwijzen:
this.head = current.getNextNode();
En nu ziet de lijst er als volgt uit:
Data: 9 (head) ⇒ Data: 7 ⇒ Data: 8 ⇒ Data: 5 ⇒ Data: 10 ⇒ Data: 12 ⇒ Data: 19 ⇒ Data: 20 ⇒ null}
3. De lengte van de linked list bepalen
Om de lengte van de linked list te kunnen bepalen maken we eerst een variabele length:
int length = 0;
Vervolgens maken we een Node current die we vullen met de head, het eerste element in de lijst en wat als laatste is toegevoegd.
Node current = this.head;
En nu is het een kwestie van de lijst helemaal doorlopen met een while-loop. Zolang de laatste node niet naar null wijst wordt de variabele length opgehoogd:
while (current != null) {
length++;
current = current.getNextNode();
}
Zo gauw als de while-loop wordt doorlopen geven we de lengte terug:
return length;
4. De linked list sorteren
Dit onderdeel is uitgeschakeld door de docent.
5. Een doubly linked list
Het nadeel van een Singly Linked list is dat je alleen maar vooruit er doorheen kunt lopen. Dit komt omdat de class Node alleen een class Nextnode heeft die verwijst naar de volgende Node. Zijn we eenmaal bij deze Nextnode dan is er geen mogelijkheid om terug te gaan. Dat maakt een Singly Linked list soms beperkt. Een Doubly Linked list kent dat nadeel niet.
De code van de Node is als volgt:
public class DoublyLinkedNode {
private int data;
private DoublyLinkedNode nextNode;
private DoublyLinkedNode previousNode;
public DoublyLinkedNode(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public DoublyLinkedNode getNextNode() {
return nextNode;
}
public void setNextNode(DoublyLinkedNode nextNode) {
this.nextNode = nextNode;
}
public DoublyLinkedNode getPreviousNode() {
return previousNode;
}
public void setPreviousNode(DoublyLinkedNode previousNode) {
this.previousNode = previousNode;
}
@Override
public String toString() {
return "Data: " + this.data;
}
}
Je ziet dat deze erg lijkt op de class Node van de singly linked list. Het verschil is dat er nu ook een private int previousNode aanwezig is. Deze wijst naar null of naar de vorige Node.
De code is voor de class DoublyLinkedList ligt voor de hand. In de methode public void insertAtHead(int data) dat er als de head niet null is de class variabele
public class DoublyLinkedList {
private DoublyLinkedNode head;
public void insertAtHead(int data) {
DoublyLinkedNode newNode = new DoublyLinkedNode(data);
newNode.setNextNode(this.head);
if (this.head != null) {
this.head.setPreviousNode(newNode);
}
this.head = newNode;
}
@Override
public String toString() {
String result = "{";
DoublyLinkedNode current = this.head;
while (current != null) {
result += current.toString() + ", ";
current = current.getNextNode();
}
result += "}";
return result;
}
}
We zullen nu laten zien wat er gebeurt als we data toevoegen. We beginnen met:
DoublyLinkedList list = new DoublyLinkedList();
list.insertAtHead(99);
Er ontstaat nu de volgende situatie:
Er is een nieuwe node gemaakt met int data = 12 en waarbij de Nodes nextNode en previousNode wijzen naar null. Vervolgens voegen we nieuwe data toe met:
list.insertAtHead(12);
Nu krijgen we de volgende situatie:
De node met data=99 (node 99) wordt de nextNode van de node 12. De previousNode van de node 99 wordt node 12. Ze verwijzen dus naar elkaar. Aan de uiteinden wijzen de previousNode en nextNode naar null.
Als we dan nog het getal 37 toevoegen krijgen we, zoals te verwachten, de volgende situatie:
6. De interface
Een interface is een speciaal soort abstracte klasse. Een abstracte klasse bevat alleen methoden die nog niet zijn gedefiniëerd. Hieronder een voorbeeld:
public abstract class AbstractClass{
public abstract void abstracteMethod();
}
public class SubClass extends AbstractClass {
public void abstracteMethod() {
String message="In deze methode is de code wel gedefinieerd.";
System.out.println(message);
}
}
In een interface kunnen ook constanten voorkomen. Een constante is een variabele die niet meer wordt gewijzigd. Het zijn vaak instellingen die voor de hele applicatie kunnen gelden. Naast constanten heeft een interface ook ongedefiniëerde methoden die pas in de subklasse worden gedefiniëerd. Een voorbeeld van een interface - die aansluit op de volgende les - is als volgt:
import java.util.EmptyStackException;
public interface StackInterface {
/**
*
* @return number of elements in the stack.
*/
public int size();
/**
*
* @return true if the stack is empty, false otherwise.
*/
public boolean isEmpty();
/**
* Inspect the element at the top of the stack.
*
* @return top element in the stack.
* @exception EmptyStackException if the stack is empty.
*/
public int top()
throws EmptyStackException;
/**
* Insert an element at the top of the stack.
*
* @param element to be inserted.
*/
public void push(int data);
/**
* Remove the top element from the stack.
*
* @return element removed.
* @exception EmptyStackException if the stack is empty.
*/
public int pop()
throws EmptyStackException;
}
Je ziet hier een interface StackInterface met vier - niet-gedefiniëerde - methoden: size(), isEmpty(), push(int data) en pop(). Wat een stack is wordt in de volgende les uitgelegd. Op basis van deze interface gaan we de stack daadwerkelijk maken waarbij we verplicht zijn om de bovenstaande vier methoden in te voeren en te definiëren.
7. De stack
Een stack is zoals een bordenautomaat in een restaurant. Je kunt er elementen op plaatsen en afhalen. Het eerste element wat op de stack wordt geplaatst kan er pas als laatste af. We noemen dat het LIFO-pricipe (Last In, First Out). Grafisch kan een stack als volgt worden voorgesteld:
Een stack kan op verschillende manieren worden gecodeerd, bijvoorbeeld met een array. Wij zullen dit gaan doen op basis van een linked list. Eerst maken we de Node.
Met de methode push(...) wordt een element op de stack geplaatst en met de methode pop() wordt deze erweer vanaf gehaald. Deze methoden hadden we ook al gezien in de StackInterface.
public class Node<E> {
private E data;
private Node<E> next;
public Node(E data, Node<E> next) {
this.data = data;
this.next = next;
}
public E getData() {
return data;
}
public void setData(E data) {
this.data = data;
}
public Node<E> getNext() {
return next;
}
public void setNext(Node<E> next) {
this.next = next;
}
@Override
public String toString() {
return "" + this.data;
}
}
We zien hierbij iets nieuws: de <E>. We noemen dit een type variabele. Je mag hiervoor van alles kiezen zoals een primitieve variabele (boolean, int, double etc.) of een referentievariabele.
De interface van de stack
Zoals we in de vorige les hebben geleerd maken we nu voor de daadwerkelijke stack een interface. Nog even een herhaling: een interface is een speciaal soort abstracte klasse die aangeeft welke methoden er in de daadwerkelijke, onderliggende, klasse moet worden gemaakt.
/**
* Interface for a stack: a collection of objects that are inserted and removed
* according to the last-in first-out principle. This interface includes the
* main methods of java.util.Stack.
*/
public interface StackInterface<E> {
/**
* Return the number of elements in the stack.
*
* @return number of elements in the stack.
*/
public int size();
/**
* Return whether the stack is empty.
*
* @return true if the stack is empty, false otherwise.
*/
public boolean isEmpty();
/**
* Inspect the element at the top of the stack.
*
* @return top element in the stack.
* @exception EmptyStackException if the stack is empty.
*/
public E top();
/**
* Insert an element at the top of the stack.
*
* @param element to be inserted.
*/
public void push(E element);
/**
* Remove the top element from the stack.
*
* @return element removed.
* @exception EmptyStackException if the stack is empty.
*/
public E pop();
}
Je ziet dat er behalve de methoden push(E element) en pop() ook nog de methoden top(), isEmpty() en size() moeten worden gedefiniëerd. Het verschil tussen pop() en top() is dat de eerstgenoemde het bovenste element verwijderd en dat top() het element alleen maar teruggeeft. De beschrijving voor de methoden isEmpty() en size() zijn niet moeilijk te begrijpen.
De stack
Als laatste maken we de daadwerkelijke stack:
public class Stack<E> implements StackInterface {
private int size;
private Node<E> top;
public Stack() {
this.size = 0;
this.top = null;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return top == null;
}
@Override
public Node<E> top() {
return top;
}
@Override
public Node<E> pop() {
if (this.isEmpty()) {
return null;
}
Node<E> node = top;
top = node.getNext();
this.size--;
return node;
}
/* Function to display the status of the stack */
public String toString() {
String display = "\nStack = ";
if (size == 0) {
display = "Empty\n";
return display;
}
Node node = top;
while (node != null) {
display += (node.getData() + " ");
node = node.getNext();
}
return display;
}
public void clear(Stack s) {
if (s.isEmpty()) {
} else {
s.pop();
clear(s);
}
}
@Override
public void push(Object element) {
Node node = new Node(element, null);
if (top == null) {
top = node;
} else {
node.setNext(top);
top = node;
}
size++;
}
8. De queue
In een queue wordt het element wat er als eerste in wordt gestopt ook als eerste weer uitgehaald. Dit heet het FIFO-principe. Je kunt het bijvoorbeeld toepassen op bederfelijke producten. Producten die het eerst in voorraad zijn worden als eerste verkocht. Een rij bij de kassa gaat ook volgens FIFO-principe. Wie als eerste in de rij staat, wordt als eerste geholpen.
We geven hieronder de interface van de queue:
public interface QueueInterface<E> {
/**
* Puts an object at the end of the queue.
*
* @param data
*/
public void enqueue(E data);
/**
* Gets an object from the head of the queue. The object will be removed
* from the queue. If there are no objects in the queue it returns null.
*
* @return E
*/
public E dequeue();
/**
*returns de head of the queue without removing it
*
* @return E
*/
public Node<E> peek();
/**
* Returns if the queue is empty
*
* @return boolean
*/
public boolean isEmpty();
}
De queue kent de methoden enqueue(E data) en dequeue(), De eerstgenoemde methode plaatst data op de queue en de laatst genoemde kan het er weer afhalen en tevens teruggeven. Dus stel we hebben de volgende code:
Queue<String> queue = new Queue();
queue.enqueue("to ");
Deze code plaatst het eerste element op de queue. Dit wordt in de head geplaatst. Als de lengte van de queue 0 is, krijgt de tail dezelfde waarde. Je kunt zeggen dat bij één element zowel de head als de tail wijzen naar hetzelfde element. Er ontstaat er nu de volgende situatie:
Bij het plaatsen van meer elementen wordt de rij verder gevuld en krijgt de tail de waarde van het laatste element:
queue.enqueue("be ");
queue.enqueue("or ");
queue.enqueue("not ");
queue.enqueue("to ");
queue.enqueue("be ");
| Node head |
Node |
Node |
Node |
Node |
Node tail |
| "to" |
"be" |
"or"
|
"not"
|
"to"
|
"be"
|
Bij de methode dequeue() wordt telkens de head eraf gehaald en krijgt de head de waarde van het volgende element in de queue. Dit gebeurt zolang als de lengte groter is dan 0. Als de lengte 0 is krijgt de head automatisch de waarde null. Ook de tail wordt nu weer op null gezet.
9. antwoorden
Dit onderdeel is uitgeschakeld door de docent.
