[موسیقی] داگ لوید: بسیار خوب. بنابراین اگر شما فقط به پایان رسید که ویدیو در لیست به تنهایی در ارتباط با عرض پوزش من به شما در ترک کردن بیت از یک مطلب یا داستان جالب. اما من خوشحالم که شما اینجا هستید را به پایان برساند هستم داستان از لیست مضاعف مرتبط. 

بنابراین اگر شما از یاد که ویدئو، ما صحبت کردیم در مورد چگونه به تنهایی در ارتباط لیست حضور پیدا توانایی ما برای مقابله با این اطلاعات که در آن تعدادی از عناصر و یا تعدادی از آیتم ها در یک لیست می تواند رشد کند و یا کوچک. ما در حال حاضر می تواند با برخورد چیزی شبیه به آن، که در آن ما نمی تواند با آن مقابله با آرایه. 

اما آنها از یک رنج می برند محدودیت مهم است که است که با تنهایی مرتبط لیست، ما تنها می تواند حرکت کند در یک جهت واحد از طریق لیست. و تنها وضعیت واقعی که در آن است که می تواند تبدیل به یک مشکل زمانی که ما در تلاش برای شد حذف یک عنصر واحد. و ما حتی نمی بحث در مورد چگونگی انجام این کار در یک لیست به تنهایی مرتبط در شبه. این قطعا شدنی است، اما می توان آن را یک بیت از یک بدون هیچ زحمتی. بنابراین اگر شما به خودتان پیدا کنید در یک وضعیت که شما در حال تلاش برای حذف عناصر واحد از لیست و یا آن را به توان مورد نیاز که به شما امکان حذف عناصر واحد از لیست، شما ممکن است بخواهید به نظر با استفاده از یک مضاعف مرتبط به جای یک لیست به تنهایی در ارتباط لیست. از آنجا که لیست مضاعف مرتبط شما اجازه می دهد به حرکت به جلو و عقب هر دو از طریق لیست جای فقط جلو را از طریق list-- فقط با اضافه کردن یک عنصر اضافی به تعریف ساختار ما برای لیست گره مضاعف مرتبط. 

باز هم، اگر شما در حال رفتن به شود حذف عناصر واحد از list-- چرا که ما در حال اضافه کردن یک فیلد اضافی به ساختار ما تعریف، گره خود برای لیست مضاعف مرتبط در حال رفتن به بزرگتر. آنها در حال رفتن به تا کلمه در ادامه متن از حافظه است. و بنابراین اگر این چیزی نیست شما در حال رفتن به نیاز به انجام، شما ممکن است تصمیم آن نه ارزش تجارت کردن به صرف اضافی بایت حافظه مورد نیاز برای یک لیست مضاعف مرتبط اگر شما نیست رفتن به حذف عناصر است. اما آنها نیز سرد برای چیزهای دیگر است. 

همانطور که گفتم، ما فقط باید برای اضافه کردن یک فیلد به ساختار ما definition-- این مفهوم از یک اشاره گر قبلی. بنابراین با یک لیست به تنهایی در ارتباط است، ما دارای ارزش و اشاره گر بعد، به این ترتیب لیست مضاعف مرتبط فقط یک راه برای حرکت به عقب است. 

در حال حاضر در تنهایی مرتبط لیست ویدئو، ما صحبت کردیم در مورد این پنج تن از می چیز اصلی که شما نیاز به قادر به انجام به کار با لیست های پیوندی. و برای بسیاری از این، این واقعیت است که یک لیست مضاعف مرتبط است واقعا یک جهش بزرگ است. ما هنوز هم می توانید از طریق جستجو و تنها حرکت رو به جلو از آغاز تا پایان. ما هنوز هم می تواند یک گره از ایجاد هوا نازک، بسیار به همان شیوه. ما می توانید لیست بسیار حذف بسیار به همان شیوه است. تنها چیزهایی که می ماهرانه مختلف، واقعا هستند، قرار دادن گره های جدید به لیست، و ما در نهایت باید در مورد حذف صحبت یک عنصر از لیست به عنوان. باز هم، بسیار سه دیگر، ما رفتن به بحث در مورد آنها در حال حاضر به دلیل آنها فقط ترفند بسیار جزئی در ایده های مورد بحث در لیست تنهایی مرتبط ویدیو. 

