ডাবলি লিংকড লিস্ট চেইনিং
এই বাস্তবায়নে প্রতিটি হ্যাশ বাকেটে একটি ডাবলি লিংকড লিস্ট থাকে। প্রতিটি নোডে next (n) এবং prev (p) পয়েন্টার থাকে, যা দুই দিকে ট্রাভার্সাল এবং ডিলিশন সহজ করে।
অ্যালগরিদম সারসংক্ষেপ
- ইনসার্ট: হ্যাশ বাকেট খালি হলে নতুন নোড হেড এবং টেল দুইটিই। না হলে টেলের পরে যোগ করুন এবং টেল আপডেট করুন।
- ডিলিট: কী ম্যাচ করলে নোড ডিলিট করুন, প্রিভ এবং নেক্স্ট পয়েন্টার আপডেট করুন। হেড/টেল হ্যান্ডল করুন।
- সার্চ: লিস্ট ট্রাভার্স করে কী খুঁজুন, পাওয়া গেলে মান প্রিন্ট করুন।
উদাহরণ কোড (সंক্ষিপ্ত)
struct HashTableEntry {
int d, k;
HashTableEntry *n, *p;
};
class HashMapTable {
HashTableEntry **ht, **top; // ht = head, top = tail
public:
void insert(int k, int v) { /* ... ডাবলি লিস্ট ইনসার্ট ... */ }
void remove(int k) { /* ... ডাবলি লিস্ট ডিলিট ... */ }
void SearchKey(int k) { /* ... সার্চ ... */ }
};আউটপুট নমুনা
Element found at key 6: 7
লাভ: ডাবলি লিংকড লিস্টে ডিলিট অপারেশন O(1) সময়ে সম্ভব (যেহেতু প্রিভ পয়েন্টার আছে)।
