Programmeren in C++/Gelinkte lijst

Introductie

We gebruiken hier de kracht van pointers om een elementaire datastructuur te ontwikkelen.

Gelinkte Lijst Algemeen

Een gelinkte lijst is een datastructuur te vergelijken met een ketting. Een ketting bestaat uit schakels, in het geval dat we hier bespreken, een enkelvoudig gelinkte lijst is de ketting enkel te doorlopen in één enkele richting. Verder kan men aan enkele schakel iets anders bevestigen. In de onderstaande afbeelding wordt de situatie geschetst. Een vierkant stelt een schakel van de ketting voor. Next is een pointer naar de volgende schakel, deze kan eventueel onbestaand zijn. In een gelinkte lijst is er altijd 1 schakel die geen opvolger heeft, de laatste schakel. Hier is next dus NULL, dit wordt aangeduid door het aardingssymbool op de afbeelding. Verder kunnen we met deze pointerketting nog niet veel doen. Door een datapointer (een pointer naar een dataobject, cirkel in figuur) toe te voegen kunnen we zo aan elke schakel een verwijzing toevoegen naar data. Vermits dit ook een pointer is, kan deze evengoed afwezig zijn.

Wat kunnen we hier nu mee? We hebben een datastructuur ontwikkeld waarbij we data op willekeurig plaatsen kunnen toevoegen, volledig dynamisch en data op willekeurige plaatsen kunnen verwijderen. Het verwijderen wordt hieronder geschetst. De grijs weergegeven schakel werd verwijderd en de next pointer verwijst nu naar het object waar de next pointer van het verwijderde object naar wees. Zo blijft de rest van de lijst intact.

Gelinkte Lijst Als bouwsteen

Nu is een gelinkte lijst als bouwsteen erg belangrijk. Vele andere datastructuren zijn erop gebaseerd, dus als men dit principe goed begrijpt zal men makkelijk kunnen overstappen naar andere datastructeren. Een simpele variant op de gelinkte lijst is de dubbelgelinkte lijst. Hierbij kan men de ketting in twee richtingen doorlopen. Er is dus een pointer naar de volgende en naar de vorig schakel waardoor men sneller kan navigeren maar waardoor het toevoegen of verwijderen iets moeilijker wordt. Er dienen nu telkens twee pointers veranderd te worden. Een andere uitbreiding op de gelinkte en de dubbelgelinkte lijst is het gesorteerd invoegen mogelijk maken.

Wanneer aan een schakel twee of meer andere schakels hangt creëert men een hiërarchie. Wanneer we bijvoorbeeld aan een schakel een verwijzing naar een linker en een rechter schakel plaatsen creëren we zo een binaire boom. Deze valt terug verder uit de breiden met ouderpointer om naar boven te navigeren. Een binaire boom is een zeer efficiente manier om in te zoeken, maar het opbouwen van deze structuur is dan weer een ander paar mouwen.

Conclusie

We kunnen concluderen dat we dus op veel plaatsen pointers en op gelinkte lijsten (die terug op pointers gebaseerd zijn) gebaseerde datastructuren zullen tegenkomen. Het is dus zeer belangrijk deze concepten goed te snappen. Let wel, pointers zijn niet noodzakelijk. In programmeertalen zoals bijvoorbeeld Java heeft de gebruiker geen pointers tot zijn beschikking (deze zijn echter wel intern aanwezig) en toch zijn ook daar die krachtige datastructuren aanwezig. Natuurlijk voorziet C++ in de STL (Standard Template Library) voorgedefinieerde implementaties (zo is de list container klasse een beschikbare dubbel gelinkte lijst).

Een Implementatie

Hier wordt een eenvoudige enkelvoudige gelinkte lijst gepresenteerd. Deze maakt gebruik van zogeheten templates om het geheel uniform te maken.

De Node klasse

Hieronder volgt de code voor de Node-klasse, welke hier de implementatie voor de gelinkte lijst is.

C++-code:

template <class T>
class Node{
private:
	T* dataPointer;
	Node *next;
public:
	// Default constructor.
	Node(){
		next=NULL;
		dataPointer=NULL;		
	}

	// Constructor die verwijzing naar data toevoegt.
	Node(T* data){
		next=NULL;
		dataPointer=data;
	}

	// Voegt een nieuwe node achteraan toe.
	void addNode(T* data){
		if(next != NULL){
			next->addNode(data);
		}else{
			next=new Node(data);
		}
	}

	// Zet de data in de huidige node.
	void setData(T* data){
		dataPointer = data;
	}

