[موسیقی بجانے] ڈوگ لایڈ: ٹھیک. تو آپ کو صرف یہ ہے کہ ختم ہو گیا تو اکیلے منسلک فہرستوں معذرت پر ویڈیو میں آپ کو چھوڑ دیا ایک cliffhanger کے تھوڑا سا. لیکن میں آپ کو ختم کرنے کے لئے یہاں ہیں خوش ہوں دوگنا سے منسلک فہرستوں کی کہانی. 

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

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

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

میں نے کہا تو، ہم صرف شامل کرنا پڑے ہمارے ڈھانچہ کرنے کے لئے ایک میدان اس تصور definition-- سابقہ ​​پوائنٹر کے. ایک اکیلے منسلک فہرست کے ساتھ تو، ہم ، قیمت اور اگلے پوائنٹر ہے تو دوگنا سے منسلک فہرست صرف ہے ایک طریقہ کے طور پر اچھی طرح سے پیچھے کی طرف منتقل کرنے کے لئے. 

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

تو ایک نیا نوڈ داخل کرنے کی اجازت ایک دوگنا سے منسلک فہرست میں. ہم نے کے لئے ایسا کرنے کے بارے میں بات اس کے ساتھ ساتھ فہرستوں اکیلے سے تعلق رکھنے والے، لیکن اضافی سے ایک جوڑے کی ہے دوگنا سے منسلک فہرست کے ساتھ پالے. ہم ہیں؟ گزر؟] کے سر میں یہاں کی فہرست اور کچھ صوابدیدی قیمت، اور ہم نئے سربراہ حاصل کرنا چاہتے ہیں اس تقریب سے باہر فہرست. یہ ایک dllnode سٹار واپس یہی وجہ ہے کہ. تو اقدامات کیا ہیں؟ وہ ایک بار پھر، بہت ملتے جلتے ہیں فہرستوں اکیلے سے تعلق رکھنے والے کے لئے ایک اضافی علاوہ کے ساتھ. ہم نے ایک نئے کے لئے جگہ مختص کرنا چاہتے ہیں نوڈ اور چیک یہ درست ہے بات کو یقینی بنانا. ہم اس نوڈ کو بھرنے کے لئے چاہتے ہیں جو بھی معلومات کے ساتھ ہم اس میں ڈال کرنا چاہتے ہیں. آخری بات ہم do-- کرنے کی ضرورت ہے ہم کیا کرنے کی ضرورت اضافی چیز، rather-- پچھلے پوائنٹر کو حل کرنے کے لئے ہے فہرست کے پرانے سر کی. یاد رکھیں کہ کیونکہ کے دوگنا سے منسلک فہرستوں، ہم آگے بڑھنے کر سکتے ہیں اور جس backwards-- ہر نوڈ اصل میں اشارہ ہے کہ کا مطلب ہے کہ دو دوسرے نوڈس کی بجائے صرف ایک کے لئے. اور اس طرح ہم کو حل کرنے کی ضرورت ہے فہرست پرانے سر کے نئے سربراہ پسماندہ کی طرف اشارہ کرنا کچھ تھا جس لنک کی فہرست، ہم سے پہلے ایسا کرنے کی ضرورت نہیں تھی. اور پہلے، ہم صرف ایک واپس فہرست کے نئے سربراہ پوائنٹر. 

تو یہاں ایک فہرست ہے. ہم اس فہرست میں 12 شامل کرنے کے لئے چاہتے ہیں. آریھ کہ نوٹس تھوڑا سا مختلف ہے. ہر نوڈ تین fields-- مشتمل اعداد و شمار، اور سرخ رنگ میں ایک اگلے پوائنٹر، اور نیلے رنگ میں گزشتہ پوائنٹر. کچھ بھی نہیں، 15 نوڈ سے پہلے آتا ہے تو اس کے پچھلے پوائنٹر شہوت انگیز null ہے. اس فہرست کے آغاز. اس سے پہلے کچھ بھی نہیں ہے. اور کچھ بھی نہیں، 10 نوڈ کے بعد آتا ہے اور تو یہ اگلے پوائنٹر کے ساتھ ساتھ، شہوت انگیز null ہے ہے. 

