CRUD Operation with Linked List || ( জাভাস্ক্রিপ্ট || পার্টঃ ৩ )

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

এখন যদি 100 এর পর আরেকটা ডাটা আসে বা আরেকটা ডাটাকে লিস্ট এ পুশ করতে হয়?

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

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

Append:

এখন আমরা 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 হিসেবে। আগের 100আছে সেটার সাথে 200 কে append করব। 200 কে append করার জন্য approach হবে —

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

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

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

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

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

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

এখন যদি 200 কে 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 হিসেবে 100 আছে এবং তার next এ 200 আছে আর 200 এর next এ আছে null. আর Tail হিসেবে আছে 200 আর তার 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 এ 200 আর তার next এ আরো node আছে। আর Tail হয়েছে 600। কারন 600 কে সবার শেষে append করা হয়েছে। এই Append Method এর মাধ্যমে CRUD এর Create টা করা হল।

Prepend:

Append শেখার পর এখন শিখবো Prepend করা। Prepend মানে পুর্বে append করা বা একটা নাম্বারের আগে আরেকটা নাম্বার বসানো।

ধরি আমাদের লিস্ট এ 3 টা ভ্যালু আছে। 10, 20, 30। এখন আমরা এখানে Prepend করব 5। এজন্য 5কে আগে নতুন একটা node হিসেবে create করতে হবে। আমরা চাচ্ছি 5 কে সবার আগে বসাব। এভাবে —

এখানে, 10 এর next এ থাকবে 20 এর address. 20 এর next এ থাকবে 30 এর address আর 30 এর পর কিছুই নেই তাই null. এখানে Head 10 আর Tail 30.

যেহেতু 5 কে Head এর সামনে বসাচ্ছি তাহলে 5 এর next এ থাকবে 10 এর address । তাহলে new node যেটা create হয়েছে সেটার next এ Head কে রেখে দিলেই হয়ে যাচ্ছে। —

→ newNode.next = head;

এখানে আরেকটা জিনিস বাকি আছে। Head and Tail কিন্তু আগের জায়গাতেই আছে। এগুল কিন্তু change করা হয়নাই। এখন, new Node টাকে করতে হবে head, আর Tail ওখানেই থাকবে। Now, 10 is no longer head. 5 কে head বানাবো। গতবার append করার সময় tail কে update করতে হয়েছিল এবার head কে update করতে হবে।

→ this.head = new Node

তাহলে, আমাদের স্টেপ হল ৩ টা —

1. Create New Node
2. ‘new node’ next will be head
3. update head

এখন আসি Code e.

   prepend(value){

    }

আগের মত prepend() নামে একটা method নিবো, যেটা একটা value নিবে এবং সবার সামনে বসাবে।

  prepend(value){
        // 1. create new node
        let node = new Node(value)
        // 2. new node next will be head
        node.next = this.head
        // 3. update head 
        this.head = node
    }

এভাবে প্রতিটা স্টেপ অনুযায়ী আগে new node create করলাম, তারপর new node এর next এ head টাকে রেখে দিলাম। তারপর head টাকে update করে দিলাম। এখন → list.prepend(5)

let list = new LinkedList(10)
list.append(20)
list.append(30)
list.prepend(5)

console.log(list);

console.log() করলে পাবো →

LinkedList {
  head: Node { value: 5, next: Node { value: 10, next: [Node] } },
  tail: Node { value: 30, next: null }
}

হয়ে গেছে prepend. 5 কে prepend করেছি, 5 Head হিসেবে সবার সামনে বসে গেছে।

Code:

এতক্ষণ Append , Prepend করে node Create এবং Update করলাম। আমরা নোড গুলোকে আগে এবং পরে insert করলাম। কিন্তু এমনও সিচুয়েশন হতে পারে যেখানে node কে মাঝখানে বসাতে হতে পারে। এজন্য শিখতে হবে Traversing। Linked List এ কিভাবে Travers করে সেটা এখন শিখতে হবে। একবার Travers করতে শিখে গেলে Linked List এর যেকোনো জায়গায় যেতে পারবো।

