Uitleg: Linked Lists in PHP

Linked lists zijn een van de meeste basale dingen die een beetje developer moet weten, een linked list is een lijst met objecten die verwijzen naar het volgende object door middel van pointers (geheugen verwijzingen).

Wat kan een reden zijn om Linked Lists te gebruiken en geen Array:

In een linked list is het makkelijker om nodes toe te voegen tussen bijvoorbeeld 2 nodes, omdat je gewoon een nieuwe node kunt maken en de pointers naar elkaar kunt laten verwijzen. Als jij bijvoorbeeld een array hebt met element 0 tot 9 en je wil na element 4 een nieuwe element op plaats 5 toevoegen moet je de boel opnieuw sorteren en herstructureren (want 5 wordt 6, 6 wordt 7 etc.), dit kost veel meer cpu en geheugen dan met een linked list.

Een andere reden kan zijn, de goede toepasbaarheid in multi threaded applications. Dit omdat je gewoon andere nodes in de lijst kunt verwijderen en tegelijk ook bewerkingen in een object kunt doen zonder dat je een fatale uitzondering krijgt. Als je een array zou gaan her-sorteren en de pointers opnieuw zou toewijzen zou het geheugen van waar de thread bezig is niet meer overeenkomen met waar de array data zich bevindt.

Voorbeeld van een real-life situatie:

Goed bruikbaar in bijvoorbeeld games, of dingen waar veel informatie in een object zit zodat het allemaal een beetje snel blijf 😉 Je kan bijvoorbeeld denken aan Command & Conquer, als je alle objecten moet tekenen op het scherm moet je x,y coordinaten bij houden, doel coordinaten, status voortuig, kleur, type, plaatje of de bitmaps voor het texture mappen etc. Om alle dingen op het scherm te tekenen loop je door de lijst, als het object binnen het kader van het scherm valt teken je hem anders sla je hem over en is die kapot geschoten, unlink je hem gewoon en is die weg 🙂

Hieronder een voorbeeld in php, om, een indruk te krijgen hoe een linked list nu eigenlijk precies werkt.

Output:

LinkedList nodes:
Naam: Victor Link, Leeftijd: 24
Naam: Henk Test, Leeftijd: 70
Naam: Piet Voorbeeld, Leeftijd: 55
Naam: Jan Klaas, Leeftijd: 18
Naam: Sander Aerts, Leeftijd: 34
Naam: Paoter Gustaaf, Leeftijd: 39

Piet Voorbeeld is 55 jaar oud

LinkedList nodes:
Naam: Henk Test, Leeftijd: 70
Naam: Piet Voorbeeld, Leeftijd: 55
Naam: Jan Klaas, Leeftijd: 18
Naam: Sander Aerts, Leeftijd: 34
Naam: Paoter Gustaaf, Leeftijd: 39

LinkedList nodes:
Naam: Henk Test, Leeftijd: 70
Naam: Piet Voorbeeld, Leeftijd: 55
Naam: Jan Klaas, Leeftijd: 18
Naam: Sander Aerts, Leeftijd: 34

