Java Technologies লিংকড লিস্ট (Linked List) গাইড ও নোট

লিংকড লিস্ট (Linked List) একটি ডাটা স্ট্রাকচার, যেখানে প্রতিটি নোড (Node) একটি ডাটা এবং পরবর্তী নোডের রেফারেন্স (link) ধারণ করে। অ্যারে থেকে আলাদা, লিংকড লিস্টে সাইজ ফিক্সড না হয়ে এটি ডাইনামিকভাবে মেমরি অ্যাসাইন করে। এটি সাধারণত ডাটা স্টোর করার জন্য ব্যবহৃত হয় যেখানে এলিমেন্টের মধ্যে যেকোনো পরিবর্তন সহজে করা যায় (যেমন ইনসার্ট বা ডিলিট)।

লিংকড লিস্টের প্রধান উপাদানগুলো হলো:

1. নোড (Node): প্রতিটি নোডে ডাটা এবং পরবর্তী নোডের রেফারেন্স থাকে।
2. হেড (Head): এটি লিংকড লিস্টের প্রথম নোডের রেফারেন্স ধারণ করে।
3. টেল (Tail) (ঐচ্ছিক): এটি লিংকড লিস্টের শেষ নোডের রেফারেন্স ধারণ করে।

লিংকড লিস্টের প্রধান সুবিধা হলো এটি ডাটা ইনসার্ট এবং ডিলিট করার ক্ষেত্রে দ্রুত কাজ করে, বিশেষত যখন অ্যারে বা অন্য ডাটা স্ট্রাকচারে এলিমেন্ট শিফট করতে হয় না।

লিংকড লিস্টের মৌলিক অপারেশনসমূহ

লিংকড লিস্টে বেশ কিছু মৌলিক অপারেশন রয়েছে, যেমন:

1. ইনসার্ট (Insert): নতুন নোড লিস্টে যোগ করা।
2. ডিলিট (Delete): একটি নির্দিষ্ট নোড লিস্ট থেকে মুছে ফেলা।
3. সার্চ (Search): একটি নির্দিষ্ট মান খোঁজা।
4. ট্রাভার্স (Traverse): পুরো লিস্টের এলিমেন্টগুলো দেখতে।

লিংকড লিস্টের জাভা ইমপ্লিমেন্টেশন

1. নোড ক্লাস (Node Class)

প্রথমে, লিংকড লিস্টের জন্য একটি Node ক্লাস তৈরি করতে হবে। এই ক্লাসে data এবং next নামে দুটি ফিল্ড থাকবে। data হল নোডের মান এবং next পরবর্তী নোডের রেফারেন্স ধারণ করে।

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

2. লিংকড লিস্ট ক্লাস (Linked List Class)

এখন আমরা একটি LinkedList ক্লাস তৈরি করব, যা আমাদের বিভিন্ন অপারেশন যেমন ইনসার্ট, ডিলিট, ট্রাভার্স ইত্যাদি সম্পাদন করবে।

class LinkedList {
    Node head;

    // Constructor to initialize an empty list
    public LinkedList() {
        head = null;
    }

    // Insert a new node at the end of the list
    public void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = newNode;
        }
    }

    // Delete a node with specific value
    public void delete(int key) {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }

        if (head.data == key) {
            head = head.next;
            return;
        }

        Node temp = head;
        while (temp.next != null && temp.next.data != key) {
            temp = temp.next;
        }

        if (temp.next == null) {
            System.out.println("Element not found");
        } else {
            temp.next = temp.next.next;
        }
    }

    // Traverse the list and print each element
    public void traverse() {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }

        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    // Search for an element in the list
    public boolean search(int key) {
        Node temp = head;
        while (temp != null) {
            if (temp.data == key) {
                return true;
            }
            temp = temp.next;
        }
        return false;
    }
}

ক্লাসের ব্যাখ্যা

1. insert(int data):
   • এই মেথডটি নতুন একটি নোড তৈরি করে এবং সেটিকে লিস্টের শেষে যোগ করে।
   • যদি লিস্ট খালি থাকে, তবে এটি হেড নোড হিসাবে সেট হয়।
2. delete(int key):
   • এই মেথডটি একটি নির্দিষ্ট মান (key) অনুসন্ধান করে, যদি পাওয়া যায় তবে সেই নোডটি মুছে ফেলে।
   • যদি লিস্টের প্রথম নোডে এটি থাকে, তবে হেড নোড পরিবর্তন হয়।
3. traverse():
   • এটি লিস্টের সমস্ত নোডে ট্রাভার্স করে এবং তাদের মান প্রিন্ট করে।
4. search(int key):
   • এটি লিস্টে একটি নির্দিষ্ট মান অনুসন্ধান করে এবং সেটি পাওয়া গেলে true রিটার্ন করে।

লিংকড লিস্ট ব্যবহার উদাহরণ

এখন আমরা লিংকড লিস্ট ব্যবহার করে কিছু অপারেশন দেখব, যেমন ইনসার্ট, ডিলিট, ট্রাভার্স এবং সার্চ।

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // Insert elements
        list.insert(10);
        list.insert(20);
        list.insert(30);
        list.insert(40);

        // Traverse and print the list
        System.out.println("Linked List:");
        list.traverse(); // Output: 10 20 30 40

        // Search for an element
        if (list.search(30)) {
            System.out.println("Element 30 found");
        } else {
            System.out.println("Element 30 not found");
        }

        // Delete an element
        list.delete(20);

        // Traverse and print the list after deletion
        System.out.println("Linked List after deletion:");
        list.traverse(); // Output: 10 30 40
    }
}

এই কোডটি ইনসার্ট, সার্চ, ডিলিট, এবং ট্রাভার্স অপারেশনগুলোর কাজ করে।

সারাংশ

লিংকড লিস্ট (Linked List) একটি গুরুত্বপূর্ণ ডাটা স্ট্রাকচার যা ডাটা ইনসার্ট এবং ডিলিট করার ক্ষেত্রে খুব কার্যকর। জাভাতে, লিংকড লিস্ট ইমপ্লিমেন্ট করতে Node ক্লাস এবং একটি LinkedList ক্লাস ব্যবহার করা হয়। এই স্ট্রাকচারে আমরা বিভিন্ন অপারেশন যেমন ইনসার্ট, ডিলিট, সার্চ, এবং ট্রাভার্স করতে পারি। লিংকড লিস্ট ডাইনামিক মেমরি ম্যানেজমেন্ট প্রদান করে এবং অ্যারে থেকে বেশি ফ্লেক্সিবল এবং কার্যকরী হতে পারে, বিশেষ করে বড় আকারের ডাটা ম্যানিপুলেশনের ক্ষেত্রে।

Linked List একটি বেসিক ডাটা স্ট্রাকচার যা বিভিন্ন নোড (Node) দিয়ে গঠিত। প্রতিটি নোডে দুটি অংশ থাকে: একটি ডেটা (data) এবং একটি পয়েন্টার (pointer) যা পরবর্তী নোডের ঠিকানা (address) নির্দেশ করে। Linked List গুলি অ্যারে ভিত্তিক ডাটা স্ট্রাকচারগুলির তুলনায় আরো নমনীয় এবং ডাইনামিক (dynamic) হয়, কারণ এতে এলিমেন্ট ইনসার্ট বা ডিলিট করা অনেক সহজ হয়।

এখানে আমরা জাভা দিয়ে Linked List এর মূল ধারণা এবং এর কিভাবে কাজ করে তা জানব।

1. Linked List এর মৌলিক উপাদান

Linked List তে প্রতিটি নোডের দুটি প্রধান উপাদান থাকে:

• Data: নোডে থাকা মূল তথ্য।
• Next (Pointer): পরবর্তী নোডের ঠিকানা (অথবা নোডের রেফারেন্স)।

উদাহরণ:

ধরা যাক, একটি লিঙ্কড লিস্ট যেটি পাঁচটি সংখ্যাকে ধারণ করছে: 10 -> 20 -> 30 -> 40 -> 50। এখানে:

• প্রথম নোডের data হবে 10 এবং next পয়েন্টার দ্বিতীয় নোডে, যার data হবে 20।
• দ্বিতীয় নোডের data হবে 20 এবং next পয়েন্টার তৃতীয় নোডে, এবং এটি চলতে থাকে।

2. Linked List এর ধরণ

Linked List মূলত তিন ধরনের হয়ে থাকে:

• Singly Linked List: এতে প্রতিটি নোডে শুধুমাত্র একটি পয়েন্টার থাকে, যা পরবর্তী নোডকে নির্দেশ করে।
• Doubly Linked List: এতে প্রতিটি নোডে দুটি পয়েন্টার থাকে, একটি পূর্ববর্তী নোডকে এবং আরেকটি পরবর্তী নোডকে নির্দেশ করে।
• Circular Linked List: এতে শেষ নোডের next পয়েন্টার প্রথম নোডের দিকে নির্দেশ করে, ফলে এটি একটি চক্রাকার লিস্ট হয়ে যায়।

3. Singly Linked List এর মৌলিক কনসেপ্ট

Singly Linked List এ প্রতিটি নোডের মধ্যে একটি data এবং একটি next পয়েন্টার থাকে যা পরবর্তী নোডকে নির্দেশ করে। এই পয়েন্টারটি শেষ নোডে null থাকে, যা নির্দেশ করে যে এটি লিস্টের শেষ নোড।

Singly Linked List এর স্ট্রাকচার:

Head -> [Data | Next] -> [Data | Next] -> [Data | Next] -> null

4. Singly Linked List এর অপারেশন

4.1 নতুন নোড ইনসার্ট করা

Linked List-এ নতুন নোড ইনসার্ট করার জন্য মূলত তিনটি পদ্ধতি রয়েছে:

• Head এ ইনসার্ট করা
• Tail (শেষ) এ ইনসার্ট করা
• কোনো নির্দিষ্ট পজিশনে ইনসার্ট করা

উদাহরণ: Head এ নতুন নোড ইনসার্ট করা

class Node {
    int data;
    Node next;

    // Constructor
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head;

    // নতুন নোড ইনসার্ট করার মেথড (Head এ)
    public void insertAtHead(int data) {
        Node newNode = new Node(data);
        newNode.next = head;  // Head এর পরবর্তী নোডটি নতুন নোডের পরবর্তী নোড হবে
        head = newNode;  // নতুন নোডটি এখন Head হয়ে যাবে
    }

    // লিঙ্কড লিস্ট প্রিন্ট করার মেথড
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        
        // Head এ ইনসার্ট করা
        list.insertAtHead(10);
        list.insertAtHead(20);
        list.insertAtHead(30);
        
        // লিস্ট প্রিন্ট করা
        list.printList();  // আউটপুট: 30 -> 20 -> 10 -> null
    }
}

ব্যাখ্যা:

• insertAtHead(int data) মেথড নতুন একটি নোড তৈরি করে এবং তা লিস্টের প্রথমে ইনসার্ট করে।
• printList() মেথডের মাধ্যমে লিস্টের সকল নোড প্রিন্ট করা হয়।

4.2 নোড ডিলিট করা

Linked List থেকে নোড ডিলিট করা সাধারণত দুটি কেসে করা হয়:

• Head নোড ডিলিট করা
• নির্দিষ্ট নোড ডিলিট করা

উদাহরণ: Head নোড ডিলিট করা

class LinkedList {
    Node head;

    // Head নোড ডিলিট করার মেথড
    public void deleteAtHead() {
        if (head != null) {
            head = head.next;  // Head নোডের পরবর্তী নোডকে নতুন Head বানানো
        }
    }

    // লিঙ্কড লিস্ট প্রিন্ট করার মেথড
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        
        // কিছু ইনসার্ট করা
        list.insertAtHead(10);
        list.insertAtHead(20);
        list.insertAtHead(30);
        
        // লিস্ট প্রিন্ট করা
        list.printList();  // আউটপুট: 30 -> 20 -> 10 -> null
        
        // Head নোড ডিলিট করা
        list.deleteAtHead();
        
        // লিস্ট প্রিন্ট করা
        list.printList();  // আউটপুট: 20 -> 10 -> null
    }
}

ব্যাখ্যা:

• deleteAtHead() মেথডটি Head নোডটি ডিলিট করে এবং পরবর্তী নোডটি নতুন Head হয়ে যায়।

5. Linked List এর ফিচার

• Dynamic Memory Allocation: Linked List এর সবচেয়ে বড় সুবিধা হল এটি ডাইনামিক মেমরি এলোকেশন করে, অর্থাৎ এলিমেন্টগুলি ইনসার্ট করার সময় এক্সট্রা মেমরি প্রয়োজন হয় না।
• Efficient Insertion/Deletion: সিংগলি লিঙ্কড লিস্টে নতুন নোড ইনসার্ট বা ডিলিট করা দ্রুত হয়, বিশেষত যখন এটি লিস্টের প্রথমে বা শেষে হয়।
• Random Access নেই: Linked List তে এলিমেন্ট অ্যাক্সেস করার জন্য লিনিয়ার সার্চ করতে হয়, যা অ্যারের তুলনায় ধীর।

Linked List একটি গুরুত্বপূর্ণ ডাটা স্ট্রাকচার যা ডাইনামিক এবং নমনীয় হয়। এটি একাধিক অপারেশন যেমন ইনসার্ট, ডিলিট, এবং ট্রাভার্সাল দ্রুত এবং কার্যকরভাবে করতে সাহায্য করে। Java দিয়ে সিংগলি লিঙ্কড লিস্ট তৈরি এবং ব্যবহার করা যায়, এবং এটি ডাটা স্ট্রাকচার এবং অ্যালগরিদম (DSA) শেখার জন্য একটি আদর্শ প্রাথমিক কনসেপ্ট।

Linked List কি?

Linked List হল একটি ডেটা স্ট্রাকচার যা উপাদানগুলির একটি সিকোয়েন্স ধারণ করে, যেখানে প্রতিটি উপাদান (Node) পরবর্তী উপাদানের রেফারেন্স বা পয়েন্টার ধারণ করে। এটি একটি ডাইনামিক ডেটা স্ট্রাকচার, যা অ্যারে থেকে বিভিন্নভাবে আলাদা, কারণ এর আকার পরিবর্তনযোগ্য এবং এটি অ্যারে থেকে বেশি কার্যকরী হতে পারে যখন উপাদানগুলির সন্নিবেশ বা অপসারণ প্রয়োজন হয়।

Singly Linked List এবং Doubly Linked List হল দুটি প্রকারের লিঙ্কড লিস্ট, যা নিম্নলিখিতভাবে ভিন্ন:

1. Singly Linked List: এতে প্রতিটি নোডে শুধুমাত্র পরবর্তী নোডের রেফারেন্স থাকে।
2. Doubly Linked List: এতে প্রতিটি নোডে পরবর্তী নোড এবং পূর্ববর্তী নোডের রেফারেন্স থাকে।

1. Singly Linked List

Singly Linked List হলো একটি লিঙ্কড লিস্ট যেখানে প্রতিটি নোডের দুটি উপাদান থাকে:

• Data: নোডের ডেটা।
• Next: পরবর্তী নোডের রেফারেন্স।

Singly Linked List এর কাঠামো:

// Singly Linked List Node class
class Node {
    int data;
    Node next;

    // Constructor
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// Singly Linked List class
class SinglyLinkedList {
    Node head;

    // Constructor
    public SinglyLinkedList() {
        this.head = null;
    }

    // Insert at the end
    public void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }

    // Display the list
    public void display() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("null");
    }

    // Delete a node with a specific value
    public void deleteNode(int value) {
        if (head == null) return;

        if (head.data == value) {
            head = head.next;
            return;
        }

        Node temp = head;
        while (temp.next != null && temp.next.data != value) {
            temp = temp.next;
        }

        if (temp.next != null) {
            temp.next = temp.next.next;
        }
    }
}

উদাহরণ:

public class Main {
    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        list.insertAtEnd(10);
        list.insertAtEnd(20);
        list.insertAtEnd(30);

        list.display();  // Output: 10 -> 20 -> 30 -> null

        list.deleteNode(20);
        list.display();  // Output: 10 -> 30 -> null
    }
}

ব্যাখ্যা:

• Node class: প্রতিটি নোডে ডেটা এবং পরবর্তী নোডের রেফারেন্স থাকে।
• insertAtEnd: একটি নতুন নোডকে তালিকার শেষে ইনসার্ট করার জন্য ব্যবহৃত হয়।
• deleteNode: একটি নির্দিষ্ট মানের নোড মুছে ফেলার জন্য ব্যবহৃত হয়।
• display: লিস্টটি কনসোলে প্রিন্ট করে।

2. Doubly Linked List

Doubly Linked List হলো একটি লিঙ্কড লিস্ট যেখানে প্রতিটি নোডে দুটি পয়েন্টার থাকে:

• Data: নোডের ডেটা।
• Next: পরবর্তী নোডের রেফারেন্স।
• Previous: পূর্ববর্তী নোডের রেফারেন্স।

Doubly Linked List এর কাঠামো:

// Doubly Linked List Node class
class DoublyNode {
    int data;
    DoublyNode next;
    DoublyNode prev;

    // Constructor
    public DoublyNode(int data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

// Doubly Linked List class
class DoublyLinkedList {
    DoublyNode head;

    // Constructor
    public DoublyLinkedList() {
        this.head = null;
    }

    // Insert at the end
    public void insertAtEnd(int data) {
        DoublyNode newNode = new DoublyNode(data);
        if (head == null) {
            head = newNode;
            return;
        }
        DoublyNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
        newNode.prev = temp;
    }

    // Display the list
    public void display() {
        DoublyNode temp = head;
        while (temp != null) {
            System.out.print(temp.data + " <-> ");
            temp = temp.next;
        }
        System.out.println("null");
    }

    // Delete a node with a specific value
    public void deleteNode(int value) {
        if (head == null) return;

        if (head.data == value) {
            head = head.next;
            if (head != null) {
                head.prev = null;
            }
            return;
        }

        DoublyNode temp = head;
        while (temp != null && temp.data != value) {
            temp = temp.next;
        }

        if (temp != null) {
            if (temp.next != null) {
                temp.next.prev = temp.prev;
            }
            if (temp.prev != null) {
                temp.prev.next = temp.next;
            }
        }
    }
}

উদাহরণ:

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();
        list.insertAtEnd(10);
        list.insertAtEnd(20);
        list.insertAtEnd(30);

        list.display();  // Output: 10 <-> 20 <-> 30 <-> null

        list.deleteNode(20);
        list.display();  // Output: 10 <-> 30 <-> null
    }
}

ব্যাখ্যা:

• DoublyNode class: প্রতিটি নোডে data, next, এবং prev পয়েন্টার থাকে।
• insertAtEnd: নতুন নোডকে তালিকার শেষে যোগ করে এবং পূর্ববর্তী নোডের রেফারেন্স আপডেট করে।
• deleteNode: একটি নির্দিষ্ট মানের নোড মুছে ফেলে এবং পূর্ববর্তী এবং পরবর্তী নোডগুলির পয়েন্টার সঠিকভাবে আপডেট করে।
• display: তালিকার উপাদানগুলো প্রদর্শন করে।

3. Singly Linked List vs Doubly Linked List

সারাংশ

• Singly Linked List একটি লিনিয়ার ডেটা স্ট্রাকচার যেখানে প্রতিটি নোড পরবর্তী নোডের রেফারেন্স ধারণ করে। এটি এক দিকে ট্রাভার্স করা সম্ভব এবং কম মেমরি ব্যবহার করে।
• Doubly Linked List আরো উন্নত ডেটা স্ট্রাকচার যেখানে প্রতিটি নোডের দুটি পয়েন্টার (next এবং prev) থাকে। এটি উভয় দিকে ট্রাভার্স করা সম্ভব এবং বেশিরভাগ ক্ষেত্রে দ্রুত ইনসার্ট এবং ডিলিট অপারেশন সাপোর্ট করে।

উপরের উদাহরণগুলো Singly Linked List এবং Doubly Linked List-এর মধ্যে পার্থক্য, ব্যবহার এবং তাদের কার্যকারিতা বুঝতে সাহায্য করে।

Circular Linked List হল একটি লিঙ্কড লিস্টের একটি ভেরিয়েন্ট, যেখানে লিঙ্কড লিস্টের শেষ নোড প্রথম নোডের সাথে সংযুক্ত থাকে, অর্থাৎ এটি একটি লুপ তৈরি করে। এতে head এবং tail এর মধ্যে কোন পার্থক্য থাকে না, এবং আপনি লিস্টের শেষে পৌঁছানোর পর পুনরায় প্রথম নোডে ফিরে আসতে পারেন।

এটি সাধারণত এমন পরিস্থিতিতে ব্যবহৃত হয় যেখানে ডাটা একত্রিত করা হয় এবং পুনরাবৃত্তি/সাইক্লিক্যাল অ্যাক্সেস প্রয়োজন। উদাহরণস্বরূপ, round-robin scheduling বা buffer management সিস্টেমে এটি ব্যবহৃত হয়।

1. Circular Linked List এর কাঠামো

একটি সাধারণ Circular Linked List তে নোডগুলো সাধারণত দুটি অংশে বিভক্ত:

1. Data: প্রতিটি নোডে যে ডাটা রয়েছে।
2. Next: পরবর্তী নোডের রেফারেন্স।

এটি সাধারণ লিঙ্কড লিস্ট থেকে আলাদা কারণ এর last node এর next পয়েন্টার প্রথম নোডের দিকে নির্দেশ করে, যার ফলে এটি সাইক্লিক্যাল হয়ে যায়।

2. Circular Linked List এর সুবিধা

• Looping: এটি লুপিং বা সাইক্লিক্যাল অ্যাক্সেস করতে সাহায্য করে। একবার আপনি লিস্টের শেষ নোডে পৌঁছালে, আপনি আবার প্রথম নোডে ফিরে যেতে পারেন।
• Efficient Traversing: Circular Linked List সাধারণত এমন সিস্টেমে ব্যবহৃত হয় যেখানে ডাটা বারবার রিড বা প্রসেস করার প্রয়োজন হয়।
• No NULL Values: শেষ নোডের পর NULL ভ্যালু থাকে না, বরং এটি সিস্টেমে সাইক্লিক্যাল লুপ তৈরি করে।

3. Circular Linked List এর ব্যবহার

Circular Linked List বিভিন্ন ধরনের প্রোগ্রামে ব্যবহৃত হতে পারে, যেমন:

• Round-Robin Scheduling: এতে প্রতিটি প্রসেসকে সঠিক পরিমাণ সময়ের জন্য প্রসেসিং করার পর, পরবর্তী প্রসেসের জন্য সিরিয়ালভাবে টাস্ক পাঠানো হয়।
• Circular Buffers: ডাটা স্টোরেজের জন্য একটি রিং বাফার ব্যবহার করা হয় যাতে ইনপুট বা আউটপুট সিস্টেম সঠিকভাবে কাজ করতে পারে।
• Gaming Applications: গেমের প্লেয়ারদের মধ্যে টার্ন নেওয়ার জন্য বা ডাটা রাউন্ডরবিনে প্রসেস করার জন্য।

4. Circular Linked List Implementation in Java

এখানে একটি সিম্পল Circular Linked List এর উদাহরণ দেয়া হলো, যেখানে একটি লিঙ্কড লিস্ট তৈরি করা হবে এবং কিছু মৌলিক অপারেশন যেমন ইনসার্ট, ট্র্যাভার্স এবং ডিলিট করা হবে।

4.1. Circular Linked List Class Implementation

class CircularLinkedList {
    // Node class
    class Node {
        int data;
        Node next;
        
        // Constructor
        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    Node head = null;  // Head node of the list
    Node tail = null;  // Tail node of the list

    // Method to insert a new node at the end
    public void insert(int data) {
        Node newNode = new Node(data);

        // If the list is empty, make the new node the head and tail
        if (head == null) {
            head = newNode;
            tail = newNode;
            newNode.next = head; // Point the next of the last node to the head
        } else {
            tail.next = newNode; // Add the new node at the end
            tail = newNode;      // Update the tail to the new node
            tail.next = head;    // Point the next of the new tail node to the head
        }
    }

    // Method to traverse and print the list
    public void traverse() {
        if (head == null) {
            System.out.println("List is empty.");
            return;
        }

        Node temp = head;
        do {
            System.out.print(temp.data + " ");
            temp = temp.next;
        } while (temp != head); // Continue until we circle back to the head
        System.out.println();
    }

    // Method to delete a node from the list
    public void delete(int data) {
        if (head == null) {
            System.out.println("List is empty.");
            return;
        }

        Node temp = head;
        Node prev = null;

        // If the node to be deleted is the head node
        if (temp.data == data) {
            if (head == tail) {  // If there's only one node
                head = tail = null;
            } else {
                head = head.next;
                tail.next = head; // Update tail's next pointer to new head
            }
            System.out.println("Node with data " + data + " deleted.");
            return;
        }

        // Search for the node to be deleted
        do {
            prev = temp;
            temp = temp.next;
        } while (temp != head && temp.data != data);

        // If node is not found
        if (temp == head) {
            System.out.println("Node with data " + data + " not found.");
            return;
        }

        // Delete the node
        prev.next = temp.next;
        if (temp == tail) {
            tail = prev;  // Update tail if it was the last node
        }
        System.out.println("Node with data " + data + " deleted.");
    }
}

public class Main {
    public static void main(String[] args) {
        CircularLinkedList list = new CircularLinkedList();

        list.insert(10);
        list.insert(20);
        list.insert(30);
        list.insert(40);
        list.insert(50);

        System.out.println("Circular Linked List:");
        list.traverse();

        list.delete(30);
        System.out.println("After deleting 30:");
        list.traverse();

        list.delete(10);
        System.out.println("After deleting 10:");
        list.traverse();
    }
}

ব্যাখ্যা:

1. Node Class: একটি Node ক্লাস তৈরি করা হয়েছে যার মধ্যে data এবং next পয়েন্টার রয়েছে।
2. Insert Method: insert(int data) মেথডটি নতুন Node তৈরি করে এবং তাকে সঠিকভাবে Circular Linked List এ যুক্ত করে।
3. Traverse Method: traverse() মেথডটি লিস্টের সমস্ত নোড প্রদর্শন করে, এবং এটি Circular হওয়ায়, head থেকে পুনরায় ঘুরে ফিরে আসে।
4. Delete Method: delete(int data) মেথডটি ডাটা অনুসারে একটি নোড মুছে ফেলে। এটি সঠিকভাবে প্রথম, মধ্য এবং শেষ নোড মুছে ফেলার জন্য প্রোগ্রাম করা হয়েছে।

5. Circular Linked List এর অন্যান্য ব্যবহার

• Round-robin Scheduling: এটি একটি সাধারণ ব্যবহার যেখানে ডাটা বা প্রক্রিয়াগুলি একটি নির্দিষ্ট অর্ডারে একে অপরকে সুইচ করে।
• Circular Buffering: সিস্টেমে ডাটা স্টোরেজ যেখানে ডাটা পুনরাবৃত্তি হয় এবং সীমিত জায়গায় সঞ্চিত থাকে।
• Music Playlist: প্লে লিস্টে গান চলার পর প্লে লিস্ট আবার প্রথম গান থেকে শুরু হতে পারে।

সারাংশ

Circular Linked List একটি বিশেষ ধরনের লিঙ্কড লিস্ট যেখানে শেষ নোডটি প্রথম নোডের সাথে যুক্ত থাকে। এটি round-robin scheduling, buffer management, এবং gaming applications এর মতো বিভিন্ন পরিস্থিতিতে ব্যবহৃত হয়। Java তে Circular Linked List তৈরি করার জন্য আমরা Node এবং CircularLinkedList ক্লাস ব্যবহার করেছি, এবং ডাটা ইনসার্ট, ট্র্যাভার্স এবং ডিলিট অপারেশনগুলো দেখানো হয়েছে।

Linked List একটি ডাটা স্ট্রাকচার যা আংশিকভাবে বা সম্পূর্ণরূপে লিন্কড নোড থেকে তৈরি। প্রতি নোডের মধ্যে একটি ডাটা এলিমেন্ট এবং পরবর্তী নোডের জন্য একটি রেফারেন্স থাকে। এটি অ্যারে থেকে আলাদা, কারণ এখানে ফিক্সড সাইজের ডাটা স্টোরেজ নেই এবং এটি dynamic memory allocation ব্যবহার করে। Linked List বিশেষত ডাটা ইনসার্ট এবং ডিলিট করার ক্ষেত্রে খুব কার্যকরী।

এই গাইডে, আমরা Linked List এর কিছু মৌলিক অপারেশন (যেমন Insertion, Deletion, এবং Traversal) জাভা দিয়ে কিভাবে বাস্তবায়ন করা যায় তা দেখব।

1. Linked List Definition

লিঙ্কড লিস্টের একটি সাধারণ গঠন হল:

• Node: একটি নোডের দুটি অংশ থাকে - data এবং next (যা পরবর্তী নোডের রেফারেন্স বা পয়েন্টার থাকে)।
• Head: লিঙ্কড লিস্টের প্রথম নোডটি head নামে পরিচিত। এটি লিস্টের সমস্ত অপারেশন পরিচালনার জন্য ব্যবহার করা হয়।

public class LinkedList {
    Node head;  // Head of the list

    // Linked List Node
    static class Node {
        int data;
        Node next;

        // Constructor
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
}

এখানে, Node ক্লাসের মধ্যে data এবং next রয়েছে। head হল লিঙ্কড লিস্টের প্রথম নোড।

2. Insertion in Linked List

Insertion হলো লিঙ্কড লিস্টের মধ্যে নতুন নোড যোগ করা। আমরা তিনটি মৌলিক ইনসারশন অপারেশন করতে পারিঃ

1. At the beginning (Start)
2. At the end (End)
3. At a specific position

2.1. Insertion at the Beginning

public void insertAtBeginning(int data) {
    Node newNode = new Node(data);
    newNode.next = head;  // Point the new node's next to current head
    head = newNode;  // Move head to point to the new node
}

এখানে, নতুন নোডটি প্রথমে ইনসার্ট করা হয় এবং head পয়েন্টারটি নতুন নোডের দিকে পরিবর্তিত হয়।

2.2. Insertion at the End

public void insertAtEnd(int data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = newNode;  // If the list is empty, make the new node the head
        return;
    }
    Node last = head;
    while (last.next != null) {
        last = last.next;  // Traverse to the last node
    }
    last.next = newNode;  // Make the last node point to the new node
}

এখানে, আমরা লিস্টের শেষ নোডে পৌঁছানোর জন্য একটি লুপ ব্যবহার করি এবং তারপর নতুন নোডকে যুক্ত করি।

2.3. Insertion at a Specific Position

public void insertAtPosition(int data, int position) {
    if (position < 0) return;

    Node newNode = new Node(data);
    if (position == 0) {
        newNode.next = head;
        head = newNode;
        return;
    }

    Node current = head;
    for (int i = 0; current != null && i < position - 1; i++) {
        current = current.next;  // Traverse to the position before the desired position
    }

    if (current == null) {
        System.out.println("Position out of range.");
        return;
    }

    newNode.next = current.next;
    current.next = newNode;  // Insert the new node at the specified position
}

এখানে, নির্দিষ্ট পজিশনে ইনসার্ট করতে একটি লুপ ব্যবহার করা হয় এবং নতুন নোডটি যুক্ত করা হয়।

3. Deletion in Linked List

Deletion হলো লিঙ্কড লিস্ট থেকে একটি নোড মুছে ফেলা। আমরা তিনটি মৌলিক ডিলিশন অপারেশন করতে পারিঃ

1. At the beginning (Start)
2. At the end (End)
3. At a specific position

3.1. Deletion at the Beginning

public void deleteAtBeginning() {
    if (head == null) {
        System.out.println("List is empty.");
        return;
    }
    head = head.next;  // Move head to the next node
}

এখানে, head পয়েন্টারটি এক সেল সামনে সরানো হয়, যা আগের প্রথম নোডকে বাদ দেয়।

3.2. Deletion at the End

public void deleteAtEnd() {
    if (head == null) {
        System.out.println("List is empty.");
        return;
    }
    if (head.next == null) {
        head = null;  // If only one node exists, set head to null
        return;
    }

    Node secondLast = head;
    while (secondLast.next != null && secondLast.next.next != null) {
        secondLast = secondLast.next;  // Traverse to the second last node
    }
    secondLast.next = null;  // Remove the last node
}

এখানে, শেষ নোডটি বাদ দেওয়ার জন্য প্রথম থেকে শেষের দিকে একবার পুরো লিস্ট পার করে দ্বিতীয় শেষ নোডে পৌঁছানো হয় এবং তার পরবর্তী নোডকে null সেট করা হয়।

3.3. Deletion at a Specific Position

public void deleteAtPosition(int position) {
    if (head == null) {
        System.out.println("List is empty.");
        return;
    }

    if (position == 0) {
        head = head.next;  // Remove the head
        return;
    }

    Node current = head;
    for (int i = 0; current != null && i < position - 1; i++) {
        current = current.next;  // Traverse to the node just before the one to delete
    }

    if (current == null || current.next == null) {
        System.out.println("Position out of range.");
        return;
    }

    current.next = current.next.next;  // Remove the node at the specified position
}

এখানে, নির্দিষ্ট পজিশনে নোড মুছে ফেলা হয়। প্রথমে সঠিক পজিশনে পৌঁছানো হয় এবং তার পরবর্তী নোডকে current.next.next তে পয়েন্ট করা হয়।

4. Traversal in Linked List

Traversal হল লিঙ্কড লিস্টে সকল নোড দেখার একটি প্রক্রিয়া। এটি সাধারণত লিস্টের প্রথম নোড থেকে শুরু করে একে একে প্রতিটি নোডে পৌঁছানো হয়।

public void traverse() {
    if (head == null) {
        System.out.println("List is empty.");
        return;
    }
    Node current = head;
    while (current != null) {
        System.out.println(current.data);  // Print data of each node
        current = current.next;  // Move to the next node
    }
}

এখানে, head থেকে শুরু করে প্রতিটি নোডের ডাটা প্রিন্ট করা হয়, এবং পরবর্তী নোডে চলে যাওয়া হয় যতক্ষণ না লিস্টের শেষ নোডে পৌঁছানো হয়।

5. Complete Linked List Implementation Example

এখন, আমরা একটি সম্পূর্ণ Linked List ক্লাস দেখব, যা Insertion, Deletion, এবং Traversal অপারেশনগুলি অন্তর্ভুক্ত করবে।

public class LinkedList {
    Node head;  // Head of the list

    // Linked List Node
    static class Node {
        int data;
        Node next;

        // Constructor
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    // Insert at the beginning
    public void insertAtBeginning(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    // Insert at the end
    public void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = newNode;
    }

    // Delete at the beginning
    public void deleteAtBeginning() {
        if (head == null) {
            System.out.println("List is empty.");
            return;
        }
        head = head.next;
    }

    // Delete at the end
    public void deleteAtEnd() {
        if (head == null) {
            System.out.println("List is empty.");
            return;
        }
        if (head.next == null) {
            head = null;
            return;
        }
        Node secondLast = head;
        while (secondLast.next != null && secondLast.next.next != null) {
            secondLast = secondLast.next;
        }
        secondLast.next = null;
    }

    // Traverse the list
    public void traverse() {
        if (head == null) {
            System.out.println("List is empty.");
            return;
        }
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        list.insertAtBeginning(10);
        list.insertAtBeginning(20);
        list.insertAtEnd(30);
        list.insertAtEnd(40);

        System.out.println("List after insertion:");
        list.traverse();  // Output: 20 -> 10 -> 30 -> 40 -> null

        list.deleteAtBeginning();
        System.out.println("List after deleting from beginning:");
        list.traverse();  // Output: 10 -> 30 -> 40 -> null

        list.deleteAtEnd();
        System.out.println("List after deleting from end:");
        list.traverse();  // Output: 10 -> 30 -> null
    }
}

এখানে, লিঙ্কড লিস্টের Insertion, Deletion, এবং Traversal অপারেশনগুলি একত্রিত করা হয়েছে। এটি একটি মৌলিক Linked List অ্যাপ্লিকেশন যা স্ট্যান্ডার্ড অপারেশনগুলো সিমুলেট করে।

সারাংশ

Linked List জাভাতে ডাটা স্ট্রাকচার হিসেবে খুবই কার্যকরী এবং এটি বিভিন্ন ধরনের Insertion, Deletion, এবং Traversal অপারেশনগুলির জন্য উপযুক্ত। এই গাইডে আমরা তিনটি প্রধান অপারেশন:

1. Insertion: লিঙ্কড লিস্টে নতুন নোড যোগ করা।
2. Deletion: লিঙ্কড লিস্ট থেকে নোড মুছে ফেলা।
3. Traversal: লিঙ্কড লিস্টের প্রতিটি নোড পরিদর্শন করা।

এগুলি বাস্তবায়ন করার মাধ্যমে, আপনি Linked List স্ট্রাকচারের সাথে কাজ করার মৌলিক ধারণা পাবেন এবং জাভাতে এর কার্যকরী ব্যবহার শিখবেন।