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

Doubly Linked List: Insert Operation (কোনো পজিশনে এলিমেন্ট যোগ)

ডাবলি লিংকড লিস্টে প্রতিটি নোডের দুটি পয়েন্টার থাকে: next (পরবর্তী) এবং prev (পূর্ববর্তী)। ইনসারশন সময় সব লিংক সঠিকভাবে আপডেট করা জরুরি।

Insert Algorithm Steps

1. নতুন Node তৈরি করুন।
2. লিস্ট খালি কিনা চেক করুন — হলে হেড ও টেইল নতুন নোড।
3. পজিশন ০ (হেড) কিনা চেক করুন — হলে হেড আপডেট।
4. অন্যথায়, টার্গেট পজিশন পর্যন্ত ট্রাভার্স করুন (currNode = currNode.next)।
5. লিংক আপডেট করুন (৪টি ধাপ):

• নতুন নোডের next = currNode.next
• পরবর্তী নোডের prev = নতুন নোড (যদি বিদ্যমান থাকে)
• নতুন নোডের prev = currNode
• currNode.next = নতুন নোড

6. টেইল আপডেট করুন (যদি শেষে ইনসার্ট হয়)।

Insert মেথড ইমপ্লিমেন্টেশন

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  // Node Class
  static Node = class {
    constructor(data) {
      this.data = data;
      this.next = null;
      this.prev = null;
    }
  };

  insert(data, position = this.length) {
    const node = new DoublyLinkedList.Node(data);
    this.length++;

    // Case 1: Empty List
    if (this.head === null) {
      this.head = node;
      this.tail = node;
      return this.head;
    }

    // Case 2: Insert at Head (Position 0)
    if (position <= 0) {
      node.prev = null;
      node.next = this.head;
      this.head.prev = node;
      this.head = node;
      return this.head;
    }

    // Case 3: Insert at Middle or Tail
    let iter = 1;
    let currNode = this.head;
    
    // Traverse to position (or last node)
    while (currNode.next !== null && iter < position) {
      currNode = currNode.next;
      iter++;
    }

    // Link Updates
    node.next = currNode.next;           // 1. New -> Next
    if (currNode.next !== null) {        // 2. Next -> New (prev)
      currNode.next.prev = node;
    }
    node.prev = currNode;                // 3. New -> Prev
    currNode.next = node;                // 4. Prev -> New

    // Update Tail if inserted at end
    if (node.next === null) {
      this.tail = node;
    }

    return node;
  }

  // Display Helper
  display() {
    let curr = this.head;
    let output = "";
    while (curr !== null) {
      output += curr.data + " <-> ";
      curr = curr.next;
    }
    console.log(output + "null");
  }
}

টেস্টিং উদাহরণ

const list = new DoublyLinkedList();

list.insert(10);      // Position default (end) -> 10
list.insert(20);      // End -> 10 <-> 20
list.insert(30);      // End -> 10 <-> 20 <-> 30
list.insert(15, 2);   // Position 2 (after 1st) -> 10 <-> 15 <-> 20 <-> 30

list.display();
// আউটপুট: 10 <-> 15 <-> 20 <-> 30 <-> null

ভিজ্যুয়াল: Insert at Position 2

BEFORE:  HEAD → [10] ⇄ [20] ⇄ [30] ← TAIL
                    ↑
                 Position 2 (0-indexed: after 1st node)

STEP 1: Create Node(15)
STEP 2: Traverse to Node(10) [iter=1, position=2]
STEP 3: Link Updates:
  New(15).next = Node(20)
  Node(20).prev = New(15)
  New(15).prev = Node(10)
  Node(10).next = New(15)

AFTER:  HEAD → [10] ⇄ [15] ⇄ [20] ⇄ [30] ← TAIL

Edge Cases Handled

• Empty List: হেড ও টেইল নতুন নোড।
• Position 0: হেড ইনসারশন, পুরানো হেডের prev আপডেট।
• Position >= Length: টেইলে ইনসার্ট (ডিফল্ট বিহেভিয়ার)۔
• Middle Insert: ৪টি লিংক আপডেট।
• Tail Update: নতুন নোড যদি শেষে যায়, টেইল পয়েন্টার মুভ।

Default Parameter: position = this.length

পজিশন না দিলে ডিফল্টভাবে শেষে (this.length) ইনসার্ট হয়। এটি append() এর মতো কাজ করে।