[Bermain muzik] DOUG LLOYD: Baiklah. Jadi, jika anda baru sahaja selesai yang video pada senarai secara tunggal berkaitan maaf Saya meninggalkan anda di luar pada sedikit cliffhanger. Tetapi saya gembira anda berada di sini untuk menyelesaikan kisah senarai duanya adalah terpakai berkaitan. 

Jadi, jika anda ingat dari video itu, kita bercakap tentang bagaimana secara tunggal berkaitan senarai lakukan menghadiri keupayaan kami untuk berurusan dengan maklumat di mana bilangan elemen atau bilangan item dalam senarai boleh berkembang atau mengecut. Kini kita boleh berurusan dengan sesuatu seperti itu, di mana kami tidak dapat menanganinya dengan pameran. 

Tetapi mereka mengalami satu had kritikal yang adalah bahawa dengan secara tunggal berkaitan senarai, kami hanya pernah boleh bergerak dalam satu arah melalui senarai. Dan hanya keadaan sebenar mana yang boleh menjadi masalah adalah apabila kita cuba untuk memadam elemen tunggal. Dan kami tidak sekali membincangkan bagaimana untuk melakukannya dalam senarai secara tunggal berkaitan dalam kod pseudo. Ia sudah pasti boleh dilakukan, tetapi ia boleh menjadi sedikit kerumitan. Jadi, jika anda mendapati diri anda dalam keadaan di mana anda cuba untuk memadam elemen tunggal dari senarai atau ia akan diperlukan bahawa anda akan memotong elemen tunggal dari senarai, anda mungkin mahu mempertimbangkan untuk menggunakan duanya adalah terpakai berkaitan senarai bukannya senarai yang secara tunggal berkaitan. Oleh kerana senarai duanya adalah terpakai berkaitan membolehkan anda untuk bergerak kedua-dua hadapan dan ke belakang melalui senarai dan bukannya hanya ke hadapan melalui list-- yang hanya dengan menambah satu elemen tambahan definisi struktur kami untuk nod senarai duanya adalah terpakai berkaitan. 

Sekali lagi, jika anda tidak akan dapat memotong elemen tunggal dari list-- kerana kami menambah satu medan tambahan kepada struktur kami definisi, nod sendiri untuk senarai duanya adalah terpakai berkaitan akan menjadi lebih besar. Mereka akan mengambil lebih banyak bait ingatan. Dan jadi jika ini bukan sesuatu anda akan perlu lakukan, anda boleh memutuskan ia tidak bernilai perdagangan luar perlu menghabiskan tambahan bait memori diperlukan untuk senarai duanya adalah terpakai berkaitan jika anda tidak akan memotong elemen tunggal. Tetapi mereka juga sejuk untuk perkara-perkara lain juga. 

Jadi seperti yang saya katakan, kita hanya perlu menambah satu medan tunggal untuk struktur kami definition-- tanggapan ini daripada penunjuk Sebelumnya. Jadi dengan senarai yang secara tunggal berkaitan, kita mempunyai nilai dan penunjuk Seterusnya, jadi senarai duanya adalah terpakai berkaitan hanya mempunyai cara untuk bergerak ke belakang juga. 

Sekarang dalam berkaitan secara tunggal senarai video, kita berbincang mengenai adalah lima daripada perkara utama yang anda perlukan untuk menjadi dapat melakukan untuk bekerja dengan senarai berkaitan. Dan bagi kebanyakan, hakikat bahawa itu senarai duanya adalah terpakai berkaitan tidak benar-benar satu lompatan besar. Kita masih boleh mencari melalui dengan hanya bergerak ke hadapan dari awal hingga akhir. Kita masih boleh mewujudkan nod daripada udara nipis, cukup banyak cara yang sama. Kita boleh memadam senarai cantik banyak cara yang sama juga. Perkara-perkara itu sahaja adalah secara halus berbeza, benar-benar, adalah memasukkan nod baru ke dalam senarai, dan kami akhirnya akan bercakap tentang memotong satu unsur dari senarai juga. Sekali lagi, cukup banyak tiga yang lain, kami tidak akan bercakap tentang mereka sekarang kerana mereka hanya tweak yang sangat kecil kepada idea-idea yang dibincangkan dalam senarai video secara tunggal berkaitan. 

