ডাবলি লিংকড লিস্ট #

ইতিমধ্যে আমরা সিঙ্গলি লিংকড লিস্ট ও সার্কুলার লিংকড লিস্ট সম্পর্কে অল্প-বিস্তর ধারণা লাভ করার চেষ্টা করেছি। তারই ধারাবাহিকতায় এখন ডাবলি লিংকড লিস্ট সম্পর্কে জানব।

সিঙ্গলি লিংকড লিস্টের মত ডাবলি লিংকড লিস্টও কতগুলো নোডের চেইন বা সমাহার। কিন্তু পার্থক্য হল নোডের ফিল্ড সংখ্যায়। সিঙ্গলি লিংকড লিস্টে প্রতিটি নোডে দুটি ফিল্ড থাকে। কিন্তু ডাবলি লিংকড লিস্টে প্রতিটি নোডে তিনটি ফিল্ড থাকে। প্রথম ফিল্ডে থাকে প্রিভিয়াস (previous) পয়েন্টার বা পূর্ববর্তী নোডের লিংক (রেফারেন্স), মাঝের ফিল্ডে থাকে ডাটা আইটেম আর শেষের ফিল্ডে থাকে নেক্সট পয়েন্টার বা পরবর্তী নোডের লিংক (রেফারেন্স)। যেহেতু প্রতিটি নোডে দুটি করে পয়েন্টার থাকে, তাই এই নোড চেইনেরও দুটি প্রান্ত থাকে। দুই প্রান্তেই নোড চেইনের পরিসমাপ্তিকে মূলত নাল (Null) রেফারেন্স দ্বারা চিহ্নিত করা হয়। অনেক সময় None দিয়েও পরিসমাপ্তি বুঝানো হয়। পরিসমাপ্তি দ্বারা বুঝানো হচ্ছে যে, এই নোডের পরে আর কোন নোড নেই।

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

এতক্ষণ আমরা যে হাত ধরাধরির কাহিনী বর্ণনা করছিলাম, এই চিত্রটা আসলে তারই মানসচিত্র (ভিজুয়ালাইজেশন - visualization)। ধরা যাক, প্রথম নোড থেকে ডাবলি লিংকড লিস্টের অগ্রযাত্রা শুরু হয়েছে। প্রথম নোডের প্রিভিয়াস পয়েন্টার নাল (Null), কারণ এর আগে কোন নোড নেই। এই নোডের ডাটা আইটেম অংশে প্রথম ভ্যালুটা থাকে। প্রথম নোডের নেক্সট পয়েন্টার অংশ দ্বিতীয় নোডকে নির্দেশ করে। এভাবে চলতে থাকে। আর তৃতীয় নোডের নেক্সট পয়েন্টার নাল (Null), কারণ এর পরে কোন নোড নেই। এটাই হল ডাবলি লিংকড লিস্ট।

অপারেশন #

এক নজরে আমরা এখন ডাবলি লিংকড লিস্টের সকল অপারেশন দেখব। সাধারণত দশ ধরনের ফাংশন বা মেথডের মাধ্যমে এই অপারেশনগুলো সম্পাদিত হয়।

appendleft(item) #

লিস্টের শুরুতে নতুন একটি নোড সংযোজনের মাধ্যমে নতুন কোন ডাটা আইটেম সংযোজন করার ক্ষেত্রে এই ফাংশন বা মেথডটি ব্যবহার করা হয়। আর্গুমেন্ট বা প্যারামিটার হিসেবে আলোচ্য ডাটা আইটেমটিকে গ্রহণ করলেও এটি কোন কিছু রিটার্ন করে না।

append(item) #

লিস্টের শেষে নতুন একটি নোড সংযোজনের মাধ্যমে নতুন কোন ডাটা আইটেম সংযোজন করার ক্ষেত্রে এই ফাংশন বা মেথডটি ব্যবহার করা হয়। আর্গুমেন্ট বা প্যারামিটার হিসেবে আলোচ্য ডাটা আইটেমটিকে গ্রহণ করলেও এটি কোন কিছু রিটার্ন করে না।

insert(position, item) #

লিস্টের নির্দিষ্ট কোন অবস্থানে (পজিশানে) নতুন একটি নোড সংযোজনের মাধ্যমে নতুন কোন ডাটা আইটেম সংযোজন করার ক্ষেত্রে এই ফাংশন বা মেথডটি ব্যবহার করা হয়। আর্গুমেন্ট বা প্যারামিটার হিসেবে আলোচ্য পজিশান ও ডাটা আইটেমটিকে গ্রহণ করলেও এটি কোন কিছু রিটার্ন করে না।

