19. Linked List - Singly

অ্যারের সীমাবদ্ধতা কাটিয়ে ওঠার জন্য Linked List একটি অত্যন্ত গুরুত্বপূর্ণ ডাইনামিক ডেটা স্ট্রাকচার। এটি কন্টিনিয়াস মেমরির বদলে বিক্ষিপ্ত মেমরিতে ডেটা স্টোর করে।

---

1. Linked List কি? (What is Linked List?)

লিঙ্কড লিস্ট হলো কতগুলো Node-এর একটি লিনিয়ার কালেকশন। প্রতিটি নোড একটি ডেটা এলিমেন্ট এবং পরের নোডের অ্যাড্রেস (Reference) ধারণ করে।

কেন লিঙ্কড লিস্ট? (Why Linked List?)

• Dynamic Size: ব্যবহারের সময় সাইজ কমানো বা বাড়ানো যায়।
• Efficient Insertion/Deletion: মাঝখানে কোনো ডেটা যোগ বা ডিলিট করার সময় এলিমেন্টগুলোকে সরাতে (Shift) হয় না।

---

2. নোড স্ট্রাকচার (Node Structure)

প্রতিটি নোড দুটি অংশ নিয়ে গঠিত:

1. Data: যেখানে আসল ডেটা থাকে।
2. Next: যা পরবর্তী নোডের মেমরি অ্যাড্রেস হোল্ড করে।

Implementation

// Java Node Class
class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

# Python Node Class
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

---

3. হেড পয়েন্টার (Head Pointer)

লিঙ্কড লিস্টের প্রথম নোডকে Head বলা হয়। পুরো লিস্টটি অ্যাক্সেস করার জন্য আমাদের শুধু হেড পয়েন্টারটি জানা থাকলেই চলে। যদি হেড null হয়, তবে লিস্টটি খালি।

---

4. ট্রাভার্সাল (Traversal)

লিস্টের শুরু থেকে শেষ পর্যন্ত প্রতিটি নোড দেখা।

3. প্রতিটি ধাপে curr.data প্রিন্ট করুন এবং curr = curr.next করে পরের নোডে যান।

Implementation

// Java Traversal
public void printList(Node head) {
    Node curr = head;
    while (curr != null) {
        System.out.print(curr.data + " -> ");
        curr = curr.next;
    }
    System.out.println("null");
}

# Python Traversal
def print_list(head):
    curr = head
    while curr:
        print(f"{curr.data} ->", end=" ")
        curr = curr.next
    print("None")

---

5. ইনসার্শন (Insertion)

শুরুতে (At the Beginning)

1. নতুন একটি নোড তৈরি করুন।
2. নতুন নোডের next-কে বর্তমান head-এ পয়েন্ট করান।
3. head-কে নতুন নোডে আপডেট করুন।

শেষে (At the End)

1. নতুন নোড তৈরি করুন।
2. যদি লিস্ট খালি থাকে, তবে একেই head বানান।
3. নতুবা, শেষ নোড পর্যন্ত যান এবং শেষ নোডের next-এ নতুন নোডটি সেট করুন।

Implementation

// Java Insertion
public Node insertAtHead(Node head, int data) {
    Node newNode = new Node(data);
    newNode.next = head;
    return newNode;
}

public Node insertAtEnd(Node head, int data) {
    Node newNode = new Node(data);
    if (head == null) return newNode;
    Node curr = head;
    while (curr.next != null) curr = curr.next;
    curr.next = newNode;
    return head;
}

# Python Insertion
def insert_at_head(head, data):
    new_node = Node(data)
    new_node.next = head
    return new_node

def insert_at_end(head, data):
    new_node = Node(data)
    if not head: return new_node
    curr = head
    while curr.next:
        curr = curr.next
    curr.next = new_node
    return head

---

6. ডিলিট অপারেশন (Deletion)

শুরু থেকে (From Beginning)

1. head-কে head.next-এ সরিয়ে দিন।

শেষ থেকে (From End)

1. শেষ নোডের আগের নোড পর্যন্ত যান।
2. সেই নোডের next-কে null করে দিন।

Implementation

// Java Deletion
public Node deleteFromBeginning(Node head) {
    if (head == null) return null;
    return head.next;
}

public Node deleteFromEnd(Node head) {
    if (head == null || head.next == null) return null;
    Node curr = head;
    while (curr.next.next != null) curr = curr.next;
    curr.next = null;
    return head;
}

# Python Deletion
def delete_from_beginning(head):
    if not head: return None
    return head.next

def delete_from_end(head):
    if not head or not head.next: return None
    curr = head
    while curr.next.next:
        curr = curr.next
    curr.next = None
    return head

---

7. সার্চ এবং লেন্থ (Search & Length)

• Search: ট্রাভার্স করার সময় চেক করুন ডেটা পাওয়া গেছে কি না।
• Length: ট্রাভার্স করার সময় একটি কাউন্টার ব্যবহার করে মোট নোড সংখ্যা বের করুন।

---

📊 কমপ্লেক্সিটি অ্যানালাইসিস (Complexity Analysis)

Operation	Time Complexity
Access/Search	O(n)
Insert at head	O(1)
Insert at tail	O(n) (যদি টেইল পয়েন্টার না থাকে)
Deletion at head	O(1)
Deletion at tail	O(n)

---

IMPORTANT

লিঙ্কড লিস্টে র্যান্ডম অ্যাক্সেস (যেমন: arr[5]) করা যায় না। যে কোনো এলিমেন্ট পেতে হলে শুরু থেকে ট্রাভার্স করতে হয়।

---

TIP

টেইল পয়েন্টার (Tail Pointer) মেইনটেইন করলে শেষে ইনসার্ট করার সময় O(1) এ করা সম্ভব।