লিঙ্কড লিস্ট হচ্ছে একধরনের লিনিয়ার ডাটা স্ট্রাকচার যেখানে ডাটা একটার পর একটা সিরিয়ালি থাকে। তবে লিঙ্কড লিস্ট Consecutive Memory Location ফলো করে না। অর্থাৎ , মেমরিতে সিরিয়ালি ডাটাগুলো স্টোর হয় না। মেমরি তে বিভিন্ন জায়গায় ডাটা স্টোর হয়।

লিঙ্কড লিস্ট ডাটা স্ট্রাকচারে দুইটি ভ্যারিয়েবল থাকে। একটি হচ্ছে headNode এবং অন্যটি হচ্ছে tailNode। headNode দ্বারা লিঙ্কড লিস্টে অ্যাড করা প্রথম নোডটিকে বুঝানো হয় এবং tailNode দ্বারা লিঙ্কড লিস্টে অ্যাড করা শেষ নোডটিকে বুঝানো হয়। headNode এবং tailNode নোডের মেমরি লোকেশন স্টোর করে রাখে। এখন লিঙ্কড লিস্টের আরেকটু ভেতরে যাওয়া যাক।

লিঙ্কড লিস্ট ডাটা স্ট্রাকচারে প্রতিটা ডাটা বা এলিমেন্ট জানে তার আগে কোন ডাটা আছে এবং তারপরে কোন ডাটা আছে। এখন , আমরা সচরাচর যেসব Number , String বা অন্য যেকোন ক্যারেক্টার ইউজ করি না কেন সেখানে আলাদা কোন স্পেস নেই যেখানে সে তারপরে কে আছে তার রেফারেন্স হোল্ড করে রাখতে পারবে। আরেকটু সিমপ্লি বললে , ধরা যাক আমাদের একটি লিঙ্কড লিস্টে ০ থেকে ১০ পর্যন্ত সংখ্যা আছে। লিঙ্কড লিস্টের থিওরি অনুযায়ী প্রতিটা এলিমেন্ট জানবে তার আগে কে আছে এবং তারপরে কে আছে। কিন্তু কথা হচ্ছে আমাদের ০ বা এমন ডাটা টাইপের মধ্যে তো কোন আলাদা জায়গা নেই যেখানে আমরা পরবর্তি এলিমেন্ট বা তার আগে এলিমেন্ট এর রেফারেন্স স্টোর করে রাখতে পারবো। এমন অবস্থায় আমাদের নিজস্ব ডাটা টাইপ বানিয়ে নিতে হবে যেখানে ডাটা বা এলিমেন্ট থাকবে এবং সাথে তার আগে বা পরে কোন এলিমেন্ট আছে সেটার রেফারেন্স বা মেমরি লোকেশন স্টোর করে রাখতে পারবো। আমরা আমাদের বানানো নতুন ডাটা টাইপের নাম দিচ্ছি Node

এখন , একটি নোড তারপরের নোডের মেমরি লোকেশন স্টোর করবে নাকি আগে এবং পরে থাকা নোডের মেমরি লোকেশন স্টোর করবে সেটি নির্ভর করে Linked List এর ধরন অনুযায়ী।

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

→ Singly Linked List

→ Doubly Linked List
→ Circular Linked List
→ Circular Singly Linked List
→ Circular Doubly Linked List

Singly Linked List : Singly Linked List এর প্রতিটা নোড তার পরে কোন নোড আছে তার রেফারেন্স বা মেমরি লোকেশন স্টোর করে রাখে। যদি কোন নোড না থাকে তাহলে None বা Null হবে।

Doubly Linked List : DoublyLinked List এর প্রতিটা নোড তার পরে এবং তার আগে কোন নোড আছে তার রেফারেন্স বা মেমরি লোকেশন স্টোর করে রাখে। যদি কোন নোড না থাকে তাহলে None বা Null হবে।

Circular Singly Linked List : Circular Singly Linked List এর সর্বশেষ নোড এর next_node ভ্যারিয়েবল সেই লিঙ্কড লিস্টের প্রথম নোডের মেমরি লোকেশন স্টোর করে।

Circular Doubly Linked List : Circular Doubly Linked List এর সর্বশেষ নোড এর next_node ভ্যারিয়েবল প্রথম নোডের মেমরি লোকেশন স্টোর করে এবং সর্বপ্রথম নোডের prev_node ভ্যারিয়েবলে সর্বশেষ নোডের মেমরি লোকেশন স্টোর করে

Singly Linked List

যেহেতু Singly Linked List এর প্রতিটা নোড তার পরে কে আছে তার রেফারেন্স হোল্ড করে সেহেতু Node class এ দুইটি প্রোপার্টি থাকবে।
1) Data
2) Next ( Memory location of next node )

Structure of Node class

class Node:
    def __init__(self , data):
        self.data = data
        self.next = None

যেহেতু সর্বশেষ নোড এর next ভ্যারিয়েবল এ কিছু থাকে না সেহেতু ইনিশিয়ালি None / null করে দেয়া হয়েছে

Basic Structure of SLL ( Singly Linked List ) class

class SLL:
    def __init__(self):
        self.head = None
        self.tail = None

Traversing operation