remove(item) #

লিস্টের শুরু থেকে নির্দিষ্ট কোন ডাটা আইটেম ও সংশ্লিষ্ট নোড অপসারণ করার জন্য এই ফাংশন বা মেথডটি ব্যবহার করা হয়। আর্গুমেন্ট বা প্যারামিটার হিসেবে আইটেমটিকে গ্রহণ করলেও এটি কোন কিছু রিটার্ন করে না। (ধরে নেয়া হয়, আইটেমটি লিস্টে রয়েছে)

popleft() #

সাধারণত এই ফাংশন বা মেথড লিস্টের প্রথম ডাটা আইটেমটিকে ও সংশ্লিষ্ট নোড অপসারণ করে এবং ডাটা আইটেম রিটার্ন করে। (ধরে নেয়া হয়, লিস্টে অন্ততপক্ষে একটি আইটেম রয়েছে)

pop() #

সাধারণত এই ফাংশন বা মেথড লিস্টের শেষের ডাটা আইটেমটিকে ও সংশ্লিষ্ট নোড অপসারণ করে এবং ডাটা আইটেম রিটার্ন করে। (ধরে নেয়া হয়, লিস্টে অন্ততপক্ষে একটি আইটেম রয়েছে)

is_empty() #

এটি একটি বুলিয়ান ফাংশন (বা মেথড)। লিস্ট খালি কিনা সেটি চেক করে True বা False রিটার্ন করে। এর কোন প্যারামিটার নেই।

size() #

এই ফাংশন (বা মেথড) লিংকড লিস্টের মোট আইটেম (নাকি নোড?) সংখ্যা রিটার্ন করে। এরও কোন প্যারামিটার নেই।

search(item) #

এটি একটি বুলিয়ান ফাংশন (বা মেথড)। একটি আইটেমকে আর্গুমেন্ট বা প্যারামিটার হিসেবে গ্রহণ করে লিংকড লিস্টে সেটি রয়েছে কিনা তা সার্চ করে দেখে এবং True বা False রিটার্ন করে।

index(item) #

এই ফাংশন বা মেথডটি একটি আইটেমকে আর্গুমেন্ট বা প্যারামিটার হিসেবে গ্রহণ করে। তারপর সেটিকে লিংকড লিস্টে সার্চ করে দেখে এর পজিশন রিটার্ন করে। (ধরে নেয়া হয়, আইটেমটি লিস্টে রয়েছে)

printlist() #

এই ফাংশন বা মেথডটি লিস্টের সবগুলো আইটেমকে প্রিন্ট করবে। (ধরে নেয়া হয়, লিস্টে ন্যূনতম একটি আইটেম রয়েছে।)

ইমপ্লিমেন্টেশন #

আমরা এখন জানি যে, ডাবলি লিংকড লিস্ট হল কতগুলো নোডের চেইন। প্রতিটি নোডকে ধারণ করার জন্য একটা Node() ক্লাস তৈরি করতে হবে আমাদের।

class Node():
    def __init__(self, item=None, previous_node=None, next_node=None):
        self.item = item
        self.previous_node = previous_node
        self.next_node = next_node

এই ক্লাসের আর্গুমেন্ট তিনটি: item, previous_node ও next_node। item দিয়ে ডাটা আইটেমকে বুঝানো হচ্ছে। আর previous_node হল উপরে উল্লেখিত পূর্ববর্তী নোডের রেফারেন্স এবং next_node হল পরবর্তী নোডের রেফারেন্স। প্রাথমিকভাবে আর্গুমেন্ট তিনটির ভ্যালু None।

এবার ডাবলি লিংকড লিস্টের অপারেশনসমূহ করার জন্য দশটা মেথড তৈরি করব আমরা। এই মেথডগুলো থাকবে DoublyLinkedList() ক্লাসের অধীন।

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

এই ক্লাসের আর্গুমেন্ট দুটি: head ও tail। হেড লিস্টের প্রথম নোডকে নির্দেশ করে। আর tail নির্দেশ করে লিস্টের সর্বশেষ নোডকে। প্রাথমিকভাবে এদের ভ্যালু None।

প্রথমে appendleft(item) মেথড নিয়ে ভাবা যাক।

