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

ল্লিঙ্কড লিস্ট হচ্ছে লিস্টের মত আরেকটা ডেটা স্ট্র্যাকচার। লিঙ্কড লিস্টে আইটেম গুলো একটা আরেকটার সাথে কানেক্টেড থাকে। অনেকটা চেইনের মত। লিঙ্কড লিস্ট মূলত অনেক গুলো নডের সমষ্টি। এখন জিজ্ঞেস করতে পারেন নড কি। নডকে চিন্তা করতে পারেন একটা বক্সের মত। যার মধ্যে দুইটা খোপ থাকে। এই খোপের একটাতে থাকে ডেটা, আরেকটাতে থাকে পরবর্তী ডেটা মেমরির কোন লোকেশনে রয়েছে, তার এড্রেস। নিচের মতঃ

এরকম অনেক গুলো নড নিয়েই লিঙ্কড লিস্ট গঠিত। লিঙ্কড লিস্টে আইটেম যত বেশি হবে, লিঙ্কড লিস্ট তত বড় হবে। লিঙ্কড লিস্টের প্রথম নডকে বলা হয় হেড। যা লিঙ্কড লিস্টের স্টার্টিং পয়েন্ট হিসেবে কাজ করে। সর্বশেষ নডের পরবর্তী আইটেমের লোকেশন সাধারণ নাল থাকে। এ থেকে বুঝতে পারি যে এটাই লিঙ্কড লিস্টের শেষ আইটেম।

লিঙ্কড লিস্ট ডেটা স্টোর করার সময় মেমরি লোকেশনের কোন সিরিয়াল মানে না। এর পরিবর্তে প্রতিটা ডেটার সাথে ঐ ডেটার মেমরি লোকেশনও ট্র্যাক রাখে। লিঙ্কড লিস্ট যেখানেই যায়গা খালি থাকবে, সেখানেই ডেটা স্টোর করবে। যেমন আমরা রাখতে চাচ্ছি 2, 4 , 6 , 8 কম্পিউটার মেমরিতে। আর আমাদের মেমরিতে আগেই কিছু ডেটা আছে নিচের মত করেঃ

memory address	0	1	2	3	4	5	6	7	8	9
cell	11			22			33

লিঙ্কড লিস্ট ব্যবহার করে  2, 4 , 6 , 8 আইটেম গুলো যদি কম্পিউটার মেমরিতে রাখি, তাহলে মেমরির ১ নং এড্রেসে 2, ২ নং এড্রেসে 4, ৪ নং এড্রেসে 6 এবং ৫ নং এড্রেসে 8 রাখবে। তখন আমাদের লিঙ্কড লিস্ট দেখতে হবে এমনঃ

লিঙ্কড লিস্টে শুধু মাত্র মেমরি লোকেশনের পয়েন্টার আপডেট করেই যে কোন যায়গায় নতুন আরেকটা আইটেম যুক্ত করে। যেমন আমরা চাচ্ছি লিঙ্কড লিস্টে নতুন একটা ডেটা যেমন 10 রাখতে। আর মেমরি লোকেশনের ৭ নং এড্রেসটা খালি আছে। তখন লিঙ্কড লিস্ট হবে এমনঃ

 

লিঙ্কড লিস্ট ইমপ্লিমেন্টেশনঃ

এবার দেখি কিভাবে লিঙ্কড লিস্ট পাইথনে ইমপ্লিমেন্ট করা যায়। আমরা জেনেছি যে লিঙ্কড লিস্টের মূলে রয়েছে নড। প্রতিটা নডের দুইটা অংশ থাকে, একটা হচ্ছে ডেটা আইটেম, আরেকটা হচ্ছে পরবর্তী ডেটা আইটেমের এড্রেস। তো সবার আগে নডের জন্য একটা ক্লাস তৈরি করে নেইঃ

# Creating a node
class Node:
    def __init__(self, item):
        self.item = item
        self.next = None