Jadi mari kita memasukkan nod baru ke dalam senarai duanya adalah terpakai berkaitan. Kita bercakap tentang melakukan ini untuk secara tunggal berkaitan senarai juga, tetapi ada beberapa tambahan menangkap dengan senarai duanya adalah terpakai berkaitan. Kami [? lulus?] dalam ketua disenaraikan di sini dan beberapa nilai sewenang-wenangnya, dan kami mahu mendapatkan ketua baru senarai daripada fungsi ini. Itulah sebabnya ia mengembalikan bintang dllnode. Jadi apakah langkah-langkah? Mereka adalah, sekali lagi, hampir sama kepada senarai secara tunggal berkaitan dengan satu tambahan tambahan. Kami mahu memperuntukkan ruang untuk yang baru nod dan periksa untuk memastikan ia adalah sah. Kami mahu mengisi nod bahawa sehingga dengan apa sahaja maklumat yang kami mahu meletakkan di dalamnya. Perkara terakhir yang perlu kita do-- yang perkara tambahan yang perlu kita lakukan, rather-- adalah untuk menetapkan penunjuk Sebelum kepala lama senarai. Ingat bahawa kerana senarai duanya adalah terpakai GLC kita boleh bergerak ke hadapan dan backwards-- yang bermakna setiap nod sebenarnya menunjukkan dua nod lain dan bukan hanya satu. Dan dengan itu kita perlu untuk menetapkan kepala lama dalam senarai untuk menunjukkan ke belakang untuk ketua baru senarai berkaitan, yang adalah sesuatu kami tidak perlu lakukan sebelum ini. Dan seperti sebelum ini, kita hanya mengembalikan penunjuk kepada ketua baru senarai. 

Jadi di sini adalah senarai. Kami mahu memasukkan 12 ke dalam senarai ini. Perhatikan rajah adalah sedikit berbeza. Setiap nod mengandungi tiga fields-- data dan penunjuk seterusnya dalam merah, dan penunjuk Sebelum warna biru. Tiada apa-apa sebelum nod 15, jadi penunjuk Sebelum adalah null. Ia adalah permulaan senarai. Tiada apa-apa di hadapannya. Dan apa-apa yang datang selepas nod 10, dan jadi ia adalah penunjuk seterusnya ialah null juga. 

Jadi mari kita menambah 12 ke senarai ini. Kita perlu [didengar] ruang untuk nod. Kita meletakkan 12 di dalamnya. Dan sekali lagi, kita perlu benar-benar berhati-hati untuk tidak memecahkan rantai. Kami mahu menyusun semula petunjuk dalam susunan yang betul. Dan kadang-kadang yang mungkin mean-- seperti yang kita akan lihat terutamanya dengan delete-- bahawa kita mempunyai beberapa petunjuk berlebihan, tetapi itu OK. 

Jadi, apa yang kita mahu lakukan dahulu? Saya akan mengesyorkan ini perkara yang anda perlu mungkin lakukan adalah untuk mengisi petunjuk daripada 12 nod sebelum anda menyentuh orang lain. Jadi apa yang 12 akan menunjukkan akan datang? 15. Apa yang datang sebelum 12? Apa-apa. Sekarang kita telah memenuhi maklumat tambahan di 12 jadi ia mempunyai Sebelumnya, Next, dan nilai. 

Sekarang kita boleh mempunyai 15-- ini tambahan langkah kita bercakap about-- kita boleh mempunyai 15 titik kembali ke 12. Dan sekarang kita boleh bergerak ketua senarai berkaitan juga menjadi 12. Jadi ia agak sama dengan apa yang kita lakukan dengan senarai secara tunggal GLC kecuali untuk langkah tambahan sebanyak menghubungkan kepala lama dalam senarai belakang untuk ketua baru senarai. 

Sekarang mari kita akhirnya memadam nod dari senarai berpaut. Jadi katakan kita ada beberapa fungsi lain yang adalah mencari nod kita mahu memadam dan telah memberikan kita penunjuk untuk betul-betul nod yang kita mahu padamkan. Kita tidak need-- mengatakan kepala masih di peringkat global diisytiharkan. Kita tidak perlu kepala di sini. Semua fungsi ini lakukan adalah kami telah mendapati penunjuk kepada yang betul-betul kita nod mahu menghilangkan. Mari kita membuangnya. Ia adalah lebih mudah dengan duanya adalah terpakai berkaitan senarai. First-- ia sebenarnya hanya beberapa perkara. Kita hanya perlu untuk menetapkan sekitarnya petunjuk nod 'supaya mereka melangkau lebih nod yang kita mahu padamkan. Dan kemudian kita boleh memadam nod tersebut. Jadi sekali lagi, kami hanya akan melalui sini. Kami nampaknya memutuskan bahawa kami mahu memadam X. nod Dan sekali lagi, apa yang saya melakukan sini-- oleh way-- yang adalah kes umum untuk nod yang ada di tengah-tengah. Terdapat beberapa kaveat tambahan yang anda perlu mengambil kira apabila anda memotong awal-awal senarai atau akhir sangat senarai. Ada beberapa khas kes sudut menangani sana. 

Jadi ini berfungsi untuk memotong mana-mana nod di tengah-tengah yang list-- yang mempunyai penunjuk yang sah ke hadapan dan penunjuk yang sah ke belakang, sah penunjuk sebelum dan Seterusnya. Sekali lagi, jika anda bekerja dengan hujung, anda perlu untuk mengendalikan mereka sedikit berbeza, dan kami tidak akan bercakap tentang itu sekarang. Tetapi anda boleh mungkin memikirkan apa yang perlu yang perlu dilakukan hanya dengan menonton video ini. 