/**
	 * **************************************************************************
	 * Linked Lists voorbeeld in php
	 * **************************************************************************
	 * Author			: Sander Aerts (sander@aerts-it.nl)
	 * Created			: 17 - 11 - 2016
	 * Last modified	: 17 - 11 - 2016
	 * **************************************************************************
	*/
	
	/**
	 *  Node object
	 */
	class listItem {
		public $name;
		public $age;
		public $head;
		public $next;
	}
	
	/**
	 *  Eerste node uit de lijst verwijderen
	 */
	function removeFirstItem(&$list)
	{
		/**
		 *  Controle of we niet de enige node zijn in de lijst
		 */
		if ( $list !=null && $list->next != null ) {
			$cNode = $list->next;
			$list  = $cNode;
		} elseif ( $list != null && $list->next == null ) {
			/**
			 *  Enige node, verwijder deze
			 */
			unset($list);
		}
	}
	
	/**
	 *  Laatste node uit de lijst verwijderen
	 */
	function removeLastItem(&$list)
	{
		if ( $list != null ) {
			/**
			 *  Ga naar de laatste node in de lijst
			 */
			$cNode = $list;
			while ( $cNode->next->next != null ) $cNode = $cNode->next;

			/**
			 * Laatste node verwijderen
			 */
			$cNode->next = null;
		}
	}
	
	/**
	 *  Node toevoegen aan begin van de lijst
	 */
	function addItemHead(&$list, $name, $age)
	{
		if ( $list == null ) {
			/* Nog geen nodes in de lijst, maak de eerste node aan  */
			$list 		= new listItem;
			$list->head = true;
			$list->next = null;
			$list->name = $name;
			$list->age  = $age;
		} else {
			/* Nieuwe node toevoegen aan begin van de lijst */
			$newItem 			= new listItem;
			$newItem->head 		= true;
			$newItem->next 		= $list;
			$newItem->name 		= $name;
			$newItem->age  		= $age;
			$list				= $newItem;
			$list->next->head	= false;
		}
	}
	
	/**
	 *  Node toevoegen aan het einde van de lijst
	 */
	function addItemTail(&$list, $name, $age)
	{
		if ( $list == null ) {
			addItemHead($list, $name, $age);
		} else {
			/**
			 *  Ga naar de laatste node in de lijst
			 */
			$cNode = $list;
			while ( $cNode->next != null ) $cNode = $cNode->next;

			/**
			 *  Nieuwe node toevoegen aan begin van de lijst
			 */
			$newItem 			= new listItem;
			$newItem->head 		= false;
			$newItem->next 		= null;
			$newItem->name 		= $name;
			$newItem->age  		= $age;
			$cNode->next		= $newItem;
		}
	}
	
	/**
	 *  Zoek iets in de lijst en resulteer dit resultaat als pointer uit de lijst
	 */
	function searchName(&$list, $name)
	{
		if ( $list != null ) {
			$cNode = $list;
			if ( $cNode->name == $name ) return($cNode);
			while ( $cNode->next != null ) {
				$cNode = $cNode->next;
				if ( $cNode->name == $name ) return($cNode);
			}
		} else {
			return(null);
		}
	}
	
	/**
	 *  Lijst weergeven
	 */
	function showList(&$list)
	{
		echo "\r\nLinkedList nodes:\r\n";
		if ( $list != null ) {
			$cNode = $list;
			echo "Naam: " . $cNode->name . ", Leeftijd: " . $cNode->age . "\r\n";
			while ( $cNode->next != null ) {
				$cNode = $cNode->next;
				echo "Naam: " . $cNode->name . ", Leeftijd: " . $cNode->age . "\r\n";
			}
		} else {
			die("Lijst bevat geen nodes!");
		}
	}
	
	header("Content-type: text/plain");
	
	/**
	 *  Nodes toevoegen aan begin van de lijst, de eerste node wordt
	 *  dus automatisch de 2de node, wat met printen van de lijst dus
	 *  tegenovergestelde volgorde weergeeft zoals hieronder toegevoegd
	 */
	addItemHead($myList, "Sander Aerts", "34");
	addItemHead($myList, "Jan Klaas", "18");
	addItemHead($myList, "Piet Voorbeeld", "55");
	addItemHead($myList, "Henk Test", "70");
	addItemHead($myList, "Victor Link", "24");
	
	/**
	 *  Node toevoegen aan het einde van de lijst, deze komt dus achter de
	 *  node "Sander Aerts"
	 */
	addItemTail($myList, "Paoter Gustaaf", "39");
	
	/**
	 *  Lijst printen
	 */
	showList($myList);
	
	/**
	 *  Zoek naar "Piet Voorbeeld" in de lijst
	 */
	$node = searchName($myList, "Piet Voorbeeld");
	echo "\r\n" . $node->name . " is " . $node->age . " jaar oud\r\n";
	
	/**
	 *  Eerst node verwijderen en lijst printen
	 */
	removeFirstItem($myList);
	showList($myList);
	
	/**
	 *  Laatste node verwijderen en lijst printen
	 */
	removeLastItem($myList);
	showList($myList);