পরবর্তী কাজ হচ্ছে একটা লিঙ্কড লিস্ট ক্লাস তৈরিঃ

class LinkedList:
    def __init__(self):
        self.head = None

এখানে head হচ্ছে প্রথম নড। এখন আমরা এই লিঙ্কডলিস্টের একটা ইনিস্ট্যান্স তৈরি করে নিব এবং তার মধ্যে কিছু আইটেম এসাইন করবঃ

linked_list = LinkedList()

# Assign item values

linked_list.head = Node('2')
second = Node('4')
third = Node('6')

প্রথম বা হেড নডে আমরা রেখেছি 2, দ্বিতীয় নডে রেখেছি 4, তৃতীয় নডে রেখেছি 6। এভাবে আরো ডেটা আইটেম রাখতে পারি। উপরে লিঙ্কড লিস্টে কিছু ভ্যালু এসাইন করেছি। কিন্তু একটা ভ্যালুর সাথে আরেকটা ভ্যালু লিঙ্ক করিনি। আর তা করতে পারি এভাবেঃ

linked_list.head.next = second
second.next = third

তৃতীয় ডেটা আইটেমের পরে অন্য কোন আইটেম না থাকায় আমাদের আর তা লিঙ্ক করতে হবে না।

এবার চাইলে লিঙ্কড লিস্টে কি কি আইটেম রয়েছে, তা আমরা প্রিন্ট করে দেখতে পারিঃ

while linked_list.head is not None:
    print(linked_list.head.item, end=" ")
    linked_list.head = linked_list.head.next

এক সাথে সম্পূর্ণ প্রোগ্রামঃ

# Creating a node
class Node:
    def __init__(self, item):
        self.item = item
        self.next = None


class LinkedList:
    def __init__(self):
        self.head = None


linked_list = LinkedList()

# Assign item values

linked_list.head = Node('2')
second = Node('4')
third = Node('6')

linked_list.head.next = second
second.next = third

while linked_list.head is not None:
    print(linked_list.head.item, end=" ")
    linked_list.head = linked_list.head.next

যা প্রিন্ট করলে পাবোঃ

2 4 6

এর আগে আমরা জেনেছি যে যে কোন ডেটা স্ট্র্যাকচারেই ব্যাসিক কিছু অপারেশন করা যায় যেমন নতুন ডেটা যুক্ত করা, কোন ডেটা রিমুভ করা ইত্যাদি। উপরে আমরা জেনেছি কিভাবে একটা খালি লিঙ্কড লিস্টে ডেটা যুক্ত করে। যখন আমাদের কাছে একটা লিঙ্কড লিস্ট থাকবে, এরপর তার মধ্যে যদি ডেটা যুক্ত করতে চাই, তাহলে কিভাবে কাজ করব?

প্রথমে দেখি কিভাবে লিঙ্কড লিস্টের শেষে ডেটা যুক্ত করা যায়। তার জন্য LinkedList ক্লাসে নিচের মেথডটি যুক্ত করিঃ

   # Method to add new node in the end
    def add_end(self, newdata):
        new_node = Node(newdata)
        if self.head is None:
            self.head = new_node
            return
        last_item = self.head
        while last_item.next:
            last_item = last_item.next
        last_item.next = new_node

এখন নতুন আইটেম যুক্ত করতে পারি এভাবেঃ

linked_list.add_end("8")

তাহলে সম্পূর্ণ প্রোগ্রাম হবে এমনঃ

# Creating a node
class Node:
    def __init__(self, item):
        self.item = item
        self.next = None


class LinkedList:
    def __init__(self):
        self.head = None

    # Method to add new node in the end
    def add_end(self, newdata):
        new_node = Node(newdata)
        if self.head is None:
            self.head = new_node
            return
        last_item = self.head
        while last_item.next:
            last_item = last_item.next
        last_item.next = new_node


