DEV Community: Matus Stafura

Insertion Sort in PHP

Matus Stafura — Thu, 09 Feb 2023 15:32:57 +0000

About Insertion Sort
Insertion Sort Algorithm
Function
Script
Time Complexity

About Insertion Sort

Insertion sort is a simple sorting that compares each element in the list to the elements that come before it and inserts it into its correct position in the sorted list. This process is repeated until all elements have been inserted into their correct positions and the list is sorted.

In insertion sort, we always start at the second index and compare values to the left (before).

Insertion Sort Algorithm

Explanation:

In insertion sort, we need to check all values, so we use two loops.

Firstly, we start the loop from the index 1.
To track the value of that index, we create a temporary variable temp in case we need to swap it.
To compare to the left, we create a temporary variable j equal to i-1.
Since we do not know how many times we need to loop, we use a while loop.

If the value of temp is less than the value on the left, we swap it and decrement j to check the next value to the left.

We also need to stop once there is nothing to check. We add the condition j >= 0 to ensure that we stay within the bounds of the list.

5, we return the sorted array.

Function

function insertionSort(array $a): array
{
  for ($i = 1; $i < count($a); $i++) {
    $temp = $a[$i];
    $j = $i - 1;
    while ($temp < $a[$j] && $j >= 0) {
      $a[$j + 1] = $a[$j];
      $a[$j] = $temp;
      $j -= 1;
    }
  }
  return $a;
}

// $list = [5, 2, 8, 9, 1];
// insertionSort($list);
// [1, 2, 5, 8, 9]

Script

Try it on replit:

https://replit.com/@stafura/InsertionSort#main.php

Time Complexity

The time complexity of the insertion sort algorithm is O(n^2) in the worst-case scenario, where n is the number of elements in the list.

Despite its quadratic time complexity, insertion sort is a simple sorting algorithm that is well-suited to small lists or lists that are nearly sorted.

More Info:

https://en.wikipedia.org/wiki/Insertion_sort

PHP Array Reduce function

Matus Stafura — Thu, 02 Feb 2023 13:02:13 +0000

About Array Reduce
Simple example
Practical example
Try the code
Use cases

About Array Reduce

array_reduce is an array function that iteratively reduces an array to a single value by applying a callback function to elements in the array.

array_reduce(
  array $array, 
  callable $callback, 
  mixed $initial = null
): mixed

It takes the following parameters:

an array (what do we want to reduce),
callback (the logic),
initial value(for example, an empty array []).

Simple example:

Let's find unique values in array.

1. We have an array of products

// an array
$products = [
  "shirt",
  "shoes",
  "shirt"
];

2. A callback function, which checks if an item is already in an array.

$reducer = function ($all, $item) {
  if (!in_array($item, $all)) {
    array_push($all, $item);
  }
  return $all;
};

The variable $item holds the value of the current iteration of $products.
The variable $all holds the return value of the previous iteration. Its initial value is defined as the last parameter in array_reduce.

3. initial value

Since we return an array in the callback, the type must match the initial array (we define an empty array as the initial value).

$initial = [];

array_reduce()

$products = [
  "shirt",
  "shoes",
  "shirt"
];

$reducer = function ($all, $item) {
  if (!in_array($item, $all)) {
    array_push($all, $item);
  }
  return $all;
};

$initial = [];

array_reduce($products, $reducer, $initial);

// this will return
// [
//   "shirt",
//   "shoes",
// ]

if we pass some initial values

array_reduce($products, $reducer, ["hat"]);

// this will return
// [
//   "hat",
//   "shirt",
//   "shoes",
// ]

also, everything in one place:

array_reduce(
  ["shirt", "shoes", "shirt"],    // an array to reduce
  function ($all, $item) {        // callback
    if (!in_array($item, $all)) {
      array_push($all, $item);
    }
    return $all;
  },
  []                              // initial
);

Obviously, we can use array_unique($products) instead to achieve the same results in this example.

Practical example:

Let's say we have an array of products(key, value structure).

$products = [
  ["name" => "Product 1", "price" => 10],
  ["name" => "Product 1", "price" => 10],
  ["name" => "Product 1", "price" => 10],
  ["name" => "Product 2", "price" => 2],
  ["name" => "Product 3", "price" => 7],
  ["name" => "Product 2", "price" => 2],
];

And we need to create an array where we count the same products ($quantity) and sum their price ($total) like this:

[
  "Product 1" => [
    "total" => ...,
    "quantity" => ...,
  ],
  "Product 2" => [
    "total" => ...,
    "quantity" => ...,
  ],
  ...
]

we can use an array_reduce function:

array_reduce($products, $reducer, []);

where we pass $products and an empty array as initial value. all we need is to write the callback.

then, in the callback:

since $item is a key-value pair (["name" => "Product 1", "price" => 10]) for simplicity, we assign the name and its price to variables.
We check if the item is in the array ($all):

if there is one with the same key, we increase its quantity by 1 and add the price.
if not, we push the item to $all and set its quantity to 1.

$products = [
  ["name" => "Product 1", "price" => 10],
  ["name" => "Product 1", "price" => 10],
  ["name" => "Product 1", "price" => 10],
  ["name" => "Product 2", "price" => 2],
  ["name" => "Product 3", "price" => 7],
  ["name" => "Product 2", "price" => 2],
];

$reducer = function ($all, $item) {
  $name = $item["name"];
  $price = $item["price"];
  if (isset($all[$name])) {
    $all[$name]["quantity"]++;
    $all[$name]["total"] += $price;
  } else {
    $all[$name]["total"] = $price;
    $all[$name]["quantity"] = 1;
  }
  return $all;
};

array_reduce($products, $reducer, []);

// and that will return:
// [
//   "Product 1" => [
//     "total" => 30,
//     "quantity" => 3,
//   ],
//   "Product 2" => [
//     "total" => 4,
//     "quantity" => 2,
//   ],
//   "Product 3" => [
//     "total" => 7,
//     "quantity" => 1,
//   ],
// ]

Try the code:

https://replit.com/@stafura/arrayreduce-in-PHP#main.php

Use cases:

There are many ways you can use the array_reduce function, such as:

