জাভাস্ক্রিপ্টে লিঙ্কড লিস্ট (Linked List) ডেটা স্ট্রাকচার

Linked List: ধারণা ও টার্মিনোলজি

Linked List হলো একটি লিনিয়ার ডেটা স্ট্রাকচার যেখানে এলিমেন্টগুলো (নোড) মেমরিতে সटा নয় থাকলে একে অপরের সাথে লিংক/পয়েন্টার দিয়ে সংযুক্ত থাকে। প্রতিটি নোড দুটি অংশ ধারণ করে: Data (মান) এবং Next (পরবর্তী নোডের রেফারেন্স)।

মূল টার্মিনোলজি

টার্ম	বর্ণনা
Node (নোড)	লিংকড লিস্টের প্রতিটি এলিমেন্ট। দুই ফিল্ড থাকে: `data` (মান) এবং `next` (পরবর্তী নোডের রেফারেন্স)।
Link (লিংক)	প্রতিটি `next` রেফারেন্স একটি লিংক। এটি পরবর্তী নোডকে পয়েন্ট করে।
Head (হেড)	লিস্টের প্রথম নোডের রেফারেন্স। এতে লিস্টের এন্ট্রি পয়েন্ট বোঝায়।
Tail (টেইল)	লিস্টের শেষ নোড (সিংগলি লিংকড লিস্টে সাধারণত ট্র্যাক করা হয় না, ডাবলি লিস্টে থাকে)।
Null Terminator	শেষ নোডের `next` হয় `null`, যা লিস্টের শেষ বোঝায়।

ভিজ্যুয়াল রিপ্রেজেন্টেশন

HEAD
  ↓
┌─────────┐    ┌─────────┐    ┌─────────┐    ┌─────────┐
│ Data: 1 │───▶│ Data: 2 │───▶│ Data: 3 │───▶│ Data: 4 │───▶ null
└─────────┘    └─────────┘    └─────────┘    └─────────┘
  Node 1        Node 2        Node 3        Node 4 (Tail)

লিঙ্কড লিস্ট vs অ্যারে

td>মেমরি ওভারহেড

বৈশিষ্ট্য	Array	Linked List
মেমরি অ্যালোকেশন	Contiguous (সटा)	Non-contiguous (বिखরে)
সাইজ	ফিক্সড (স্ট্যাটিক) / ডাইনামিক (JS-এ)	ডাইনামিক (রানটাইমে বড়ানো/ছোটানো যায়)
এক্সেস (Access)	O(1) — ইনডেক্স দিয়ে ডাইরেক্ট	O(n) — ট্রাভার্সাল দিয়ে
ইনসারশন/ডিলিশন (শুরু/মাঝপথ)	O(n) — শিফটিং লাগে	O(1) — শুধু পয়েন্টার চেঞ্জ (রেফারেন্স থাকলে)
কম (শুধু ডেটা)	বেশি (ডেটা + পয়েন্টার)
Cache Locality	ভালো	খারাপ

লিঙ্কড লিস্টের প্রকারভেদ

Singly Linked List: শুধু next পয়েন্টার (ফরওয়ার্ড ট্রাভার্সাল)۔
Doubly Linked List: next + prev পয়েন্টার (ফরওয়ার্ড + ব্যাকওয়ার্ড)۔
Circular Linked List: শেষ নোড প্রথম নোডকে পয়েন্ট করে।

সিম্পল Node ক্লাস (JavaScript)

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

// ব্যবহার
const node1 = new Node(10);
const node2 = new Node(20);
node1.next = node2; // node1 -> node2

console.log(node1.data);     // 10
console.log(node1.next.data); // 20