Traversing:

Traversing এর কাজ হল এক জায়গা থেকে আরেক জায়গায় যাওয়া। Simply যদি একতা array’র কথা বলি, তাহলে array এর index ধরে ধরে, এক index থেকে আরেক index এ যাওয়াই Traversing. নিচের array তে 1,2,3,4,5,6,7 আছে। যার index ধরে ধরে আমরা একটা থেকে আরেকটায় যেতে পারি। যখন 1 থেকে 2 তারপর 3 তারপর 4 এ যেতে পারছি তার মানে আমরা 4 নাম্বার ভ্যালুর index এর access পেয়ে গেছি। ঠিক এই কাজটাই করতে হবে Linked List এ।

কিন্তু Linked List এ ডাটা গুলো পরপর নেই কিন্তু Connected অবস্থায় আছে। 1 এর পর 2 তারপর 3 তারপর 4 এভাবে Connected আছে। এখন এই head থেকে আমাদের শুরু করতে হবে। head থেকে যাব তারপরের টায়, সেখান থেকে তারপরের টায়, আবার সেখান থেকে পরেরটায়। এভাবে যেতে যেতে যখন null আসবে তখন যাওয়া বন্ধ করে দিব।

এখন আমরা Travers করতে পারছি কী না তা চেক করার জন্য print করব। print নামে একতা method নিয়ে।

 print(){

    }

লিস্টের সবগুলো ডাটাকে প্রিন্ট করার জন্য For Loop বা While Loop চালাতে পারি। For Loop চালাব না কারণ আমরা ধরি আমরা জানিনা কতগুলো ডাটা আছে বা ডাটার Length কত। কয়েক কোটি ডাটাও থাকতে পারে। যেহেতু Linked List এর Length জানিনা তাই While Loop ব্যবহার করবো।

তাহলে এখানে লুপটা কতক্ষন চলবে? যতক্ষন না data is not equal to null হবে ততক্ষন। এর মানে যতক্ষন ডাটা থাকবে ততক্ষন চলবে। যখন ডাটা null হবে তখন লুপটা থেমে যাবে। আর যেহেতু head থেকেই লুপটা শুরু হবে তাই data হিসেবে this.head কে data variable এ নিয়ে নিলাম।

print(){
let data = this.head
while(data != null){

}
   }

এখন লুপটা চলতে শুরু করলে প্রথমে head এ যাবে, তখন সেটাকে প্রিন্ট করে ফেলব। console.log করব data.value কে । console.log(data.value)। কারন এখানে data বলতে পুরো নোড টাকে বোঝাবে আর ভ্যালু টা থাকবে data.value তে।

print(){
let data = this.head
while(data != null){
console.log(data.value)
}
   }

এরপরে আরেকটা কাজ আছে। যদি লুপটা এভাবে চলতে থাকে তাহলে প্রথম ডাটা টাই ডাটা হিসেবে থেকে যাবে আর শুধু সেটাই প্রিন্ট হবে। তাই ডাটা টাকে সামনের দিকে আগায় দিতে হবে। কিভাবে আগাবো? যেই ডাটা আগে ছিল সেটাতে তার পরের ডাটা টা রেখে দিব। data = data.next । তাহলে data variable , next ডাটা টাতে চলে যাবে। এভাবে এই ডাটা টা একটার পর আরেকটায় একঘর করে আগাতে থাকবে। যখন দেখবে আর কোনো ভ্যালু নাই (data != null) তখন লুপটা বন্ধ হয়ে যাবে।

print(){
let data = this.head
while(data != null){
console.log(data.value)
data = data.next
}
   }

এখন list.print() করলে লুপটা চলবে আর ডাটা গুলো প্রিন্ট হবে।

list.print()

এভাবেঃ —

Insertion In a Position:

ধরি আমাদের কাছে একটা লিস্ট আছে। এতে 4 টা ডাটা আছে। 10,20,30,40। এখন এখানে নতুন এজটা node (25) create করে সেটাকে এই ডাটাগুললোর 3 নাম্বার পজিশনে Insert করতে হবে।

