Linked lists

Een krachtig hulpmiddel bij het programmeren zijn linked lists, hoewel het voor newbies erg moeilijk kan zijn wordt het veel in programma's toegepast. Het idee van linked lists is dat je objecten makkelijk kunt toevoegen en verwijderen. Klinkt moeilijk ? Kijk eerst maar even naar het voorbeeldje hieronder.

Dit is een voorbeeld van een linked list die ik wil gaan bespreken. Het begint bij wereld die ziet dat er twee ruimtes in de wereld zitten die gemaakt moeten worden. Als de ruimtes gemaakt worden weten deze dat er monsters in moeten komen en de monsters weten vervolgens weer dat ze een wapen en armor hebben. Je hoeft dus zelf niks meer te doen, de linked list weet wat er moet gebeuren en zorgt ervoor dat het gebeurt.

Om het wat duidelijker te maken zal ik proberen het zo goed mogelijk uit te leggen aan de hand van een voorbeeld.


class CNode
{
public:
  // deze parameters bewaren het adres van de node waar deze node 
  // aan gekoppeld is.
  CNode *parentNode;
  CNode *childNode;
  CNode *prevNode;
  CNode *nextNode;  

  // Check of deze node aan een child of parent node is gekoppelt.
  bool HasParent() { return (parentNode != NULL);}
  bool HasChild() {return (childNode != NULL);}

  // check of deze node het eerste child van een parent is.
  bool IsFirstChild()
  {
    if (parentNode)
       return (parentNode->childNode == this);
    else 
       return false;
  }

  //check of deze node het laatste child van een parent is.
  bool IsLastChild()
  {
    if (parentNode)
       return (parentNode->prevNode == this);
    else 
       return false;
  }

Voor zover het eerste deel, er komt nog meer in deze klasse maar om het een beetje duidelijk te houden leg ik het per deel uit. Eerst komen de pointers die wijzen naar de parentNode, childNode, vorige node (prevNode) en volgende node (nextNode). Kijk maar naar het bovenste plaatje waar wereld de parent is van ruimte 1 en ruimte 2. Het is niet helemaal goed getekend op deze manier maar ruimte 2 is de nextNode van ruimte 1 en monster 2 is de nextNode van monster 1. Als je dit weet kun je aan de hand hiervan dus controleren of de node een parent of childnode heeft en of het het eerste of laatste childnode is. Nu het volgend stukje sourcecode (gaat gewoon verder in dezelfde klasse).

// maak deze node vast aan een parent node
void AttachTo(CNode *newParent)
{
  // Als de node al een parent heeft moet je deze losmaken
  if (parentNode)
    Detach();

  parentNode = newParent;

  // als de parentnode voor deze node al een child heeft moeten de pointers 
  // van deze child(ren) en de parent zelf goed ingesteld worden.
  if (parentNode->childNode)
  {
     prevnode = parentNode->childNode->prevNode;
     nexNode = parentNode->childNode;
     parentNode->childNode->prevNode->nextNode = this;
     parentNode->childNode->prevNode = this;
  }
  // als de parentnode geen child heeft zijn er geen problemen.
  else
  {
     parentNode->childNode = this;
  }
}

// maak een child aan deze node vast
void Attach(CNode *newChild)
{
  //als de childnode al vast zit moet je hem losmaken
  if (newChild->HasParent());
      newChild->Detach();

  newChild->parentNode = this;   
  
  // als er al een child aan deze parent vastzit moet je de adressen 
  // in de pointers opnieuw instellen
  if (childNode)
  {
     newChild->prevNode = childNode->prevNode;
     newChild->nextNode = childNode;
     childNode->prevNode->nextNode = newChild;
     childNode->prevNode = newChild;
  }
  else
  {
    childNode = newChild;
  }
}  
Met dit deel van de code kunnen we nodes toevoegen in de lijst, hoe dit gebeurt kun je afleiden uit de code. Om je toch een beetje op weg te helpen moet je bedenken dat als een parent node een child node heeft (kan maar 1 child hebben) dat de nextnode van het nieuwe child het oude child van de parent is. Dit geld dus ook voor als er meer nodes aan het oude child node gekoppeld waren. Kortgezegd moeten alle geheugenadressen weer naar de goede (nieuwe) nodes wijzen. Misschien wordt het met een tekening wat duidelijker.

Het adres van childNode 1 staat in de pointer "childNode" van de parentNode. Als er nu een childNode 3 bij komt moet dit adres verandert worden. Bovendien moet het prevNode adres van childNode 1 worden verandert die eerst naar childNode 2 wees, en moet het nextNode adres van childNode 2 worden verandert die eerst naar childNode 1 wees.

Het is moeilijk als je hier nog geen kennis van hebt maar als je het goed bekijkt moet je er dacht ik wel uit komen. Nu we nodes aan elkaar kunnen koppelen moeten we ze natuurlijk ook weer los kunnen maken, snel verder dus.


void Detach()
{
  // als dit de child van een parent is moeten de adressen van de parent goed 
  // worden ingesteld 
  if (parentNode && parentNode->childNode == this)
  {
     if (nextNode != this)
        parentNode->childNode = nextNode;
     else
        parentNode->childNode = NULL;
  }

  // links van andere childNodes goed instellen
  prevNode->nextNode = nextNode;
  nextNode->prevNode = prevNode;

  // de node uit de lijst verwijderen door naar zichzelf te laten wijzen
  prevNode = this;
  nextNode = this;
}

int CountNodes()
{
  if (childNode)
    return childNode->CountNodes() + 1;
  else 
    return - 1;
}
Ik neem aan dat dit deel duidelijk moet zijn als je weet hoe je nodes toe voegt. Hier wordt namelijk precies hetzelfde gedaan alleen hier wordt een node verwijdert. Bovendien zit hier nog een functie in om het aantal nodes te tellen. Dan nu nog het laatste deel en je linked list is klaar.

CNode()
{
  parentNode = childNode = NULL;
  prevNode = nextNode = this;
}

CNode (CNode *node)
{
  parentNode = childNode = NULL;
  prevNode = nextNode = this;
  AttachTo(node);
}

virtual ~CNode()
{
  Detach();
  
  While (childNode)
  {
    delete childNode;
  }
}
}
En dat waren dan linked lists, best wel pittig maar zeer makkelijk in het gebruik.

Succes

Vampire,