اسکپ لسٹ ڈیٹا اسٹرکچر

اس سے پہلے ڈیٹا اسٹرکچرز کے تعارفی ٹٹوریل میں ہم نے Binary Search کے بارے میں بات کی تھی کہ اس کے تحت کسی خاص ترتیب میں موجود بڑے سے بڑے ڈیٹا میں سے مطلوبہ ویلیو چند کوششوں میں تلاش کی جا سکتی ہے۔ البتہ اس کی سہولت Array میں تو دستیاب ہوتی ہے لیکن Linked List میں یہ سہولت میسر نہیں ہوتی۔ اس کی وجہ یہ ہے کہ اررے کے تمام خانے میموری میں ایک ہی جگہ اکٹھے موجود ہوتے ہیں اور ہر خانے کا ایک انڈیکس نمبر ہوتا ہے، یعنی اررے کی پہلی اور آخری انڈیکس کی مدد سے اس کے درمیان والی انڈیکس معلوم کی جا سکتی ہے۔ چنانچہ اررے کی اسی خصوصیت کو استعمال کرتے ہوئے بائنری سرچ کے تحت اررے کو اس وقت تک دو حصوں میں تقسیم کیا جاتا رہتا ہے جب تک مطلوبہ ویلیو نہ مل جائے۔ لیکن چونکہ لنکڈ لسٹ کے آبجیکٹس میموری کے اندر مختلف جگہوں پر بکھرے پڑے ہوتے ہیں اور ان میں سے کسی آبجیکٹ کا انڈیکس نمبر نہیں ہوتا، اس لیے لنکڈ لسٹ کے درمیان تک پہنچنے کے لیے اس کے آدھے آبجیکٹس سے گزرنا ضروری ہے جو کہ کارکردگی کے لحاظ سے اچھی بات نہیں ہے۔ چنانچہ اس کے حل کے لیے Skip List ڈیٹا اسٹرکچر استعمال کیا جا سکتا ہے جو کہ ایک طرح سے لنکڈ لسٹ کی ایڈوانس شکل ہے۔

فرض کریں ہم نے اپنے کمپیوٹر پروگرام میں ایک لنکڈ لسٹ بنائی ہے جس میں ایک لاکھ ویلیوز ترتیب کے ساتھ یعنی Sorted صورت میں موجود ہیں۔ اگر ہمیں کہا جائے کہ فلاں ویلیو اس لنکڈ لسٹ میں تلاش کریں تو ہمارے پاس اس کے سوا کوئی حل نہیں کہ ہم لسٹ کے آغاز سے شروع ہو جائیں اور ایک ایک کر کے تمام ویلیوز کو چیک کریں۔ اگر مطلوبہ ویلیو لنکڈ لسٹ میں ستر ہزار ویلیوز کے بعد کہیں موجود ہے تو آپ سمجھ سکتے ہیں کہ ہم نے ایک ویلیو کی تلاش کے لیے ستر ہزار سے زیادہ موازنے کیے ہیں جو کہ کارکردگی کے نقطۂ نظر سے اچھی صورتحال نہیں ہے۔

چنانچہ Skip List میں اس صورتحال کا ایک حل پیش کیا گیا ہے۔ فرض کریں ہم ایک لاکھ والی لسٹ سے ایک مخصوص فاصلے سے چار مختلف ویلیوز لے کر ان کی ایک نئی لنکڈ لسٹ بنا لیتے ہیں۔ مثلاً پہلی ویلیو بیس ہزار پوزیشن والی، دوسری چالیس ہزار پوزیشن والی، تیسری ساٹھ ہزار پوزیشن والی اور چوتھی اَسی ہزار پوزیشن والی۔ اب اگر کوئی ویلیو تلاش کے لیے دی جائے تو پہلے اسے دوسری لسٹ میں سے تلاش کیا جائے گا جس میں صرف چار ویلیوز موجود ہیں:

1. پہلے یہ دیکھا جائے گا کہ یہ ویلیو بیس ہزار سے چھوٹی ہے یا بڑی ہے؟
2. اگر بڑی ہے تو پھر یہ دیکھا جائے گا کہ یہ چالیس ہزار سے چھوٹی ہے یا بڑی ہے؟
3. اگر بڑی ہے تو پھر یہ دیکھا جائے گا کہ ساٹھ ہزار سے چھوٹی ہے یا بڑی؟
4. اگر بڑی ہے تو پھر یہ دیکھا جائے گا کہ اسی ہزار سے چھوٹی ہے یا بڑی؟
5. اگر یہ ویلیو اَسی ہزار سے چھوٹی ہے تو ہمیں پتہ چل گیا ہے کہ پہلی یعنی مکمل لنکڈ لسٹ میں یہ ویلیو ساٹھ ہزار اور اَسی ہزار کے درمیان میں موجود ہے۔

آپ دیکھ سکتے ہیں کہ Skip List میں صرف چار موازنوں نے ہمیں مطلوبہ ویلیو کے قریب پہنچا دیا ہے، جبکہ Linked List میں اس مقصد کے لیے ساٹھ ہزار سے زیادہ موازنے کرنے پڑتے۔

یہ میں نے صرف ایک مثال کے طور پر عرض کیا ہے ورنہ Skip List ڈیٹا اسٹرکچر میں حسب ضرورت اصل لسٹ کی کئی نقلیں بنائی جاتی ہیں، جن میں اصل لسٹ میں سے مخصوص فاصلوں سے لی گئی ویلیوز کو کاپی کیا جاتا ہے۔ یعنی سب سے اوپر والی لسٹ میں سب سے کم ویلیوز ہوتی ہیں، اس سے نیچے والی میں اس سے زیادہ، اور اس طرح سب سے نیچے والی لسٹ اصل ہوتی ہے جس میں تمام ویلیوز موجود ہوتی ہیں۔ مطلوبہ ویلیو کی تلاش کے لیے پروگرام سب سے اوپر والی لسٹ سے شروع کرتا ہے اور موازنہ کرتے کرتے نیچے والی لسٹوں پر منتقل ہوتا چلا جاتا ہے۔ اگر مطلوبہ ویلیو لسٹ میں موجود ہو تو عموماً یہ آخری یعنی مکمل لسٹ میں سے دستیاب ہوتی ہے، لیکن اس بات کا بھی کسی حد تک امکان ہوتا ہے کہ یہ ویلیو اوپر والی کسی لسٹ میں سے ہی مل جائے۔ اسکپ لسٹ کے استعمال میں اضافی لسٹوں کے لیے کمپیوٹر میموری میں کچھ زیادہ جگہ درکار ہوتی ہے لیکن اس سے کارکردگی میں جو بہتری آتی ہے اس کی وجہ سے میموری کے اس اضافی استعمال کی کچھ خاص پروا نہیں کی جاتی۔