সার্কুলার লিংকড লিস্ট #

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

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

সিঙ্গলি লিংকড লিস্টের সাথে সার্কুলার লিংকড লিস্টের পার্থক্য মূলত এই নাল (Null) রেফারেন্সে। সার্কুলার লিংকড লিস্টে কোন নাল রেফারেন্স থাকে না। বরং এর শেষ নোডে প্রথম নোডের লিংক বা রেফারেন্স থাকে। ফলশ্রুতিতে সার্কুলার লিংকড লিস্টকে চক্রাকার বেনজিন বলয়ের সাথে তুলনা করা যায়।

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

এবার এই হাত ধরাধরি করে চক্রাকারে দাঁড়ানোটাকে বিবেচনা করা যাক। এই হিউম্যান চেইনে প্রত্যেক হিউম্যানকে নোড হিসেবে কল্পনা করা যায়। আমাদের মূলদেহকে সেই নোডের ডাটা আইটেম আর ডানহাতকে পরবর্তী নোডের লিংক বা রেফারেন্স হিসেবে কল্পনা করা যায়। আর বামহাত? কথায় আছে ভাল কাজে বাম হাত দিতে নাই। যাহোক, এবার একটা ছবি দেখা যাক।

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

অপারেশন #

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

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, next_node=None):
        self.item = item
        self.next_node = next_node

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

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

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

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

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

def appendleft(self, item):
    new_node = Node(item)
    new_node.next_node = self.head
    current = self.head
    if self.head is not None:
        while current.next_node is not self.head:
            current = current.next_node
        current.next_node = new_node
    else:
        new_node.next_node = new_node
    self.head = new_node

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

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

def append(self, item):
    new_node = Node(item)
    current = self.head
    if current:
        while True:
            if current.next_node is self.head:
                current.next_node = new_node
                new_node.next_node = self.head
                break
            else:
                current = current.next_node
    else:
        self.head = new_node
        new_node.next_node = 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, current)
                previous.next_node = new_node
                current = False
                print(item, "inserted to position", position)

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

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

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

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

def size(self):
    current = self.head
    count = 0
    while current:
        count += 1
        if current.next_node is self.head:
            current = False
        else:
            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
        elif current.next_node is self.head:
            break
        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
        elif current.next_node is self.head:
            current = False
        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
        temp = current.item
        if current.next_node is self.head:
            self.head = None
        else:
            self.head = current.next_node
            next_node = self.head
            while next_node.next_node is not current:
                next_node = next_node.next_node
            next_node.next_node = self.head
        del current
        return temp

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

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

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

আমাদের প্রথম কাজ হল সর্বশেষ নোডটিকে খুঁজে বের করা। কিভাবে করা যায়? আমরা কিন্তু ইতিমধ্যে শিখে এসেছি। যেই নোডের next_node ভ্যারিয়েবল হেডকে পয়েন্ট করে সেটাই সর্বশেষ নোড। সেজন্য একটা লুপ ঘুরিয়ে আমরা সর্বশেষ নোডটিকে খুঁজে বের করেছি। রিমুভ করার আগে নোডের আইটেমটা একটা 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
            elif current.next_node is self.head:
                current = None
            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

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

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

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

উপরের আলোচনা থেকে এটা স্পষ্ট বোঝাই যাচ্ছে, সার্কুলার লিংকড লিস্টের অপারেশন ও ইমপ্লিমেন্টেশন অনেকটা সিঙ্গলি লিংকড লিস্টের মতই। একটু চেষ্টা করলেই পারা যাবে।