ڈیٹا اسٹرکچرز اور الگورتھمز کے موضوع پر ایک نظر

فرض کریں میں آپ کو قلم اور کاغذ پکڑا کر کہتا ہوں کہ آپ نے تین کام کرنے ہیں:

1. میں پچاس بندوں کے نام باری باری لکھواؤں گا انہیں آپ نے اس کاغذ پر لکھنا ہے۔
2. اگر ضرورت پڑی تو میں آپ سے کہوں گا کہ فلاں بندے کا نام لسٹ میں دیکھ کر بتائیں کہ وہ موجود ہے یا نہیں۔
3. ضرورت پڑنے پر میں آپ سے کہوں گا کہ فلاں بندے کا نام لسٹ سے نکال دیں۔

Data Structures and Algorithms کا موضوع ان تین کاموں کے گرد گھومتا ہے یعنی نیا ریکارڈ میموری میں اسٹور کرنا، مطلوبہ ریکارڈ تلاش کرنا، اور کوئی ریکارڈ ختم کرنا۔ اس مثال میں یوں سمجھ لیں کہ (1) قلم پروسیسر ہے اور کاغذ میموری ہے۔ (2) جس ترتیب سے کاغذ پر آپ نے یہ ڈیٹا لکھا ہے مثلاً ایک لائن چھوڑ کر، یا ایک صفحے پر دو کالموں میں، یا حروف تہجی کی ترتیب سے، یعنی جس ڈھانچے میں یہ ڈیٹا کاغذ پر موجود ہے، اسے آپ ڈیٹا اسٹرکچر سمجھ لیں۔ (3) اور آپ نے بندوں کے نام لکھنے، تلاش کرنے اور ختم کرنے کے لیے جو طریقہ کار استعمال کیا ہے ، اسے الگورتھم سمجھ لیں۔

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

اس ٹٹوریل میں ہم زیادہ ٹیکنیکل ڈیٹیلز میں نہیں جائیں گے بلکہ تعارفی انداز میں دیکھیں گے کہ ڈیٹا اسٹرکچرز استعمال کرتے ہوئے ڈیٹا پراسیسنگ کے حوالے سے عام طور پر کس نوعیت کے مسائل پیش آتے ہیں اور ان سے کیسے نمٹا جاتا ہے۔ ڈیٹا اسٹرکچرز دو طرح کے ہوتے ہیں:

1. ایک Linear جس میں ڈیٹا ایک ریل گاڑی کی مانند میموری میں موجود ہوتا ہے، اس نوعیت کے ڈیٹا اسٹرکچرز میں Array, Linked List, Stack, Queue شامل ہیں۔
2. دوسرا Non-Lenear جس میں ڈیٹا کی شکل کسی گراف یا درخت کی طرح ہوتی ہے، اس نوعیت کے ڈیٹا اسٹرکچرز میں Tree, Graph شامل ہیں۔

آئیں پہلے ایک نظر چند اصطلاحات پر ڈال لیتے ہیں۔ کسی بھی مقصد کے لیے ڈیٹا کی تمام ویلیوز کو پڑھنا Traversal کہلاتا ہے، اگر یہ عمل پہلی نوعیت کے ڈیٹا اسٹرکچرز کے لیے ہے تو اسے Linear Traversal کہتے ہیں جبکہ دوسری نوعیت کے ڈیٹا اسٹرکچرز کے لیے اس عمل کو آپ Non-Linear Traversal کہہ سکتے ہیں۔ ڈیٹا میں کوئی نئی ویلیو شامل کرنا Insertion کہلاتا ہے، کوئی خاص ویلیو تلاش کرنا Search کہلاتا ہے، کوئی ویلیو ختم کرنا Deletion کہلاتا ہے۔ ڈیٹا کی تمام ویلیوز کو ترتیب دینا Sorting کہلاتا ہے اور ڈیٹا کے مختلف حصوں کو آپس میں اکٹھا کرنا Merging کہلاتا ہے۔

کسی بھی ڈیٹا اسٹرکچر کو استعمال کرنے یعنی کمپیوٹر کی میموری میں اسٹور کرنے کے بنیادی طور پر دو طریقے ہیں، ایک طریقہ Array اور دوسرا طریقہ Objects ہے:

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

ڈیٹا میں کوئی ویلیو کتنی تیز رفتاری سے داخل (Insert) کی جا سکتی ہے، کوئی ویلیو کتنی تیز رفتاری سے تلاش (Search) کی جا سکتی ہے، کتنی تیز رفتاری سے مطلوبہ ویلیو تک رسائی (Access) کی جا سکتی ہے، کتنی تیز رفتاری سے مطلوبہ ویلیو ختم (Delete) کی جا سکتی ہے۔ ان کاموں کی رفتار جانچنے کے عمل کو Time Complexity کہتے ہیں اور اس سلسلہ میں عام طور پر درج ذیل اصطلاحات استعمال ہوتی ہیں:

