Linked List in PHP Tutorial

Udemy Generic 728x90

Major disadvantage of using arrays is that arrays are static data structure so can not be resized easily . A single memory block is allocated for array . If memory is available in chunks but not in a single block , defragmentation of memory is required  to get a single block . If we need a data structure that addresses most of the issues of array , definitely it is LINKED LIST.

Linked List is a dynamic data structure. It allocates memory for item when we add it . It uses a special architecture to store items ,known as node. Each node includes two parts data and next. data stores given item and next stores address to next node.The last node has a reference to null.
Reference to linked list is called head. When list is empty head reference to null.

Linked List ADT(Abstract Data Type)

Linked List ADT defines specifications of linked list and operations that can be performed on linked list. Linked List ADT is given below.

  • LinkedList() creates empty linked list.
  • insertAtLast(item) adds given item to the end of linked list.
  • insertAtFirst(item) adds given item to the beginning of linked list.
  • addAtPos(item, pos) adds given item to the specified position in the linked list. If position is greater than linked list size , exception is thrown.
  • removeByIndex(index) removes item at specified position in  the list.
  • contains(item) checks whether given item exists in list or not . If item exists , true is returned otherwise false is returned.
  • get(index) returns item at given index.
  • toArray() converts list into array and returns it.
  • size() returns the number of items in the list. It needs no parameters and returns an integer.
  • isEmpty() tests to see whether the list is empty. It needs no parameters and returns a boolean value.
  • used data type /data structure-  To implement linked list we have used PHP Classes as underlying data structure.

PHP Implementation of Linked List

To implement linked list we have created two classes Node and LinkedList. Node class stores item and address to next node.Node class basically works as data storage. LinkedList class provides implementation of linked list operations. PHP implementation of linked list is given below.

