Implementieren Sie verknüpfte Liste in PHP

Question

Wie sollte ich eine verknüpfte Liste in PHP implementieren? Ist eine Implementierung in PHP integriert?

Ich muss viele Operationen einfügen und löschen, und gleichzeitig muss ich die Reihenfolge beibehalten.

Ich möchte nur PHP ohne spezielle Erweiterungen verwenden.

Answer 1

Es gibt SplDoublyLinkedList. Ist das auch in Ordnung?

Answer 2

Hier ist eine verkettete Listenimplementierung in PHP gezogen von: http://www.codediesel.com/php/linked-list-in-php/ die eine verknüpfte Liste in PHP hinzufügen, löschen, umkehren und leeren kann.

<?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

Hier ist der Code in PHP, die Liste Linked umsetzen wird, nur mit der Referenz von Kopfknoten dh ersten Knoten und fügen Sie dann auf den ersten, letzten und einen Schlüssel löschen, und auch den Code der Schlüssel halten in Liste.

<?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; 

-Code heraus setzen, wie:

$ 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

ich auch ein Programm zu schreiben versuchte, eine verkettete Liste in PHP zu erstellen. Hier ist was ich geschrieben habe und es hat für mich funktioniert. Ich hoffe, es hilft, die Frage zu beantworten.

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

Hier ist eine weitere Linked-List-Implementierung mit einem Array von Elementen. Die Add-Funktion hält die Elemente sortiert.

<?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; 

Die Ausgabe lautet:

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

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

- 2-4-5-7-10

Answer 6

Wenn nicht glaube, die meisten Leute verstehen, was verknüpfte Listen sind. Die Grundidee ist, dass Sie die Daten so organisieren möchten, dass Sie mit dem aktuellen Knoten auf den vorherigen und nächsten Knoten zugreifen können. Die anderen Funktionen wie hinzufügen, löschen, einfügen, Kopf usw. sind Zucker, obwohl notwendig. Ich denke, das SPL-Paket deckt viel ab. Problem ist, dass ich eine PHP 5.2.9 Klasse brauche. Ich denke, ich muss es selbst implementieren.