Implement linked list in php

0 votes
asked Sep 2, 2010 by osgx

How should I implement a linked list in PHP? Is there a implementation built in into 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.

5 Answers

0 votes
answered Sep 2, 2010 by nikic

There is SplDoublyLinkedList. Is this okay, too?

0 votes
answered Sep 18, 2012 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
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();
0 votes
answered Sep 3, 2016 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

/**
 * 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
0 votes
answered Sep 15, 2017 by raluca-constanda

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

<?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-4-5-7-10

-2-4-5-7-10

0 votes
answered Sep 15, 2017 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.

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}
Welcome to Q&A, where you can ask questions and receive answers from other members of the community.
Website Online Counter

...