<br />
&lt;?php  </p>
<p> /* This file implement linked list in PHP.<br />
    For this purpose we have created two classes<br />
      1)- Node class - It simulate node of linked list in PHP.<br />
      2)- LinkedList - implements all linked list functions.</p>
<p>  */</p>
<p> class LinkedList{<br />
     //link to first node of linked list<br />
     private $head;</p>
<p>     // link to last node of linked list<br />
     private $lastNode;</p>
<p>     // count of total item in linked list<br />
     private $count;</p>
<p>     function __construct(){</p>
<p>         $this-&gt;head     = NULL;<br />
         $this-&gt;lastNode = NULL;<br />
         $this-&gt;count    = 0;<br />
     }</p>
<p>     public function insertAtLast($item) {<br />
         $node = new Node($item);</p>
<p>         if($this-&gt;head != NULL) {</p>
<p>             $this-&gt;lastNode-&gt;next = $node;<br />
             $this-&gt;lastNode       = &amp;$node;<br />
             $this-&gt;count++;</p>
<p>         }else {<br />
             $this-&gt;insertAtFirst($item);<br />
         }<br />
     }</p>
<p>     public function insertAtFirst($item) {</p>
<p>         $node = new Node($item);<br />
         if($this-&gt;head == NULL){</p>
<p>             $this-&gt;head     = &amp;$node;<br />
             $this-&gt;lastNode = &amp;$node;</p>
<p>         } else {</p>
<p>             $node-&gt;next      = $this-&gt;head;<br />
             $this-&gt;head      = &amp;$node;</p>
<p>         }</p>
<p>         $this-&gt;count++;</p>
<p>     }</p>
<p>     public function insertAtPos($item , $position){</p>
<p>         if($position &lt;= $this-&gt;count){<br />
             if($position == 0){<br />
                 $this-&gt;insertAtFirst($item);<br />
             }else if($position == $this-&gt;count){<br />
                 $this-&gt;insertAtLast($item);<br />
             }else{<br />
                 $this-&gt;insert($item , $position);<br />
             }</p>
<p>         }else {</p>
<p>             throw new Exception(&quot;Index out of bound&quot;);</p>
<p>         }</p>
<p>     }</p>
<p>     public function toArray(){<br />
         $listItem = array();<br />
         $currentNode = $this-&gt;head;<br />
         $i =0;<br />
         while($currentNode !== NULL){<br />
          $listItem[$i] = $currentNode-&gt;getData();<br />
          $currentNode  = $currentNode-&gt;next;<br />
          $i++;<br />
         }<br />
         return $listItem;<br />
     }</p>
<p>     public function removeByIndex($index){</p>
<p>         if($this-&gt;count &gt; $index){<br />
             if($index == 0){</p>
<p>                 $this-&gt;removeFirst();<br />
             }else {</p>
<p>                 $this-&gt;remove($index);<br />
             }<br />
         }else{</p>
<p>             throw new Exception(&quot;Index out of bounds&quot;);<br />
         }</p>
<p>     }</p>
<p>     public function contains($item){<br />
         $status = FALSE;<br />
         $currentNode = $this-&gt;head;<br />
         for($i = 0; $i &lt; $this-&gt;count-1; $i++){<br />
             if($item === $currentNode-&gt;getData()){<br />
                 $status = TRUE;<br />
                 break;<br />
             }<br />
             $currentNode = $currentNode-&gt;next;<br />
         }<br />
         return $status;<br />
     }</p>
<p>     public function get($index){</p>
<p>         if(($this-&gt;size() &gt; $index) &amp;&amp; ($index &gt;= 0)){<br />
             $currentNode = $this-&gt;head;<br />
             for($i = 0;$i &lt;= $index; $i++){<br />
                if($i == $index){<br />
                    $itemData = $currentNode-&gt;getData();<br />
                    return $itemData;<br />
                }<br />
                $currentNode = $currentNode-&gt;next;<br />
             }</p>
<p>         } else {</p>
<p>             throw new Exception(&quot;Index out of bounds&quot;);<br />
         }</p>
<p>     }</p>
<p>     public function size(){</p>
<p>        return $this-&gt;count;</p>
<p>     }</p>
<p>     public function isEmpty(){</p>
<p>        if($this-&gt;head == NULL){<br />
            return TRUE;<br />
        }else{<br />
            return FALSE;<br />
        }<br />
     }</p>
<p>     function removeFirst(){</p>
<p>         $this-&gt;head = $this-&gt;head-&gt;next;<br />
         $this-&gt;count--;<br />
     }</p>
<p>     private function remove($index){</p>
<p>         $currentNode = $this-&gt;head;<br />
         for($i = 0; $i &lt; $index; $i++ ){<br />
             if($i == $index-1){<br />
                 $toBeRemovedReference = $currentNode-&gt;next;<br />
                 $currentNode-&gt;next    = $toBeRemovedReference-&gt;next;</p>
<p>                 if($toBeRemovedReference-&gt;next == NULL){  // If it is last node ,update instance<br />
                                                           //   variable<br />
                      $this-&gt;lastNode    = $currentNode;</p>
<p>                 }<br />
                 $this-&gt;count--;<br />
              }<br />
              $currentNode = $currentNode-&gt;next;<br />
         }</p>
<p>     }</p>
<p>     private function insert($item , $position){</p>
<p>         $currentNode = $this-&gt;head;<br />
         $node        = new Node($item);<br />
         for($i = 1; $i &lt;= $position ; $i++){</p>
<p>            if($position == $i){<br />
                $nextNodeReference = $currentNode-&gt;next;<br />
                $currentNode-&gt;next = $node;<br />
                $node-&gt;next        = $nextNodeReference;<br />
                $this-&gt;count++;<br />
                break;<br />
            }<br />
            $currentNode = $currentNode-&gt;next;</p>
<p>         }<br />
     }</p>
<p> }</p>
<p>class Node{</p>
<p>     // stores added item<br />
     public $data;</p>
<p>     // stores address to next node<br />
     public $next;</p>
<p>     // Node constructor<br />
     function __construct($item = FALSE){</p>
<p>         $this-&gt;data = $item;<br />
         $this-&gt;next = NULL;<br />
     }</p>
<p>     // returns item<br />
     public function getData(){<br />
         return $this-&gt;data;<br />
     }<br />
 }<br />

Complexity analysis of Linked List

  • LinkedList() It takes almost constant time to create a empty linked list so its complexity is O(1).
  • insertAtLast(item) Inserting an item to the end of list do not require traversing so takes constant time.Thus its time complexity is O(1).
  • insertAtFirst(item) Insertion of any item to the beginning of list takes constant time so its time complexity is O(1).
  • addAtPos(item, pos) To insert an item at specific position we have to traverse upto that position and then insertion logic is performed. It reveals that insertion at specific position depends on number of element in list so its time complexity is 0(n).
  • removeByIndex(index) To remove an item at given index we have to traverse node thus its time complexity is O(n).
  • contains(item) To check whether given item exist or not we have to traverse whole list.Thus its time complexity is O(n).
  • get(index) To get data at given index traversing to that index is required so its time complexity is 0(n).
  • toArray() To get data from each node whole list is traversed . This causes its time complexity to be O(n).
  • size() Time complexity of this function is O(1).
  • isEmpty() Time complexity of this function is O(1).

Selection criteria for Linked List

Linked list can shrink or grow at runtime easily so linked list data structure can be used if list is large enough and its size may vary a lot.

Complexity analysis reveals that insertion deletion and accessing function have time complexity O(n) so avoid this data structure if you have to perform these operation over data frequently.

Linked List also uses additional memory to store reference of next node.

Udemy Generic 728x90

Spread the word. Share this post!