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

اگر مجھ سے کہا جائے کہ ایک کمپیوٹر پروگرام بناؤں جو ایک لاکھ ویلیوز کو میموری میں اسٹور کر سکے، تو میں یوں کروں گا کہ اس مقصد کے لیے اپنے پروگرام کے اندر ایک Array بناؤں گا جس کا سائز ایک لاکھ ہوگا۔ البتہ اس سلسلہ میں یہ مسائل درپیش ہوں گے:

1. اگر کل ویلیوز صرف دس ہزار موصول ہوئیں تو اس دوران کمپیوٹر میموری کے بقیہ نوے ہزار خانے مختص رہیں گے اور کوئی دوسرا پروگرام انہیں استعمال نہیں کر سکے گا۔
2. اگر کل ویلیوز ایک لاکھ سے زیادہ آگئیں تو پھر ایک نیا اررے بنا کر پرانے اررے کی تمام ویلیوز اس میں منتقل کرنا پڑیں گی۔
3. اگر اس اررے کی ویلیوز ایک خاص ترتیب میں یعنی Sorted صورت میں میموری کے اندر موجود ہیں، تو پھر ایک نئی ویلیو کو اس کی ترتیب کے اعتبار سے اررے کے درمیان میں شامل کرنے کے لیے کئی ہزار ویلیوز کو اپنی جگہ چھوڑ کر ایک ایک خانہ آگے منتقل ہونا پڑے گا۔

آپ سمجھ سکتے ہیں کہ کارکردگی کے نقطۂ نظر سے یہ صورتحال کچھ اچھی نہیں ہے، چنانچہ اس سے نمٹنے کے لیے Array کی بجائے عام طور پر Objects کی صورت میں کمپیوٹر میموری کے اندر ڈیٹا اسٹور کیا جاتا ہے۔ Linked List بھی ایک ایسا ہی ڈیٹا اسٹرکچر ہے جو کمپیوٹر میموری میں آبجیکٹس کی صورت میں ویلیوز کو اسٹور کرتا ہے جس سے درج بالا مسائل حل ہو جاتے ہیں، مثلاً:

1. لنکڈ لسٹ کی صورت میں ڈیٹا اسٹور کرنے کے لیے پہلے سے یہ بتانا ضروری نہیں ہے کہ کل ویلیوز کی تعداد کیا ہوگی، چنانچہ ایک لاکھ ویلیوز کے لیے ایک لاکھ میموری کے خانے پہلے سے ریزرو نہیں کرنا پڑیں گے۔
2. اسی طرح اگر ہمارا اندازہ شروع میں ایک لاکھ ویلیوز کا تھا لیکن بعد میں اگر دو یا تین لاکھ ویلیوز بھی آجائیں گی تو کوئی مسئلہ نہیں، کمپیوٹر کی میموری جس مقدار میں دستیاب ہوگی ہم اسی اعتبار سے اس میں جتنی چاہیں ویلیوز اسٹور کر سکتے ہیں۔
3. جیسا کہ آپ جانتے ہوں گے کہ میموری کے اندر اررے کے خانے ایک تسلسل کے ساتھ بغیر کسی وقفے کے موجود ہوتے ہیں، اس لیے ترتیب والے اررے کے درمیان میں کسی نئی ویلیو کے اضافے کے لیے باقی ویلیوز کو آگے منتقل کرنا پڑتا ہے۔ لیکن اس کے برعکس لنکڈ لسٹ کی ویلیوز میموری کے اندر آبجیکٹس کی صورت میں مختلف جگہوں پر بکھری پڑی ہوتی ہیں، البتہ ان آبجیکٹس کو ایک دوسرے کے ساتھ منسلک کرنے کے لیے ہر آبجیکٹ میں اس سے آگے والے آبجیکٹ کا ریفرنس (پوائنٹر) رکھا جاتا ہے۔ اور اس ڈیٹا اسٹرکچر کے نام ’’لنکڈ لسٹ‘‘ کی وجہ بھی یہی ہے کہ اس میں آبجیکٹس کو آپس میں لنک کیا جاتا ہے۔ چنانچہ لنکڈ لسٹ میں نئی ویلیو کے اضافے کے لیے ڈیٹا کو شفٹ کرنے کی ضرورت نہیں ہوتی بلکہ جس جگہ نئی ویلیو کا اضافہ کرنا ہو وہاں پہلے سے موجود دو آبجیکٹس کے ریفرنسز اس نئے آبجیکٹ کے ساتھ منسلک کر دیے جاتے ہیں۔

لنکڈ لسٹ کو میموری کے اندر اسٹور کرنے کے بعد اس کے ڈیٹا پر ہم جس قسم کا کام کرنا چاہتے ہیں، اس کی نوعیت کے اعتبار سے لنکڈ لسٹ کی درج ذیل صورتیں استعمال کی جاتی ہیں:

Singly Linked List

جیسا کہ اس کے نام سے اندازہ ہو رہا ہے کہ اس لسٹ میں ہر آبجیکٹ اپنے سے اگلے والے ایک آبجیکٹ کے ساتھ منسلک ہوتا ہے۔ جو کمپیوٹر پروگرام یہ سنگلی لنکڈ لسٹ بناتا ہے وہ اپنے پاس اس لسٹ کے پہلے آبجیکٹ کا ریفرنس رکھتا ہے جسے Head کہتے ہیں۔ یہ پہلا آبجیکٹ دراصل اس لسٹ پر کوئی بھی کام کرنے کے لیے نقطۂ آغاز ہوتا ہے۔ لنکڈ لسٹ عام طور پر دو طرح کی لسٹس کے لیے استعمال ہوتا ہے، ایک Stack لسٹ اور دوسری Queue لسٹ۔

• پہلی نوعیت کی لسٹ یعنی Stack کے نام سے ظاہر ہے کہ یہ ایسے کاموں کے لیے استعمال ہوتی ہے جس میں کچھ چیزیں ایک دوسرے کے اوپر اسٹاک کی جائیں۔ جیسے باورچی خانے میں پلیٹیں ایک دوسرے کے اوپر رکھی جاتی ہیں، یا کچھ گیمز میں کارڈز ایک دوسرے کے اوپر رکھے جاتے ہیں، یا اس طرح کے دیگر آئیڈیاز آپ سوچ سکتے ہیں۔ چنانچہ اسٹاک کا تصور یہ ہے کہ جو چیز سب سے آخر میں رکھی جائے گی وہی سب سے پہلے اٹھائی جائے گی۔ اسے اصطلاح میں LIFO کہا جاتا ہے یعنی Last In First Out کہ لنکڈ لسٹ میں جو آبجیکٹ سب سے آخر میں شامل کیا جائے گا وہ سب سے پہلے نکالا جائے گا۔ دوسرے لفظوں میں اسٹاک والی لنکڈ لسٹ میں جس طرف سے آبجیکٹ شامل کیا جاتا ہے اسی طرف سے نکالا جاتا ہے۔
• دوسری نوعیت کی لسٹ یعنی Queue کے نام سے بھی ظاہر ہے کہ یہ ایسے کاموں کے لیے استعمال ہوتی ہے جس میں قطار کی صورت بنتی ہو۔ جیسے کسی بینک کے سامنے بل جمع کرانے کی قطار، کسی ریسٹورنٹ میں ٹیبل حاصل کرنے کی قطار، یا اس طرح کے دیگر آئیڈیاز آپ سوچ سکتے ہیں۔ چنانچہ کیو کا تصور یہ ہے کہ جو چیز پہلے قطار میں شامل ہوگی وہ پہلے باہر نکلے گی۔ اسے اصطلاح میں FIFO کہا جاتا ہے یعنی First In First Out کہ لنکڈ لسٹ میں جو آبجیکٹ سب سے پہلے شامل ہوگا وہ سب سے پہلے نکالا جائے گا۔ مطلب یہ ہوا کہ کیو والی لنکڈ لسٹ میں ایک طرف سے آبجیکٹ شامل کیا جاتا ہے اور دوسری طرف سے نکالا جاتا ہے۔

Doubly Linked List

ایسی لنکڈ لسٹ جس میں ہر آبجیکٹ میں ایک کی بجائے دو ریفرنسز رکھے جاتے ہیں، ایک ریفرنس پیچھے والے آبجیکٹ کا اور دوسرا ریفرنس آگے والے آبجیکٹ کا۔ یعنی ڈبلی لنکڈ لسٹ کے تمام آبجیکٹس اپنے سے اگلے اور پچھلے آبجیکٹس کے ساتھ منسلک ہوتے ہیں۔ جو پروگرام یہ ڈبلی لنکڈ لسٹ بناتا ہے وہ اپنے پاس دو آبجیکٹس Head اور Tail رکھتا ہے۔ Head آبجیکٹ کی مدد سے لسٹ کے آغاز سے شروع ہو کر آخر تک جایا جا سکتا ہے، جبکہ Tail آبجیکٹ کی مدد سے لسٹ کے آخر سےشروع ہو کر آغاز تک جایا جا سکتا ہے۔ جیسا کہ ہم جانتے ہیں کہ سنگلی لنکڈ لسٹ میں Head آبجیکٹ سے آغاز کرنا پڑتا ہے اور پھر اس کے بعد والے ہر آبجیکٹ کا Next ریفرنس استعمال کرتے ہوئے مطلوبہ آبجیکٹ تک پہنچا جاتا ہے۔ لیکن ڈبلی لنکڈ لسٹ میں Head آبجیکٹ اور Tail آبجیکٹ کے علاوہ ہر اس آبجیکٹ کو نقطۂ آغاز بنایا جا سکتا ہے جس کا ریفرنس اس وقت آپ کے پاس موجود ہے، اس لیے کہ ہر آبجیکٹ میں Next ریفرنس بھی موجود ہے اور Previous ریفرنس بھی، جنہیں استعمال کرتے ہوئے لسٹ میں حسب ضرورت کسی طرف بھی جایا جا سکتا ہے۔

Circular Linked List

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