summing up all the elements of an array,
flattening a nested array,
grouping elements based on some criterion,
counting the occurrences of items in an array,
filtering an array based on some condition.

more info:
https://www.php.net/manual/en/function.array-reduce.php

Selection Sort in PHP

Matus Stafura — Thu, 26 Jan 2023 12:48:52 +0000

About Selection Sort
Selection Sort Algorithm
Function
Time Complexity

About Selection Sort

Selection sort is an in-place comparison-based sorting algorithm. It works by repeatedly finding the minimum element from the unsorted part of the array and swapping it with the first element of the unsorted part. The process continues until the entire array is sorted. It has a time complexity of O(n^2) making it inefficient for large data sets.

Selection Sort Algorithm

The algorithm involves looping and comparing two values and we keep the track of the index of the minimum value.

Steps in a loop:

We need to track an index of minimum value, so we assign a temporary variable, $min_i, to $i at the beginning of the loop.
In the loop, we compare the values of $min_i and $j.
If the value at index $j is less than the value at $i, we change $min_i with the new index of the lesser value at position $j.

Loop #1

We compare the first value (which is 5) with all of the values, and we find that the value at index 1 is less than 5. Once the loop is over, we swap 5 and 1.


Loop #1

Loop #2

Now, the first index is already sorted, so we continue the loop and compare 5 with the rest of the array. We find that 3 is less than 5, and we swap them at the end.


Loop #2

Loop #3

Values 1 and 3 are sorted, but in this last loop, the $min_i does not change (there are no values that are less than 4), so we do not swap. That is also why we have a condition to skip the swap if $i != $min_i.


Loop #3


Final

Function

function selectionSort(array $a): array
{
  for ($i = 0; $i < count($a) - 1; $i++) {
    $min_i = $i;
    for ($j = $i + 1; $j < count($a); $j++) {
      if ($a[$j] < $a[$min_i]) {
        $min_i = $j;
      }
    }
    if ($i != $min_i) {
      $temp = $a[$i];
      $a[$i] = $a[$min_i];
      $a[$min_i] = $temp;
    }
  }
  return $a;
}

// $a = [5, 1, 4, 3];
// selectionSort($a);
// [1, 3, 4, 5]

You can also find the script here:

https://gist.github.com/matusstafura/09c0af86c749f5e5066f920d44f31ba1

Time Complexity

The time complexity of selection sort is O(n^2) where n is the number of elements in the array.

More info: https://en.wikipedia.org/wiki/Selection_sort

Bubble Sort in PHP

Matus Stafura — Thu, 19 Jan 2023 13:23:02 +0000

About Bubble Sort
Bubble Sort Algorithm
Function
Optimized version
Scripts
Time Complexity

About Bubble Sort

Bubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted. It compares each pair of adjacent items and swaps them to be in the correct order.

Also known for its inefficiency and time complexity of O(n^2).

Bubble sort algorithm

Let's sort an array of numbers(integers) [5, 1, 4, 3].

To make the algorithm easier to explain, let's visualize the array where the height represents the value.

The algorithm involves looping and comparing two values. For example, in a 4-value array, we would loop a maximum of 3 times, as we compare j and j+1.

In our example (the script is below):

$i = value of outer loop
$j = value of inner loop
$a[$j] = value of an array at the position of $j
$a[$j+1] = value of an array at the position of $j+1

Comparison #1

We start at the beginning of the array and compare the first two elements, 5 and 1(before). Since 5 is greater than 1, we swap them(after).

Comparison #2

We increment the value of j in the loop and compare the next two elements, 5 and 4(before). Since 5 is greater than 4, we swap them(after).

Comparison #3

We increment the value of j in the loop and compare the next two elements, 5 and 3(before). Since 5 is greater than 3, we swap them(after).

NOTICE: It is important to note that the highest number, 5, is now in its correct sorted position and does not need to be compared again. In the next loop, we will only need to loop 2 times, as opposed to 3 times (the total number of elements in the array minus 1).

Comparison #4

Once our first loop is complete, we start again from the beginning of the array. We compare the first two elements, 1 and 4(before). Since 1 is not greater than 4, we continue in the loop without swapping them(after).

Comparison #5

We increment the value of j in the loop and compare the next two elements, 4 and 3(before). Since 4 is greater than 3, we swap them. We skip the number 5, as it is already in its sorted position(after).

Number 5 is already sorted so we skip it.

Comparison #6

In our last loop, we compare the first two elements, 1 and 3(before). Since 1 is not greater than 3, we continue in the loop without swapping them(after).

The final array looks like this(after): [1, 3, 4, 5].

Function

The loops

To compare two values in an array, we need a loop within a loop.

Instead of looping in the traditional way:

for ($i = 0; $i < count($a) - 1; $i++) { // outer loop
  for ($j = $i + 1; $j < count($a); $j++) { // inner loop
    // ...
  }
}

we do it in the opposite direction, where we decrement in the outer loop, so we can skip the last sorted number.

for ($i = count($a) - 1; $i > 0; $i--) { // outer loop
  for ($j = 0; $j < $i; $j++) { // inner loop
    // ...
  }
}

Swap

In the loop we check the two values and swap if $a[$j] > $a[$j + 1].

if ($a[$j] > $a[$j + 1]) { 
  $temp = $a[$j];
  $a[$j] = $a[$j+1];
  $a[$j+1] = $temp;
}

Bubble Sort Algorithm

function bubbleSort(array $a): array
{
  for ($i = count($a) - 1; $i > 0; $i--) {
    for ($j = 0; $j < $i; $j++) {
      if ($a[$j] > $a[$j + 1]) { 
        $temp = $a[$j];
        $a[$j] = $a[$j+1];
        $a[$j+1] = $temp;
      }
    }
  }
  return $a;
}

// $bs = [5, 2, 8, 9, 1];
// bubbleSort($bs);
// [1, 2, 5, 8, 9]

Optimized version

But what if we have a situation where an array(on the left) is almost sorted and after an outer loop is finished we have all items sorted.

If we used the script above, we would have 15 comparisons for an array [6, 1, 2, 3, 4, 5]. However, it is clear that after the first loop, all numbers are sorted, meaning we do not have to loop through [1, 2, 3, 4, 5, 6] several more times.

We can optimize this by tracking whether any swaps were made during the outer loop. If there were no swaps, we can break the loop and return the array, as it is now sorted.

So we loop once more and if there is no swap, we can break the loop and return the array, because all is sorted.

Explanation:

Let's define a variable $swap within the outer loop.
We set $swap to true if there is a swap in the condition.
If there is no swap in the outer loop, we don't need to check the rest, so we break the loop and return the sorted array.

The following optimization has only 9 comparisons for an array [6, 1, 2, 3, 4, 5]. It skips the loops where $i = 3, 2, and 1.

function bubbleSortOptimized(array $a): array
{
  for ($i = count($a) - 1; $i > 0; $i--) {
    $swap = false;
    for ($j = 0; $j < $i; $j++) {
      if ($a[$j] > $a[$j + 1]) { 
        $temp = $a[$j];
        $a[$j] = $a[$j+1];
        $a[$j+1] = $temp;
        $swap = true;
      }
    }
    if (!$swap) break;
  }
  return $a;
}

// $bs = [6, 1, 2, 3, 4, 5];
// bubbleSortOptimized($bs);
// [1, 2, 3, 4, 5, 6]

Scripts

Both scripts can be found here: https://gist.github.com/matusstafura/7b049a323624a99a9f0120492888621e

Time Complexity

The time complexity of bubble sort is O(n^2) in the worst and average cases, and O(n) in the best case (when the input is already sorted).

Introduction to Stacks & Queues in PHP

Matus Stafura — Thu, 12 Jan 2023 12:45:30 +0000

1. Stack
- Node in Stack
- Constructor in Stack
- Push
- Pop
- Stack in Arrays
- Time Complexity in Stack
2. Queue
- Node in Queue
- Constructor in Queue
- Enqueue
- Dequeue
- Queues in Arrays
- Time Complexity in Queue

Stack

A stack is a type of data structure in which items are added and removed in a last-in, first-out (LIFO) order. Inserting an element into a stack is referred to as a "push" operation, and removing an element is called a "pop" operation.

Simple example: Image you open your browser and visit youtube.com and then google.com and finally gmail.com.

Your current browsing history looks like this (where 'gmail.com' is your currently open website):
youtube.com->google.com->gmail.com

An example of using a stack in practice is when clicking the "back" button in a web browser, which allows you to return to the previous webpage google.com after navigating away from it, with the current webpage gmail.com being removed from the top of the stack.

youtube.com->google.com

If you click back again you are back at the start.

youtube.com

Node in Stack

A node is a basic unit that stores a piece of data and a reference to the next and previous node in the list. Similar to singly linked list.



class Node
{
    public $value;
    public $next;

    public function __construct($value)
    {
        $this->value = $value;
        $this->next = null;
    }
}

This Node class has two fields:
1, data, which stores a value of the element,
2, next, which is a reference to the next node in the list

Constructor in Stack

Let's create a class that represents a stack data structure.

This class has two instance variables:

$top: a reference to the first node in the list,
$height: an integer that counts the number of nodes in the stack(it is 1 because we create a new node in the constructor).



class Stack
{
    public $top;
    public $height;

    public function __construct(public $value)
    {
        $newNode = new Node($value);
        $this->top = $newNode;
        $this->height = 1;
    }
}

Before we move to main operations, let's create a helper method to print all nodes in the stack.

EXPLANATION:

In the method printStack() we define a local variable $temp and assigns it the value of $this->top, which is a reference to the first node in the list.

It then enters a while loop that continues until $temp is not null, meaning there is no more next node.

After echoing the value, the function assigns $temp the value of $temp->next, which moves $temp to the next node in the list, to continue the loop.



public function printStack()
{
    $temp = $this->top;
    while ($temp != null) {
        echo $temp->value."\n";
        $temp = $temp->next;
    }
}

Push

When we "push" a node onto a stack, we are adding a new element to the top of the stack. A stack follows the LIFO (Last In First Out) principle, which means that the last element added to the stack will be the first one to be removed. So when you push a new node into a stack, this new node will be the new top node of the stack.

From left to right in the image, we are adding values. First, 7, then 1, and finally 6. Notice that the reference to the top is changing with the newly added value.

EXPLANATION:

We create a new node.
If the stack is empty, the new node is assigned as the first node and the top reference is pointing to it.
If the stack is not empty, the new node is connected to the current top node using the next reference.
The top reference is updated to the new node.
finally, we increment the count (height) of the stack.

From top to bottom, we are visiting websites that are "stacked" on top of each other.



public function push($value)
{
    $newNode = new Node($value);
    if ($this->height == 0) {
        $this->top = $newNode;
    } else {
        $newNode->next = $this->top;
        $this->top = $newNode;
    }
    $this->height++;
}

// $s = new Stack('youtube.com'); 
// $s->push('google.com');
// $s->push('gmail.com');
// $s->printStack();
// 
// gmail.com
// google.com
// youtube.com

Pop

"Pop" is an operation on a stack that removes the element at the top of the stack and returns it. This operation also updates the top reference of the stack to the next element and decrements the count (height) of the stack.

Remember: For something to be a stack you just have to add and remove from the same end.

From left to right in the image, we are removing values. First, 6, then 1, and finally 7. Notice that the reference to the top is changing with the newly added value.

EXPLANATION:

If the stack is empty, we return null.
Else, we assign a temporary variable to the current top of the stack.
We change the top reference to the next element in the stack.
Once the top is changed, we can reset the previous top (stored in the temporary variable) to null.
Finally, we decrease the count (height) of the stack.

From top to bottom, when we click the "back" button, we visit previous websites that are "stacked" on top of each other.



public function pop()
{
    if ($this->height == 0) {
        return null;
    }
    $temp = $this->top;
    $this->top = $this->top->next;
    $temp->next = null;
    $this->height--;
    return $temp;
}

// $s = new Stack('youtube.com'); 
// $s->push('google.com');
// $s->push('gmail.com');
// $s->pop(); // removes top
// $s->printStack();
// 
// google.com
// youtube.com

Stack in Arrays

In PHP, built-in functions like array_push and array_pop can be used to implement a stack using an array data structure.