1. پہلی اصطلاح ہے۔ یعنی ڈیٹا میں سے کوئی ویلیو تلاش کرنے کے لیے اس کی تمام ویلیوز کو ایک ایک کر کے دیکھنا پڑے۔ ایسا اس صورت میں ہوتا ہے جب ڈیٹا ترتیب سے یعنی Sorted صورت میں موجود نہ ہو، اور نہ ہی ڈیٹا کی ہر ویلیو کے لیے کوئی Key بنائی گئی ہو۔
2. دوسری اصطلاح ہے۔ فرض کریں کہ اگر کمپیوٹر کی میموری میں ایک لاکھ لوگوں کے ریکارڈز موجود ہیں اور مجھے ان میں سے کوئی ایک نام تلاش کرنا ہے تو کیا کمپیوٹر پروگرام ایک لاکھ نام پڑھ کر مجھے ان میں سے مطلوبہ نام تلاش کر کے دے گا؟ ظاہر ہے کہ یہ اچھا طریقہ نہیں ہے۔ آپ جانتے ہوں گے کہ جب ڈیٹا ترتیب کے ساتھ موجود ہو تو اس میں سے مطلوبہ ویلیو تلاش کرنا آسان ہو جاتا ہے۔ مثلاً جب ہم ٹیلیفون ڈائریکٹری یا کسی زبان کی ڈکشنری میں سے کوئی لفظ تلاش کرتے ہیں تو کیا اس کے تمام صفحات دیکھتے ہیں؟ بالفرض مطلوبہ نام Fahad ہے تو ہم ڈائریکٹری کو درمیان سے کھول کر دیکھتے ہیں کہ اس صفحہ پر جو نام موجود ہیں وہ F سے پہلے والے کسی حرف سے شروع ہو رہے ہیں یا بعد والے۔ اگر بعد والے حرف سے شروع ہو رہے ہیں تو پھر ہم آدھی ڈائریکٹری کو نظرانداز کر کے باقی آدھی میں سے وہ نام تلاش کرتے ہیں۔ یعنی چند کوششوں پر ہمیں مطلوبہ نام مل جاتا ہے۔ اس عمل کو Binary Search کہا جاتا ہے اس لیے کہ تلاش کے اس طریقے میں ڈیٹا کو تب تک کو دو حصوں میں تقسیم کیا جاتا رہتا ہے جب تک کہ مطلوبہ ریکارڈ نہ ملے۔ کے مطابق اگر ویلیوز کی تعداد 1000 ہے تو زیادہ سے زیادہ 10 کوششوں میں مطلوبہ ویلیو مل جائے گی، اگر ویلیوز کی تعداد 100000 (ایک لاکھ) ہے تو مطلوبہ ویلیو زیادہ سے زیادہ 17 کوششوں میں مل جائے گی، اگر ویلیوز کی تعداد 1000000 (دس لاکھ) ہے تو مطلوبہ ویلیو زیادہ سے زیادہ 20 کوششوں میں مل جائے گی۔ آپ دیکھ سکتے ہیں کہ جیسے جیسے ویلیوز کی تعداد بڑھتی جا رہی ہے تلاش کرنے کی کوششوں کا تناسب کم ہوتا چلا جا رہا ہے، اس لیے کہ آدھا ڈیٹا تو پہلی ہی کوشش میں نظر انداز ہو جاتا ہے اور اس کے بعد کی کوششیں بھی ڈیٹا کو دو حصوں میں تقسیم کرتی جاتی ہیں۔
3. تیسری اصطلاح ہے۔ یعنی ڈیٹا میں سے مطلوبہ ویلیو ایک ہی کوشش میں مل جائے۔ مثلاً Hashing کے طریقہ کار میں ڈیٹا کے ہر ریکارڈ کے لیے اس کی ایک یا ایک سے زیادہ ویلیوز کو استعمال کرتے ہوئے ایک Key جنریٹ کی جاتی ہے جو کہ اس ریکارڈ کا لیبل بن جاتی ہے۔ بالفرض اگر آپ کو بتا دیا جائے کہ مطلوبہ شخص ریل گاڑی کے فلاں نمبر کے ڈبے میں ہے وہاں جا کر اسے وصول کر لیں، اب آپ کو کے مطابق ریل گاڑی کے تمام ڈبے باری باری چیک کرنے ضرورت نہیں ہے، بلکہ کے مطابق آپ براہ راست اس نمبر کے ڈبے تک پہنچ سکتے ہیں۔ البتہ ہیشنگ کے طریقہ کار کے تحت میموری میں ایسا ڈیٹا اسٹور کیا جاتا ہے جس کے ریکارڈز کو انفرادی طور پر تلاش کرنے کی ضرورت ہو اور یہ ریکارڈز کسی خاص ترتیب سے درکار نہ ہوں۔ کیونکہ اس طریقہ کار میں ریکارڈز کے لیے جنریٹ ہونے والی Keys تو ترتیب سے موجود ہوتی ہیں لیکن ریکارڈز کسی ترتیب سے موجود نہیں ہوتے، یعنی ڈیٹا کو کسی خاص ترتیب سے دیکھنے کے لیے اسے باقاعدہ Sort کرنا پڑتا ہے۔

   Hashing کے لیے سب سے اچھا الگورتھم وہ تصور ہوتا ہے جو منفرد سے منفرد Key جنریٹ کرے تاکہ ڈیٹا آپس میں گڈمڈ نہ ہو جائے۔ اگر ہیشنگ کا الگورتھم دو مختلف ویلیوز کے لیے ایک ہی Key جنریٹ کر دے تو اسے اصطلاح میں Collision کہا جاتا ہے۔ اس صورتحال سے نمٹنے کا عمل Collision Resolution کہلاتا ہے۔ اس سلسلہ میں ایک طریقہ Linear Probing کا ہے جس کے مطابق اگر کسی ویلیو کے لیے جنریٹ ہونے والی Key کے تحت پہلے سے کوئی ویلیو موجود ہے تو پھر Hash Table میں اس کے بعد والی کوئی خالی جگہ تلاش کر کے وہاں یہ نئی ویلیو اسٹور کی جاتی ہے، لیکن عین ممکن ہے کہ یہ نئی جگہ مستقبل میں آنے والی کسی اور ویلیو کی جگہ ہو، چنانچہ بعد میں آنے والی ویلیو بھی اسی تکنیک کے تحت اس سے آگے کسی خالی جگہ پر اسٹور کی جائے گی۔ آپ دیکھ سکتے ہیں کہ ویلیوز ایک دوسرے کی جگہ لے رہی ہیں، لیکن اگر اسٹور کرنے اور تلاش کرنے کی تکنیک ایک ہی ہو تو پھر مطلوبہ ویلیو کو Linear Probing تکنیک کے تحت ڈھونڈ لیا جاتا ہے۔ البتہ اس تکنیک کے تحت اگر بڑے ڈیٹا کو اسٹور کیا جائے تو امکان ہے کہ بہت سی ویلیوز ایک دوسرے کی جگہ لے لیں، یعنی ایک ویلیو کی جگہ دوسری ویلیو، اس کی جگہ تیسری ویلیو، اس کی جگہ چوتھی ویلیو لے۔ اسے اصطلاح میں Clustering کہتے ہیں جس سے نمٹنے کا ایک طریقہ Quadratic Probing ہے یعنی ویلیوز کو کچھ جگہیں چھوڑ کر اسٹور کیا جائے، دوسرا طریقہ Separate Chaining کا ہے کہ ہیش ٹیبل کے کسی خانے میں اگر Collision کی وجہ سے ایک سے زیادہ ویلیوز آ رہی ہیں تو پھر ان ویلیوز کو ایک لسٹ میں اسٹور کر کے اس خانے کے ساتھ منسلک کر دیا جائے۔

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