	// Vraagt de data in de huidige node op.
	T* getData(){
		return dataPointer;
	}

        // Zet next op NULL
        void clearNext(){
                next=NULL;
        }

	// Vraagt het volgende element op
	Node * getNext(){
		return next;
	}

	// Zoekt de schakel die data bevat en verwijdert deze, 
	// geeft het nieuwe begintpunt van de gelinkte lijst terug,
	// nodig indien het eerste element verwijderd zou worden.
	Node * verwijder(T* data){
		if(dataPointer != data && next != NULL){
			if(next->getData() != data){
				next->verwijder(data);
			}else{
                                next->setData(NULL);
                                next->clearNext();
				next=next->getNext();
			}

			return this;
		}else{
			return next;
		}
	}

	// Schrijf de lijst uit.
	void write(ostream &os){
		if(dataPointer != NULL){
			// Schrijf de data indien die er is
			os << *dataPointer;		
		}else{
			// Schrijf null indien data afwezig
			os << "null";
		}
		if(next != NULL){
			// Schrijf ->
			os << "->";
			// Roep de volgende op
			next->write(os);
		}else{
			// Newline
			os << endl;
		}
	}

	// Destructor.
	~Node(){
                dataPointer=NULL;
		delete next;
	}
};

Test en Bespreking

De Node klasse maakt gebruik van templates om zo gelijk welk type data dat nodig is aan de schakels te kunnen hangen. De klasse heeft twee private leden. De pointer naar de volgende Node (next) en een pointer naar de data (dataPointer). We definieren twee constructors, een detructor, een methode om de dataPointer op te vragen en te wijzigen, een methode om de next pointer naar NULL te laten wijzen en methode om een pointer naar de volgende schakel te bekomen. Verder definieren we drie operaties: addNode, verwijder en uitschrijven.

addNode

Addnode doet het volgende, we stappen van begin tot einde door de lijst (het einde bereiken we wanneer next gelijk is aan NULL. Hier komt al een performantie bottleneck naar boven. Hoe langer de lijst hoe trager dit zal lopen. Misschien is het wel een goed idee om een verwijzing naar het einde van de lijst bij te houden ?

verwijder

Bij het verwijderen lopen we door de lijst tot het gezochte element gevonden is of tot het einde van de lijst gevonden is. Indien we de data vinden sluiten we de node kort. MAAR vermits nodes dynamisch gealloceerd worden dienen deze ook vrijgegeven worden. Dus dienen we deze node te verwijderen met delete. We dienen echter op te passen voor een cascade effect. Zodat de resterende elementen van de lijst niet mee gedelete worden, dus zetten we de next pointer van de te verwijzen node eerst op NULL alsook de datapointer (de gelinkte lijst is niet verantwoordelijk voor de dataPointer dus daar moeten we afblijven). Merk ook op dat het verwijderen van de lijst in feite van achter naar voor loopt.

write

Hetgeen we bij write doen is de simpelste operatie van alle, we stappen gewoon door de gelinkte lijst tot het einde en schrijven ondertussen de elementen uit, wanneer we op het einde van de lijst gekomen zijn beëindigen we de regel.

Test

Hieronder volgt de code van een eenvoudig testprogramma waarin de kracht van de templates ook geïllustreerd wordt. Eerst maken we een gelinkte lijst aan die werkt met int's gevolgd door een gelinkte lijst die met char*'s (strings) werkt. Van de eerste gelinkte lijst verwijderen we alle elementen op oneven posities (inclusief het eerst!).

C++-code:

#include <iostream>
using std::ostream;
using std::cout;
using std::endl;

#include "Node.h"



int main(int argc, char **argv){
	int getallen[] = {1,2,3,4,5,6,7,8,9,10};	
	Node<int> linkedList(&getallen[0]);

	linkedList.write(cout);

	// Nu voegen we de rest toe
	for(int i=1;i<10;i++){
		linkedList.addNode(&getallen[i]);
	}
	
	linkedList.write(cout);

	// Verwijder alles op even indices.
	for(int i=0;i<10;i+=2){
		linkedList=*linkedList.verwijder(&getallen[i]);
	}

	linkedList.write(cout);

	char* strings[] = {"Een","Twee","Drie","Vier","Vijf"};
	Node<char*> stringLijst(&strings[0]);
	// Nu voegen we de rest toe
	for(int i=1;i<5;i++){
		stringLijst.addNode(&strings[i]);
	}

	stringLijst.write(cout);

}