যার Output টা হবে এরকম -

তাহলে এটা করতে কি রকতে হবে?

প্রথমত ১ টা নতুন node create করতে হবে। তারপর যেই পজিশনে এই node টা Insert করতে হবে তার Previous value কে ধরতে হবে। Position দেয়া আছে 3, তাহলে previous value হবে 3–1 । এখানে previous value 20 । তারপর previous value’র next এ new node তাকে রাখতে হবে। prev.next = node । এবং বর্তমান যেই node (25) আছে সেটাকে previous.next এর সাথে connect করে দিব। এখানে previous ছিল ২০ আর previous.next হল ৩০।

এখন কোডঃ

আগের মতই একটা method নিতে হবে। যেহেতু insert করছি সেহেতু insertAt() নিলাম। এবং একটা value and একটা position দেয়া হবে যে কত তম পজিশনে value টা insert করতে হবে। তাই প্যারামিটার হিসেবে value and position নিলাম।

insertAt(value, position){
        
    }

এখন, যদি 5 দিয়ে বলা হয় 1 নাম্বার পজিশনে বসাতে তাহলে আমার লুপ চালানোর দরকার নাই। কারন এতা prepend করলেই হয়ে যাবে। So, যদি position === 1 হয় তাহলে this.prepend(value)।

 insertAt(value, position){
        if(position === 1){
            this.prepend(value)
        }
    }

এখন list.insertAt(25, 1) করলে আমরা দেখব —

25 prepend হয়ে সবার আগে বসে গেছে।

এখন যদি 50 দিয়ে বলা হয় 6নাম্বার পজিশনে বসাতে হবে। তাহলে append করলেই হয়ে যাবে। কিন্তু এখানে একটা ঝামেলা আছে। আমরা 5 টা ডাটা আছে দেখে এখন বুঝতে পারছি ৬ নাম্বার পজিশনটাই Last পজিশন, কিন্তু কোটি কোটি ডাটা থাকলে তখন Last পজিশনটা জানতে পারতাম না। তাই node যখন create করব তখন থকেই length নামে একটা variable maintain করলে এই সমস্যার সমাধান করা যাবে। যখন একটা মাত্র নোড create হবে তখন length টা থাকবে 1 । তাই → this.length = 1।

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

এরপর প্রত্যেকবার যখন append বা prepend হবে তখন length , 1 করে বারবে।

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

        this.length++
    }

  prepend(value){
        let node = new Node(value)
        node.next = this.head
        this.head = node

        this.length++
    }

এখন এই list টা প্রিন্ট করলে length টা পেয়ে যাবো।—

LinkedList {
  head: Node { value: 25, next: Node { value: 5, next: [Node] } },
  tail: Node { value: 30, next: null },
  length: 5
}

এখানে length : 5 , এখন যদি 80 দিয়ে বলা হয় 6 নাম্বার পজিশনে রাখতে, list.insertAt(80, 6) ?

তাহলে append করে দিলেই হয়ে যাবে। প্রথমত else if এ চলে যাব। যদি position length এর থেকে ১ বেশি হয় তাহলে append method টা কল হবে।

else if (position === this.length + 1){
this.append(value)
}

 insertAt(value, position){
        if(position === 1){
            this.prepend(value)
        } else if (position === this.length + 1){
            this.append(value)
        }
    }

এখন এটা প্রিন্ট করলে পাবো —

25
5
10
20
30
80
LinkedList {
  head: Node { value: 25, next: Node { value: 5, next: [Node] } },
  tail: Node { value: 80, next: null },
  length: 6
}

এখানে ৮০ টা ৬ নাম্বার পজিশনে append হয়ে গেছে।

এখন Insert at any position. এটা কিভাবে করব সেটা উপরে লিখে রেখেছি। else নিয়ে -