$stack = [];
array_push($stack, 'youtube.com');
array_push($stack, 'google.com');
array_push($stack, 'gmail.com');
array_pop($stack);

// $stack = [
//   "youtube.com",
//   "google.com",
// ]

The time complexity of array push and pop operations in PHP, when implemented using the array_push and array_pop functions, is O(1) on average.

NOTICE: You can achieve the stack principle also when you prepend and pop first element in array, when implemented using array_unshift and array_shift functions, but is O(n) in the worst case.

Time Complexity in Stack

Push: O(1) - This operation takes constant time, as it only involves adding an element to the top of the stack.
Pop: O(1) - This operation also takes constant time, as it only involves removing the top element from the stack.

NOTE: These complexities are for basic implementations of stacks and queues using arrays or linked lists.

Queue

A Queue is a linear data structure, in which the first element added is the first one to be removed. This order is known as First-In-First-Out (FIFO).

A common example of a queue is a line of people waiting for an order, where the person who arrived first will be served first. The main difference between a queue and a stack is in how elements are removed. In a stack, the most recently added element is removed first, while in a queue, the least recently added element is removed first.

FULL SCRIPT:
https://gist.github.com/matusstafura/4bd1beeba61f1995b3fcd18a77bf87c6

Node in Queue

We use the same definition as in stack.



class Node
{
    public $value;
    public $next;

    public function __construct($value)
    {
        $this->value = $value;
        $this->next = null;
    }
}

Constructor in Queue

Let's create a class that represents a queue data structure.

This LinkedList class has three instance variables:

$first: a reference to the first node in the list,
$last: a reference to the last node in the list,
$length: an integer that counts the number of nodes in the list.



class Queue
{
    public $first;
    public $last;
    public $length;

    public function __construct(public $value)
    {
        $newNode = new Node($value);
        $this->first = $newNode;
        $this->last = $newNode;
        $this->length = 1;
    }
}

For printing we use the same logic of echoing values as in the stack.



public function printQueue()
{
    $temp = $this->first;
    while ($temp != null) {
        echo $temp->value."\n";
        $temp = $temp->next;
    }
}

Enqueue

To enqueue means to add new node to a queue(also known as push, add or insert operation).

From top to bottom, we are adding values to the queue.

EXPLANATION:

We create a new node.
If the queue is empty, the new node is assigned as the first and last node.
If the queue is not empty, the next reference of the last node is connected to the new node.
The last reference is updated to the new node.
We increase the length of a queue.



public function enqueue($value)
{
    $newNode = new Node($value);
    if ($this->length == 0) {
        $this->first = $newNode;
        $this->last = $newNode;
    } else {
        $this->last->next = $newNode;
        $this->last = $newNode;
    }
    $this->length++;
}

// $q = new Queue("first customer");
// $q->enqueue("second customer");
// $q->enqueue("third customer");
// 
// $q->printQueue();
// first customer
// second customer
// third customer

Dequeue

To "dequeue" (also known as pop, remove or delete) refers to the operation of removing the element at the front of the queue.

From top to bottom, we are removing values to the queue

The queue follows the First-In-First-Out (FIFO) ordering principle so we need to remove first one.

EXPLANATION:

We return null if the queue is empty.
If the queue has only one node, we reset its first and last references to null.
Otherwise, we assign the first reference to the next node.
We unlink the previous first node by resetting it to null.
Finally, we decrease the length of the queue.



public function dequeue()
{
    if ($this->length == 0) {
        return null;
    }
    $temp = $this->first;
    if ($this->length == 1) {
        $this->first = null;
        $this->last = null;
    } else {
        $this->first = $this->first->next;
        $temp->next = null;
    }
    $this->length--;
    return $temp;
}

// $q = new Queue("first customer");
// $q->enqueue("second customer");
// $q->enqueue("third customer");
// $q->dequeue();
// 
// $q->printQueue();
// second customer
// third customer

Queues in Arrays



$stack = [];
array_push($stack, 'youtube.com');
array_push($stack, 'google.com');
array_push($stack, 'gmail.com');
array_shift($queue);

// $stack = [
//   "google.com",
//   "gmail.com",
// ]

The time complexity of array_push function in this example is O(1) and for the array_shift function in PHP is O(n), where n is the size of the input array.

Time Complexity in Queue

In our example for linked list:

Enqueue: O(1) - This operation takes constant time, as it only involves adding an element to the back of the queue.
Dequeue: O(1) - This operation takes constant time, as it only involves removing the front element from the queue.

FULL SCRIPT:
https://gist.github.com/matusstafura/e70b13f3cbf38a3efc00b3dcb561bb59

Introduction to Doubly Linked List and Basic Operations in PHP

Matus Stafura — Thu, 05 Jan 2023 07:37:11 +0000

Doubly linked list is similar to singly linked list where
a singly linked list has a single link to the next element. A doubly linked list has two links: one to the next element and one to the previous element.

You can read more about singly linked list in the previous article:
https://dev.to/matusstafura/introduction-to-singly-linked-list-and-basic-operations-in-php-1d71

About Node
Doubly Linked List
Constructor
Print all nodes
1. Append
2. Get
3. Set
4. Prepend
5. Insert
6. Pop First
7. Pop Last
8. Remove
Time Complexity

About a Node

In a doubly linked list, a node is a basic unit that stores a piece of data and a reference to the next and previous node in the list.

Here is an example of a node class in doubly linked list in PHP:

class Node
{
    public $value;
    public $next;
    public $prev;

    public function __construct($value)
    {
        $this->value = $value;
        $this->prev = null;
        $this->next = null;
    }
}

This Node class has three fields:
1, data, which stores a value of the element,
2, next, which is a reference to the next node in the list
3, prev, which is a reference to the previous node in the list

Here is an example of how to create a node and link it to another node:

$nodeFirst = new Node(7);
$nodeSecond = new Node(3);

// connect $nodeFirst to nodeSecond with `next`
$nodeFirst->next = $nodeSecond;
// connect $nodeFirst to nodeSecond with `prev` (1)
$nodeSecond->prev = $nodeFirst;
// null<-7<=>3->null

// now you can receive value from second node
$nodeFirst->next->value; // 3
// and get previous value like this
$nodeSecond->prev->value; // 7