def appendleft(self, item):
    new_node = Node(item)
    new_node.previous_node = None
    new_node.next_node = self.head
    if self.head is None:
        self.tail = new_node
    else:
        self.head.previous_node = new_node
    self.head = new_node

এই মেথড সবসময় হেডে আইটেম (আসলে নোড) যোগ করবে। তাই প্রথমেই নোড ক্লাসের মাধ্যমে একটি নতুন নোড তৈরি করেছি আমরা। লিস্টে নতুন হেড আসা মানে বর্তমান হেডকে চলে যেতে হবে দ্বিতীয় অবস্থানে। তাই নতুন নোডের next_node ভ্যারিয়েবলে self.head (ক্লাস ভ্যারিয়েবল)-এ থাকা নোডের রেফারেন্স দিয়েছি আমরা। আর এই নতুন নোডের আগে যেহেতু কোন নোড নেই তাই এর previous_node ভ্যারিয়েবলে None অ্যাসাইন করে দিয়েছি। এখন ঘটনা হল, কোন লিস্টে self.head এ কিছু থাকতেও পারে আবার নাও থাকতে পারে। কিছু না থাকার মানে হল লিস্টে কেবলমাত্র আমাদের যোগ করা নোডটিই আছে। সেক্ষত্রে এই নোডটিই লিস্টের প্রথম ও শেষ নোড। তাই self.tail এ আমরা নতুন নোডের রেফারেন্স দিয়েছি। আর self.head এ কোন নোড থাকলে তার previous_node ভ্যারিয়েবলে নতুন নোডের রেফারেন্স দিতে হবে। সবশেষে, self.head (ক্লাস ভ্যারিয়েবল)-এ আমাদের নতুন নোডের রেফারেন্স দিয়েছি।

এবার আমরা append(item) মেথডটি নিয়ে ভাবব। এই মেথড সবসময় লিস্টের শেষে নতুন আইটেম (আসলে নোড) যোগ করবে। তাহলে কিন্তু ব্যাপারটা বেশ সহজ। একটা নতুন নোড তৈরি করতে হবে। বর্তমানে লিস্টের শেষে (self.tail এ) থাকা নোডটির next_node ভ্যারিয়েবল এই নতুন নোডটিকে পয়েন্ট করবে। আর নতুন নোডটির previous_node ভ্যারিয়েবল পয়েন্ট করবে self.tail এ থাকা নোডটি।

def append(self, item):
    new_node = Node(item)
    if self.head is None:
        self.head = self.tail = new_node
    else:
        new_node.previous_node = self.tail
        new_node.next_node = None
        self.tail.next_node = new_node
        self.tail = new_node

insert(position, item) মেথডটি বেশ মজার। লিস্টের হেডে (জিরো পজিশনে) বা লিস্টের একেবারে শেষের পজিশনে (টেইলে) যোগ করার ক্ষেত্রে যথাক্রমে appendleft(item) ও append(item) মেথড কল করে কাজ সারতে পারব। কিন্তু দুটি নোডের মাঝখানে কোন নোড যোগ করতে চাইলে একটু কষ্ট করতে হবে আমাদের।

def insert(self, position, item):
    if position == 0:
        self.appendleft(item)
        print(item, "inserted to position", position)
    elif position == self.size():
        self.append(item)
        print(item, "inserted to position", position)
    elif position > self.size():
        print("Index out of range")
    else:
        current = self.head
        index = 0
        while current:
            if index != position:
                previous = current
                current = current.next_node
                index += 1
            else:
                new_node = Node(item, previous, current)
                previous.next_node = new_node
                current.previous_node = new_node
                current = False
                print(item, "inserted to position", position)

ধরা যাক, চার নম্বর পজিশনে একটা নতুন নোড যোগ করব আমরা। তারমানে বর্তমানে চার নম্বর পজিশনে থাকা নোডটি চলে যাবে পাঁচ নম্বর পজিশনে, পাঁচ নম্বর পজিশনে থাকা নোডটি চলে যাবে ছয় নম্বর পজিশনে। অর্থাৎ এক ঘর করে সরবে। তাই নতুন একটি নোড তৈরি করে এর next_node ভ্যারিয়েবল দিয়ে বর্তমানে চার নম্বর পজিশনে থাকা নোডটিকে ও previous_node ভ্যারিয়েবল দিয়ে বর্তমানে তিন নম্বর পজিশনে থাকা নোডটিকে পয়েন্ট করাব আমরা। আর তিন নম্বর পজিশনে থাকা নোডটির next_node ভ্যারিয়েবল পয়েন্ট করবে নতুন নোডটিকে। ব্যাস, হয়ে গেল ইনসার্ট।

