Static List / Array List In PHP Tutorial

Udemy Generic 728x90

What is List

List is a collection of item. It defines methods to insert item, to delete a particular item , access an item etc. It differs from other data structure as it allows insertion/deletion/accessing operation at any place in list (item can be inserted at beginning,end or middle.In the same way any item can be deleted ).

Example

Lets say we have to store information of top ten richest person in the world so which data structure should we use? Obviously we should use data structure that allows insertion/deletion/accessing operation at any place so.To meet such scnerio we use LIST.

Types of list

Based on memory allocation scheme list can be categorized in two groups.

  • Static List
  • Dynamic List

Static List

Static list is a type of list in which a single memory block is allocated for all its element. In real world static list is implemented using array.It is also refered in some programming language as arrayList.

Dynamic List

Dynamic list is a type of list in which memory is allocated in chunks.In dynamic list each item has reference to its next item.Based on underlying approach dynamic list can be divided into these parts

  • Singly linked list
  • Doubly linked list
  • circular linked list

Static List ADT(Abstract Data Type)

Static list ADT defines specification and basic operation that static list must support.Static list ADT is given below.

  • ArrayList() creates empty arrayList and returns it .
  • add(item) adds given item to the end of list.
  • addAtPos(item, pos) adds given item at specified position in the list.
  • 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 queue. It needs no parameters and returns an integer.
  • isEmpty() tests to see whether the queue is empty. It needs no parameters and returns a boolean value.
  • used data type /data structure- To implement queue we have used array as underlying data structure.

PHP Implementation of Static List / ArrayList

<br />
&lt;?php</p>
<p> class ArrayList{</p>
<p> private $arrayList = NULL;</p>
<p> function __construct(){<br />
     $this-&gt;arrayList = array();<br />
 }</p>
<p> function add($item) {<br />
     array_push($this-&gt;arrayList,$item);<br />
     return true;<br />
 }</p>
<p>function addAtPos($item,$index) {<br />
     if(($index &lt; $this-&gt;size()) &amp;&amp; ($index &gt;= 0)){<br />
         $this-&gt;shiftItemsUp($index,$this-&gt;size()-1);<br />
         $this-&gt;arrayList[$index] = $item;<br />
     } else {<br />
         throw new Exception(&quot;Index out of bounds&quot;);<br />
     }<br />
 }</p>
<p> function removeByIndex($index) {<br />
     if(array_key_exists($index, $this-&gt;arrayList)){<br />
         $this-&gt;shiftItemsDown($index,$this-&gt;size()-1);<br />
         array_pop($this-&gt;arrayList);<br />
     } else {<br />
         throw new Exception(&quot;Key does not exist&quot;);<br />
     }<br />
 }</p>
<p> function contains($item){<br />
     if(in_array($item, $this-&gt;arrayList, TRUE)){<br />
         return TRUE;<br />
     } else {<br />
         return FALSE;<br />
     }<br />
 }</p>
<p> function get($index){<br />
     if(array_key_exists($index,$this-&gt;arrayList)){<br />
         return $this-&gt;arrayList[$index];<br />
     }else {<br />
         return -1;<br />
     }<br />
 }</p>
<p> function toArray(){<br />
     return $this-&gt;arrayList;<br />
 }</p>
<p> function size(){<br />
     $size = count($this-&gt;arrayList);<br />
     return $size;<br />
 }</p>
<p> function isEmpty(){<br />
     $isEmpty = empty($this-&gt;arrayList);<br />
     return $isEmpty;<br />
 }</p>
<p> function shiftItemsUp($startIndex, $endIndex){<br />
     for($i = $endIndex;$i &gt;= $startIndex; $i--){<br />
         $this-&gt;arrayList[$i+1] = $this-&gt;arrayList[$i];<br />
     }<br />
 }</p>
<p> function shiftItemsDown($startIndex, $endIndex){<br />
     for($i = $startIndex;$i &lt;= $endIndex; $i++){<br />
         $this-&gt;arrayList[$i] = $this-&gt;arrayList[$i+1];<br />
     }<br />
 }</p>
<p>}<br />

Complexity  analysis of Static List operations

  • ArrayList() Time complexity of this function is O(1)
  • add(item) It adds item at top of list so does not require shifting of element . Thus its time complexity is constant and represented as O(1) in Big O notation.
  • addAtPos(item, pos) This function adds given item at specified position so items at given position and higher position are shifted upward. Shifting item is proportional to number of items in list. Thus time complexity of addAtPost is O(n).
  • removeByIndex(index) Removing an item at specified index causes shifting of items downward and it is proportional to number of items in list. Thus its time complexity is O(n).
  • contains(item) To check whether given item exists in list or not linear search has been used.Linear search exhibits time complexity in order of n(total number of items in list) so its time complexity is O(n) .
  • get(index) As we are using array as underlying data structure and cost of accessing an item in array is O(1). Thats why time complexity of get is O(1).
  • toArray() Time complexity of this function is O(1).
  • size() Time complexity of this function is O(1).
  • isEmpty() Time complexity of this function is O(1).

 

Selection criteria for Static List / Array List

Array List is basically used when we have to access data to frequently as accessing operation in array list is cheap. While selecting Array List as data structure we should also keep in mind that in Array List memory is allocated in single block. Let say memory is available in chunks but we need a block so program will crash.

Udemy Generic 728x90

Spread the word. Share this post!

  • http://xesau.eu Xesau

    The time complexity of a Static List contains is not O(n) where n(total number of items in list), but
    O(i), where i(index of the item).