DSA: Arrays and Linked Lists

In modern programming languages, we’re quite fortunate—many of the intricate details of Data Structures and Algorithms (DSA) are abstracted away for us.

For instance, PHP offers a built-in class for Doubly Linked Lists called SplDoublyLinkedList in its Standard PHP Library (SPL). This class simplifies tasks like adding, removing, and traversing elements without the need to manage nodes and pointers manually.

For more information, click here.

Using such built-in abstractions allows developers to focus on application logic rather than re-implementing common data structures. These native classes are optimised for performance and help avoid errors, like pointer issues or memory management problems.

Over the course of my career, I've rarely had to implement a full-fledged algorithm or custom data structure from scratch. However, understanding the basics has been invaluable for debugging, optimising, and appreciating how the tools we rely on every day actually work.

This article will focus on some foundational concepts: arrays and linked lists These structures form the building blocks of efficient code, and even if you’re not writing them by hand, knowing how they function can be useful.

So, what exactly is a data structure?

At its core, a data structure is a specialised way of organising, managing, and storing data so that it can be used efficiently. Think of it as a container with specific rules about how data can be accessed, inserted, or removed—like a filing system in an office.

It’s worth noting that data structures differ from data types. A data type defines the nature of a piece of data—such as whether it’s an integer, a string, or a floating-point number. A data structure, on the other hand, defines how multiple pieces of data are organised and related to one another, such as an array, stack, or linked list. For example, an array might hold integers (a data type) but defines how those integers are stored and accessed sequentially.

These structures form the building blocks of efficient code, and even if you’re not writing them by hand, knowing how they function can be incredibly useful in your day-to-day work.

Arrays

An array is one of the simplest and most widely used data structures. Arrays allow for efficient access to data using an index, making operations like reading or updating a value at a specific position almost instantaneous.

However, arrays have their limitations. Their fixed size means you need to know the number of elements in advance, and operations like inserting or deleting elements can be costly, as they often require shifting elements. Despite these drawbacks, arrays are a foundational data structure that serves as the building block for more complex structures like matrices, hash tables, and more.

class ArrayExample
{
    public function createArray(): array
    {
        return [1, 2, 3, 4, 5];
    }

    public function getElement(array $array, int $index): ?int
    {
        return $array[$index] ?? null;
    }

    public function insertElement(array &$array, int $index, $value): array
    {
        array_splice($array, $index, 0, [$value]);

        return $array;
    }

    public function deleteElement(array &$array, int $index): array
    {
        if (array_key_exists($index, $array)) {
            unset($array[$index]);
            $array = array_values($array);
        }

        return $array;
    }
}

Lets see it in action.

// Create an array
$arrayObject = new ArrayExample();
$data = $arrayObject->createArray();
print_r($data); // Output: [1, 2, 3, 4, 5]

// Access an element by index
echo $arrayObject->getElement($data, 2); // Output: 3

// Insert an element at a specific position
$data = $arrayObject->insertElement($data, 2, 99);
print_r($data); // Output: [1, 2, 99, 3, 4, 5]

// Delete an element at a specific position
$array = $arrayObject->deleteElement($data, 3);
print_r($array); // Output: [1, 2, 99, 4, 5]

// Attempt to access an element out of bounds
$invalidElement = $arrayObject->getElement($array, 10);
echo $invalidElement; // Output: NULL

Linked Lists

A linked list is a dynamic data structure consisting of nodes, where each node contains a piece of data and a reference (or pointer) to the next node in the sequence. Unlike arrays, they’re more flexible for scenarios where the number of elements is unknown or frequently changing.

Linked lists come in various forms:

• Singly Linked Lists: Each node points to the next node.

class Node
{
    public ?Node $next = null;

    public function __construct(public string $data)
    {

    }
}

class LinkedList
{
    public ?Node $head = null;

    public function insert(string $data): void
    {
        $node = new Node($data);

        if ($this->head === null) {
            $this->head = $node;
            return;
        }

        $current = $this->head;
        while ($current->next !== null) {
            $current = $current->next;
        }

        $current->next = $node;
    }

    public function display(): string
    {
        $display = [];

        $current = $this->head;
        while ($current !== null) {
            $display[] = $current->data;
            $current = $current->next;
        }

        return implode(" -> ", $display);
    }

    public function current(): ?string
    {
        if ($this->head === null) {
            return null;
        }

        $current = $this->head;
        while ($current->next !== null) {
            $current = $current->next;
        }

        return $current->data;
    }

    public function goBack(): ?string
    {
        if (
            $this->head === null ||
            $this->head->next === null
        ) {
            return null;
        }

        $current = $this->head;
        $previous = null;

        while ($current->next !== null) {
            $previous = $current;
            $current = $current->next;
        }

        $previous->next = null;

        return $previous->data;
    }
}

But why use one? Well… an example could be a web browser. These typically allow you to navigate backward and forward through the pages you've visited. The browser maintains a history of your visited pages, often referred to as the back and forward history.

• Dynamic nature: The history can grow as you visit more pages, and it doesn't need a predefined size.

• Efficient operations: A singly linked list is perfect for traversing the history forward and backward. Each page visited is stored as a node in the linked list, where each node points to the next page in the history.

Lets see it in action:

// Create a new browser history list
$history = new LinkedList();

$history->insert('Home');
$history->insert('Contact');
$history->insert('About');
$history->insert('Products');
$history->insert('FAQ');

// Display History
echo $history->display(); 
// Output: 'Home -> Contact -> About -> Products -> FAQ'

// Get current page
echo $history->current(); // 'FAQ'