ڈیٹا کو میموری کے اندر ترتیب سے اسٹور کرنے یا میموری سے ڈیٹا کسی خاص ترتیب سے حاصل کرنے کا طریقہ کیا ہے؟

1. ایک صورت یہ ہے کہ جب ویلیوز موصول ہو رہی ہوں تو میموری میں انہیں ان کی اپنی ترتیب والی جگہ پر اسٹور کیا جائے، اس طرح جب یہ ڈیٹا درکار ہوگا تو اسی ترتیب میں اسے حاصل کیا جا سکتا ہے۔
2. دوسری صورت یہ ہے کہ اگر یہ ڈیٹا انفرادی ویلیوز کی بجائے ریکارڈز پر مشتمل ہے تو پھر ان ریکارڈز کو عام طور پر ان کے لیے جنریٹ ہونے والی Keys کے تحت ترتیب دیا جاتا ہے۔ اور پھر اگر ریکارڈز کی کسی خاصی ویلیو مثلاً فون نمبر کی ترتیب میں ریکارڈز دیکھنا مقصود ہو تو انہیں فون نمبرز کے مطابق Sort کر کے حاصل کیا جاتا ہے۔ ڈیٹا کو Sort کرنے کے لیے مختلف قسم کے الگورتھمز استعمال ہوتے ہیں جن میں Quicksort, Heapsort, Merge Sort, Bubble Sort, Selection Sort, Insertion Sort وغیرہ شامل ہیں۔

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