1. Ceate The node
2. Find Previous node.

   insertAt(value, position){
        if(position === 1){
            this.prepend(value)
        } else if (position === this.length + 1){
            this.append(value)
        } else {
            // 1. Ceate The node
            let node = new Node(value)
            // 2. Find previous node
            let prevNode = this.findNode(position - 1);
             console.log({prevNode: prevNode});
        }
    }

    findNode(n){
        
    }

প্রথমত একতা নতুন node ক্রিয়েট করলাম। এরপর previous node টা খুজে বের করতে হবে। তাই আলাদা একটা findNode method নিলাম। যেটা একটা নাম্বার নিয়ে previous node টা খুজে বের করবে। এবং সেই node টা store করব prevNode variable এ → let prevNode = this.findNode(position — 1)।

store করার সময় findNode এ (position — 1) pass করে দিব।কারন আগেই বের করেছি যে previous node টা new node এর আগের পজিশনে থাকবে।

এখন findNode মেথড টা previous node কে কিভাবে বের করবে?

findNode(n) {
    let count = 1
    let data = this.head;
    while (data != null) {
        if (count == n) break;
      count++;
      data = data.next;
    }
    return data
  }

এখানে previous node কে খুজে পেতে একটা লুপ চালাতে হবে। আগের print method এর মতই একটা লুপ চলবে । একট াcount variable নিয়ে সেখানে প্রত্যেক লুপে এক এক করে বারবে আর প্রত্যেকবার count++ হবে।

যখন count এর মান n (position) এর সমান হবে তখন লুপ টা break করে দিবো।

এরপর prevNode টা কনসোল করলে previous node টা পেয়ে যাবো।

insertAt(value, position){
        if(position === 1){
            this.prepend(value)
        } else if (position === this.length + 1){
            this.append(value)
        } else {
            // 1. Ceate The node
            let node = new Node(value)
            // 2. Find previous node
            let prevNode = this.findNode(position - 1);
             console.log({prevNode: prevNode});
        }
    }

let list = new LinkedList(10);
list.append(20);
list.append(30);
list.prepend(5);
list.insertAt(80, 4);

এখানে 5, 10, 20, 30 আছে। list.insertAt(80, 4) করলে —

{ prevNode: Node { value: 20, next: Node { value: 30, next: null } } }

পজিশন 4 এর previous node 20 কে পাচ্ছি।

এখন 3 নাম্বার স্টেপ →

new node হল 80 আর previous node হল 20 । যেহেতু 20 এবং 30 এর মাঝখানে 80 কে বসাতে হবে। সেহেতু new node এর next টা হবে 30 যেটা আগে previous node এর next ছিলো।

// 3. previous node next will be new node next

      newNode.next = prevNode.next;

এরপর ৪ নাম্বার স্টেপ এ →

previous node এর next টা হবে new Node

এবং সবশেষে length টা ++ হবে। this.length ++

// 4. previous node next will be new node next

      prevNode.next = newNode
       this.length ++

এখন List টা প্রিন্ট করলে দেখব —

80, 4 নাম্বার পজিশনে insert হয়েছে।

code:

insertAt(value, position) {
    if (position === 1) {
      this.prepend(value);
    } else if (position === this.length + 1) {
      this.append(value);
    } else {
      let newNode = new Node(value);
      let prevNode = this.findNode(position - 1);
      newNode.next = prevNode.next;
      prevNode.next = newNode
      this.length ++
    }
  }

  findNode(n) {
    let count = 1;
    let data = this.head;
    while (data != null) {
      if (count == n) break;
      count++;
      data = data.next;
    }
    return data;
  }

Delete:

কোনো পজিশনের ডাটা Delete করতে হলে যা করতে হবে —

ধরি আমার কাছে 4 টা ডাটা আছে- 10,20,30,40. এখন এখান থেকে বলা হল 2 অথবা 3 নাম্বার পজিশনের ডাটা টা Delete করতে হবে। অথবা বলা হতে পারে প্রথম বা শেষ ডাটা টা Delete করতে। তাহলে কি করব?