بنابراین اجازه دهید درج یک گره جدید به یک لیست مضاعف مرتبط. ما در مورد انجام این کار برای صحبت لیست تنهایی مرتبط به عنوان خوب، اما یک زن و شوهر از اضافی وجود دارد دریچه با لیست مضاعف مرتبط. بودند [؟ عبور؟] در سر از لیست اینجا و برخی از ارزش های خودسرانه، و ما می خواهیم به رئیس جدید از لیست خارج از این تابع. به همین دلیل آن را می گرداند یک ستاره dllnode. پس چه مراحل است؟ آنها هستند، دوباره، بسیار شبیه لیست به تنهایی در ارتباط علاوه بر این با یک اضافی. ما می خواهیم به اختصاص فضا برای یک جدید گره و چک کنید تا مطمئن شوید که آن را معتبر است. ما می خواهیم برای پر کردن آن گره تا با هر اطلاعات ما می خواهم به در آن قرار داده. آخرین چیزی که ما نیاز به انجام چیزی که فوق العاده ما نیاز به انجام، rather-- است به رفع اشاره گر قبلی از سر قدیمی از لیست. به یاد داشته باشید که به دلیل لیست مضاعف مرتبط، ما می توانیم به جلو حرکت و backwards-- که بدان معنی است که هر گره در واقع اشاره به دو گره دیگر به جای فقط یک. و بنابراین ما نیاز به تعمیر سر قدیمی از لیست به نقطه رو به عقب برای رئیس جدید لیست پیوندی، که چیزی بود ما مجبور به انجام قبل از. و مانند قبل، ما فقط بازگشت اشاره گر به رئیس جدید این فهرست است. 

بنابراین در اینجا یک لیست است. ما می خواهیم به قرار دادن 12 به این لیست است. توجه داشته باشید که نمودار کمی متفاوت است. هر گره شامل سه fields-- داده ها، و یک اشاره گر به رنگ قرمز، و یک اشاره گر قبلی به رنگ آبی. هیچ چیز قبل از 15 گره می آید، بنابراین اشاره گر قبلی خود تهی است. این آغاز این فهرست است. هیچ چیز قبل از آن وجود دارد. و هیچ چیز پس از گره 10، و پس از آن اشاره گر تهی است و همچنین. 

بنابراین 12 اضافه کردن به این لیست دهید. ما [نامفهوم] فضا برای گره نیاز دارند. ما قرار داده است 12 داخل آن است. و سپس دوباره، ما نیاز به واقعا می شود مراقب باشید به شکستن زنجیره ای است. ما می خواهیم به تنظیم مجدد اشاره گر را در جهت درست. و گاهی اوقات که ممکن است mean-- به عنوان ما به خصوص را ببینید با delete-- که ما مجبور برخی از اشاره گر کار برکنار شده، اما این OK. 

بنابراین چه چیزی ما می خواهیم انجام اولین بار؟ من توصیه می کنم چیزهایی که شما باید احتمالا انجام به پر کردن اشاره گر از 12 گره قبل از شما را لمس هر کس دیگری. پس چه شده است 12 رفتن به نقطه به بعد؟ 15. چه می آید قبل از 12؟ هیچ چی. در حال حاضر ما را پر کرده ام اطلاعات اضافی در 12 پس از آن تا قبلی، بعدی، و ارزش. 

