>> [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.