is_empty() মেথডটা বেশ সহজ। লিস্টে যদি কমপক্ষে একটি নোডও থাকে তবে self.head এ তার রেফারেন্স থাকবেই। শুধু হেড খালি (None) কিনা সেটা চেক করে দেখলেই চলে। খালি হলে True রিটার্ন করবে, অন্যথায় False রিটার্ন করবে।

def is_empty(self):
    if self.head is None:
        return True
    else:
        return False

size() মেথডটি is_empty() মেথডের মতই সহজ। ছোটবেলার মত করে একটা while লুপ ঘুরিয়ে নোড কাউন্ট করা শুরু করতে হবে। আর যখনই কোন নোডের next_node এর রেফারেন্সে None পাওয়া যাবে তখনই লুপ থামিয়ে দিতে হবে। এবার মোট কতবার লুপ ঘুরল সেটা হিসেব করলেই কিন্তু লিস্টের সাইজ পাওয়া যাবে। তাই না?

def size(self):
    current = self.head
    count = 0
    while current:
        count += 1
        current = current.next_node
    return count

উপরের size() মেথডের ইমপ্লিমেন্টেশন ঠিকমত বুঝে থাকলে index(item) মেথডটি ইমপ্লিমেন্ট করা সহজ হবে। আমরা জানি যে, এই মেথডের কাজ হল কোন আইটেমের ইনডেক্স পজিশন রিটার্ন করা। আমরা ধরে নিলাম, ডাবলি লিংকড লিস্টের ইনডেক্স সিস্টেম পাইথনের চিরাচরিত লিস্টের মতই। মানে জিরো থেকে শুরু হবে।

def index(self, item):
    current = self.head
    index = 0
    while current:
        if current.item == item:
            return index
        else:
            current = current.next_node
            index += 1
    return None

এজন্য আমরা হেড থেকে আইটেম খোঁজা শুরু করেছি। না পেলে পরবর্তী নোডে চলে গিয়েছি। আর যখনই পরবর্তী নোডে চলে গিয়েছি তখনই ইনডেক্সের মান ১ করে বাড়িয়ে দিয়েছি। যখন কাঙ্ক্ষিত ডাটা আইটেম কোন নোডে পাওয়া গিয়েছে তখন লুপ টার্মিনেট করে দিয়েছি। এভাবে আমরা আমাদের কাঙ্ক্ষিত ডাটা আইটেমের (আসলে নোডের) ইনডেক্স নম্বর পেয়ে গিয়েছি।

search(item) মেথড আগের index(item) মেথডের মতই। পার্থক্য শুধু এতটুকু যে এই মেথড কাঙ্ক্ষিত আইটেম খুঁজে পেলে True রিটার্ন করবে। অন্যথায় False রিটার্ন করবে।

def search(self, item):
    current = self.head
    found = False
    while current and not found:
        if current.item == item:
            found = True
        else:
            current = current.next_node
    if current is None:
        print("Item not found")
    return found

popleft() মেথডের কাজ হল appendleft(item) মেথডের ঠিক উল্টো। মানে, লিস্টের প্রথম নোডটিকে রিমুভ করা ও এর আইটেমকে রিটার্ন করা।

def popleft(self):
    if self.is_empty():
        print("Empty list")
    else:
        current = self.head
        next_node = current.next_node
        if next_node is None:
            temp = current.item
            del current
            self.head = self.tail = None
            return temp
        else:
            temp = current.item
            del current
            next_node.previous_node = None
            self.head = next_node
            return temp

self.head-এ যেহেতু লিস্টের প্রথম নোডটি থাকে, তাই এটা রিমুভ করব আমরা। এটা রিমুভ করার পর এর ঠিক পরের নোডটি হেডে চলে আসবে। আর নতুন হেডের previous_node ভ্যারিয়েবল কোন নোডকে পয়েন্ট করবে না, তাই None অ্যাসাইন করব। এবার প্রথম নোডটি রিমুভ করার পালা। রিমুভ করার আগে নোডের আইটেমটা একটা temp ভ্যারিয়েবলে রেখে দিয়েছি যাতে নোড রিমুভ করার পরে আইটেমটা রিটার্ন করা যায়। উল্লেখ্য যে, লিস্টে কেবলমাত্র একটি নোড থাকলে, এটি রিমুভ করার পর self.head ও self.tail এ None অ্যাসাইন করে দেব আমরা। বলুন তো কেন?

