php 在php中实现链表

Implement linked list in php

提问by osgx

How should I implement a linked list in PHP? Is there a implementation built in into PHP?

我应该如何在 PHP 中实现链表？是否有内置于 PHP 中的实现？

I need to do a lot of insert and delete operations, and at same time I need to preserve order.

我需要做很多插入和删除操作，同时我需要保留顺序。

I'd like to use only PHP without any special extensions.

我只想使用没有任何特殊扩展的 PHP。

回答by NikiC

There is SplDoublyLinkedList. Is this okay, too?

有SplDoublyLinkedList。这也行吗？

回答by Lal Zada

Here is a linked list implementation in PHP pulled from: http://www.codediesel.com/php/linked-list-in-php/which can add, delete, reverse and empty a linkedlist in PHP.

这是从 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();

回答by krishna Prasad

Here is the code in php which will implement Linked List, only with the reference of head node i.e first node and then you add at first, last and delete a key, and also maintain the code of the keys in list.

下面是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;

Code out put as:

代码输出为：

$ 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

回答by Raluca Constanda

Here is another Linked list implementation using an array of elements. The add function keeps the elements sorted.

这是另一个使用元素数组的链表实现。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;

The output is:

输出是：

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

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

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

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

-2-4-5-7-10

-2-4-5-7-10

回答by JalalJaberi

Just to clarify, implementing linked list inPHP using PHP arrays probably is not a good idea, because PHP array is hash-table under the hood (not simple low-level arrays). Simultaneously, you don't get advantages of pointers.

澄清一下，在PHP 中使用 PHP 数组实现链表可能不是一个好主意，因为 PHP 数组是底层的哈希表（不是简单的低级数组）。同时，您不会获得指针的优势。

Instead, you can implement data structures like linked list forPHP using extensions, that means you are implementing a data structure inC toPHP.

相反，您可以使用扩展为PHP实现像链表这样的数据结构，这意味着您正在用C到PHP实现数据结构。

Spl data structures are an example, another example is php-ds extension, specially in case of linked lists, you can use this: https://www.php.net/manual/en/class.ds-sequence.php

spl 数据结构是一个例子，另一个例子是 php-ds 扩展，特别是在链表的情况下，你可以使用这个：https: //www.php.net/manual/en/class.ds-sequence.php

Sequence ADT is the unification of List ADT and Vector ADT, so you can use Sequence ADT implemented data structures as lists.

Sequence ADT 是 List ADT 和 Vector ADT 的统一，所以你可以使用 Sequence ADT 实现的数据结构作为列表。

Hope this could help someone choose wisely.

希望这可以帮助人们明智地选择。

回答by Harshita

I was also trying to write a program to create a linked list in PHP. Here is what I have written and it worked for me. I hope it helps to answer the question.

我还试图编写一个程序来在 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}

回答by Emmanuel Mahuni

If don't think most people understand what linked lists are. The basic idea is you want to keep data organised is such a way that you can access the previous and next node using the current node. The other features like add, delete, insert, head etc are sugar, though necessary. I think the SPL package does cover a lot. Problem is I need a PHP 5.2.9 class. Guess I've to implement it myself.

如果不认为大多数人理解链表是什么。基本思想是您希望将数据组织起来，以便您可以使用当前节点访问上一个和下一个节点。尽管有必要，但其他功能如添加、删除、插入、头部等都是糖。我认为 SPL 包确实涵盖了很多内容。问题是我需要一个 PHP 5.2.9 类。猜猜我必须自己实现它。