Linked Lists are a fundamental data structure in computer science, where elements (called nodes) are connected sequentially through pointers. Unlike arrays, Linked Lists are dynamic, meaning they can grow or shrink in size without the need for resizing operations. In this tutorial, we’ll cover the basics of implementing a Linked List in PHP.
Structure of a Linked List Node
Each node in a Linked List consists of two parts:
- Data: The value stored in the node.
- Next: A reference (pointer) to the next node.
Here’s an example implementation of a basic node in PHP:
class Node {
public $data;
public $next;
public function __construct($data) {
$this->data = $data;
$this->next = null;
}
}
Implementing a Simple Linked List
To manage the nodes, we create a LinkedList class that maintains the head of the list and provides methods to manipulate it.
Basic Operations
1. Add Node to the End
We add a node to the end of the list by iterating through the nodes until we reach the last one.
class LinkedList {
private $head;
public function __construct() {
$this->head = null;
}
public function append($data) {
$newNode = new Node($data);
if ($this->head === null) {
$this->head = $newNode;
} else {
$current = $this->head;
while ($current->next !== null) {
$current = $current->next;
}
$current->next = $newNode;
}
}
}
2. Display the List
We can traverse the list to print all the elements.
public function display() {
$current = $this->head;
while ($current !== null) {
echo $current->data . " -> ";
$current = $current->next;
}
echo "NULL\n";
}
3. Delete a Node
Deleting a node involves finding the node and updating the pointer of the previous node.
public function delete($data) {
if ($this->head === null) {
return;
}
if ($this->head->data === $data) {
$this->head = $this->head->next;
return;
}
$current = $this->head;
while ($current->next !== null && $current->next->data !== $data) {
$current = $current->next;
}
if ($current->next !== null) {
$current->next = $current->next->next;
}
}
Example Usage
Here’s how to use the Linked List implementation:
$linkedList = new LinkedList();
$linkedList->append(10);
$linkedList->append(20);
$linkedList->append(30);
echo "Initial List:\n";
$linkedList->display();
$linkedList->delete(20);
echo "After Deleting 20:\n";
$linkedList->display();
*Output:
*
Initial List:
10 -> 20 -> 30 -> NULL
After Deleting 20:
10 -> 30 -> NULL
Conclusion
Linked Lists are a powerful tool for dynamic data manipulation. While PHP has built-in array functions that often serve similar purposes, understanding Linked Lists is essential for grasping fundamental data structures and improving algorithmic thinking. This implementation provides a starting point for more advanced structures like Doubly Linked Lists and Circular Linked Lists.