Dynamic Array Data Structure in PHP

When talking about array data structure in general (not in PHP), we know that arrays

  • can hold any data type as value
  • are fixed in size (have fixed capacity)
  • have random access (can get or set items using indexes in constant time O(1))

In PHP, arrays are mighty dynamic by default, but in our previous article we have seen how we can simulate fixed array data structure in PHP.

Since arrays are fixed in size by default, how can we make them dynamic? For example, how can we accomplish adding an item to an array instance which is already full? This is typically done like this:

  1. create a new array which is double in size when comparing to our old array
  2. copy all values from the old array to the new array
  3. take the existing reference which points to the old array and make it point to the new array
  4. insert value to the array

For testing purposes I have implemented a DynamicArray class which is based on FixedArray class. You can find it in GitHub repo: https://github.com/cicnavi/alg-ds-php/blob/master/src/Ds/Arrays/DynamicArray.php

Let’s see how it could work. I have cloned the whole repo in ‘alg-ds-php’ folder on my computer, and used PowerShell to navigate to it. This is a Composer enabled repository, so I first enter the command ‘composer install’ to install any dependencies. This will enable me to use the ‘psys’ REPL for PHP, which is great for testing purposes. It is located in ‘vendor\bin\psysh’

I will create a new DynamicArray instance with initial capacity set to 2. I’ll try to add three items to that array, and then check the available capacity.

By using this concept we get a higher level data structure which uses basic array data structure behind the scenes. In that way we still get constant time when accessing values using index, but have a dynamic behavior when it comes to the array size.

All of this comes out-of-the-box when we use default array data structure in PHP, but as developers we have to be aware of array basic data structure concepts in general, and how we can build higher level abstractions on those basic data structure concepts.

You can run the tests for DynamicArray class by entering the command:

./vendor/bin/phpunit --bootstrap vendor/autoload.php --testdox tests/Ds/Arrays/DynamicArrayTest.php

Note that the original SplFixedArray class (which is used in my code behind the scenes) has a setSize() method (http://php.net/manual/en/splfixedarray.setsize.php) which allows to change the size of an array. I have purposely omitted such option to show how to create a dynamic array manually.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: