Linked List (জাভাস্ক্রিপ্ট || পার্টঃ ২)

Linked List জানার জন্য আগে একটু array এর লিমিটেশন জানতে হবে।

নরমালি কম্পিউটারে ডাটা স্টোর করলে বা কাজ করলে সেগুলো RAM এ জমা হয়। ধরি আমাদের একটা র‍্যাম আছে। এবং এখানে ডাটা রাখবো —

Array হিসেবে রাখলে - array এর একটা বৈশিষ্ঠ হল, Array is a contiguous block of memory. ধরি array তে কিছু ডাটা আছে- [10, 20, 30, 40] । তাহলে সেগুলো সিরিয়ালি এক লাইনে মেমরি বা র‍্যামে জায়গা দখল করবে, এভাবে —

এখন যদি ডাটার পরিমান অনেক বেশি হয়ে যায় তাহলে ? —

এভাবে দুই লাইনে চলে যাবে। কিন্তু array তে এরকম ভাবে দুই লাইনে ডাটা রাখা যায় না। কারন Array is a contiguous block of memory। এটাই array এর একটা লিমিটেশন। এ কারণে array কে properly utilize করা সম্ভব হয়না।

আমাদের মেমরিতে অনেকগুলো জায়গা খালি আছে কিন্তু আমরা এটাকে ব্যবহার করতে পারছি না। সেক্ষত্রে ডাটা লস হয়ে যাচ্ছে বা প্রোগ্রামটাও Crash করতে পারে। এই জায়গাটাতেই আসে Linked List.

Linked List এর মধ্যে ডাটা গুল ছরিয়ে ছিটিয়ে থাকে কিন্তু একটা আরেকটার সাথে Linked অবস্থায় থাকে। নিচে — র‍্যামের মধ্যে ডাটা গুলো ছড়িয়ে ছিটিয়ে আছে কিন্তু একটা আরেকটার সাথে Linked অবস্থায় আছে।

কিভাবে Linked থাকে?

এভাবে একটার সাথে আরেকটা ডাটার address জমা থাকে। ২০ এর address টা store থাকবে ১০ এর কাছে, যাতে ১০ থেকে ২০ এ যাওয়া যায়। আবার ৩০ এর address store করবে ২০, এভাবে একটা ডাটার address আরেকটা ডাটার কাছে স্টোর করা থাকবে। এবং এই ডাটা গুলোকে Linked List e বলব ‘Node’.

Node টা কি?

Node হল একটা অবজেক্ট যার মধ্যে ভ্যালু থাকবে এবং ভ্যালুর সাথে আর কোন ভ্যালু কানেক্টেড আছে তার addressদেখাবে। মানে, এই নোড থেকে যার কাছে যাব সেই নোডের address থাকবে next এর কাছে। next পরবর্তি ভ্যালুকে represent করে।। ধরি আমাদের একটা ভ্যালু আছে ১০ তাহলে Node টা হবে —

Node = {
value: 10,
next: address
}

উপরের এই Node এর ভ্যালু ১০ এবং পরবর্তি ভ্যালুর address কে এখানে next হিসেবে থাকবে। এটাই লিঙ্কড লিস্ট।

ধরি আমাদের মেমরিতে কিছু ডাটা আছে এবং সেই ডাটা গুলো মেমরির নির্দিষ্ট কিছু জায়গায় আছে। যেমন, 100 আছে মেমরির 1 হাজার তম ঘরে, 200 আছে মেমরির 2 হাজার তম ঘরে, 300 আছে 3 হাজার তম ঘরে।

100 ---> 200 ---> 300 
 1k ---   2k ---  3k

এখন এই data গুলোকে একটার সাথে আরেকটার লিংক করাতে হবে । কিভাবে?

ডাটার সাথে আরেকটা ডাটার address গ্রুপিং করে। OOP এর সাহায্যে গ্রুপিং করতে হবে। ১০০ থেকে ২০০ তে যেতে হলে ২০০ এর address কে ১০০ এর সাথে গ্রুপ বানাতে হবে। এভাবে — (100, 2k)

            data = (100,2k) ---> (200,3k) --->(300) --->
 memory location =   1k      ---    2k     ---   3k

এখন, ৩০০ এর পর তো আর ডাটা নেই তাহলে ? যখন শেষে আর কোনো ডাটা থাকবে না তখন address হিসেবে null add হবে।

(100,2k) ---> (200,3k) --->(300, null) --->
 1k      ---    2k     ---   3k

এখানে ৩০০ এর পর কোনো ডাটা নেই তাই ৩০০ এর সাথে পরবর্তি ডাটার address হিসেবে null add হবে। এর মানে ৩০০ এর পরে আর কোনো ডাটা available নেই ।

Now, Linked List এ ফার্স্ট এর ডাটা কে বলা হয় Head এন্ড লাস্ট ডাটা কে বলা হয় Tail. উপরের ডাটা গুলোতে ১০০ হল Head অ্যান্ড ৩০০ হল Tail. উপরের ডাটা গুলোর LInked List টা ভিজুয়ালি হবে এরকম —

LinkedList = {
  value: 100,
  next: {
    value: 200,
    next: {
      value: 300,
      next: null,
    },
  },
};

প্রথম ভ্যালু হিসেবে থাকবে ১০০, আর এটার সাথে next হিসেবে থাকবে 200 এর address.

LinkedList = {
  value: 100,
  next: { address}
};

যেহেতু ২০০ টাও একটা ভ্যালু , তাহলে next হিসেবে আসবে —

LinkedList = {
  value: 100,
  next: { 
  value: 200,
   next: address
}
};

200 এর পর আছে ৩০০। তাহলে ২০০ এর নেক্সট address এ আসবে —

LinkedList = {
  value: 100,
  next: { 
  value: 200,
   next: {
    value: 300,
      next : address
}
}
};

এখন যেহেতু ৩০০ এর পর আর কোন ডাটা নাই সেক্ষেত্রে ৩০০ এর নেক্সট হিসেবে আসবে null.

LinkedList = {
  value: 100,
  next: { 
  value: 200,
   next: {
    value: 300,
      next : null
}
}
};

যতক্ষন না নেক্সট হিসেবে null আসতেছে ততক্ষন পর্ক্সন্ত এটা চলতেই থাকবে। এই Data Structure টাই হল Linked List.

এখন, আমরা Linked List বানাবো -

Linked List বানানোর আগে class use করে আগে Node বানাতে হবে —

class Node {
constructor(value, next = null){
    this.value = value,
    this.next = next
}
}
let node = new Node(100)
console.log(node);

যেহেতু ডাটা গুলো node হিসেবে থাকবে সেহেতু আগে নোড বানাবো, এই Node এর constructor একটা ভ্যালু পাবে আর সেটাকে node বানাবে। এক্ষেত্রে, যেই ভ্যালু টা পাবে সেটাকে ভ্যালু আর পরের ডাটাকে বানাবে এই ভ্যালুর নেক্সট। যদি কোনো ভ্যালু না দেই তাহলে নেক্সট হিসেবে null থাকবে।

উপরের কোড টা কনসোল করলে —

 Node { value: 100, next : null}

এরকম একটা node পাওয়া যাবে। যার ভ্যালু ১০০ আর নেক্সট null. এখন বানাবো Linked List —

class Node {
constructor(value, next = null){
    this.value = value,
    this.next = next
}
}

class LinkedList{
    constructor(value){
        let node = new Node(value)
        console.log(node);
    }
}

let list = new LinkedList(100)

উপরের কোড অনুযায়ী -

একটা ক্লাস নিলাম LinkedList, যার constructor একটা value নিবে ।

let node = new Node(value)
console.log(node);

constructor এর মধ্যে new Node দিয়ে Node Class তাকে invoke করলে উপরের Node class টা একটা Node return করবে। সেই Node কে node variable এর মধ্যে store করে console.log(node) করলে আমরা পাব —

Node { value: 100, next: null }

এখন, এখানে একটা ব্যাপার বুঝতে হবে — যখন আমাদের কাছে ৩ টা ডাটা ১০০ — ২০০ — ৩০০ ছিল তখন Head ছিল ১০০ আর Tail ছিল ৩০০। লিন্তু এখানে একটাই ডাটা তাহলে এটাই হবে Head আর এটাই হবে Tail। এজন্য এখানে যেই node create হয়েছে সেটাকে আমরা বলে দিব তুমিই Head আর তুমিই Tai।