pop() মেথডের কাজ append(item) মেথডের উল্টো। মানে, লিস্টের সর্বশেষ নোডটিকে রিমুভ করা ও এর আইটেমকে রিটার্ন করা।

def pop(self):
    if self.is_empty():
        print("Empty list")
    else:
        current = self.tail
        previous = current.previous_node
        if previous is None:
            temp = current.item
            del current
            self.head = self.tail = None
            return temp
        else:
            temp = current.item
            del current
            previous.next_node = None
            self.tail = previous
            return temp

self.tail-এ লিস্টের সর্বশেষ নোডটিকে পাব আমরা। এই নোডের ঠিক আগের নোডটি হবে নতুন টেইল। তাই এর next_node ভ্যারিয়েবলে None অ্যাসাইন করে দিয়েছি। সর্বশেষ নোডটি রিমুভ করার আগে নোডের আইটেমটা একটা temp ভ্যারিয়েবলে রেখে দিয়েছি যাতে নোড রিমুভ করার পরে আইটেমটা রিটার্ন করা যায়।

remove(item) মেথডটি একটু কঠিন মনে হতে পারে। তাই একটু মনোযোগী হতে হবে এবার। (এতক্ষণ অমনোযোগী ছিলাম আমরা?)

def remove(self, item):
    if self.is_empty():
        print("Empty list")
    else:
        current = self.head
        previous = None
        found = False
        while current and not found:
            if current.item == item:
                found = True
            else:
                previous = current
                current = current.next_node
        if current is None:
            print("Item not found")
        elif previous is None:
            self.popleft()
            print(item, "removed")
        else:
            temp = current.next_node
            del current
            print(item, "removed")
            previous.next_node = temp
            temp.previous_node = previous

যেহেতু আমরা কোন আইটেম রিমুভ করব, তাই সবার আগে চেক করে দেখা দরকার লিস্টে আদৌ কোন নোড আছে কিনা। সেজন্য আমরা আমাদের is_empty() মেথডের সাহায্য নিয়েছি। লিস্ট খালি না হলে যে আইটেমটি রিমুভ করতে হবে একটা while লুপ ঘুরিয়ে সেটাকে খোঁজ দ্যা সার্চ করেছি। কাঙ্ক্ষিত ডাটা আইটেম হেডে থাকলে popleft() আর টেইলে থাকলে pop() মেথড কল করাই যথেষ্ট। অন্যথায়, যেই নোডে কাঙ্ক্ষিত ডাটা আইটেমটি রয়েছে সেটাকে কারেন্ট নোড হিসেবে ধরে নিলাম। এবার এখানে কারসাজি রয়েছে। কারেন্ট নোডের next_node ভ্যারিয়েবল যে নোডটিকে পয়েন্ট করছে তার রেফারেন্স কারেন্ট নোডের ঠিক আগের নোডের next_node ভ্যারিয়েবলে অ্যাসাইন করে দিয়েছি। আর কারেন্ট নোডের previous_node ভ্যারিয়েবল যে নোডটিকে পয়েন্ট করছে তার রেফারেন্স কারেন্ট নোডের ঠিক পরের নোডের previous_node ভ্যারিয়েবলে অ্যাসাইন করে দিয়েছি। তারপর কারেন্ট নোডকে ডিলিট করে দিয়েছি আমরা। আচ্ছা, del current এই স্টেটমেন্টের সহীহ ফযিলত কি? বলুন তো!

printlist() মেথডটা আসলে অমন আহামরি কঠিন কিছু না। বিখ্যাত নাবিক ক্রিস্টোফার কলম্বাসের মত আবিষ্কারের নেশায় মেতে উঠতে হবে। একটা জাহাজে চড়ে থুক্কু লুপ ঘুরিয়ে সবগুলো নোড আবিষ্কার করতে হবে। তারপর সেই নোডের ডাটা আইটেমকে প্রিন্ট করতে হবে।

def printlist(self):
    if self.is_empty():
        print("Empty list")
    else:
        current = self.head
        while current:
            print(current.item)
            current = current.next_node

আশা করি একটু চেষ্টা করলেই ডাবলি লিংকড লিস্ট ইমপ্লিমেন্ট করতে পারা যাবে এখন।