Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- <?php
- class LinkedList {
- // object Node representing the head of the list
- private $head;
- // object Node representing the tail of the list
- private $tail;
- public function __construct() {
- $this->head = new Node(null);
- $this->tail = new Node(null);
- $this->head->setNext($this->tail);
- $this->tail->setPrevious($this->head);
- }
- /**
- * Add node to the tail of the list
- * @param type $key
- * @param type $data
- * @return boolean
- */
- public function addTail($data) {
- $this->attach($this->tail->getPrevious(), new Node($data));
- }
- /**
- * Add node to the head of the list
- * @param type $key
- * @param type $data
- */
- public function addHead($data) {
- $this->attach($this->head, new Node($data));
- }
- /**
- * Removes a node
- * @param Node $node node to remove
- */
- public function remove($nodeToRemove) {
- $this->detach($nodeToRemove);
- }
- /**
- * Returns the number of elements in the linked list
- * @return int
- */
- public function count() {
- $count = 0;
- $p = $this->head->getNext();
- while ($p->getNext() != null) {
- $p = $p->getNext();
- $count++;
- }
- return $count;
- }
- /**
- * Adds a node after another
- * @param Node $prev the node after which we want to add (e.g. head, tail or another generic node)
- * @param Node $node the node to add
- */
- private function attach($prev, $node) {
- $node->setPrevious($prev);
- $node->setNext($prev->getNext());
- $node->getNext()->setPrevious($node);
- $node->getPrevious()->setNext($node);
- }
- /**
- * Removes a node from the list
- * @param Node $node the node to remove from the list
- */
- private function detach($node) {
- $node->getPrevious()->setNext($node->getNext());
- $node->getNext()->setPrevious($node->getPrevious());
- }
- public function __toString() {
- $r = 'LinkedList { ';
- $h = $this->head->getNext();
- while ($h->getNext() != null) {
- $r .= $h->getData() . ', ';
- $h = $h->getNext();
- }
- return $r . '}';
- }
- }
- /**
- * Class that represents a node in a doubly linked list
- */
- class Node {
- private $data;
- // the next node
- private $next;
- // the previous node
- private $previous;
- /**
- * @param string $data the content of the node
- */
- public function __construct($data) {
- $this->data = $data;
- }
- /**
- * Sets a new value for the node data
- * @param string the new content of the node
- */
- public function setData($data) {
- $this->data = $data;
- }
- /**
- * Sets a node as the next node
- * @param Node $next the next node
- */
- public function setNext(Node $next) {
- $this->next = $next;
- }
- /**
- * Sets a node as the previous node
- * @param Node $previous the previous node
- */
- public function setPrevious(Node $previous) {
- $this->previous = $previous;
- }
- /**
- * Returns the node data
- * @return mixed the content of the node
- */
- public function getData() {
- return $this->data;
- }
- /**
- * Returns the next node
- * @return Node the next node of the node
- */
- public function getNext() {
- return $this->next;
- }
- /**
- * Returns the previous node
- * @return Node the previous node of the node
- */
- public function getPrevious() {
- return $this->previous;
- }
- public function __toString() {
- return "Node($this->data)";
- }
- }
- $foo = new LinkedList();
- for ($i = 0; $i < 200000; ++$i) {
- // echo "putting $i\n";
- $foo->addTail($i);
- }
- echo "start counting", PHP_EOL;
- echo "count: ", $foo->count(), PHP_EOL;
- // php crashes during the count()!
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement