Singly Linked List এবং Doubly Linked List গাইড ও নোট

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-এর মধ্যে পার্থক্য, ব্যবহার এবং তাদের কার্যকারিতা বুঝতে সাহায্য করে।