ধরি আমাদের কাছে আছে 4 টা ডাটা। 10,20,30,40. এখনে Head 10 আর Tail 40.

যখন 1 নাম্বার পজিশনের ডাটা Delete করব তখন Head টা হবে তার পরের ডাটা টা বা, 20 । head = head.next

তাহলে প্রথম ধাপে এটা করার পর , যদি শেষ ডাটা টা delete করতে বলা হয়?

তাহলে Tail এক ঘর বাম দিকে আগায় আসবে। Tail টা হয়ে যাবে 40 থেকে 30. বা, tail = tail.previous।

এরপর আসবে any position এর ডাটা Delete. আগেই Insert at position এর মাধ্যমে previous node খুজে পেতে একটা findNode মেথড এর সাহায্য নিয়ে previous node খুজে বের করেছি। এখন সেই findNode এর সাহায্যেই previous node টা বের করবো যাতে Data access করা যায়। এখন previous node এর পরের ডাটাটাই Delete করতে হবে। তাই previous node এর next হবে তার next ডাটা টা। previousNode.next = previousNode.next.next.

এই তিনটা স্টেপ কে এখন Code করব-

ধাপ ১।

১ নাম্বার পজিশনের ডাটা ডিলিট করার সময় this.head = this.head.next

if (position === 1) {
      this.head = this.head.next
}

ধাপ 2।

শেষ পজিশনের ডাটা ডিলিট করার সময় previous node টা খুজে বের করে সেটাকেই tail করে দিবো। this.tail = prevNode

else if (position === this.length + 1) {
      let prevNode = this.findNode(position - 1);
      this.tail = prevNode

ধাপ 2।

প্রথম এবং শেষ বাদে অন্য যেকোনো পজিশনের ডাটা Delete করার সময় previous node টা খুজে বের করে prevNode এর next এ, তার next এর next কে রেখে দিব। prevNode.next = prevNode.next.next;

else {
      let prevNode = this.findNode(position - 1);
      prevNode.next = prevNode.next.next;
      this.length --
    }

এরপর প্রত্যেকবার delete এ যেহেতু 1 টা করে ডাটা কমে যাবে এজন্য Length টাও কমে যাবে। তাই length — — হবে।

Code:

 delete(position){
     if (position === 1) {
      this.head = this.head.next
    } 
    else if (position === this.length + 1) {
      let prevNode = this.findNode(position - 1);
      this.tail = prevNode
    } 
    else {
      let prevNode = this.findNode(position - 1);
      prevNode.next = prevNode.next.next;
      this.length --
    }
  }

let list = new LinkedList(20);
list.append(30);
list.append(40);
list.prepend(10);
list.delete(1)
list.print();

Update:

Update টা kind of easy ই বলা যায়। এখানে একটা পজিশন দিয়ে দেয়া হবে আর একএকটাতা given value দিয়ে বলা হবে ঐ পজিশনের ডাটা টা change করে given value কে বসাতে । Edit করা যাকে বোঝায়।

আগে findNode method দিয়ে previous node টাকে খুজে বের করেছি কিন্তু এখন আর এটা করতে হবে না। এখন যে পজিশন দেয়া হবে সেই পজিশনকেই বের করে সেটাই update করতে হবে। ধরি 2 নাম্বার পজিশনে বলা হল 100 কে রাখতে। তাহলে 2 নাম্বার পজিশনে থাকা 20 মুছে value হিসেবে 100 বসবে।

তাহলে, findNode method থেকে যেই node টা পাবো সেটাকে foundNode হিসেবে নিব। এবং foundNode এর value কে পরিবর্তন করে givenValue দিয়ে দিবো।

স্টেপ ১।

→ Create update method. and take givenValue and position as parameters.

 update(givenValue, position){
   
  }

স্টেপ ২।

→ find the node and store it in a variable

let foundNode = this.findNode(position)

স্টেপ ৩ ।

→ update foundNode value to givenValue

foundNode.value = givenValuej

Now, invoke the update method by giving value and position.

list.update(100,1)