PHP Classes

File: class.LinkedList.php

Recommend this page to a friend!
  Classes of Scott Furt   LinkedList   class.LinkedList.php   Download  
File: class.LinkedList.php
Role: ???
Content type: text/plain
Description: The class
Class: LinkedList
A simple Linked List implementation
Author: By
Last change:
Date: 21 years ago
Size: 6,399 bytes


Class file image Download
<? /* Double-Ended Linked-List PHP class. Scott Hurring ( This code is public domain, but i do hope that if you use portions of it you give me some credit. Thanks. I felt like learning about PHP References, so i wrote this little implementation of a Linked List for PHP. ... PHP supports all this stuff natively, so this code really doesn't serve much purpose, other than being a good tool to help me learn a bit more about references. In PHP, if you have an array of "nodes", see: array_push(), array_unshift(), array_pop(), and array_shift(); The "node" structure ($this->node) can be *any* kind of array you want. // Functions provided by this class push($node) Adds the node to the END of the list pop() Removes a node from the END of the list unshift($node) Adds the node to the BEGINNING of the list shift() Removes a node from the BEGINNING of the list // How the code works // Get a fresh node to populate $node = $list->node(); // Populate it $node['field'] = "Some data"; // Put it onto the list $list->push($node); $list->unshift($node); // You get the idea... */ class LinkedList { /* Define node structure here (don't touch 'next', it points to the next node) */ var $_node = array( // Contains reference to next node 'next' => NULL, // Define your node structure below: // Process ID 'pid' => 0, // Time of process start 'start' => 0, // Duration of process 'duration' => 0, ); // Head is a reference to first node // (which should always be an empty 'dummy' head node) var $head = NULL; // Number of nodes in the linked list // (not including the 'dummy' head node) var $count = 0; // Set $dbg=1 to print some debugging info var $dbg = 0; // Constructor function LinkedList() { // Create and insert 'dummy' head node at beginning of list $dummy_head = $this->_node; $this->head = &$dummy_head; $this->debug("[LinkedList]: Constructor, creating dumy head"); } /* Put $node onto BOTTOM of list */ function unshift(&$node) { // Get pointer to first node $first =& $this->first(); // $node is now the first item $node['next'] = $first; // point the dummy head at $node $this->head['next'] = $node; $this->count++; return 1; } /* Remove (and return) BOTTOM element from the list Returns NULL if list is empty */ function shift() { // Get copy of first node $first = $this->first(); // There is no first item if ($first == NULL) return NULL; // Point the 'dummy' head at the node after the removed node ($first) $this->head['next'] = $first['next']; // Clear pointers for the removed node $first['next'] = NULL; $first['prev'] = NULL; $this->count--; return $first; } /* Put $node onto the TOP of the list */ function push(&$node) { // Get pointer to last node $last =& $this->last(); $this->debug("[push]: current last = {$last['pid']} new last = {$node['pid']}"); // Insert $node after the current last element $last['next'] = $node; // $node is now the end of the list $node['next'] = NULL; $this->count++; return 1; } /* Remove (and return) TOP node from the list Returns NULL if list is empty */ function pop() { $last = $this->last(); $next_to_last =& $this->next_to_last(); // If the last item is the head, then it's an empty list if ($last == $this->head) return NULL; $this->debug("[pop]: last = {$last['pid']} next_to_last = {$next_to_last['pid']}"); // next_to_last is now the end $next_to_last['next'] = NULL; $this->count--; return $last; } /* Return the BOTTOM node without modifying the list. Returns NULL if list is empty $node =& $this->first() returns pointer to actual node $node = $this->first() returns copy of node data */ function &first() { // Pointer to the first 'non-dummy' element $curr =& $this->head['next']; // List is empty if ($curr == NULL) return NULL; return $curr; } /* Return the TOP node without modifying the list. Returns NULL if list is empty $node =& $this->last() returns pointer to actual node $node = $this->last() returns copy of node data */ function &last() { // Get pointer to the 'dummy' head node $curr =& $this->head; // Iterate through list BOTTOM->TOP, until reaching the TOP node while($curr['next'] != NULL) $curr = &$curr['next']; return $curr; } /* Return the next-to-last node either return a copy or a ref depending on how it's called */ function &next_to_last() { // Pointer to 'dummy' head node $curr =& $this->head; // Iterate through the list BOTTOM->TOP, until reaching TOP-1 node while($curr['next']['next'] != NULL) $curr = &$curr['next']; return $curr; } /* Update the contents of an existing node */ function update($index, &$node) { // Pointer to the node that's being updated $curr =& $this->search($index); $this->debug("[update]: (index=$index), (pid={$curr['pid']})"); // Set the pointer correctly in the new node, then // replace the current node with the new data $node['next'] = $curr['next']; $curr = $node; return 1; } /* Return a specific node */ function &search($index) { // Pointer to first data node $curr =& $this->first(); $i = 0; while ($i++ < ($index-1)) { if ($curr == NULL) return NULL; $curr = &$curr['next']; } return $curr; } /* Return an empty node struct to popuate and 'push' or 'unshift' onto the list */ function new_node() { return $_node; } /* Show all items in the list BOTTOM->TOP */ function show() { print "\nShowing list (count==". $this->count .")\n"; // Copy of BOTTOM node $curr = $this->first(); if ($curr == NULL) print "\tNOTHING TO SHOW\n"; while($curr != NULL) { print "\tPID=". $curr['pid']; print " (next: ". $curr['next']['pid'] .")"; print " (time: ". $curr['time'] .")"; print "\n"; $curr = $curr['next']; } print "\n"; return 1; } /* Print debugging output, if ($this->dbg) */ function debug($text) { if ($this->dbg == 1) print $text ."\n"; return 1; } } // End LinkedList class ?>