class Node {
constructor(value, next = null){
    this.value = value,
    this.next = next
}
}
class LinkedList{
    constructor(value){
        let node = new Node(value)
        this.head = node
        this.tail = node
    }
}

let list = new LinkedList(100)
console.log(list)

এখন যদি console.log(list) করি তাহলে —

LinkedList {
  head: Node { value: 100, next: null },
  tail: Node { value: 100, next: null } 
}

একটা LinkedList create হয়েছে যার মধ্যে Head নামে একটা property আর Tail নামে আরেকটা property আছে। Head এর value হিসেবে আছে ১০০ আর next হিসেবে null আর Tail এর value হিসেবে আছে 100 আর next হিসেবে আছে null. কারন আমরা এখানে বলে দিছি যখন একটা value থাকবে তখন সেটাই head আর সেটাই Tail.

এখন যদি ১০০ এর পর আরেকটা ডাটা আসে তাহলে?

ধরলাম ২০০ আসছে। তাহলে Head হবে ১০০ আর তার নেক্সট null না হয়ে হবে ২০০ । Tail হবে ২০০ আর তার নেক্সট হবে null. কারন ২০০ এর পর আর ডাটা নাই।

LinkedList {
  head: Node { value: 100, next: 200},
  tail: Node { value: 200, next: null } 
}

এখন আমরা Linked List এর Append method দেখব।

class LinkedList{
    constructor(value){
        let node = new Node(value)
        this.head = node,
        this.tail = node 
    }

    append(value){
        
    }
}

append একটা Method, যেতা একটা input নিবে value হিসেবে।আগের ১০০ আছে সেটার সাথে ২০০ কে append করব। ২০০ কে append করার জন্য approach হবে —

১. ১০০ কে একটা node বানাতে হয়েছিল তেমনই ২০০ কেও আগে একটা node বানাতে হবে। যাতে করে গ্রুপিং করা যায় এবং এটি তার পরবর্তি ডাটাকে হোল্ড করতে পারে।

append(value){
        let node = new Node(value)
    }

২. Tail এর next এ এই node টাকে রেখে দিব। কারন append হয় শেষের দিক থেকে। তাই tail হিসেবে ১০০ আছে , ১০০ এর next এ এই node টাকে রাখবো।

append(value){
        let node = new Node(value)
          this.tail.next = node
    }

৩. এখানে এখনো head and Tail 100 কেই বোঝাচ্ছে। কারন আমরা tail.next এ ২০০ কে রাখছি but Tail কে assign করি নাই। তাই ৩ নাম্বার স্টেপ — Tail টা হবে নতুন node টা।

append(value){
        let node = new Node(value)
          this.tail.next = node
          this.tail = node
    }

এখন যদি ২০০ কে append করি এবং list টা কনসোল করি —

let list = new LinkedList(100)
list.append(200)

তাহলে রেজাল্ট পাব —

LinkedList {
  head: Node { value: 100, next: Node { value: 200, next: null } },
  tail: Node { value: 200, next: null }
}

এখানে দেখা যাচ্ছে Head হিসেবে ১০০ আছে এবং তার next এ ২০০ আছে আর ২০০ এর next এ আছে null. আর Tail হিসেবে আছে ২০০ আর তার next এ আছে null.

এভাবে আমরা যদি আরো ভ্যালুকে append করি —

let list = new LinkedList(100)
list.append(200)
list.append(300)
list.append(400)
list.append(500)
list.append(600)

তাহলে রেজাল্ট পাবো এরকম—

LinkedList {
  head: Node { value: 100, next: Node { value: 200, next: [Node] } },
  tail: Node { value: 600, next: null }
}

যেটাতে দেখা যাচ্ছে Head 100 তার next এ ২০০ আর তার next এ আরো node আছে। আর Tail হয়েছে ৬০০। কারন ৬০০ কে সবার শেষে append করা হয়েছে।

পরবর্তি অংশঃ →

CRUD Operation in Linked List.

Medium