Implementar la lista vinculada en php

Question

¿Cómo debo implementar una lista vinculada en PHP? ¿Hay una implementación incorporada en PHP?

Necesito hacer muchas operaciones de inserción y eliminación, y al mismo tiempo necesito preservar el orden.

Me gustaría usar solo PHP sin extensiones especiales.

Answer 1

Hay SplDoublyLinkedList. ¿Esto está bien también?

Answer 2

Aquí hay una implementación de la lista vinculada en PHP extraída de: http://www.codediesel.com/php/linked-list-in-php/ que puede agregar, eliminar, invertir y vaciar una lista enlazada en PHP.

<?php 
class ListNode 
{ 
    public $data; 
    public $next; 
    function __construct($data) 
    { 
     $this->data = $data; 
     $this->next = NULL; 
    } 

    function readNode() 
    { 
     return $this->data; 
    } 
} 

class LinkList 
{ 
    private $firstNode; 
    private $lastNode; 
    private $count; 

    function __construct() 
    { 
     $this->firstNode = NULL; 
     $this->lastNode = NULL; 
     $this->count = 0; 
    } 

    //insertion at the start of linklist 
    public function insertFirst($data) 
    { 
     $link = new ListNode($data); 
     $link->next = $this->firstNode; 
     $this->firstNode = &$link; 

     /* If this is the first node inserted in the list 
      then set the lastNode pointer to it. 
     */ 
     if($this->lastNode == NULL) 
      $this->lastNode = &$link; 
      $this->count++; 
    } 


    //displaying all nodes of linklist 
    public function readList() 
    { 
     $listData = array(); 
     $current = $this->firstNode; 
     while($current != NULL) 
     { 
      array_push($listData, $current->readNode()); 
      $current = $current->next; 
     } 
     foreach($listData as $v){ 
      echo $v." "; 
     } 
    } 

    //reversing all nodes of linklist 
    public function reverseList() 
    { 
     if($this->firstNode != NULL) 
     { 
      if($this->firstNode->next != NULL) 
      { 
       $current = $this->firstNode; 
       $new = NULL; 

       while ($current != NULL) 
       { 
        $temp = $current->next; 
        $current->next = $new; 
        $new = $current; 
        $current = $temp; 
       } 
       $this->firstNode = $new; 
      } 
     } 
    } 



    //deleting a node from linklist $key is the value you want to delete 
    public function deleteNode($key) 
    { 
     $current = $this->firstNode; 
     $previous = $this->firstNode; 

     while($current->data != $key) 
     { 
      if($current->next == NULL) 
       return NULL; 
      else 
      { 
       $previous = $current; 
       $current = $current->next; 
      } 
     } 

     if($current == $this->firstNode) 
     { 
       if($this->count == 1) 
       { 
        $this->lastNode = $this->firstNode; 
       } 
       $this->firstNode = $this->firstNode->next; 
     } 
     else 
     { 
      if($this->lastNode == $current) 
      { 
       $this->lastNode = $previous; 
      } 
      $previous->next = $current->next; 
     } 
     $this->count--; 
    } 


     //empty linklist 
    public function emptyList() 
    { 
     $this->firstNode == NULL; 

    } 


    //insertion at index 

    public function insert($NewItem,$key){ 
     if($key == 0){ 
     $this->insertFirst($NewItem); 
    } 
    else{ 
     $link = new ListNode($NewItem); 
     $current = $this->firstNode; 
     $previous = $this->firstNode; 

     for($i=0;$i<$key;$i++) 
     {  
       $previous = $current; 
       $current = $current->next; 
     } 

      $previous->next = $link; 
      $link->next = $current; 
      $this->count++; 
    } 

    } 
} 

$obj = new LinkList(); 
$obj->insertFirst($value); 
$obj->insert($value,$key); // at any index 
$obj->deleteNode($value); 
$obj->readList(); 

Answer 3

Este es el código en php que implementará lista enlazada, sólo con la referencia de la cabeza nodo es decir primer nodo y luego añadir en un principio, al final y eliminar una clave, y también mantienen el código de las llaves en lista.

<?php 

/** 
* Class Node 
*/ 
class Node 
{ 
    public $data; 
    public $next; 

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

/** 
* Class LinkList 
*/ 
class LinkList 
{ 
    public $head = null; 

    private static $count = 0; 

    /** 
    * @return int 
    */ 
    public function GetCount() 
    { 
     return self::$count; 
    } 

    /** 
    * @param mixed $item 
    */ 
    public function InsertAtFist($item) { 
     if ($this->head == null) { 
      $this->head = new Node($item); 
     } else { 
      $temp = new Node($item); 

      $temp->next = $this->head; 

      $this->head = $temp; 
     } 

     self::$count++; 
    } 