تو اس فہرست میں 12 شامل ہیں. ہم نوڈ کے لئے [اشراوی] کی جگہ کی ضرورت. ہم نے اس کے 12 کے اندر ڈال دیا. اور پھر، ہم واقعی کرنے کی ضرورت ہے محتاط سلسلہ توڑنے کے لئے نہیں. ہم پنرویوستیت کرنا چاہتے ہیں صحیح ترتیب میں اشارہ. اور کبھی کبھی کہ mean-- سکتا ہم خاص طور پر نظر آئے گا کے طور پر delete-- ساتھ ہم نے کچھ ہے کہ فالتو اشارہ، لیکن یہ ٹھیک ہے. 

تو ہم سب سے پہلے کیا کرنا چاہتے ہو؟ میں سفارش کرے گا چیزیں آپ کو شاید کرنا چاہیے کیا 12 اشارہ کو بھرنے کے لئے ہے نوڈ آپ کسی اور کو چھو سے پہلے. تو کیا 12 اگلے کی طرف اشارہ کرنے جا رہا ہے؟ 15. کیا 12 سے پہلے آتا ہے؟ کچھ بھی نہیں. اب ہم بھر دیا ہے 12 میں اضافی معلومات تو یہ پچھلا اگلا، اور قیمت ہے. 

اب ہم کر سکتے ہیں 15-- یہ اضافی ہم بات کر رہے تھے about-- قدم واپس 12 15 نقطہ ہو سکتا ہے. اور اب ہم کے سر کو منتقل کر سکتے ہیں لنک کی فہرست بھی 12 ہونا. تو یہ خوبصورت کی طرح ہے جو ہم اکیلے سے تعلق رکھنے والے کی فہرست کے ساتھ کر رہے تھے، کے اضافی مرحلے کے علاوہ فہرست پرانے سر منسلک فہرست کے نئے سربراہ کے پاس واپس. 

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

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

تو ہم الگ تھلگ ہے ایکس ایکس نوڈ ہے ہم نے فہرست سے خارج کرنا چاہتے ہیں. ہم کیا کریں؟ سب سے پہلے، ہم پنرویوستیت کرنے کی ضرورت باہر اشارہ. ہم پنرویوستیت کرنے کی ضرورت 9 کے اگلے 13 سے زائد کو چھوڑ دیں اور نقطہ 10-- جس سے ہم صرف کیا ہے کیا ہے. اور ہم بھی کرنے کی ضرورت ہے 10 کے سابقہ ​​پنرویوستیت بجائے 13 کی طرف اشارہ کے 9 کی طرف اشارہ کرنے. 

تو ایک بار پھر، یہ تھا کے ساتھ شروع کرنے کے لئے آریھ. یہ ہماری سلسلہ تھا. ہم، 13 سے زائد جائیں کرنے کی ضرورت لیکن ہم بھی محفوظ کرنے کی ضرورت ہے فہرست کی سالمیت. ہم کسی بھی کھو نہیں کرنا چاہتے یا تو سمت میں معلومات. تو ہم پنرویوستیت کرنے کی ضرورت اشارہ احتیاط تو ہم بالکل چین نہیں ٹوٹتے. 

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

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

ہم کس طرح داخل ہے؟ ٹھیک ہے، ہم صرف ہمیشہ ہیں آغاز پر tacking کی ہم مؤثر طریقے سے داخل کر رہے ہیں تو. تو ہم rearrange-- کرنے کی ضرورت ہے یہ تو پر منحصر ایک singly- یا دوگنا سے منسلک فہرست، ہم تین ایسا کرنے کی ضرورت ہو سکتی یا چار آپریشن زیادہ سے زیادہ. لیکن ایک بار پھر، یہ ہمیشہ تین یا چار ہے. یہ کتنے کوئی فرق نہیں پڑتا عناصر، ہماری فہرست میں ہیں یہ ہمیشہ تین یا چار operations-- ہے صرف منسوخی ہمیشہ ہے جیسے تین یا چار آپریشن. یہ مسلسل وقت ہے. تو یہ واقعی بہت اچھا ہے. 

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

اور اس طرح ایک تلاش کرنے کی کوشش ایک لنک list-- میں عنصر تلاش important-- ہے اب لکیری وقت لگ سکتا ہے. فہرست طویل ہو جاتا ہے، اس ایک اضافی قدم لگ سکتا ہے فہرست میں ہر ایک عنصر میں حکم ہم کے لئے تلاش کر رہے ہیں تلاش کرنے کے لئے. تو تجارتی آف ہے. ایک حامی کے تھوڑا سا ہے یہاں اور con عنصر. 

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

میں ڈوگ لایڈ ہوں. یہ CS50 ہے.