When I first started teaching data structures in PHP, I noticed a recurring theme: students would look at a Linked List implementation and ask, "Why bother? PHP arrays already do all of this."

The Myth: PHP Arrays are Linked Lists

It's a common trap. In PHP, you can array_push(), array_pop(), and array_shift(). To the naked eye, it feels like you're working with a dynamic list. But here is the reality: a PHP array is actually an ordered map—a sophisticated hash table. When you remove the first element of a massive PHP array using array_shift(), PHP has to re-index every single remaining element. If you have 10,000 items, that's a lot of wasted work just to move one pointer.

A true Linked List doesn't care about indices. It doesn't store items in a contiguous block of memory. Instead, it stores "nodes," where each node is just a little package containing a piece of data and a reference to the next package. Removing the first item is as simple as telling the list, "Your new head is the second item." Done. $O(1)$ complexity. No re-indexing, no sweating.

Building the Node-Link Architecture

To do this in PHP, we can't use arrays. We need objects. I like to think of a Node as a train car. The car holds the cargo (the data) and a coupling (the reference) to the next car.

class Node {
    public $data;
    public $next;

    public function __construct($data) {
        $this->data = $data;
        $this->next = null; // By default, this is the end of the line
    }
}

Now, the Linked List itself is really just a wrapper that keeps track of where the "train" starts. I call this the $head. If the head is null, the list is empty. If you want to add something to the end, you start at the head and "walk" through the $next references until you hit null.

Let's look at a practical implementation for a Music Playlist. In a playlist, you want to be able to add songs quickly without worrying about where they sit in a numeric index.

class Playlist {
    private $head = null;

    public function addSong($title) {
        $newNode = new Node($title);

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

        // We have to traverse to the end of the list
        $current = $this->head;
        while ($current->next !== null) {
            $current = $current->next;
        }
        $current->next = $newNode;
    }

    public function showPlaylist() {
        $current = $this->head;
        while ($current !== null) {
            echo $current->data . " -> ";
            $current = $current->next;
        }
        echo "END\n";
    }
}

$myVibes = new Playlist();
$myVibes->addSong("Lo-Fi Beats");
$myVibes->addSong("Synthwave Sunset");
$myVibes->addSong("Deep Focus");
$myVibes->showPlaylist(); 
// Output: Lo-Fi Beats -> Synthwave Sunset -> Deep Focus -> END

Notice that addSong doesn't use count() or any numeric keys. It's purely about object references. This is where the power lies. If I wanted to implement a removeSong($title) method, I wouldn't need to shift an entire array; I would simply find the node before the one I want to delete and point its $next reference to the node after the one I'm deleting. The "deleted" node just floats away and gets cleaned up by PHP's garbage collector.

📋 Practical Task

Exercise: Browser History Back-Button Simulator

In this exercise, you will implement a simplified version of a browser's history stack using the Linked List concept. Instead of adding to the end of the list, you need to add new pages to the front (the head) of the list, because the most recently visited page is always the first one you'd return to when clicking "Back".

Requirements:

• Create a PageNode class to hold the URL and the reference to the previous page.
• Create a BrowserHistory class with two methods:
  • visit($url): Adds a new URL to the front of the list.
  • goBack(): Removes the current head (the current page) and returns the URL of the new head (the previous page). If there is no previous page, return "No history available".

Test your code with this sequence:

$history = new BrowserHistory();
$history->visit("google.com");
$history->visit("github.com");
$history->visit("stackoverflow.com");
echo $history->goBack(); // Should return "github.com"
echo $history->goBack(); // Should return "google.com"
echo $history->goBack(); // Should return "No history available"