    /** 
    * @param mixed $item 
    */ 
    public function InsertAtLast($item) { 
     if ($this->head == null) { 
      $this->head = new Node($item); 
     } else { 
      /** @var Node $current */ 
      $current = $this->head; 
      while ($current->next != null) 
      { 
       $current = $current->next; 
      } 

      $current->next = new Node($item); 
     } 

     self::$count++; 
    } 

    /** 
    * Delete the node which value matched with provided key 
    * @param $key 
    */ 
    public function Delete($key) 
    { 
     /** @var Node $current */ 
     $current = $previous = $this->head; 

     while($current->data != $key) { 
      $previous = $current; 
      $current = $current->next; 
     } 

     // For the first node 
     if ($current == $previous) { 
      $this->head = $current->next; 
     } 

     $previous->next = $current->next; 

     self::$count--; 
    } 

    /** 
    * Print the link list as string like 1->3-> ... 
    */ 
    public function PrintAsList() 
    { 
     $items = []; 
     /** @var Node $current */ 
     $current = $this->head; 
     while($current != null) { 
      array_push($items, $current->data); 
      $current = $current->next; 
     } 

     $str = ''; 
     foreach($items as $item) 
     { 
      $str .= $item . '->'; 
     } 

     echo $str; 

     echo PHP_EOL; 
    } 
} 

$ll = new LinkList(); 

$ll->InsertAtLast('KP'); 
$ll->InsertAtLast(45); 
$ll->InsertAtFist(11); 
$ll->InsertAtLast('FE'); 
$ll->InsertAtFist('LE'); 
$ll->InsertAtFist(100); 
$ll->InsertAtFist(199); 
$ll->InsertAtLast(500); 

$ll->PrintAsList(); 
echo 'Total elements ' . $ll->GetCount(); 
echo PHP_EOL; 
$ll->Delete(45); 
$ll->PrintAsList(); 
echo 'Total elements ' . $ll->GetCount(); 
echo PHP_EOL; 
$ll->Delete(500); 
$ll->PrintAsList(); 
echo 'Total elements ' . $ll->GetCount(); 
echo PHP_EOL; 
$ll->Delete(100); 
$ll->PrintAsList(); 
echo 'Total elements ' . $ll->GetCount(); 
echo PHP_EOL; 

Código cabo puso como:

$ php LinkList.php 
199->100->LE->11->KP->45->FE->500-> 
Total elements 8 
199->100->LE->11->KP->FE->500-> 
Total elements 7 
199->100->LE->11->KP->FE-> 
Total elements 6 
199->LE->11->KP->FE-> 
Total elements 5 

Answer 4

También estaba tratando de escribir un programa para crear una lista enlazada en PHP. Esto es lo que he escrito y funcionó para mí. Espero que ayude a responder la pregunta.

Created a php file. Name: LinkedList.php 
{code} 
<?php 

require_once (__DIR__ . "/LinkedListNodeClass.php"); 

$node_1 = new Node(); 
Node::createNode($node_1, 5); 
echo "\n Node 1 is created."; 

$head = &$node_1; 
echo "\n Head is intialized with Node 1."; 

$node_2 = new Node(); 
Node::createNode($node_2, 1); 
echo "\n Node 2 is created."; 

Node::insertNodeInLinkedList($head, $node_2); 

$node_3 = new Node(); 
Node::createNode($node_3, 11); 
echo "\n Node 3 is created."; 

Node::insertNodeInLinkedList($head, $node_3); 

$node_4 = new Node(); 
Node::createNode($node_4, 51); 
echo "\n Node 4 is created."; 

Node::insertNodeInLinkedList($head, $node_4); 

$node_5 = new Node(); 
Node::createNode($node_5, 78); 
echo "\n Node 5 is created."; 

Node::insertNodeInLinkedList($head, $node_5); 

$node_6 = new Node(); 
Node::createNode($node_6, 34); 
echo "\n Node 6 is created."; 

Node::insertNodeInLinkedList($head, $node_6); 

$node_7 = new Node(); 
Node::createNode($node_7, 99); 
echo "\n Node 7 is created."; 

Node::insertNodeInHeadOfLinkedList($head, $node_7); 

$node_8 = new Node(); 
Node::createNode($node_8, 67); 
echo "\n Node 8 is created."; 

Node::insertNodeInHeadOfLinkedList($head, $node_8); 

$node_9 = new Node(); 
Node::createNode($node_9, 101); 
echo "\n Node 9 is created."; 

Node::insertNodeAfterAPositionInLinkedList($head, 5, $node_9); 

$node_10 = new Node(); 
Node::createNode($node_10, 25); 
echo "\n Node 10 is created."; 

Node::insertNodeAfterAPositionInLinkedList($head, 2, $node_10); 

echo "\n Displaying the linked list: \n"; 
Node::displayLinkedList($head); 

?> 
{code} 

This file is calling a class to create, insert and display nodes in linked list. Name: LinkedListNodeClass.php 
{code} 
<?php 

class Node { 
    private $data; 
    private $next; 

    public function __construct() { 
    //does nothing... 
    } 

    //Creates a node 
    public function createNode($obj, $value) { 
    $obj->data = $value; 
    $obj->next = NULL; 
    }  

    //Inserts a created node in the end of a linked list 
    public function insertNodeInLinkedList($head, &$newNode) { 
    $node = $head; 
    while($node->next != NULL){ 
     $node = $node->next; 
    } 
    $node->next = $newNode; 
    } 

    //Inserts a created node in the start of a linked list 
    public function insertNodeInHeadOfLinkedList(&$head, &$newNode) { 
    $top = $head; 
    $newNode->next = $top; 
    $head = $newNode; 
    } 

    //Inserts a created node after a position of a linked list 
    public function insertNodeAfterAPositionInLinkedList($head, $position, &$newNode) { 
    $node = $head; 
    $counter = 1; 
    while ($counter < $position){ 
     $node = $node->next; 
     $counter++; 
    } 
    $newNode->next = $node->next; 
    $node->next = $newNode; 
    } 

    //Displays the Linked List 
    public function displayLinkedList($head) { 
    $node = $head; 
    print($node->data); echo "\t"; 
    while($node->next != NULL){ 
     $node = $node->next; 
     print($node->data); echo "\t"; 
    } 
    } 
} 

?> 
{code} 

Answer 5

Aquí hay otra implementación de la lista enlazada que utiliza una matriz de elementos. La función de agregar mantiene los elementos ordenados.

<?php 

class LinkedList{ 

    private $_head = null; 
    private $_list = array(); 

    public function addNode($val) { 

     // add the first element 
     if(empty($this->_list)) { 
      $this->_head = $val; 
      $this->_list[$val] = null; 
      return; 
     } 

     $curr = $this->_head; 

     while ($curr != null || $curr === 0) { 

      // end of the list 
      if($this->_list[$curr] == null) { 
       $this->_list[$curr] = $val; 
       $this->_list[$val] = null; 
       return; 
      } 

      if($this->_list[$curr] < $val) { 
       $curr = $this->_list[$curr]; 
       continue; 
      } 
      $this->_list[$val] = $this->_list[$curr]; 
      $this->_list[$curr] = $val; 
      return; 

     } 

    } 

    public function deleteNode($val) { 

     if(empty($this->_list)) { 
      return; 
     } 

     $curr = $this->_head; 

     if($curr == $val) { 

      $this->_head = $this->_list[$curr]; 
      unset($this->_list[$curr]); 

      return; 
     } 

     while($curr != null || $curr === 0) { 

      // end of the list 
      if($this->_list[$curr] == null) { 
       return; 
      } 

      if($this->_list[$curr] == $val) { 
       $this->_list[$curr] = $this->_list[$val]; 
       unset($this->_list[$val]); 
       return; 
      } 

      $curr = $this->_list[$curr]; 
     } 
    } 

    function showList(){ 
     $curr = $this->_head; 
     while ($curr != null || $curr === 0) { 
      echo "-" . $curr; 
      $curr = $this->_list[$curr]; 
     } 


    } 
} 

$list = new LinkedList(); 

$list->addNode(0); 
$list->addNode(3); 
$list->addNode(7); 
$list->addNode(5); 
$list->addNode(2); 
$list->addNode(4); 
$list->addNode(10); 

$list->showList(); 

echo PHP_EOL; 
$list->deleteNode(3); 

$list->showList(); 

echo PHP_EOL; 

$list->deleteNode(0); 

$list->showList(); 

echo PHP_EOL; 

La salida es:

-0-2-3-4-5-7-10

-0-2-4-5-7-10

- 2-4-5-7-10

Answer 6

Si no cree que la mayoría de las personas entienden qué son las listas vinculadas. La idea básica es que desee mantener los datos organizados de tal manera que pueda acceder al nodo anterior y siguiente utilizando el nodo actual. Las otras funciones como agregar, eliminar, insertar, cabeza, etc. son azúcar, aunque necesarias. Creo que el paquete de SPL cubre mucho. El problema es que necesito una clase PHP 5.2.9. Creo que tengo que implementarlo yo mismo.