NOTICE: This is very similar to singly linked list, we only add reference prev (1) to make it doubly linked list.

This code creates two nodes with data values 7 and 3, and links them together by setting the next field of nodeFirst to nodeSecond and prev of nodeSecond to nodeFirst.

Doubly Linked List

Constructor

Let's create a class that represents a doubly linked list data structure.

This LinkedList class has three instance variables:

$head: a reference to the first node in the list,
$tail: a reference to the last node in the list,
$length: an integer that counts the number of nodes in the list.

NOTICE: If there is only one Node in the list, head and tail points to the same Node.

class DoublyLinkedList
{
    public $head;
    public $tail;
    public $length;

    public function __construct(public $value)
    {
        $newNode = new Node($value);
        $this->head = $newNode;
        $this->tail = $newNode;
        $this->length = 1;
    }
}

NOTE #1: We don't have to initialize a new node in the constructor, but it's convenient to do for this explanation.
NOTE #2: In this article I use integers as data type as a node value.

Print all nodes

Before we move to basic operations, let's create a helper method to print all nodes in the doubly linked list.

EXPLANATION:

In the method printAll() we define a local variable $temp and assigns it the value of $this->head, which is a reference to the first node in the list.

It then enters a while loop that continues until $temp is not null, meaning there is no more next node.

After echoing the value, the function assigns $temp the value of $temp->next, which moves $temp to the next node in the list, to continue the loop.

    // add to DoublyLinkedList class
    public function printAll()
    {
        $temp = $this->head;
        while ($temp != null) {
            echo $temp->value;
            $temp = $temp->next;
        }
        echo PHP_EOL;
    }

1. Append

To append a node means to add a new node at the end of a doubly linked list.

On the left side, we have an example of a doubly linked list with a single node. On the right is the node we want to append. The resulting linked list would look like the one shown at the bottom of the image.

EXPLANATION:

we create a new node with a value.
if the linked list is empty, we assign the head and tail to the new node because it is the only node in the list.
otherwise, we link the new node to the tail with the prev attribute.
we link the tail node to the new node with the next attribute.
we change the tail reference to the new node.
we increase the count (length) of the doubly linked list.

// add to DoublyLinkedList class
    public function append($value)
    {
        $newNode = new Node($value);

        if ($this->length == 0) {
            $this->head = $newNode;
            $this->tail = $newNode;
        } else {
            $newNode->prev = $this->tail;
            $this->tail->next = $newNode;
            $this->tail = $newNode;
        }

        $this->length++;
    }

$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$dll->printAll();
// 2 7 3 9

2. Get

To get a node means to retrieve a node at a certain index in the doubly linked list. The method returns a node object, not just the value of the node.

EXPLANATION:

first, we make sure that the index is within the bounds of the doubly linked list; it should be greater than zero and less than the count(length) of the doubly linked list.
we assign the head of the list to a temporary variable temp so that we can track our position as we traverse the list.
then we loop through the list until we reach the desired index.
the method returns the node at the specified index.

// add to DoublyLinkedList class
    public function getNode($index)
    {
        if ($index < 0 || $index >= $this->length) {
            return null;
        }

        $temp = $this->head;
        for ($i = 0; $i < $index; $i++) {
            $temp = $temp->next;
        }

        return $temp;
    }
$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$node = $dll->getNode(1);
echo $node->value; 
// 7

The script looks like one for a singly linked list and works fine. But we can make it even better because we track the prev node as well.

Why?

Let's say we have a million nodes in the list and we want to get the 999,998th one (the last but one, because the index starts at 0). Instead of looping through almost the entire list, we can traverse from the tail and get it way faster.

There are many ways we can optimize this. This is one approach where we check if the index is in the first half or the second half of the list.

If it is in the first half (from the beginning), we traverse the way we did in the previous example. If it is in the second half, we traverse from the tail. Instead of using the next reference, we use prev.

Like this:

// add to DoublyLinkedList class
    public function getNodeOptimized($index)
    {
        if ($index < 0 || $index >= $this->length) {
            return null;
        }

        if ($index < $this->length / 2) {
            $temp = $this->head;
            for ($i = 0; $i < $index; $i++) {
                $temp = $temp->next;
            }
        } else {
            $temp = $this->tail;
            for ($i = $this->length - 1; $i > $index; $i--) {
                $temp = $temp->prev;
            }
        }

        return $temp;
    }
$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$dll->getNodeOptimized(3)->value; // one loop from tail instead of three loops from head
$dll->printAll();
// 9

3. Set

To set a node is to replace a value of an existing node at certain index with a new value.

EXPLANATION:

we use the existing method getNode() to find the node at the specified index, or return null if the index is out of bound.
we assign a new value to the node that was retrieved.

// add to DoublyLinkedList class
    public function setNode($index, $value)
    {
        $temp = $this->getNode($index);
        if ($temp) {
            $temp->value = $value;
        }
    }
$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$dll->setNode(1,54); // replaces value at index 1 with value 54
$dll->printAll();
// 2 54 3 9

4. Prepend

To prepend a node means to add a new node at the beginning of a linked list.

On the left is a node we want to prepend and on the left is an existing doubly linked list. The resulting linked list would look like the one shown at the bottom of the image.

EXPLANATION:

we create a node.
if there are no nodes in the list, we assign the head and tail to the new node.
otherwise, we link the new node to the head first.
we link the head with the prev attribute to the new node.
we change the head reference to the new node.
we increment the count (length) of the doubly linked list.

// add to DoublyLinkedList class
    public function prepend($value)
    {
        $newNode = new Node($value);
        if ($this->length == 0) {
            $this->head = $newNode;
            $this->tail = $newNode;
        } else {
            $newNode->next = $this->head;
            $this->head->prev = $newNode;
            $this->head = $newNode;
        }

        $this->length++;
    }
$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$dll->prepend(15); // adds a node with value 15 at the beginning
$dll->printAll();
// 15 2 7 3 9

5. Insert

To insert a node in a doubly linked list means to add a new node to the list at a specific position, shifting any subsequent nodes to the right to make room for the new node. For example, if we have a linked list with three nodes(2, 7, 3) and we want to insert a new node (X) between 7 and 3, the resulting linked list would look like (2, 7, X, 3).

