Doubly Linked List হলো Linked List এর একটি টাইপ যেখানে প্রতিটা নোড তার আগের নোড ও পরের নোডের মেমরি লোকেশন স্টোর করে রাখতে পারে। যদি আগে বা পরে নোড না থাকে তাহলে খালি থাকে। এর আগে আমরা Singly Linked List ( SLL ) নিয়ে আলোচনা করেছিলাম দুইটি পার্টে
→ Part - A
→ Part - B

Structure of Node class for Doubly Linked List ( DLL )

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

Basic Structure of Doubly Linked List ( DLL )

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

এখানে আপাদত DLL এর head এবং tail None করে রাখা হয়েছে। অর্থাৎ কিছু নেই। নতুন নোড ইন্সার্ট করার সময় এগুলো আপডেট করবো।

আমরা Singly Linked List ( SLL ) এ দেখেছিলাম কোন লিঙ্কড লিস্টের head থেকে tail পর্যন্ত ট্রাভার্স করতে পারি। যেহেতু , SLL এর প্রতিটি নোড শুধুমাত্র পরবর্তি নোডের মেমরি লোকেশন স্টোর করে রাখতে পারে। কিন্তু DLL এ আমরা tail থেকে head পর্যন্ত ট্রাভার্স করতে পারি। কারন DLL এর প্রতিটি নোড তার আগের এবং পরের নোডের মেমরি লোকেশন স্টোর করে রাখে।

Traversing Algorithm

→ প্রথমে temp ( temporary ) variable এর মধ্যে head অথবা tail নোড কে রাখতে হবে।
→ যদি head থেকে tail পর্যন্ত ট্রাভার্স করতে চাই তাহলে প্রতিবার নোডে থাকা ডাটা প্রিন্ট করে temp = temp.next করতে হবে।
→ যদি tail থেকে headপর্যন্ত ট্রাভার্স করতে চাই তাহলে প্রতিবার নোডে থাকা ডাটা প্রিন্ট করে temp = temp.prev করতে হবে।

Traversing operation of DLL ( head → tail )

def forwardTraverse(self):
    temp = self.head
    while temp:
        print(temp.data , end = " ")
        temp = temp.next

Traversing operation of DLL ( tail → head )

def backwardTraverse(self):
    temp = self.tail
    while temp:
        print(temp.data , end = " ")
        temp = temp.prev

Insertion Operation

→ DLL এ Insertion SLL এর মতোই। শুধুমাত্র প্রতিবার নোড অ্যাড করার সময় prev এবং next কে আপডেট করতে হবে।
→ SLL এর মতোই DLL এ ৩ ভাবে নোড ইন্সার্ট করা যায়
১) insertFront → সবার প্রথমে নোড অ্যাড করা
২) insertEnd → সবার শেষে নোড অ্যাড করা
৩) insertAt → লিঙ্কড লিস্টের যেকোন জায়গায় নোড অ্যাড করা

insertFront Algorithm

→ আগে দেখতে হবে লিঙ্কড লিস্ট খালি কিনা। যদি খালি হয় তাহলে নতুন তৈরি করা নোডটিই head এবং tail নোড।
→ যদি আগে থেকে নোড থাকে তাহলে বর্তমানে head নোড এর prev হবে নতুন তৈরি করা নোড এবং নতুন তৈরি করা নোডের next হবে বর্তমান head নোড।
অর্থাৎ , head→prev = new_node হবে এবং new_node→next = head হবে। এরপর head = new_node হবে।

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

insertEnd Algorithm

→ আগে দেখতে হবে লিঙ্কড লিস্ট খালি কিনা। যদি খালি হয় তাহলে নতুন তৈরি করা নোডটিই head এবং tail নোড।
→ যদি আগে থেকে নোড থাকে তাহলে বর্তমানে tail নোড এর next হবে নতুন তৈরি করা নোড এবং নতুন তৈরি করা নোডের prev হবে বর্তমান tail নোড। এরপর tail হবে নতুন নোড।
অর্থাৎ , tail→next = new_node হবে এবং new_node→prev = tailহবে। এরপর tail= new_node হবে।

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

insertAt Algorithm

→ ইউজারের থেকে পজিশন ইনপুট নিতে হবে এবং DLL এর length বের করে নিতে হবে।
→ যদি পজিশন ১ এর থেকে কম বা length+1 এর থেকে বেশি হয় তাহলে invalid position error দেখাতে হবে।
→ যদি পজিশন ভ্যালিড হয় তাহলে দেখতে হবে ইউজার থেকে নেয়া পজিশন ১ অথবা length + 1 কিনা ? যদি ১ হয় তাহলে insertFront() method call করতে হবে এবং যদি length + 1 হয় তাহলে insertEnd() method call করতে হবে। আলাদা কোন কোড লেখার দরকার নেই , যেহেতু আগে থেকেই মেথড বানানো আছে।
→ নাহলে , SLL এর মতো ইউজারের দেয়া পজিশন এর আগের পজিশনে থাকা নোড পর্যন্ত ট্রাভার্স করে নিতে হবে এবং নিচের মতো করে নোডগুলোকে আপডেট করতে হবে।
মনে করলাম , শেষ পর্যন্ত যে নোডটিকে ট্রাভার্স করেছি সেটি হচ্ছে current_node , নতুন তৈরি করা নোড হচ্ছে new_node এবং ইউজারের দেয়া পজিশনে থাকা নোড হচ্ছে next_node। যেহেতু আমরা ইউজার থেকে নেয়া পজিশনের আগের পজিশন পর্যন্ত ট্রাভার্স করবো সেহেতু সেখানে যে নোডটি পাবো সে নোডের next কে অন্য একটি ভ্যারিয়েবলে সেট করলেই next_node পেয়ে যাবো।

1. new_node.next = next_node

2. next_node.prev = new_node

3. current_node.next = new_node

4. new_node.prev = current_node
   এবার একটু কোড করে দেখা যাক 🙂

def insertAt(self , data , pos):
    length = self.length() #SLL এ আমরা কোন লিঙ্কড লিস্টের লেংথ বের করা শিখেছিলাম
    if pos < 1 or pos > length + 1:
        raise ValueError("Invalid position")
    elif pos == 1:
        self.insertFront(data)
    elif pos == length + 1:
        self.insertEnd(data)
    else:
        current_node = self.head
        target_pos = pos - 1
        current_pos = 1
        new_node = Node(data)
        while current_pos < target_pos:
            current_node = current_node.next
            current_pos += 1
        next_node = current_node.next
        new_node.next = next_node
        next_node.prev = new_node
        current_node.next = new_node
        new_node.prev = current_node

Test Code

dll = DLL()
for i in range(10):
    dll.insertFront(i)
dll.forwardTraverse() #Output : 9 8 7 6 5 4 3 2 1 0 
dll.backwardTraverse() #Output : 0 1 2 3 4 5 6 7 8 9 
char_array = ["A" , "B" , "C" , "D" , "E"]
for char in char_array:
    dll.insertEnd(char)
dll.backwardTraverse() #Output : E D C B A 0 1 2 3 4 5 6 7 8 9

ডাটা স্ট্রাকচার শুধুমাত্র থিওরি পড়ে কোড করে গেলেই হবে না। খাতায় ভিজ্যুয়ালি এঁকে insert and delete operation করতে হবে🙂নাহলে কিছুই মনে থাকবে না🙂