Linked List Traversing বলতে বোঝায় লিঙ্কড লিস্টে থাকা প্রতিটা নোড এক্সেস করে তার মধ্যে থাকা ডাটা শো করা।
Traversing Algorithm
→ প্রথমে একটি temp ( temporary ) variable নিয়ে সেখানে headNode স্টোর করতে হবে। headNode স্টোর করা মানে প্রথম নোডের মেমরি লোকেশন স্টোর করা।
→ while loop চালিয়ে দেখতে কন্ডিশন দিয়ে দেখতে হবে “ যদি নোড None না হয় তাহলে নোডের মধ্যে থাকা ডাটা প্রিন্ট করবে এবং temp variable আপডেট করে তারপরে থাকা নোডের মেমরি লোকেশন স্টোর করতে হবে।

#Iterative approc
def Traverse(self):
    temp = self.head
    while temp:
        print(temp.data)
        temp = temp.next

Length of SLL

→ আমাদেরকে লিঙ্কড লিস্ট ট্রাভার্স করতে হবে এবং প্রতিটা নোড ট্রাভার্স করা হয়ে গেলে count variable এর মান ১ করে বাড়াতে হবে

def length(self):
    temp = self.head
    count = 0
    while temp:
        count += 1
        temp = temp.next
    return count

Insertion Operation

লিঙ্কড লিস্টে ৩টি ইনশার্শন মেথড রয়েছে
→ insertFront
→ insertEnd
→ insertAt

Algorithm of insertFront

→ প্রথমে নোড তৈরি করতে হবে ( node = Node(data) )
→ যদি লিঙ্কড লিস্ট খালি হয় অর্থাৎ , head == None হয় তাহলে তৈরি করা নোডটি head এবং tail নোড হবে
→ যদি লিঙ্কড লিস্ট খালি না হয় তাহলে প্রথমে তৈরি করা প্রথম নোডের next ভ্যারিয়েবলে headNode এর মেমরি লোকেশন সেট করতে হবে এবং পরে নতুন নোডটিকে headNode হিসেবে সেট করতে হবে

def insertFront(self , data):
    node = Node(data)
    if self.head == None:
        self.head = node
        self.tail = node
    else:
        node.next = self.head
        self.head = node

Algorithm of insertEnd

→ প্রথমে নোড তৈরি করতে হবে ( node = Node(data) )
→ যদি লিঙ্কড লিস্ট খালি হয় অর্থাৎ , head == None হয় তাহলে তৈরি করা নোডটি head এবং tail নোড হবে
→ যদি লিঙ্কড লিস্ট খালি না হয় তাহলে tail node এর next ভ্যারিয়েবল এর ভ্যালু হিসেবে বসবে তৈরি করা নতুন নোড এবং tail হবে নতুন নোড

def insertEnd(self , data):
    node = Node(data)
    if self.head == None:
        self.head = node
        self.tail = node
    else:
        self.tail.next = node
        self.tail = node

Algorithm of insertAt

→ প্রথমে ইউজারের থেকে Index Number নিতে হবে। অর্থাৎ , ইউজার কোন পজিশনে নতুন নোড বসাতে চায়।
→ লেংথ বের করতে হবে এবং ইউজারের থেকে নেয়া ইন্ডেক্স ভ্যালিডেশন করতে হবে। যদি ইন্ডেক্স ১ এর থেকে ছোট হয় বা length + 1 এর থেকে বড় হয় তাহলে Invalid Index এরর দেখাতে হবে।
→ যদি ইন্ডেক্স ঠিক থাকে তাহলে দেখতে হবে যে , ইন্ডেক্স ১ বা length + 1 কিনা। যদি ১ হয় তাহলে insertFront() method call করতে হবে এবং যদি index = length + 1 হয় তাহলে insertEnd method call করতে হবে
→ যদি ইন্ডেক্স ১ অথবা length + 1 না হয় তাহলে নতুন নোড তৈরি করতে হবে।
→ ইউজার যে ইন্ডেক্স এ নোড বসাতে চায় সেই ইন্ডেক্স এ থাকা নোড সহ এর আগের ইন্ডেক্স এ থাকা নোড এক্সেস করতে হবে। ধরে নিলাম আগের ইন্ডেক্স এ থাকা নোড হচ্ছে prev_node এবং যে ইন্ডেক্স এ ইউজার নোড বসাতে চায় সেই ইন্ডেক্স এ থাকা নোড হচ্ছে next_node এবং নতুন করে বানানো নোড হচ্ছে current_node । এখন , prev_node এর next হবে current_node এবং current_node এর next হবে next_node

এই এলগরিদমটা বেশিরভাগেরই মাথার উপর দিয়ে গেছে🥲সো , একটু প্র্যাক্টিক্যালি কোড করে দেখা যাক🙂

def insertAt(self , index , data):
    length = self.length()
    if index < 1 or index > length + 1:
        raise ValueError("Invalid Index")
    elif index == 1:
        self.insertFront(data)
        return
    elif index == length + 1:
        self.insertEnd(data)
        return
    else:
        current_node = Node(data)
        prev_node = self.head
        cur_index = 1
        while cur_index < index - 1:
            prev_node = prev_node.next
            cur_index += 1
        current_node.next = prev_node.next
        prev_node.next = current_node

আজকের আর্টিকেল এই পর্যন্ত। নেক্সট আর্টিকেল এ ডিলিট অপারেশন নিয়ে এক্সপ্লেইন করা হবে🙂