EXPLANATION:

we check if the index is within the bounds of the list.
if the index is 0, we do not need to traverse the list and can use the existing prepend($value) method to insert the new node at the beginning of the list. If the index is the last position in the list (where the index is equal to the length of the list), we can use the append($value) method to insert the new node at the end of the list.
otherwise, we create a new node with the given value.
we need to find the node at the index immediately before the position where we want to insert the new node. We assign this node to a temporary variable called 'before'.
we also need to track the node after the index where we want to insert the new node. We assign this node to a temporary variable called 'after'.
we link the new node with the prev attribute to the 'before' node and the next attribute to the 'after' node.
we link the before node to the new one (using the next attribute) and we link the after node to the new one (using the prev attribute).
finally, we increment the count (length) of the linked list.

// add to DoublyLinkedList class
    public function insert($index, $value)
    {
        if ($index < 0 || $index > $this->length) {
            return null;
        }

        if ($index == 0) {
            $this->prepend($value);
            return;
        }

        if ($index == $this->length) {
            $this->append($value);
            return;
        }

        $newNode = new Node($value);
        $before = $this->getNode($index - 1);
        $after = $before->next;

        $newNode->prev = $before;
        $newNode->next = $after;
        $before->next = $newNode;
        $after->prev = $newNode;

        $this->length++;
    }

$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$dll->insert(2, 77); // inserts a node with value 77 at index 2
$dll->printAll();
// 2 7 77 3 9

6. Pop First

To pop first means to remove the node at the beginning of the linked list.

EXPLANATION:

we check if the linked list is not empty.
if there is only one node in the list, we just reset the head and tail to null.
otherwise, we create a temporary variable called $temp and assign it the head.
we then assign the head to the next node.
we reset the prev attribute of the head to null.
and unlink $temp by changing temp->next to null.
we decrease the count (length) of the linked list.

// add to DoublyLinkedList class
    public function popFirst()
    {
        if ($this->length == 0) {
            return null;
        }

        $temp = $this->head;
        if ($this->length == 1) {
            $this->head = null;
            $this->tail = null;
        } else {
            $this->head = $this->head->next;
            $this->head->prev = null;
            $temp->next = null;
        }

        $this->length--;
        return $temp;
    }

$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$dll->popFirst(); // removes first node
$dll->printAll();
// 7 3 9

7. Pop Last

To pop last node is to remove the last node in the linked list.

It is faster and easier to remove the last node in a doubly linked list than it is in a singly linked list. We do not need to traverse the entire list to get to the end; we use the existence of the tail and the prev reference.

EXPLANATION:

we check if the linked list is not empty.
if there is only one node in the linked list, we reset the head and tail to null.
we assign the tail to the previous node.
we unlink the last node next and prev to null.
we decrease the count (length) of the linked list.

// add to DoublyLinkedList class
    public function popLast()
    {
        if ($this->length == 0) {
            return null;
        }
        $temp = $this->tail;
        if ($this->length == 1) {
            $this->head = null;
            $this->tail = null;
        } else {
            $this->tail = $this->tail->prev;
            $this->tail->next = null;
            $temp->prev = null;
        }

        $this->length--;
    }

$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$dll->popLast(); // removes last node
$dll->printAll();
// 2 7 3

8. Remove

To remove a node from a linked list means to remove it from the list at a certain index and update the next pointers of the surrounding nodes to maintain the integrity of the list.

It is the opposite of the insertion.

EXPLANATION:

we check if the index is within the bounds of the linked list.
if the index is 0, we can use the popFirst() method to remove the node at the beginning of the list. If the index is the last position in the list (where the index is equal to the length of the list), we can use the popLast() method to remove the node at the end of the list.
else, we find the node with existing method getNode().
we link the node before and after the node we want to remove.
we unlink temp(node to remove) from the list by assigning null to prev and next.
we decrease the count (length) of the linked list.

// add to DoublyLinkedList class
    public function remove($index)
    {
        if ($index < 0 || $index >= $this->length) {
            return null;
        }

        if ($index == 0) {
            return $this->popFirst();
        }

        if ($index == $this->length - 1) {
            return $this->popLast();
        }

        $temp = $this->getNode($index);

        $temp->next->prev = $temp->prev;
        $temp->prev->next = $temp->next;
        $temp->next = null;
        $temp->prev = null;

        $this->length--;
        return $temp;
    }

$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$dll->remove(2); // removes node at index 2
$dll->printAll();
// 2 7 9

You can find the full script here: https://gist.github.com/matusstafura/c53bf80421d0b312a9b42193f68ac5ea

Time Complexity

The time complexity for common operations on a doubly linked list is as follows:

Insertion at the beginning: O(1)
Insertion at the end: O(1)
Insertion after a given node: O(1)
Deletion at the beginning: O(1)
Deletion at the end: O(1)
Deletion of a given node: O(1)
Search: O(n)
Access: O(n)

Note: these time complexities applies for the doubly linked list with a head and a tail pointer, which allow for efficient insertion and deletion at the beginning and end of the list. Without these pointers, the time complexity for insertion and deletion at the beginning and end of the list would be O(n).

Introduction to Singly Linked List and Basic Operations in PHP

Matus Stafura — Fri, 30 Dec 2022 12:31:07 +0000

About Node
Singly Linked List
Constructor
Print all nodes
1. Append
2. Get
3. Set
4. Prepend
5. Insert
6. Pop First
7. Pop Last
8. Remove
Time Complexity

You can find Introduction do doubly linked list here.

A singly linked list is a linear data structure that consists of a sequence of nodes, where each node stores a reference to an element and a link to the next node in the sequence.

Every non-empty linked list has a head(first node in list) and tail(last node in linked list).

A singly linked list may look like this:

About a Node

In a singly linked list, a node is a basic unit that stores a piece of data and a reference to the next node in the list.

Here is an example of a node class in PHP:

class Node
{
  public $value;
  public $next;

  public function __construct($value)
  {
    $this->value = $value;
    $this->next = null;
  }
}

This Node class has two fields:
1, data, which stores the element, and
2, next, which is a reference to the next node in the list.

The next field is initialized to null to indicate that the node is the last node in the list.

Here is an example of how to create a node and link it to another node:

