লিংকড লিস্টপড়তে ৫ মিনিট লাগবে

সার্কুলার লিংকড লিস্ট (Circular Linked List)

যে শেকলের কোনো শেষ নেই — শেষের কড়াটা আবার প্রথম কড়ার সাথে জোড়া লাগানো

access: O(n)insert head: O(1)insert tail: O(1)traverse full circle: O(n)space: O(n)

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

একটা সার্কুলার লিংকড লিস্ট (Circular linked list) ঠিক এভাবেই কাজ করে। এটা এমন একটা লিংকড লিস্ট, যার একদম শেষের নোডের পয়েন্টারটা null বা ফাঁকা না থেকে, সরাসরি আবার প্রথম নোড বা হেড (head)-এর দিকে পয়েন্ট করে থাকে। ফলে পুরো চেইনটা মিলে একটা কমপ্লিট রিং তৈরি হয়।

সাধারণত আপনি এই রিংয়ের যেকোনো একটা নোডের ঠিকানা (যেটাকে head বা বর্তমান নোড বলা যায়) সেভ করে রাখেন। সেখান থেকে next পয়েন্টার ধরে ধরে আপনি পুরো গোল চক্করটা ঘুরে আসতে পারবেন। যেহেতু এর কোনো শেষ বা 'হার্ড স্টপ' নেই, তাই আপনাকে ততক্ষণ ঘুরতে হবে যতক্ষণ না আপনি আবার সেই শুরুর নোডটায় ফেরত আসছেন (এভাবেই পুরো একবার ঘোরা কাউন্ট করা হয়)।

নতুন কিছু ঢোকানো বা ইনসার্ট করা

একটা সার্কুলার লিস্টের শুরুতে বা হেডে (head) নতুন নোড ঢোকাতে হলে:

আগে নতুন নোডটা বানান, আর তার next পয়েন্টারকে বর্তমান হেডের দিকে তাক করে দিন।
এরপর হাঁটতে হাঁটতে একদম শেষের নোড বা টেইল (tail)-এর কাছে যান (যার next পয়েন্টার পুরোনো হেডের দিকে তাক করা ছিল)।
সেই টেইলের next পয়েন্টারটাকে চেঞ্জ করে নতুন নোডের দিকে তাক করে দিন।
সবশেষে head নামটাকে সরিয়ে নতুন নোডের ঘাড়ে বসিয়ে দিন।

আপনার কাছে যদি টেইল (tail) বা শেষের নোডটার ঠিকানিন আগে থেকে সেভ করা থাকে, তবে ২ নম্বর ধাপটা একদম চোখের পলকে (O(1) স্পিডে) হয়ে যায় — ফলে পুরো কাজটাই O(1)-এ শেষ হয়। শুধু হেডের ঠিকানা থাকলে টেইল পর্যন্ত হেঁটে আসতে O(n) সময় লাগে।

◈ Explore circular list

← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন

দ্রষ্টব্য: সার্কুলার লিংকড লিস্টের সবচেয়ে বড় বিপদের জায়গা হলো: এটা যে গোল হয়ে ঘুরছে, সেটা ভুলে যানয়া। আপনি যদি সাধারণ লিস্টের মতো শুধু 'সামনে null আছে কি না' চেক করে লুপ চালান, তবে ওই লুপ জীবনেও শেষ হবে না! তাই লুপ থেকে বের হওয়ার একমাত্র উপায় হলো এটা চেক করা যে, আপনি আবার শুরুর নোডটায় ফিরে এসেছেন কি না।

সার্কুলার লিস্ট জীবনে কোথায় কাজে লাগে?

এর গোল হয়ে ঘোরার স্বভাবটাই কিছু কিছু ক্ষেত্রে একদম পারফেক্ট সমাধান দেয়:

রাউন্ড-রবিন শিডিউলিং (Round-robin scheduling) — অপারেটিং সিস্টেম যখন অনেকগুলো কাজ বা প্রসেসকে একটার পর একটা সময় দেয়। সার্কুলার লিস্ট থাকলে শেষের কাজটা শেষ হওয়ার পর কোনো এক্সট্রা কোড ছাড়াই অটোমেটিক আবার প্রথম কাজের কাছে চলে যানয়া যায়।
গানের প্লেলিস্ট (Repeat mode) — শেষ গানটা বাজার পর আবার প্রথম গানটা বাজানেন। সার্কুলার লিস্ট দিয়ে এটা একদম ন্যাচারালি হ্যান্ডেল করা যায়।
মাল্টিপ্লেয়ার বোর্ড গেম (Turn-based games) — লুডু বা মনোপোলির মতো গেমে প্লেয়াররা গোল হয়ে বসে একটার পর একটা চাল দেয়। শেষের জনের চাল শেষ হলে আবার প্রথম জনের পালা আসে।
বাফার রিং (Buffer rings) — নেটওয়ার্ক প্যাকেট বা অডিও বাফারের কাজে একটা ফিক্সড সাইজের সার্কুলার অ্যারে বা লিস্ট ব্যবহার করা হয়, যাতে জায়গা শেষ হলে মেমোরি নষ্ট না করে আবার প্রথম দিক থেকে লেখা শুরু করা যায়।

পুরো চক্করটা ধরা বা ডিটেক্ট (Detect) করা

লিস্ট ধরে ঘোরার সময়, যেকোনো একটা নোড থেকে শুরু করুন আর সেই নোডে ফিরে এলেই থেমে যান:

pseudocode

current = head
do:
    visit(current)
    current = current.next
while current != head

এখানে একটা ডু-হোয়াইল (do-while) লুপ ব্যবহার করা হয়েছে — এতে অন্তত একবার শুরুর নোডে ঢোকা যায়, আর তারপর আবার ঘুরে সেখানে ফিরে না আসা পর্যন্ত লুপ চলতে থাকে।

সার্কুলার বনাম সাধারণ লিংকড লিস্ট

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