echo $history->goBack(); // 'History'
echo $history->goBack(); // 'About'
echo $history->goBack(); // 'Contact'
echo $history->goBack(); // 'Home'

• Doubly Linked Lists: Each node has pointers to both the next and previous nodes.

Ok so what if we want to navigate back and forth through a list? We can adjust the Linked List to have previous and next pointers. An example of this could be pagination.

class Node
{
    public ?Node $next = null;
    public ?Node $prev = null;

    public function __construct(public string $data)
    {

    }
}

class LinkedList
{
    public ?Node $head = null;
    public ?Node $current = null;

    public function insert(string $data): void
    {
        $node = new Node($data);

        if ($this->head === null) {
            $this->head = $node;
        }
        
        $this->current = $this->head;
        while ($this->current->next !== null) {
            $this->current = $this->current->next;
        }

        $this->current->next = $node;
    }

    public function display(): string
    {
        $display = [];

        $current = $this->head;
        while ($current !== null) {
            $display[] = $current->data;
            $current = $current->next;
        }

        return implode(" -> ", $display);
    }

    public function current(): ?string
    {
        return $this->current?->data;
    }

    public function back(): ?string
    {
        if ($this->head === null || $this->head === $this->current) {
            return null;
        }

        $current = $this->head;
        $previous = null;

        while ($current !== $this->current) {
            $previous = $current;
            $current = $current->next;
        }

        $this->current = $previous;
        return $this->current?->data;
    }

    public function forward(): ?string
    {
        if ($this->current === null || $this->current->next === null) {
            return null;
        }

        $this->current = $this->current->next;
        return $this->current->data;
    }
}

This code above implements a Doubly Linked List in PHP, a data structure where each node contains pointers to both the next and the previous node. This allows for efficient bidirectional traversal of the list. The LinkedList class has three main properties: $head, $tail, and $current, which track the first node, the last node, and the currently active node, respectively.

A good example of its usage could be a pagination object. Lets see it in action:

// Create pagination
$pages = new LinkedList();
$pages->insert('Page 1');
$pages->insert('Page 2');
$pages->insert('Page 3');

// Move to Page 2
$pages->forward();
echo $pages->current(); // 'Page 2'

// Move to Page 3
$pages->forward();
echo $pages->current(); // 'Page 3'

// Move to Page 2
$pages->back();
echo $pages->current(); // 'Page 2'

// Move to Page 1
$pages->back();
echo $pages->current(); // 'Page 1'

• Circular Linked Lists: Similar to a Doubly Linked List but the last node points back to the first node, and vice versa - forming a loop.

class LinkedList
{
    public ?Node $head = null;
    public ?Node $tail = null;
    public ?Node $current = null;

    public function insert(string $data): void
    {
        $node = new Node($data);

        if ($this->head === null) {
            $this->head = $node;
            $this->tail = $node;
            $this->current = $node;
            $node->next = $node;
            $node->prev = $node;
            return;
        }

        $node->prev = $this->tail;
        $node->next = $this->head;
        $this->tail->next = $node;
        $this->head->prev = $node;
        $this->tail = $node;
    }

    public function display(): ?string
    {
        $display = [];

        if ($this->head === null) {
            return null;
        }

        $current = $this->head;
        do {
            $display[] = $current->data;
            $current = $current->next;
        } while ($current !== $this->head);

        return implode(" <-> ", $display);
    }

    public function current(): ?string
    {
        return $this->current?->data;
    }

    public function forward(): ?string
    {
        if ($this->current === null || $this->current->next === null) {
            return $this->current->data ?? null;
        }

        $this->current = $this->current->next;

        return $this->current->data;
    }

    public function back(): ?string
    {
        if ($this->current === null || $this->current->prev === null) {
            return $this->current->data ?? null;
        }

        $this->current = $this->current->prev;

        return $this->current->data;
    }
}

Lets see it in action:

$list = new LinkedList();

$list->insert("A");
$list->insert("B");
$list->insert("C");

$list->current();
echo $list->forward(); // Output: 'B'
echo $list->forward(); // Output: 'C'
echo $list->forward(); // Output: 'A'
echo $list->back(); // Output: 'C'

It’s probably starting to get a little more complex now, so lets break down some of the functions:

insert(string $data): void

This method adds a new node to the linked list with the provided data.

• If the list is empty (i.e., head is null), the new node becomes both the head and tail of the list. The node's next and prev pointers point to itself, making the list circular.

• If the list is not empty, the new node is added after the current tail node:

  • The next pointer of the new node points to the head (because the list is circular).

  • The prev pointer of the new node points to the old tail.

  • The old tail's next pointer is updated to point to the new node.

  • The head's prev pointer is updated to point to the new node (to maintain the circular structure).

  • Finally, the new node becomes the new tail of the list.

forward(): ?string

This method moves the current pointer to the next node in the list and returns the data of the new current node.

• It first checks if the current node is null or if the current node has no next node. If either condition is true, it simply returns the current node's data (this would happen if there's only one node in the list).

• Otherwise, it moves the current pointer to the next node.

• It then returns the data of the new current node.

• Circular behaviour: When it reaches the last node, the next node will be the first node (head), so it "wraps around."

back(): ?string

This method moves the current pointer to the previous node in the list and returns the data of the new current node.

• It checks if the current node is null or if the current node has no prev node. If either is true, it returns the current node's data (if there's only one node).

• Otherwise, it moves the current pointer to the prev node.

• It then returns the data of the new current node.

• Circular behaviour: When it reaches the first node, the previous node will be the last node (tail), so it "wraps around."

To be continued…

Watch out for more content about DSA. Coming soon!

Want some examples of what we’ve discussed in this article? Check out my code repository.

Subscribe now