$nodeFirst = new Node(10);
$nodeNext = new Node(20);

// connect $nodeNext to nodeFirst
$nodeFirst->next = $nodeNext; // 10->20->null

// now you can receive value from second node
$nodeFirst->next->value; // 20

This code creates two nodes with data values 10 and 20, and links them together by setting the next field of nodeFirst to nodeNext. The resulting singly linked list would look like this:

$nodeFirst->$nodeNext->null

Singly Linked List

Constructor

Let's create a class that represents a linked list data structure.

This LinkedList class has three instance variables:

$head: a reference to the first node in the list,
$tail: a reference to the last node in the list,
$length: an integer that counts the number of nodes in the list.

NOTICE: If there is only one Node in the list, head and tail points to the same Node.

class LinkedList
{
    public $head;
    public $tail;
    public $length;

    public function __construct(public $value)
    {
        $newNode = new Node($value);
        $this->head = $newNode;
        $this->tail = $newNode;
        $this->length = 1;
    }
}

The __construct takes an integer value as a parameter and creates a new node with that value. This new node is then set as both the head and tail of the list, and the length is set to 1.

NOTE: We don't have to initalize a new node in the constructor, but it's convenient to do for this explanation.
NOTE #2: In this article I use integers as data type as a node value.

Print all nodes

Before we move to basic operations, let's create a helper method to print all nodes in the singly linked list.

EXPLANATION:

In the method printAll() we define a local variable $temp and assigns it the value of $this->head, which is a reference to the first node in the list.

It then enters a while loop that continues until $temp is not null, meaning there is no more next node.

After echoing the value, the function assigns $temp the value of $temp->next, which moves $temp to the next node in the list, to continue the loop.

public function printAll()
{
    $temp = $this->head;
    while ($temp != null) {
        echo $temp->value . '->';
        $temp = $temp->next;
    }
}

Basic operations:

1. Append

To append a node means to add a new node at the end of a linked list.

On the left is a linked list (only one node is shown in the image) and on the right is the node we want to append. The resulting linked list would look like the one shown at the bottom of the image.

EXPLANATION:

we create a new node with a value.
if the linked list is empty, we assign the head and tail to the new node because it is the only node in the list.
otherwise, we link the last node in the linked list to the new one with $this->tail->next = $newNode and change the tail to the new one with $this->tail = $newNode.
we increment the count (length) of the linked list.

// add to the linked list Class
public function append($value)
{
    $newNode = new Node($value);
    if ($this->length == 0) {
        $this->head = $newNode;
        $this->tail = $newNode;
    } else {
        $this->tail->next = $newNode;
        $this->tail = $newNode;
    }
    $this->length++;
}

$l = new LinkedList(4);
$l->append(3);
$l->append(5);

$l->printAll();
// 4->3->5->

2. Get

To get a node means to retrieve a node at a certain index in the linked list, starting from 0. The method returns a node object, not just the value of the node.

EXPLANATION:

first, we ensure that the index is within the bounds of the linked list; it should be greater than zero and less than the count of the singly linked list.
we assign the head of the linked list to a variable $temp so that we can track our position as we traverse the list.
then we loop through the list until we reach the desired index.
the method returns the node at the specified index.

public function getNode($index)
{
    if ($index < 0 || $index >= $this->length) {
        return null;
    }
    $temp = $this->head;
    for ($i = 0; $i < $index; $i++) {
        $temp = $temp->next;
    }
    return $temp;
}

$l = new LinkedList(4);
$l->append(3);
$l->append(5);

$node = $l->getNode(2);
echo $node->value;
// 5

3. Set

To set a node is to replace a value of an existing node at certain index with a new value.

EXPLANATION:

we use the existing getNode() method to find the node at the specified index, or return null if the index is out of bounds.
we assign a new value to the node that was retrieved.

public function setNode($index, $value)
{
    $temp = $this->getNode($index);
    if ($temp) {
        $temp->value = $value;
    }
}

$l = new LinkedList(4);
$l->append(3);
$l->append(5);
$l->setNode(2,11); // set a value of 11 at index 2 if node exists

$l->printAll();
// 4->3->11->

4. Prepend

To prepend a node means to add a new node at the beginning of a linked list.

On the right is a linked list and on the left is the node we want to prepend. The resulting linked list would look like the one shown at the bottom of the image.

We need to do two things:

1, connect the new node to the head of the existing linked list.
2, change the head to the newly created node.

EXPLANATION:

1, we create a new node with a value.
2, if there are no nodes in the linked list, we assign the head and tail to the new node.
3, otherwise, we link the new node to the head with $newNode->next = $this->head and change the head to the new node with $this->head = $newNode.
4, finally, we increment the count (length) of the linked list.

public function prepend($value)
{
    $newNode = new Node($value);
    if ($this->length == 0) {
        $this->head = $newNode;
        $this->tail = $newNode;
    } else {
        $newNode->next = $this->head;
        $this->head = $newNode;
    }
    $this->length++;
}

$l = new LinkedList(4);
$l->append(3);
$l->append(5);
$l->prepend(48);

$l->printAll();
// 48->4->3->5->

5. Insert

To insert a node in a linked list means to add a new node to the list at a specific position, shifting any subsequent nodes to the right to make room for the new node. For example, if we have a linked list with three nodes (3, 4, 7) and we want to insert a new node (X) between the nodes 4 and 7, the resulting linked list would look like (3, 4, X, 7).

EXPLANATION:

we check if the index is within the bounds of the linked list.
if the index is 0, we do not need to traverse the list and can use the existing prepend($value) method to insert the new node at the beginning of the list. If the index is the last position in the list (where the index is equal to the length of the list), we can use the append($value) method to insert the new node at the end of the list.
otherwise, we create a new node with the given value.
we need to find the node at the index immediately before the position we want to insert the new node. We assign this node to a temporary variable.
we link the new node to the next node in the linked list.
then, we point the previous node (the one stored in the temporary variable) to the new node.
finally, we increment the count (length) of the linked list.

NOTE: Steps 5 and 6 have to be in that order. We cannot link temp(previous node) to the new node, because it unlinks the rest of the linked list.

public function insert($index, $value)
{
    if ($index < 0 || $index >= $this->length) {
        return null;
    }
    if ($index == 0) {
        $this->prepend($value);
        return;
    } elseif ($index == $this->length) {
        $this->append($value);
        return;
    }
    $newNode = new Node($value);
    $temp = $this->getNode($index - 1);
    $newNode->next = $temp->next;
    $temp->next = $newNode;
    $this->length++;
}

$l = new LinkedList(4);
$l->append(3);
$l->append(5);
$l->insert(1,22);

$l->printAll();
// 4->22->3->5->

6. Pop First

To pop first means to remove the node at the beginning of the linked list.

EXPLANATION:

we check if the linked list is not empty.
if there's only one node in the list, we just reset the head and tail to null.
otherwise, we create a temporary variable called $temp and assign it to the head.
we then assign the head to the next node
and unlink $temp by changing temp->next to null.
we decrease the count (length) of the linked list.

public function popFirst()
{
    if ($this->length == 0) {
        return null;
    }
    if ($this->length == 1) {
        $this->head = null;
        $this->tail = null;
    } else {
        $temp = $this->head;
        $this->head = $temp->next;
        $temp->next = null;
    }
    $this->length--;
}

$l = new LinkedList(4);
$l->append(3);
$l->append(5);
$l->popFirst();

$l->printAll();
// 3->5->

7. Pop Last

To pop last node is to remove the last node in the linked list.

EXPLANATION:

we check if the linked list is not empty.
if there is only one node in the linked list, we reset the head and tail to null.
otherwise, we need to traverse the list to the end and find a node before the last one. We can do this by creating two temporary variables called 'temp' and 'prev', where the 'temp' variable is one step ahead.
we loop through the entire linked list just to find the node before the last one.
then, we assign the tail to 'prev'.
we unlink the last node (the new tail's next node).
we decrease the count (length) of the linked list.

public function pop()
{
    if ($this->length == 0) {
        return null;
    }

    if ($this->length == 1) {
        $this->head = null;
        $this->tail = null;
    } else {
        $temp = $this->head;
        $prev = $this->head;
        while ($temp->next) {
            $prev = $temp;
            $temp = $temp->next;
        }
        $this->tail = $prev;
        $this->tail->next = null;
    }
    $this->length--;
}

$l = new LinkedList(4);
$l->append(3);
$l->append(5);
$l->pop();

$l->printAll();
// 4->3->

8. Remove

To remove a node from a linked list means to remove it from the list at a certain index and update the next pointers of the surrounding nodes to maintain the integrity of the list.

It is the opposite of the insertion.

EXPLANATION:

we check if the index is within the bounds of the linked list.
if the index is 0, we can use the popFirst() method to remove the node at the beginning of the list. If the index is the last position in the list (where the index is equal to the length of the list), we can use the pop() method to remove the node at the end of the list.
otherwise, we need to find the node at the index immediately before the position where we want to remove the node. We assign this node to a temporary variable.
we update the next pointer of the previous node to point to the node after the one we want to remove. This effectively removes the node from the linked list.
we decrease the count (length) of the linked list.

public function remove($index)
{
    if ($index < 0 || $index >= $this->length) {
        return null;
    }
    if ($index == 0) {
        $this->popFirst();
        return;
    } elseif ($index == $this->length - 1) {
        $this->pop();
        return;
    }
    $temp = $this->getNode($index - 1);
    $temp->next = $temp->next->next;
    $this->length--;
}
$l = new LinkedList(4);
$l->append(3);
$l->append(5);
$l->remove(1);

$l->printAll();
// 4->5->

You can see the entire script here:
https://gist.github.com/matusstafura/6d7bf89bdde17e83fa39def977ffe7aa

Time Complexity

The time complexity (or "Big O") of basic operations on a singly linked list depends on the operation being performed and the position of the node being accessed.

Time complexity for some common operations:

Accessing a node by index: O(n)
Inserting a node at the beginning or end of the list: O(1)
Inserting a node at a specific index: O(n)
Removing a node from the beginning or end of the list: O(1)
Removing a node from a specific index: O(n)

In general, singly linked lists have a time complexity of O(n) for operations that require traversing the list to find a specific node, since these operations require visiting each node in the list until the desired node is found. On the other hand, operations that do not require traversing the list, such as inserting or removing a node at the beginning or end of the list, have a time complexity of O(1).

It's important to note that these time complexities are worst-case scenarios and the actual time taken by the operation may be faster in some cases. For example, if we have a reference to the node we want to remove, we can remove it in O(1) time without traversing the list. Similarly, if we are inserting a node at a specific index and we already have a reference to the node at that index, the insertion operation will also take O(1) time.

DEV Community: Matus Stafura

Insertion Sort in PHP

Table of Contents

About Insertion Sort

Insertion Sort Algorithm

Function

Script

Time Complexity

More Info:

PHP Array Reduce function

Table of Contents

About Array Reduce

Simple example:

1. We have an array of products

2. A callback function, which checks if an item is already in an array.

3. initial value

array_reduce()

if we pass some initial values

also, everything in one place:

Practical example:

Try the code:

Use cases:

Selection Sort in PHP

Table of Contents

About Selection Sort

Selection Sort Algorithm

Loop #1

Loop #2

Loop #3

Function

Time Complexity

Bubble Sort in PHP

Table of Contents

About Bubble Sort

Bubble sort algorithm

Comparison #1

Comparison #2

Comparison #3

Comparison #4

Comparison #5

Comparison #6

Function

The loops

Swap

Bubble Sort Algorithm

Optimized version

Scripts

Time Complexity

Introduction to Stacks & Queues in PHP

Table of Contents

Stack

Node in Stack

Constructor in Stack

Push

Pop

Stack in Arrays

Time Complexity in Stack

Queue

Node in Queue

Constructor in Queue

Enqueue

Dequeue

Queues in Arrays

Time Complexity in Queue

Introduction to Doubly Linked List and Basic Operations in PHP

Table of Contents

About a Node

Doubly Linked List

Constructor

Print all nodes

1. Append

2. Get

3. Set

4. Prepend

5. Insert

6. Pop First

7. Pop Last

8. Remove

Time Complexity

Introduction to Singly Linked List and Basic Operations in PHP