Welcome to our tutorial focusing on Linked List Operations in PHP. Singly-Linked Lists are among the most fundamental data structures used in computer science. They provide an efficient way to store and access data that is not necessarily contiguous in memory. This ability distinguishes linked lists from arrays, making them an indispensable tool in a programmer's toolkit.
To work with linked lists in PHP, we need to define a ListNode
class, which represents a node in the linked list.
php1class ListNode { 2 public $value; 3 public $next; 4 5 public function __construct($value) { 6 $this->value = $value; // Holds the value or data of the node 7 $this->next = null; // Points to the next node in the linked list; default is null 8 } 9} 10 11// Initialization of linked list 12class LinkedListExample { 13 public static function main() { 14 $head = new ListNode(1); 15 $head->next = new ListNode(2); 16 $head->next->next = new ListNode(3); 17 $head->next->next->next = new ListNode(4); 18 $head->next->next->next->next = new ListNode(5); 19 } 20}
In the ListNode
class:
$value
holds the data of the node.$next
is a reference to the next node in the linked list. It isnull
by default, meaning the node does not point to any other node when it's freshly created.
To understand this, consider that a linked list is a linear data structure where each element is a separate object known as a node
. A node
comprises data and a reference (link) to the next node in the sequence.
The provided code creates a linked list in which each node points to the next as follows: 1 -> 2 -> 3 -> 4 -> 5
, and the last node points to null
.
One example of a problem to practice involves reversing a linked list, a common operation in interviews and the industry. To reverse a linked list, we'll need to sequentially rearrange the next
link of each node to point toward its previous node.
Here is what the code might look like. Note that this code uses of additional memory:
php1class ListNode { 2 public $value; 3 public $next; 4 5 public function __construct($value) { 6 $this->value = $value; 7 $this->next = null; 8 } 9} 10 11class ReverseLinkedList { 12 public static function reverseLinkedList($head) { 13 $prev = null; 14 $current = $head; 15 while ($current !== null) { 16 $nextNode = $current->next; 17 $current->next = $prev; 18 $prev = $current; 19 $current = $nextNode; 20 } 21 return $prev; 22 } 23 24 // Test 25 public static function main() { 26 $head = new ListNode(1); 27 $head->next = new ListNode(2); 28 $head->next->next = new ListNode(3); 29 $head->next->next->next = new ListNode(4); 30 $head->next->next->next->next = new ListNode(5); 31 32 $reversedHead = self::reverseLinkedList($head); 33 while ($reversedHead !== null) { 34 echo $reversedHead->value . " "; 35 $reversedHead = $reversedHead->next; // Output: 5 4 3 2 1 36 } 37 } 38}
I urge you to observe, analyze, and understand the problem and the corresponding solution. This practice will facilitate a well-rounded understanding of linked list operations and their applications. By the end of the tutorial, you should feel more comfortable tackling linked list problems, allowing you to handle similar tasks in technical interviews. Let's get started with practical exercises!