Today's lesson will build upon our foundational understanding of linked lists by diving into practical implementation exercises using PHP. These problems sharpen your coding skills and prepare you for scenarios you might encounter in technical interviews.
Picture a scenario in which you have a sequence of events stored in a linked list. Your task is to look back in time — essentially, to reverse the chronology of these events. In technical terms, this means traversing a singly linked list in reverse order while keeping its structure intact. This skill is critical, whether for reversing transaction logs or simply navigating through a playlist from the end to the start.
Consider a browser's back-button functionality, where the most recently visited pages must be revisited in reverse. This operation mirrors our task of reverse traversal in a linked list, capturing the essence of a real-world application.
One may consider creating a new linked list while iterating over the original list, inserting each element at the head of the new list. Although this approach might work, it's an unnecessary approach that results in extra processing and memory usage that we can avoid.
A more sophisticated solution would use a stack. By using a stack in PHP, we ensure an orderly collection of the nodes' values as we navigate the list. Once the traversal is complete, we extract the values in reverse, thanks to the stack's Last-In-First-Out property.
Let's visualize it with a deck of cards: We pick each card from the top (the head of the linked list) and place it into a pile (the stack). When we finish, we pick up the cards from the pile now in reverse order.
Let's tackle it with PHP:
php1// Use an SPL Stack to hold node values. 2$stack = new SplStack(); 3 4// Traverse the linked list and push node values to the stack. 5$currentNode = $head; 6while ($currentNode !== null) { 7 $stack->push($currentNode->value); 8 $currentNode = $currentNode->next; 9} 10 11// Pop from the stack to obtain elements in reversed order. 12while (!$stack->isEmpty()) { 13 echo $stack->pop(), "\n"; 14}
In this code, we create an SplStack
object to store integers. We then iterate through the linked list using a while
loop. For each node visited, we push its value onto the stack. After traversing the entire list, we pop the values off the stack. This reversal is possible because stacks operate on a Last In, First Out (LIFO) principle, which means the last element added to the stack will be the first one removed, thus reversing the order of the elements.
Next up, we face a seemingly simple task: determining the size of a linked list. Imagine it as a conga line at a party. You'd like to know how many people are in the line without disturbing the dance. Start at the beginning and count each person until you reach the end.
In scenarios such as buffering data streams or executing batch operations, we often need to know the size of a list of tasks to allocate resources efficiently. This real-world implication highlights the utility of accurately determining the length of a linked list.
While it may be tempting to convert the linked list to an array and use its count
function, such an approach is needlessly burdensome. We would create a new data structure when a more straightforward method can be employed.
To calculate the length efficiently, we'll employ a classic traversal technique. It's a counting exercise: start at the first node (like the first person in the conga line) and increment a counter as we follow the links until we reach the end. The counter then reflects the conga line's length.
Implementing this strategy in PHP is straightforward, lets create a function called calculateLinkedListLength
:
php1<?php 2function calculateLinkedListLength($head) { 3 // Initialize a counter for the length. 4 $length = 0; 5 6 // Iterate through the list, incrementing the length counter. 7 $currentNode = $head; 8 while ($currentNode !== null) { 9 $length++; 10 $currentNode = $currentNode->next; 11 } 12 13 // Return the final count. 14 return $length; 15} 16?>
In this code, we initialize an integer $length
to zero, which will serve as our counter. We then loop through each node of the linked list, incrementing $length
by one each time a new node is encountered. When the end of the list is reached (which we know occurs when $currentNode
is null
), we exit the loop and return the total count.
The direct traversal method we used to calculate the length of a linked list is more efficient because it has a time complexity of O(n), where n is the number of elements in the list. This is the best possible complexity for this task, as we need to visit each node to ensure an accurate count. In contrast, converting the linked list to an array first would incur an additional time and space overhead, resulting in an overall time complexity of O(n) for traversal and O(n) for array creation and manipulation, thereby unnecessarily impacting performance and resource usage.
Today, we practiced critical operations on linked lists, namely reversing a list's traversal and calculating its length. Both solutions involved traversing the linked list but with different goals in mind. We efficiently solved these problems using structurally simple yet powerful techniques in PHP. We will transition to a series of exercises designed to reinforce your understanding of linked lists and prepare you for tackling similar problems in real-world scenarios or technical interviews.