CODEWITHSUNDEEP
phplinked-list
osgx
osgx

Reputation: 94245

Implement linked list in php

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.

Upvotes: 28

Views: 64528

Answers (9)

Farhan
Farhan

Reputation: 5

Link list MVC Example - PHP

Model Code:

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

Controller Code:

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

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

Upvotes: 0

Lal
Lal

Reputation: 1628

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;
        $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();

Note that some bugs have been fixed in this post. See comments.

Upvotes: 27

Saddam Khan
Saddam Khan

Reputation: 171

// 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();
}

Upvotes: -2

JalalJaberi
JalalJaberi

Reputation: 2617

Just to clarify, implementing linked list in PHP 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.

Instead, you can implement data structures like linked list for PHP using extensions, that means you are implementing a data structure in C to 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

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

Hope this could help someone choose wisely.

Upvotes: 0

Emmanuel Mahuni
Emmanuel Mahuni

Reputation: 1944

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.

Upvotes: 0

Raluca Constanda
Raluca Constanda

Reputation: 89

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

Upvotes: 2

Harshita
Harshita

Reputation: 21

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}

Upvotes: 0

krishna Prasad
krishna Prasad

Reputation: 3812

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

Upvotes: 7

NikiC
NikiC

Reputation: 101936

There is SplDoublyLinkedList. Is this okay, too?

Upvotes: 31

Related Questions