A linked list is a collection of objects known as nodes. Each node is connected to the next node with a link, which is nothing but an object reference. If we consider the following image, each box represents a node. The arrow indicates the link between the nodes. This is an example of a singly linked list. The last node contains the next link of a NULL, so that it marks the end of the list:

A node is an object, meaning it can store any data type as simple as a string, integer, or float, or complex, such as an array, array of arrays, objects, or object arrays. We can store anything as per our need.

We can also perform a wide variety of operations on a linked list, such as the following ones:

• Checking whether the list is empty
• Displaying all items in the list
• Searching an item in the list
• Getting the size of the list
• Inserting a new item at the beginning or end of the list
• Removing an item from the beginning or end of the list
• Inserting a new item at a specific place or before/after an item
• Reversing a list

These are only some of the operations that can be performed on a linked list.

Let's write a simple linked list to store some names:

class ListNode { 
    public $data = NULL; 
    public $next = NULL; 

    public function __construct(string $data = NULL) { 
        $this->data = $data; 
    } 
}

We mentioned earlier that a linked list consists of nodes. We have created a simple class for our node. The ListNode class has two properties: one that will store the data and the other for the link called next. Now, we are going to implement a linked list using the ListNode class. For simplicity, we will just have two operations: insert and display:

class LinkedList { 
    private $_firstNode = NULL; 
    private $_totalNodes = 0; 

    public function insert(string $data = NULL) { 
       $newNode = new ListNode($data); 

        if ($this->_firstNode === NULL) {           
            $this->_firstNode = &$newNode;             
        } else { 
            $currentNode = $this->_firstNode; 
            while ($currentNode->next !== NULL) { 
                $currentNode = $currentNode->next; 
            } 
            $currentNode->next = $newNode; 
        } 
       $this->_totalNode++; 
        return TRUE; 
    } 

    public function display() { 
      echo "Total book titles: ".$this->_totalNode."
"; 
        $currentNode = $this->_firstNode; 
        while ($currentNode !== NULL) { 
            echo $currentNode->data . "
"; 
            $currentNode = $currentNode->next; 
        } 
    } 
} 

The preceding code actually implements our two basic operations for insert and display nodes. In the LinkedList class, we have two private properties: $_firstNode and $_totalNodes. Both have the default value of NULL and 0, respectively. We need to mark the head node or first node, so that we always know where we have to start from. We can also call it the front node. Whatever name we provide, it will be mainly used to indicate the start of the linked list. Now, let's move to the insert operation code.

The insert method takes one argument, which is the data itself. We will create a new node with the data using the ListNode class. Before inserting a book title in our linked list, we have to consider two possibilities:

• The list is empty and we are inserting the first title
• The list is not empty and the title is going to be added at the end

Why do we need to consider both cases? The answer is pretty simple. If we do not know whether the list is empty or not, we might get different results for our operations. We might also create invalid linking between the nodes. So, the idea is if the list is empty, our insert item is going to be the first item of the list. This is what the first part of the code is doing:

$newNode = new ListNode($data); 

if ($this->_firstNode === NULL) {             
          $this->_firstNode = &$newNode; 
}

We can see from the preceding code segment that we are creating a new node with the data and naming the node object $newNode. After that, it checks whether $_firstNode is NULL or not. If it is NULL, then the list is empty. If it is empty, then we assign the $newNode object to the $_firstNode property. Now, the remaining part of the insert method represents our second condition, which is that the list is not empty, and we have to add the new item at the end of the list:

$currentNode = $this->_firstNode;    
while ($currentNode->next !== NULL) { 
  $currentNode = $currentNode->next; 
} 
$currentNode->next = $newNode; 

Here, we get the first node of the list from the $_firstNode property. Now, we are going to iterate from the first node until the end of the list. We will ensure this by checking the condition that the next link for the current node is not NULL. If it is NULL, then we have reached the end of the list. In order to make sure that we are not looping to the same node all the time, we set the next node on from the current node as the current item during the iteration process. The while loop code implements the logic. Once we get out of the while loop, we set the last node of the linked list as $currentNode. Now, we have to assign the next link of the current last node to the newly created node named $newNode, so we simply put the object to the next link of the node. This object reference will work as a link between two node objects. At the end, we also increment the total node count value by 1 by post-incrementing the $_totalNode property.

If we look at our display method, we can see that we are using almost similar logic to iterate through each of the nodes and displaying its content. We first get the head item for the linked list. Then, we iterate through the list until the list item is NULL. Inside the loop, we display the node data by showing its $data property. Now, we have a node class ListNode to create individual nodes for the linked list, and we have the LinkedList class to do basic insert and display operations. Let's write a small code to utilize the LinkedList class to create a linked list for book titles:

$BookTitles = new LinkedList(); 
$BookTitles->insert("Introduction to Algorithm"); 
$BookTitles->insert("Introduction to PHP and Data structures"); 
$BookTitles->insert("Programming Intelligence"); 
$BookTitles->display(); 

Here, we create a new object for LinkedList and name it $BookTitles. Then, we insert new book items using the insert method. We add three books, and then, we are displaying the book names using the display method. If we run the preceding code, we will see following output:

Total book titles: 3
Introduction to Algorithm
Introduction to PHP and Data structures
Programming Intelligence

As we can see, there is a counter at the first line that shows that we have three book titles, along with their names. If we look carefully, we will see that the book titles are displayed the same way that we entered them. This means our implemented linked list is actually maintaining the order. This is because we have always entered the new node at the end of the list. We could have done this differently if we wanted. As our first example, we have covered a lot about linked lists and how to construct them. In the upcoming sections, we will explore more about how to create different types of linked lists, and with more complex examples. For now, we are going to focus on the different types of linked lists.