在php中实现链表

Question

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

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

我想只使用 PHP，而不使用任何特殊扩展。

Answer 1

// Here's a basic implementation of SplDoublyLinkedList using PHP.
$splDoubleLinkedList = new SplDoublyLinkedList();
$splDoubleLinkedList->push('a');
$splDoubleLinkedList->push('3');
$splDoubleLinkedList->push('v');
$splDoubleLinkedList->push('1');
$splDoubleLinkedList->push('p');
// $splDoubleLinkedList->unshift('10');
// $splDoubleLinkedList->pop();
$splDoubleLinkedList->add(3, 3.0);
// First of all, we need to rewind list.
$splDoubleLinkedList->rewind();
// Use while, check if the list has valid node.
while($splDoubleLinkedList->valid()){
  // Print current node's value.
   echo $splDoubleLinkedList->current()."\n";
 // Turn the cursor to next node.
 $splDoubleLinkedList->next();
}

Answer 2

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

Answer 3

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

相反，您可以使用扩展为 PHP 实现链接列表等数据结构，这意味着您正在用 C 语言实现数据结构到 PHP。

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

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

希望这可以帮助人们做出明智的选择。

Answer 4

链接列表 MVC 示例 - PHP

模型代码：

    <?php

class SongNode
{
    public $songName;
    public $artistName;
    public $next;

    public function __construct($songName, $artistName)
    {
        $this->songName = $songName;
        $this->artistName = $artistName;
        $this->next = null;
    }
}

class Playlist
{
    private $head;
    private $tail;

    public function __construct()
    {
        $this->head = null;
        $this->tail;
    }

    public function addSong($songName, $artistName)
    {
        $newNode = new SongNode($songName, $artistName);
        if ($this->head === null) {
            $this->head = $this->tail = $newNode;
        } else {
            $this->tail->next = $newNode;
            $this->tail = $newNode;
        }
    }

    public function removeSong($songName)
    {
        if ($this->head === null) return "Playlist is empty.";

        $current = $this->head;
        $previous = null;
        while ($current != null && $current->songName != $songName) {
            $previous = $current;
            $current = $current->next;
        }

        if ($current == null) return "Song not found.";

        if ($previous == null) {
            $this->head = $this->head->next;
        } else {
            $previous->next = $current->next;
        }

        if ($current->next == null) {
            $this->tail = $previous;
        }

        return "$songName removed from the playlist.";
    }

    public function getSongs()
    {
        $songs = [];
        $current = $this->head;
        while ($current != null) {
            $songs[] = "{$current->songName} by {$current->artistName}";
            $current = $current->next;
        }
        return $songs;
    }
}

控制器代码：

<?php

include  __DIR__ . '/../models/playlistModel.php';
require_once __DIR__ . '/../views/playlist/PlaylistView.php';

class PlaylistController
{
    private $model;

    public function __construct()
    {
        $this->model = new Playlist();
    }

    public function handleRequest()
    {
        if ($_SERVER['REQUEST_METHOD'] == 'POST' && isset($_POST['addSong'])) {
            $this->add($_POST['songName'], $_POST['artistName']);
        }
        $this->listSongs();
    }

    private function add($songName, $artistName)
    {
        $this->model->addSong($songName, $artistName);
    }

    private function listSongs()
    {
        $songs = $this->model->getSongs();
        $view = new PlaylistView();
        $view->output($songs);
    }
}


View Code:

    <?php
    class PlaylistView
    {
    public function output($songs)
    {
        echo "<h3>Playlist</h3>";
        echo '<form action="" method="post">
                <input type="text" name="songName" placeholder="S Name" required>
                <input type="text" name="artistName" placeholder="Artist Name" required>
                <button type="submit" name="addSong">Add </button>
              </form>';

        if (empty($songs)) {
            echo "<p>No songs in the playlist</p>";
        } else {
            foreach ($songs as $song) {
                echo "<p>" . htmlspecialchars($song) . "</p>";
            }
        }
    }
}

index.php 代码

 <?php
// Start the session
session_start();

require_once __DIR__ . "/controllers/PlaylistController.php";

$controller = new PlaylistController();
$controller->handleRequest();

// Check if the user is logged in, otherwise redirect to login page
// if (!isset($_SESSION["loggedin"]) || $_SESSION["loggedin"] !== true) {
//     header("location: views/auth/login.php");
//     exit;
// }

?>

<!DOCTYPE html>
<html lang="en">

<head></head>

<body></body>
</html>

Answer 5

以下是 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;
        $this->lastNode == NULL;
        $this->count = 0;
    }
    
    
    //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 6

这是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 7

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

我还尝试编写一个程序来用 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 9

有 SplDoublyLinkedList。这也可以吗？