[Powered by Google Translate] پروگرامنگ میں، ہم اکثر اقدار کی فہرست کی نمائندگی کرنے کی ضرورت ہے، اس طرح کے ایک حصے میں طالب علموں کے نام کے طور پر یا تازہ ترین کوئز ان کے اسکور. 

C زبان میں اعلان کیا، arrays استعمال کیا جا سکتا ہے کی فہرست محفوظ. یہ آسان ہے ایک فہرست کے عناصر کو گننا ایک صف میں جمع ہے، اور اگر آپ تک رسائی حاصل کرنے کی ضرورت ہے یا ith فہرست عنصر پر نظر ثانی کچھ صوابدیدی انڈیکس کے لئے، میں جو مسلسل وقت میں کیا جا سکتا ہے، لیکن arrays نقصانات ہے، بھی ہے. 

جب ہم نے ان سے اعلان، ہم کہنا ضروری ہے سامنے وہ کتنا بڑا ہو، ایسا ہے، وہ کس طرح بہت سے عناصر کو جمع کر سکتے ہیں کس طرح اور بڑے ان عناصر ہیں، جو ان کی قسم کی طرف سے مقرر کیا جاتا ہے. مثال کے طور پر، int آمد (10) 10 اشیاء کو جمع کر سکتے ہیں جو ایک int کے سائز کے ہیں. 

ہم اعلان کے بعد ایک صف کے سائز کو تبدیل نہیں کر سکتے. ہم ایک نئی صف بنانے کے لئے ہے اگر ہم زیادہ عناصر کو محفوظ کرنا چاہتے ہیں. وجہ سے اس کی حد موجود ہے یہ ہے کہ ہمارے پروگرام پوری صف ذخیرہ میموری کا ایک ملحق حصہ کے طور پر. کہنا ہے کہ یہ بفر جہاں ہم اپنے صف میں محفوظ ہے. دوسرے متغیر ہو سکتا ہے ٹھیک ہے اگلی صف واقع یاد میں، تو ہم نہیں کر سکتے صرف صف بڑا بنا. 

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

یہاں integers کے ایک بہت سادہ منسلک کی فہرست کے لئے کچھ C کوڈ ہے. تم نے دیکھا ہے کہ ہم نے ہر نوڈ کی نمائندگی کر سکتے ہیں ، struct جس میں 2 چیزوں پر مشتمل ہے کے طور پر فہرست میں محفوظ کی عددی 'ویل نامی فہرست میں اگلے نوڈ لنک جو ہم نامی پوائنٹر کے طور پر کی نمائندگی کرتے ہیں 'اگلے. اس طرح، ہم مکمل فہرست کو ٹریک کر سکتے ہیں ، صرف ایک 1st نوڈ پوائنٹر کے ساتھ اور پھر ہم اگلے اشارہ پر عمل کر سکتے ہیں 2nd نوڈ، 3rd نوڈ، 4th نوڈ، اور اس پر، جب تک کہ ہم نے فہرست کے آخر میں ملتا ہے. 

آپ 1 فائدہ یہ ہے کو دیکھنے کے لئے کرنے کے قابل ہو سکتا ہے - مستحکم صف ڈھانچے پر ایک لنک کی فہرست کے ساتھ ہم میموری کا ایک بڑا حصہ کی ضرورت نہیں ہے، مکمل طور پر. فہرست کے 1st نوڈ یاد میں اس جگہ پر رہ سکتے ہیں، اور 2nd نوڈ یہاں پر تمام طرح کی ہو سکتی ہے. ہم تمام مراکز پر کوئی بات نہیں کہاں سے حاصل کیا وہ یاد میں ہیں، کیونکہ 1st نوڈ سے شروع، ہر نوڈ کے اگلے پوائنٹر ہمیں بتاتی ہے کہاں آگے جانے کے لئے ہے. 

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