Jadi kami telah diasingkan X. X adalah nod kami mahu memadam dari senarai. Apa yang kita lakukan? Pertama, kita perlu untuk menyusun semula petunjuk luar. Kita perlu menyusun semula 9. berikut untuk melangkau lebih 13 dan menunjukkan kepada 10-- yang adalah apa yang kita baru sahaja selesai. Dan kita juga perlu menyusun semula 10 yang terdahulu untuk menghala ke 9 dan bukan menunjuk ke 13. 

Jadi sekali lagi, ini adalah gambar rajah untuk memulakan dengan. Ini adalah rangkaian kami. Kita perlu untuk melangkau lebih 13, tetapi kita perlu juga memelihara integriti senarai. Kami tidak mahu kehilangan apa-apa maklumat dalam arah. Oleh itu, kita perlu untuk menyusun semula petunjuk dengan berhati-hati jadi kami tidak memecahkan rantai pada semua. 

Oleh itu, kita boleh mengatakan 9. penunjuk Seterusnya menunjuk ke tempat yang sama yang tiga belas Next penunjuk mata sekarang. Kerana kami akhirnya akan mahu untuk melangkau lebih 13. Jadi di mana sahaja 13 mata seterusnya, anda mahu sembilan untuk menunjukkan sana. Jadi itulah yang. Dan kemudian di mana sahaja 13 mata di belakang kepada, apa sahaja yang datang sebelum 13, kita mahu 10 untuk menunjukkan itu bukannya 13. Sekarang perhatikan, jika anda mengikuti anak panah, kita boleh turun 13 tanpa benar-benar kehilangan apa-apa maklumat. Kami terus integriti senarai, bergerak kedua-dua ke hadapan dan ke belakang. Dan kemudian kita boleh hanya jenis untuk membersihkannya sehingga sedikit dengan menarik senarai bersama-sama. Oleh itu, kita disusun semula itu petunjuk mana pihak. Dan kemudian kita dibebaskan X nod yang mengandungi 13, dan kami tidak mematahkan rantai. Oleh itu, kita telah berbuat baik. 

Nota terakhir di sini pada senarai berkaitan. Jadi kedua-dua singly- dan dua kali ganda berkaitan senarai, seperti yang kita lihat, sokongan sisipan benar-benar berkesan dan penghapusan unsur-unsur. Anda cukup banyak boleh lakukan dalam masa yang berterusan. Apa yang kita perlu lakukan untuk memadam elemen sesaat yang lalu? Kami berpindah satu penunjuk. Kami berpindah penunjuk lain. Kami dibebaskan X-- mengambil masa tiga operasi. Ia sentiasa mengambil masa tiga operasi untuk memadam node-- bahawa untuk membebaskan nod. 

Bagaimana kita memasukkan? Well, kami hanya sentiasa tacking pada mulanya jika kita memasukkan cekap. Oleh itu, kita perlu rearrange-- bergantung kepada jika ia yang singly- atau dua kali ganda berkaitan senarai, kita mungkin perlu melakukan tiga atau empat operasi max. Tetapi sekali lagi, ia sentiasa tiga atau empat. Tidak kira berapa banyak elemen dalam senarai kami, ia sentiasa tiga atau empat operations-- seperti penghapusan sentiasa tiga atau empat operasi. Ia adalah masa yang berterusan. Jadi, itu benar-benar hebat. 

Dengan tatasusunan, kita telah melakukan sesuatu seperti jenis kemasukan. Anda mungkin ingat sisipan yang jenis bukan algoritma masa yang berterusan. Ia sebenarnya cukup mahal. Jadi ini adalah lebih baik untuk memasukkan. Tetapi seperti yang saya nyatakan di secara tunggal berkaitan senarai video, kami mempunyai Kelemahan di sini juga, kan? Kami telah kehilangan keupayaan untuk rawak mengakses elemen. Kita tidak boleh mengatakan, saya mahu beberapa elemen empat atau unsur nombor 10 dalam senarai berpaut dengan cara yang sama yang kita boleh berbuat demikian dengan array atau kita boleh hanya terus indeks ke dalam elemen array kita. 

Dan sebagainya cuba untuk mencari elemen dalam list-- berpaut jika pencarian adalah important-- sekarang mungkin mengambil masa linear. Seperti senarai mendapat lebih lama, ia mungkin mengambil satu langkah tambahan untuk setiap elemen tunggal dalam senarai dalam untuk mencari apa yang kita cari. Jadi ada keseimbangan perdagangan. Ada sedikit pro dan con unsur di sini. 

Dan senarai duanya adalah terpakai berkaitan tidak adalah jenis terakhir gabungan struktur data yang kita akan bercakap tentang, mengambil semua binaan asas blok C yang meletakkan bersama-sama. Kerana sebenarnya, kita boleh malah menjadi lebih baik daripada ini untuk mewujudkan satu struktur data yang anda mungkin boleh untuk mencari melalui dalam masa yang berterusan juga. Tetapi lebih kepada yang dalam video lain. 

Saya Doug Lloyd. Ini adalah CS50.