Dec 202012
 

A linked list implementation in PHP. I need to look into whether I need a destructor or not.

 

  include_once("rc/collections/RListIterator.php");
  include_once("rc/collections/RAbstractList.php");
/**
 * An RList implemented as a linked list.
 *
 * @author Steven Bolin - December 2012 - All rights reserved
 */
final class RLinkedList extends RAbstractList implements RList {

  private $head; // The first link
  private $tail; // The latest link
  private $size; // The size of the list

  public function __construct() {
    $this->head = new RLinkedListNode(null);
    $this->tail = $this->head;
    $this->size = 0;
  }

  /**
   * Inserts the specified element at the specified position in this list
   * @param int $index - The index at which to enter the element
   * @param mixed $element - The element to add to the List
   */
  public function addAt($index, $element) {
    if($index >= 0 && $index <= $this->size && $element !== null) {
      $count = 0;
      $currentNode = $this->head;
      while($count < $index) {         $currentNode = $currentNode->next();
        $count++;
      }
      $newNode = new RLinkedListNode($element);
      $newNode->setNext($currentNode->next());
      $currentNode->setNext($newNode);
      $this->size++;
    }
  }

  /**
   * Removes all of the elements from this list.
   */
  public function clear() {
    $this->head = $this->tail;
    $this->size = 0;
  }

  /**
   * Returns the element at the specified position in this list.
   * @param int $index - The index of the element to return.
   * @return mixed - Returns the element at the specified position in this list.
   */
  public function get($index) {
    $result = null;
    if($this->indexInRange($index) && is_numeric($index)) {
      $count = 0;
      $currentNode = $this->head;
      while($count <= $index) {         $currentNode = $currentNode->next();
        $count++;
      }
      $result = $currentNode->value();
    }
    return $result;
  }

  /**
   * Returns an iterator over the elements in this list in proper sequence.
   * @return \RListIterator - Returns an iterator over the elements in this list 
   * in proper sequence.
   */
  public function iterator() {
    return new RListIterator($this);
  }

  /**
   * Removes the element at the specified position in this list.
   * @param int $index - the index of the element to remove.
   */
  public function removeIndex($index) {
    if($this->indexInRange($index) && is_numeric($index)) {
      $count = 0;
      $currentNode = $this->head;
      while($count < $index) {         $currentNode = $currentNode->next();
        $count++;
      }
      $currentNode->setNext($currentNode->next()->next());
      $this->size--;
    }    
  }

  /**
   * Replaces the element at the specified position in this list with the 
   * specified element
   * @param int $index - The index at which to place element
   * @param mixed $element - The element to place at index
   */
  public function set($index, $element) {
    if($this->indexInRange($index) && is_numeric($index)) {
      $count = 0;
      $currentNode = $this->head;
      while($count < $index) {         $currentNode = $currentNode->next();
        $count++;
      }
      $currentNode->next()->setValue($element);
    }    
  }

  /**
   * Returns the number of elements in this list.
   * @return int - Returns the number of elements in this list.
   */
  public function size() {
    return $this->size;
  }

  /**
   * Returns a string representation of the List.
   * @return string - Returns a string representation of the List.
   */
  public function toString() {

    $result           = "[";
    if($this->size > 0) {
      $node = $this->head->next();
      $result .= $this->dealWithObject($node->value());
    }

    $j = 1;
    while($j<$this->size) {
      $node = $node->next();
      $result .= ", " . $this->dealWithObject($node->value());
      $j++;
    }

    $result .= "]";

    return $result;
  }

  // Some items may be objects yet still not have a toString method defined. 
  // This deals with them.
  private function dealWithObject($possibleObject) {
    $result = null;

    if(is_object($possibleObject)) {
      if(method_exists($possibleObject, "toString")) {
        $result = $possibleObject->toString();
      }
    } else {
      $result = $possibleObject;
    }

    return $result;
  }

  private function indexInRange($index) {
    return ($index < $this->size && $index >= 0);
  }
} // end RLinkedList class

final class RLinkedListNode {

  private $next;
  private $value;

  public function __construct($value) {
    $this->next = null;
    $this->value = $value;
  }

  public function next() {
    return $this->next;
  }

  public function value() {
    return $this->value;
  }

  public function setNext(RLinkedListNode $next=null) {
    $this->next = $next;
  }

  public function setValue($value) {
    $this->value = $value;
  }

} // end Node class
 Posted by at 9:17 am