مثال کے طور پر، اگر ہم درمیان میں ایک نوڈ رکھنے چاہتی تھی فہرست کے 2nd اور 3rd نوڈس  ہم 2nd یا 3rd نوڈس میں منتقل نہیں کریں گے. کا کہنا ہے کہ ہم اس سرخ نوڈ داخل کر رہے ہیں. ہمیں کرنا پڑے گا نئی نوڈ کے اگلے پوائنٹر مقرر کیا گیا ہے 3rd نوڈ کی طرف اشارہ اور پھر 2nd نوڈ اگلے پوائنٹر rewire ہمارے نئے نوڈ کی طرف اشارہ ہے. تو، ہم نے مکھی پر ہمارے فہرستوں کا سائز تبدیل کر سکتے ہیں کے بعد سے ہمارے کمپیوٹر تخکرمن پر انحصار نہیں کرتا، اشارہ کا استعمال کرتے ہوئے ان کی ذخیرہ کرنے منسلک بلکہ. 

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

اب، اصل میں کچھ کوڈ لکھنے لنک کی فہرست کے ساتھ کام کرتا ہے. چلو کا کہنا ہے کہ ہم integers کی ایک لنک کی فہرست کی ضرورت ہے. ہم نے ہماری فہرست میں ایک نوڈ دوبارہ نمائندگی کرسکتے ہیں 2 شعبوں کے ساتھ ایک struct کے طور پر، 'ویل' نامی ایک عددی قیمت اور ایک فہرست کے اگلے نوڈ کی اگلی پوائنٹر. ٹھیک ہے، کافی آسان لگتا ہے. 

چلو کا کہنا ہے کہ ہم نے ایک تقریب کو لکھنے کے لئے چاہتے ہیں جو فہرست اور پرنٹس traverses قیمت فہرست کے آخری نوڈ میں محفوظ ہے. ٹھیک ہے، اس کا مطلب ہے کہ ہم فہرست میں تمام مراکز کو گزرنا کرنے کی ضرورت ہوگی گزشتہ ایک کو تلاش کرنے کے لئے، لیکن ہم نہیں انہوں نے مزید کہا رہے ہیں یا کوئی بھی چیز حذف، ہم کو تبدیل کرنا چاہتے نہیں فہرست میں اگلے اشارہ کی اندرونی ساخت. 

تو، ہم traversal کے لئے ایک پوائنٹر خاص طور پر کی ضرورت ہو گی جو ہم نے فون 'کرالر. گے اس فہرست کے تمام عناصر کے ذریعے کرال اگلے اشارہ کی سیریز کے بعد. ہم محفوظ ہیں 1st نوڈ پر ایک پوائنٹر ہے، فہرست یا 'سر'. 1st نوڈ ہیڈ پوائنٹس. یہ قسم پوائنٹر نوڈ کو ہے. 

فہرست میں اصل 1st نوڈ کو حاصل کرنے کے لئے، ہم dereference اس پوائنٹر ہے، لیکن اس سے پہلے کہ ہم اس dereference کر سکتے ہیں، ہم چیک کرنے کے لیے کی ضرورت ہے اگر پوائنٹر شہوت انگیز null سب سے پہلے ہے. اگر یہ شہوت انگیز null ہے، فہرست خالی ہے، اور ہم باہر ایک پیغام ہے کہ کیونکہ فہرست خالی ہے کو پرنٹ کرنا چاہئے، آخری نوڈ نہیں ہے. لیکن، چلو کا کہنا ہے کہ فہرست خالی نہیں ہے. اگر یہ نہیں ہے، تو ہم پوری فہرست کے ذریعے کرال چاہئے ہم فہرست کے آخری نوڈ حاصل کرنے کے لئے، جب تک اور ہم کس طرح بتا دو اگر ہم فہرست میں آخری نوڈ میں تلاش کر رہے ہیں کر سکتے ہیں؟ 

ٹھیک ہے، اگر ایک نوڈ کے اگلے پوائنٹر خالی ہے، ہم جانتے ہیں کہ ہم آخر میں ہو کے بعد سے گزشتہ اگلے پوائنٹر فہرست میں کوئی اگلے نوڈ کی طرف اشارہ کرنا ہوگا. یہ اچھی پریکٹس ہے ہمیشہ گزشتہ نوڈ کے اگلے شہوت انگیز null initialized پوائنٹر رکھنے کے ایک معیاری جائیداد ہے جو ہمیں تنبیہات سب جب ہم نے فہرست کے آخر تک پہنچ چکے ہیں. 

