在php中實現鏈表PHP

Question

我應該如何在PHP中實現鏈表？是否有內置於PHP的實現？

我需要做大量的插入和刪除操作，同時我需要保持順序。

我只想使用沒有任何特殊擴展名的PHP。

Answer 1

有SplDoublyLinkedList。這也好嗎？

Answer 2

以下是PHP中的鏈表實現：http://www.codediesel.com/php/linked-list-in-php/，它可以在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

這裏是在PHP代碼將實現鏈表，只有頭節點，即第一個節點的引用，然後添加在第一，最後和刪除鍵，也保持按鍵的代碼在列表中。

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

碼出放爲：

$ 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

我也試圖寫一個程序來創建一個PHP鏈表。這是我寫的，它爲我工作。我希望這有助於回答這個問題。

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

這是另一個使用元素數組的鏈表實現。 add函數保持元素排序。

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

的輸出是：

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

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

- 2-4-5-7-10

Answer 6

如果不認爲大多數人理解鏈表是什麼。基本思想是你想保持數據的組織方式，這樣你就可以使用當前節點訪問前一個和下一個節點。像添加，刪除，插入，頭等其他功能是糖，儘管是必要的。我認爲SPL包涵蓋了很多。問題是我需要一個PHP 5.2.9類。猜猜我必須自己實現它。