Linked List Data Structure: Creation and Traversal in DSA
Introduction
A Linked List is a fundamental data structure where elements (nodes) are connected using pointers.
👉 Unlike arrays:
- No fixed size
- Dynamic memory allocation
- Efficient insertions
Each node contains:
- Data
- Pointer to next node
🔹 Structure of a Node
[ Data | Next ]
👉 Example:
10 → 20 → 30 → NULL
🔹 1. Creation of Linked List in PHP
🧑💻 Step 1: Create Node Class
<?php
class Node {
public $data;
public $next;
public function __construct($data) {
$this->data = $data;
$this->next = null;
}
}
?>🧑💻 Step 2: Create Linked List Class
<?php
class LinkedList {
public $head;
public function __construct() {
$this->head = null;
}
// Create list by adding nodes at end
public function insert($data) {
$newNode = new Node($data);
if ($this->head == null) {
$this->head = $newNode;
return;
}
$temp = $this->head;
while ($temp->next != null) {
$temp = $temp->next;
}
$temp->next = $newNode;
}
}
?>🧪 Example: Creating a Linked List
<?php
$list = new LinkedList();
$list->insert(10);
$list->insert(20);
$list->insert(30);
?>👉 Created List:
10 → 20 → 30 → NULL
🔹 2. Traversal of Linked List
💡 Concept
Traversal means visiting each node one by one.
👉 Start from head
👉 Move using next pointer
🧑💻 Traversal Code
<?php
public function traverse() {
$temp = $this->head;
while ($temp != null) {
echo $temp->data . " → ";
$temp = $temp->next;
}
echo "NULL";
}
?>🧪 Full Example
<?php
class Node {
public $data;
public $next; public function __construct($data) {
$this->data = $data;
$this->next = null;
}
}
class LinkedList {
public $head; public function __construct() {
$this->head = null;
}
public function insert($data) {
$newNode = new Node($data);
if ($this->head == null) {
$this->head = $newNode;
return;
} $temp = $this->head;
while ($temp->next != null) {
$temp = $temp->next;
} $temp->next = $newNode;
}
public function traverse() {
$temp = $this->head;
while ($temp != null) {
echo $temp->data . " → ";
$temp = $temp->next;
} echo "NULL";
}
}// Usage
$list = new LinkedList();
$list->insert(10);
$list->insert(20);
$list->insert(30);$list->traverse();?>⚡ Time Complexity
| Operation | Complexity |
|---|---|
| Creation | O(n) |
| Traversal | O(n) |
🎯 Key Points
✅ Linked List is dynamic
✅ No index access (unlike arrays)
✅ Traversal is required to access elements
No comments yet! You be the first to comment.