linked_list = LinkedList()

# Assign item values
linked_list.head = Node('2')
second = Node('4')
third = Node('6')

# Connect nodes
linked_list.head.next = second
second.next = third

linked_list.add_end("8")

# Print the linked list item
while linked_list.head is not None:
    print(linked_list.head.item, end=" ")
    linked_list.head = linked_list.head.next

সাধানত তিন ধরনের লিঙ্কড লিস্ট রয়েছে। যেমনঃ

• Singly Linked List
• Doubly Linked List
• Circular Linked List

সিঙ্গলি লিঙ্কড লিস্টঃ

উপরে আমরা যে লিঙ্কড লিস্ট নিয়ে আলোচনা করেছি, তাই হচ্ছে সিঙ্গলি লিঙ্কড লিস্ট। প্রথম নডের সাথে দ্বিতীয় নডের লোকেশন থাকে, দ্বিতীয় নডের সাথে তৃতীয় নডের লোকেশন থাকে। এভাবে শেষ পর্যন্ত। প্রথম নড হেড হিসেবে কাজ করে। শেষ নডে পরবর্তী নডের লোকেশন যেহেতু থাকে না, তাই নাল সেট করা থাকে।

ডাবলি লিঙ্কড লিস্টঃ

সিঙ্গলি লিঙ্কড লিস্টে প্রতিটা নডে পরবর্তী ডেটার লোকেশন থাকে। কিন্তু ডাবলি লিংক লিস্টে প্রতিটি নডে পরবর্তী ডেটার লোকেশন সহ পূর্ববর্তী ডেটার লোকেশনও সেভ থাকে। যেন একই সাথে সামনের দিকে অথবা পেছনের দিকেও ডেটা এক্সপ্লোর করা যায়।
ডাবলি লিঙ্কড লিস্ট আমরা নিচের মত করে ইমপ্লিমেন্ট করতে পারিঃ

# Creating a node
class Node:
    def __init__(self, item):
        self.item = item
        self.next = None
        self.prev = None


class DoublyLinkedList:
    def __init__(self):
        self.head = None

    # Adding items
    def add_item(self, new_item):
        new_node = Node(new_item)
        new_node.next = self.head
        if self.head is not None:
            self.head.prev = new_node
        self.head = new_node


# Print the Doubly Linked list
def print_list(node):
    while node is not None:
        print(node.item),
        last = node
        node = node.next


linked_list = DoublyLinkedList()

# Assign item values

linked_list.add_item(5)
linked_list.add_item(2)
linked_list.add_item(72)
linked_list.add_item(33)

print_list(linked_list.head)

সার্কুলার লিঙ্কড লিস্টঃ সার্কুলার লিঙ্কড লিস্টে লাস্ট নডের সাথে নেক্সট নডের লোকেশন হিসেবে প্রথম বা হেড নডের লোকেশন পয়েন্ট করা থাকে। এর ফলে পুরো লিঙ্কড লিস্ট একটা সার্কুলার লিঙ্কড লিস্ট হিসেবে কাজ করে।

সার্কুলার লিঙ্কড লিস্ট সিঙ্গলি অথবা ডাবলি, দুই ধরনেরই হতে পারে।

সার্কুলার সিঙ্গলি লিঙ্কড লিস্টঃ

সার্কুলার সিঙ্গলি লিঙ্কড লিস্টে লাস্ট আইটেমের নেক্সট পয়েন্টারে প্রথম আইটেম পয়েন্ট করা থাকে।

সার্কুলার ডাবলি লিঙ্কড লিস্টঃ

সার্কুলার ডাবলি লিঙ্কড লিস্টে লাস্ট আইটেমের নেক্সট পয়েন্টারে প্রথম আইটেম পয়েন্ট করার পাশা পাশী প্রথম আইটেমে লাস্ট আইটেমের লোকেশন পয়েন্ট করা থাকে।