لہذا، اگر کرالر → اگلے شہوت انگیز null ہے، یاد رکھیں کہ تیر نحو محولہ لقب ضبطی کے لئے ایک شارٹ کٹ ہے ایک struct پوائنٹر، تو تک رسائی اس کے اگلے عجیب برابر میدان: (* کرالر) اگلے. ایک بار جب ہم آخری نوڈ کو تلاش کر لیا ہے، ہم کرالر → ویل کو پرنٹ کرنے کے لئے چاہتے ہیں، موجودہ نوڈ میں قدر جو ہم جانتے ہیں کہ گزشتہ ایک ہے. دوسری صورت میں، اگر ہم نے ابھی تک فہرست میں آخری نوڈ میں نہیں ہیں، ہم فہرست میں اگلے نوڈ پر منتقل ہے چیک کرنے کے لیے اور اگر وہ آخری ہے. ایسا کرنے کے لئے، ہم صرف ہماری کرالر پوائنٹر قائم موجودہ نوڈ کے اگلے قیمت کی طرف اشارہ کرنے کے لئے، یہ ہے کہ فہرست میں اگلے نوڈ ہے. اس ترتیب کی طرف سے کیا جاتا ہے کرالر = کرالر اگلے →. اس کے بعد ہم نے مثال کے طور پر ایک لوپ کے ساتھ اس عمل کو دہرائیں، جب تک ہم آخری نوڈ کو تلاش کریں. لہذا مثال کے طور پر، اگر کرالر سر کی طرف اشارہ کرتے ہوئے کر رہے تھے ہم کرالر کرالر اگلے → کی طرف اشارہ ہے، جو 1st نوڈ کے اگلے میدان کے طور پر ایک ہی ہے. تو، اب ہماری کرالر 2nd نوڈ کی طرف اشارہ ہے، اور، پھر، ہم ایک لوپ کے ساتھ اس دہرانے جب تک ہم آخری نوڈ کو تلاش کر لیا ہے، ہے، نوڈ کے اگلے پوائنٹر شہوت انگیز null جہاں اشارہ کر رہا ہے. اور ہم وہاں ہیں، ہم فہرست میں آخری نوڈ تلاش کر لیا ہے، اور اس کی قدر کو پرنٹ کرنے کے لئے، ہم صرف کرالر → ویل کا استعمال کریں. 

Traversing اتنا بھی برا نہیں ہے، لیکن کیا داخل کے بارے میں؟ کی اجازت دیتا ہے کا کہنا ہے کہ ہم 4th پوزیشن میں ایک عددی داخل کرنا چاہتے ہیں ایک عددی فہرست میں. جو موجودہ 3rd اور 4th نوڈس کے درمیان ہے. ایک بار پھر، ہم صرف فہرست گزرنا ہے 3rd عنصر ہے، جس سے ہم کے بعد داخل کر رہے ہیں حاصل کرنے کے لئے. لہذا، ہم ایک کرالر پوائنٹر دوبارہ تشکیل فہرست گزرنا، اگر ہمارے سر پوائنٹر خالی ہے چیک کرنے کے لیے، اور اگر یہ نہیں ہے، سر نوڈ میں ہماری کرالر پوائنٹر اشارہ کرتے ہیں. تو، ہم 1st عنصر میں ہیں. ہم آگے 2 مزید عناصر کو ہم سے پہلے داخل کر سکتے ہیں ہے، تو ہم لوپ کے لئے استعمال کر سکتے ہیں int میں = 1، میں + +، میں <3 اور iteration لوپ میں سے ہر ایک میں، ہماری کرالر پوائنٹر 1 نوڈ کی طرف سے آگے آگے بڑھانے ، اگر موجودہ نوڈ کے اگلے میدان خالی ہے کی جانچ پڑتال کی طرف سے اور اگر ایسا نہیں ہے، اگلے نوڈ پر ہماری کرالر پوائنٹر کو منتقل اسے موجودہ نوڈ کے اگلے پوائنٹر کے برابر مقرر کر. تو، کے بعد ہمارے لیے لوپ ایسا کہتے ہیں کہ میں دو بار، ہم 3rd نوڈ تک پہنچ ہے، اور ایک بار ہماری کرالر پوائنٹر نوڈ کے پیچھے پہنچ گیا ہے جو ہم ہمارے نئے عددی شامل کرنے کے لئے چاہتے ہیں، ہم واقعی کس طرح داخل ہو؟ 

ٹھیک ہے، ہمارے نئے عددی فہرست میں داخل ہے اپنے ہی نوڈ struct کے ایک حصے کے کے طور پر، چونکہ یہ واقعی مراکز کی ایک ہی تسلسل ہے. تو، نوڈ کو ایک نئی پوائنٹر کہا جاتا ہے 'new_node، اور یاد کی طرف اشارہ ہے کہ اب ہم مختص مقرر ، نوڈ ہی کے لئے ڈھیر پر اور کتنی میموری ہم پر مختص کرنے کی ضرورت ہے؟ ، ویسے، ایک نوڈ کا سائز اور ہم عدد صحیح ہے کہ ہم پر داخل کرنا چاہتے ہیں اس کی ویل میدان قائم کرنے کے لئے کرنا چاہتے ہیں. چلو کہتے ہیں، 6. اب، نوڈ ہماری عددی قیمت پر مشتمل ہے. یہ بھی اچھی مشق ہے، نئے نوڈ کے اگلے میدان میں ابتدا شہوت انگیز null اشارہ، لیکن اب کیا ہوا؟ 

ہم نے فہرست کے اندرونی ڈھانچے کو تبدیل کرنا ہوگا اور اگلے اشارہ فہرست میں موجودہ میں موجود 3rd اور 4th نوڈس. چونکہ اگلے اشارہ فہرست کے حکم کا تعین اور چونکہ ہم ہمارے نئے نوڈ داخل کر رہے ہیں براہ راست فہرست کے وسط میں، یہ تھوڑا مشکل ہو سکتا ہے. یہ اس لئے ہے کیونکہ یاد ہے، ہمارے کمپیوٹر صرف فہرست میں نوڈس کے محل وقوع کے جانتا ہے گزشتہ نوڈس میں محفوظ اگلے اشارہ کی وجہ سے. لہذا، اگر ہم نے کبھی ان مقامات میں سے کسی کے ٹریک کو کھو دیا ہے، ہماری فہرست میں اگلے اشارہ میں سے ایک کو تبدیل کرنے کی طرف سے کہنا، مثال کے طور پر کہتے ہیں، ہم کو تبدیل کر دیا گیا 3rd نوڈ اگلے میدان یہاں کچھ نوڈ کی طرف اشارہ ہے. ہم قسمت سے باہر ہو سکتا ہے کیونکہ ہم نہیں کریں گے، چاہتے ہیں کسی بھی فہرست کے باقی جہاں تلاش خیال ہے، اور یہ کہ ظاہر ہے بہت برا ہے. لہذا، ہم نے حکم کے بارے میں بہت ہوشیار رہنا ہے جس میں ہم اندراج کے دوران ہمارے اگلے اشارہ جوڑتوڑ. 

تو، یہ آسان کرنے کے لئے، کا کہنا ہے کہ کہ ہماری پہلی 4 نوڈس اشارہ کی سیریز کی نمائندگی کرنے والے تیر کے ساتھ A، B، C، اور D کہا جاتا کہ نوڈ مربوط. لہذا، ہم ہمارے نئے نوڈ کو شامل کرنے کے لئے کی ضرورت ہے میں نوڈس سی اور ڈی کے درمیان یہ صحیح ترتیب میں کرنا ضروری ہے، اور میں تم سے کیوں ظاہر کریں گے. 

غلط پہلے طریقہ کو دیکھو. ، ہے، ہم جانتے ہیں کہ نئے نوڈ C بعد دائیں آنا ہوگا تو C اگلے پوائنٹر قائم new_node اشارہ. ٹھیک ہے، ٹھیک ہے لگتا ہے، ہم صرف کی طرف سے اب ختم ہے D نئے نوڈ کے اگلے پوائنٹر نقطہ بنا لیکن انتظار، کہ ہم کس طرح کر سکتے ہیں؟ صرف ایک چیز ہے جو ہمیں بتائیں کہ وہ کہاں D تھے، اگلے پوائنٹر پہلے C میں جمع ہے، لیکن ہم صرف اس پوائنٹر rewrote نیا نوڈ کی طرف اشارہ کرنے کے لئے، تو ہم اب کوئی سراگ نہیں ہے جہاں D میموری میں ہے، اور ہم نے فہرست کے باقی کو کھو دیا ہے. بالکل اچھا نہیں ہے. 

تو، کس طرح ہم یہ حق کیا کرتے ہیں؟ سب سے پہلے، نئے نوڈ کے ڈی میں اگلے پوائنٹر اشارہ اب دونوں نئے نوڈ اور سی اگلے اشارہ رہے ہیں اور اسی نوڈ، D کی طرف اشارہ کرتے ہوئے، لیکن وہ ٹھیک ہے. اب ہم C نئے نوڈ میں اگلے پوائنٹر اشارہ کر سکتے ہیں. لہذا، ہم نے کوئی ڈیٹا کھوئے بغیر اس نے کیا ہے. کوڈ میں، C موجودہ نوڈ ہے کہ traversal پوائنٹر کرالر اشارہ کر رہا ہے، اور D موجودہ نوڈ کے اگلے فیلڈ کی طرف سے کی طرف اشارہ کیا ہے نوڈ کی طرف سے ظاہر کیا جاتا ہے، یا کرالر → اگلے. لہذا، ہم نے سب سے پہلے نئے نوڈ کے اگلے پوائنٹر قائم کرالر اگلے → کی طرف اشارہ کرنے کے لئے، اسی طرح ہم نے کہا new_node اگلے پوائنٹر کرنا چاہیے مثال D کی طرف اشارہ ہے. اس کے بعد، ہم نے موجودہ نوڈ کے اگلے پوائنٹر مقرر کر سکتے ہیں ہمارے نئے نوڈ، بالکل اسی طرح جیسے ہم C ڈرائنگ میں new_node کی طرف اشارہ کا انتظار کرنا پڑا. اب سب کچھ ترتیب میں ہے، اور ہم نہیں کھو دیا کسی بھی اعداد و شمار کے ٹریک، اور ہم صرف کرنے کے قابل تھے فہرست کے وسط میں ہمارے نئے نوڈ چپکی سب کچھ کی تعمیر نو یا کسی بھی عناصر منتقل کئے بغیر جس طرح سے ہم ایک مقررہ لمبائی صف کے ساتھ تھا گے. 

لہذا، منسلک کی فہرست بنیادی، لیکن اہم، متحرک آنکڑا ڈھانچہ ہیں جس میں فائدہ اور نقصان دونوں ہیں arrays اور دیگر ڈیٹا کے ڈھانچے کے مقابلے میں، اور اکثر کمپیوٹر سائنس میں معاملہ ہے، یہ جانتے ہیں کہ جب ہر آلے کا استعمال کرنے کے لئے ضروری ہے، تاکہ آپ صحیح کام کے لئے صحیح سے مؤثر ہتھیار کو منتخب کر سکتے ہیں. 

مزید مشق کے لئے، افعال لکھنے کی کوشش کریں ایک لنک کی فہرست سے نوڈس کو خارج کر دیں - تاکہ جس میں آپ کو پنرویوستیت کے بارے میں ہوشیار رہنا ہوگا یاد رکھیں آپ کی اگلی اشارہ اس بات کا یقین کرنے کے لئے کہ آپ کو آپ کی فہرست کا ایک حصہ کھو نہیں - یا ایک لنک کی فہرست میں نوڈس شمار کے لئے ایک تقریب یا ایک مذاق ایک، منسلک فہرست میں نوڈس کے سب کے حکم کا راستہ. 

میرا نام جیکسن Steinkamp ہے، CS50 ہے.