حالا ما می توانیم 15-- این اضافی مرحله ما about-- ما صحبت می کردند می توانید 15 نقطه تماس تا 12 داشته باشد. و در حال حاضر ما می تواند سر از حرکت لیست پیوندی به 12 نیز می باشد. پس از آن بسیار شبیه به آنچه ما با لیست به تنهایی در ارتباط انجام می دهند، به جز برای گام اضافی اتصال سر قدیمی از لیست به رئیس جدید بازگشت. 

حالا اجازه دهید در نهایت حذف یک گره از یک لیست پیوندی. بنابراین اجازه دهید می گویند که ما برخی از عملکرد های دیگر که پیدا کردن یک گره ما می خواهیم به حذف و ما یک اشاره گر به داده دقیقا گره که ما می خواهیم را حذف کنید. ما حتی نمی need-- می گویند هنوز هم سر در سطح جهانی اعلام کرد. ما سر اینجا لازم نیست. همه این تابع انجام شده است ما را یک اشاره گر به ما دقیقا گره پیدا شده است می خواهید برای خلاص شدن از. بیایید خلاص شدن از آن. آن را خیلی آسان تر با لیست مضاعف مرتبط. First-- آن را در واقع فقط چند چیز. ما فقط نیاز به تعمیر اطراف اشاره گر گره ها به طوری که آنها جست و خیز بیش گره ما می خواهیم را حذف کنید. و پس از آن ما می توانیم آن گره را حذف کنید. پس دوباره، ما فقط رفتن را از طریق اینجا. ما تصمیم گرفته که ما می خواهیم X. گره را حذف کنید و دوباره، آنچه من انجام here-- توسط way-- یک مورد کلی برای یک است گره است که در وسط. یک زن و شوهر وجود دارد هشدارهای اضافی است که شما نیاز به در نظر گرفتن زمانی شما در حال حذف ابتدا از لیست و یا پایان بسیار از لیست. یک زن و شوهر از خاص وجود دارد موارد گوشه ای برای مقابله با است. 

بنابراین این کار برای پاک کردن هر گره در وسط یک list-- که یک اشاره گر به جلو مشروع و یک اشاره گر مشروع رو به عقب، مشروع قبلی و بعدی اشاره گر. باز هم، اگر شما در حال کار با به پایان می رسد، شما می نیاز به رسیدگی آن کمی متفاوت، و ما در حال رفتن به بحث در مورد که در حال حاضر. اما شما احتمالا می تواند کشف کردن آنچه نیاز به فقط با تماشای این فیلم انجام شده است. 

X. X بنابراین ما جدا شده ام گره است ما می خواهیم از لیست حذف کنید. چه کنیم؟ اول، ما نیاز به تنظیم مجدد اشاره گر خارج است. ما نیاز به تنظیم مجدد 9 بعدی به جست و خیز بیش از 13 و نقطه به نقطه 10-- که چیزی است که ما فقط انجام داده ام. و ما نیز نیاز به تنظیم مجدد 10 قبلی به نقطه را به 9 به جای اشاره به 13. 

بنابراین دوباره، این بود که نمودار برای شروع با. این زنجیره ما بود. ما باید به جست و خیز بیش از 13، اما ما نیاز به حفظ هم یکپارچگی لیست. ما نمی خواهیم از دست دادن هر اطلاعات در هر دو جهت. بنابراین ما نیاز به تنظیم مجدد اشاره گر به دقت بنابراین ما زنجیره ای در همه شکستن نیست. 

بنابراین ما می توانیم 9 اشاره گر می گویند اشاره به همان محل که سیزده بعدی اشاره گر اشاره در حال حاضر. از آنجا که ما در نهایت هستید رفتن به می خواهم به جست و خیز بیش از 13. بنابراین هر جا که 13 امتیاز بعدی، شما می خواهید نه به نقطه وجود دارد به جای آن. بنابراین این است که. و پس از آن هر کجا که 13 امتیاز برگشت به، هر آنچه که می آید قبل از 13، ما می خواهیم به نقطه 10 به جای 13. در حال حاضر متوجه، اگر شما به دنبال فلش، ما می توانیم 13 قطره در واقع بدون از دست دادن هر گونه اطلاعات. ما در یکپارچگی لیست نگه داشته ام، حرکت هر دو جلو و عقب. و پس از آن ما فقط می توانید مرتب سازی بر از آن را پاک کردن کمی با کشیدن فهرست با هم. بنابراین ما بخواهند صفحاتی دوباره مرتب اشاره گرها در هر دو طرف. و سپس ما آزاد X را گره که شامل 13، و ما شکستن زنجیره ای است. بنابراین ما خوب است. 

توجه داشته باشید نهایی در اینجا در لیست های پیوندی. بنابراین هر دو singly- و مضاعف مرتبط لیست ها، به عنوان ما دیده ایم، پشتیبانی درج واقعا کارآمد و حذف عناصر. شما می توانید تقریبا انجام آن را در زمان ثابت است. چیزی که ما باید انجام دهید را حذف کنید یک عنصر فقط یک ثانیه قبل؟ ما یک اشاره گر منتقل شده است. ما اشاره گر دیگر منتقل کرد. ما آزاد X-- در زمان سه عملیات. این همیشه طول می کشد سه عملیات به حذف کنید که node-- را به رایگان یک گره. 

چگونه وارد کنیم؟ خب، ما فقط همیشه ضمیمه در آغاز اگر ما در حال قرار دادن موثر است. بنابراین ما نیاز به rearrange-- بسته به آن singly- یا مضاعف مرتبط لیست، ما ممکن است نیاز به انجام سه و یا چهار عملیات حداکثر. اما باز هم، آن را همیشه سه یا چهار. مهم نیست که چگونه بسیاری از عناصر در فهرست ما، آن را همیشه سه یا چهار operations-- درست مثل این است که همیشه حذف سه یا چهار عملیات. این زمان ثابت است. به طوری که واقعا بزرگ است. 

با آرایه ها، ما انجام شد چیزی شبیه به مرتب سازی درجی. شما احتمالا به یاد آورید که درج مرتب کردن بر اساس یک الگوریتم زمان ثابت نیست. این در واقع بسیار گران است. پس این است که خیلی بهتر برای قرار دادن. اما همانطور که در ذکر به تنهایی در ارتباط لیست ویدئو، ما یک حرکت نزولی را اینجا بیش از حد، درست است؟ ما توانایی از دست داده ام به طور تصادفی عناصر دسترسی داشته باشید. ما نمی توانیم بگوییم، من می خواهم تعداد عنصر چهار یا عنصر شماره 10 از یک لیست پیوندی راه همان است که ما می توانیم انجام این کار با یک آرایه یا ما می توانیم فقط به طور مستقیم صفحه اول به عنصر آرایه را می دهد. 

و به این ترتیب تلاش برای پیدا کردن عنصر در یک list-- مرتبط اگر جستجوی important-- است اکنون ممکن است زمان خطی است. به عنوان فهرست می شود دیگر، آن ممکن است یک گام اضافی را برای هر عنصر در لیست در جهت پیدا کردن آنچه که ما دنبال آن هستید. بنابراین تعادل وجود دارد. یک بیت از یک حرفه ای وجود دارد و عنصر باهم در اینجا. 

و لیست مضاعف مرتبط نیستند آخرین نوع از ترکیب ساختار داده که ما در مورد صحبت می کنید، در نظر گرفتن همه ساختمان های اساسی بلوک های C یک کنار هم قرار دادن. چرا که در واقع، ما می توانیم حتی بهتر از این برای ایجاد یک ساختار داده هایی را که شما ممکن است قادر به جستجو از طریق در زمان ثابت است. اما بیشتر که در یک ویدیو دیگر. 

من داگ لوید هستم. این CS50 است.