Linked List in Data Structures (DSA) – Complete Guide

Linked List in PHP (DSA)

🚀 Introduction

A Linked List is a linear data structure where elements (called nodes) are connected using pointers. Unlike arrays, linked lists are not stored in contiguous memory locations.

Each node contains:

• Data
• Reference (pointer) to the next node

👉 This makes insertion and deletion operations efficient.

📦 Types of Linked Lists

1️⃣ Singly Linked List

Each node points to the next node.

[Data | Next] → [Data | Next] → NULL

2️⃣ Doubly Linked List

Each node has two pointers:

• Previous
• Next

NULL ← [Prev | Data | Next] → [Prev | Data | Next] → NULL

3️⃣ Circular Linked List

The last node points back to the first node.

[Data] → [Data] → [Data]
   ↑__________________↓

⚙️ Basic Operations

• Insertion (beginning, end, position)
• Deletion
• Traversal
• Searching

🧑‍💻 PHP Implementation (Singly Linked List)

<?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;
    }
        // Insert at beginning
    public function insertAtBeginning($data) {
        $newNode = new Node($data);
        $newNode->next = $this->head;
        $this->head = $newNode;
    }
        // Insert at end
    public function insertAtEnd($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;
    } 
       // Display the list
    public function display() {
        $temp = $this->head;
        while ($temp != null) {
            echo $temp->data . " -> ";
            $temp = $temp->next;
        }
        echo "NULL";
    }
}
// Example Usage
$list = new LinkedList();
$list->insertAtBeginning(10);
$list->insertAtEnd(20);
$list->insertAtEnd(30);$list->display();
?>

<?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;
    }
        // Insert at beginning
    public function insertAtBeginning($data) {
        $newNode = new Node($data);
        $newNode->next = $this->head;
        $this->head = $newNode;
    }
        // Insert at end
    public function insertAtEnd($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;
    } 
       // Display the list
    public function display() {
        $temp = $this->head;
        while ($temp != null) {
            echo $temp->data . " -> ";
            $temp = $temp->next;
        }
        echo "NULL";
    }
}
// Example Usage
$list = new LinkedList();
$list->insertAtBeginning(10);
$list->insertAtEnd(20);
$list->insertAtEnd(30);$list->display();
?>

⚡ Time Complexity

🎯 Advantages

✅ Dynamic size (no fixed limit)
✅ Efficient insertion and deletion
✅ No memory reallocation like arrays

❌ Disadvantages

❌ No direct access (no indexing)
❌ Extra memory for pointers
❌ Slower traversal compared to arrays

🧠 Common Interview Questions

1. Reverse a linked list
2. Find the middle node
3. Detect a loop (cycle detection)
4. Merge two linked lists
5. Remove the nth node from the end

🔥 Pro Tip

Most interview problems are based on:

• Two-pointer technique (fast & slow pointer)
• Recursion
• Dummy node approach

🏁 Conclusion

Linked Lists are a fundamental part of Data Structures and Algorithms. They are widely used in real-world applications such as:

• Memory management
• Graph implementations
• Undo/Redo systems