>> [MUSIC PLAYING]
Doug LLOYD: Baiklah.
Jadi jika Anda baru saja selesai yang video pada daftar tunggal-linked maaf
Saya meninggalkan Anda off pada sedikit cliffhanger.
Tapi aku senang kau di sini untuk menyelesaikan kisah daftar doubly-linked.
>> Jadi, jika Anda ingat dari video yang, kita berbicara
tentang bagaimana secara tunggal-linked daftar lakukan menghadiri kemampuan kita
untuk menangani informasi di mana jumlah elemen
atau jumlah item di daftar dapat tumbuh atau menyusut.
Kita sekarang dapat menangani sesuatu seperti itu, di mana
kita tidak bisa menghadapinya dengan array.
>> Tapi mereka menderita satu batasan kritis yang
adalah bahwa dengan tunggal-linked daftar, kita dapat hanya pernah bergerak
dalam satu arah melalui daftar.
Dan satu-satunya situasi nyata mana yang bisa menjadi masalah
adalah ketika kita mencoba untuk menghapus satu elemen.
Dan kita bahkan tidak membahas bagaimana melakukannya dalam daftar sendiri-sendiri-linked di pseudocode.
Hal ini tentu bisa dilakukan, tapi itu bisa menjadi sedikit merepotkan.
Jadi jika Anda menemukan diri Anda dalam situasi di mana
Anda mencoba untuk menghapus elemen tunggal dari daftar
atau itu akan diperlukan bahwa Anda akan menghapus
elemen tunggal dari daftar, Anda mungkin ingin
untuk mempertimbangkan menggunakan doubly-linked daftar bukannya daftar tunggal-linked.
Karena daftar doubly-linked memungkinkan Anda untuk bergerak maju dan mundur baik
melalui daftar bukannya hanya maju melalui list-- yang
hanya dengan menambahkan satu elemen tambahan definisi struktur kami
untuk daftar node doubly-linked.
>> Sekali lagi, jika Anda tidak akan akan menghapus elemen tunggal
dari list-- karena kami menambahkan bidang ekstra untuk struktur kami
definisi, node sendiri untuk daftar doubly-linked
akan menjadi lebih besar.
Mereka akan mengambil up byte lagi memori.
Dan jadi jika ini bukan sesuatu yang Anda akan perlu melakukan,
Anda mungkin memutuskan itu tidak layak trade off
harus menghabiskan ekstra byte memori yang dibutuhkan
untuk daftar ganda-linked jika Anda tidak akan menghapus elemen tunggal.
Tapi mereka juga keren untuk hal-hal lain juga.
>> Jadi seperti yang saya katakan, kita hanya perlu menambahkan satu bidang tunggal untuk struktur kami
definition-- gagasan ini dari pointer Sebelumnya.
Jadi dengan daftar sendiri-linked, kami memiliki nilai dan pointer berikutnya,
sehingga doubly-linked list hanya memiliki cara untuk bergerak mundur juga.
>> Sekarang di-linked sendiri-sendiri Daftar video, kami berbicara
tentang ini adalah lima dari hal utama yang harus
mampu lakukan untuk bekerja dengan daftar terkait.
Dan untuk sebagian besar, kenyataan bahwa itu daftar ganda-linked
tidak benar-benar sebuah lompatan besar.
Kita masih bisa mencari melalui dengan hanya bergerak maju dari awal sampai akhir.
Kita masih bisa membuat simpul dari udara tipis, cukup banyak dengan cara yang sama.
Kita bisa menghapus daftar cukup banyak cara yang sama juga.
Satu-satunya hal yang yang agak berbeda,
benar-benar, yang memasukkan node baru ke dalam daftar,
dan kami akhirnya akan berbicara tentang menghapus satu elemen dari daftar juga.
Sekali lagi, cukup banyak tiga lainnya, kami
tidak akan berbicara tentang mereka sekarang karena mereka hanya
tweak sangat kecil pada ide-ide yang dibahas dalam daftar video yang tunggal-linked.
>> Jadi mari kita menyisipkan node baru ke dalam daftar doubly-linked.
Kami berbicara tentang melakukan hal ini untuk daftar tunggal terkait juga,
tapi ada beberapa tambahan menangkap dengan daftar doubly-linked.
Kami [? lewat?] di kepala daftar di sini dan beberapa nilai sewenang-wenang,
dan kami ingin mendapatkan kepala baru daftar dari fungsi ini.
Itu sebabnya ia mengembalikan bintang dllnode.
Jadi apa langkah-langkah?
Mereka adalah, sekali lagi, sangat mirip untuk daftar sendiri-linked
dengan satu tambahan ekstra.
Kami ingin mengalokasikan ruang untuk baru node dan cek untuk memastikan itu berlaku.
Kami ingin mengisi simpul yang up dengan informasi apapun yang kita
ingin menempatkan di dalamnya.
Hal terakhir yang perlu kita do-- yang hal ekstra yang perlu kita lakukan, rather--
adalah untuk memperbaiki pointer Sebelumnya kepala lama daftar.
Ingat bahwa karena daftar doubly-linked,
kita dapat bergerak maju dan backwards-- yang
berarti bahwa setiap node sebenarnya poin dua node lain, bukan hanya satu.
Dan jadi kita harus memperbaiki kepala lama daftar
untuk menunjuk ke belakang untuk kepala baru dari linked list, yang adalah sesuatu yang
kita tidak perlu melakukan sebelumnya.
Dan seperti sebelumnya, kami hanya mengembalikan pointer ke kepala baru dari daftar.
>> Jadi, inilah daftar.
Kami ingin memasukkan 12 ke daftar ini.
Perhatikan bahwa diagram sedikit berbeda.
Setiap node berisi tiga fields-- data, dan pointer Berikutnya merah,
dan pointer Sebelumnya biru.
Tidak ada yang datang sebelum 15 node, sehingga pointer Sebelumnya adalah nol.
Ini adalah awal dari daftar.
Tidak ada sebelum.
Dan tidak ada yang datang setelah 10 node, dan jadi pointer Berikutnya adalah null juga.
>> Jadi mari kita tambahkan 12 ke daftar ini.
Kita perlu [tidak terdengar] ruang untuk node.
Kami menempatkan 12 di dalamnya.
Dan sekali lagi, kita harus benar-benar hati untuk tidak melanggar rantai.
Kami ingin mengatur ulang pointer dalam urutan yang benar.
Dan kadang-kadang yang mungkin mean-- seperti yang kita akan melihat sangat
dengan delete-- bahwa kita memiliki beberapa pointer berlebihan, tapi itu OK.
>> Jadi apa yang kita ingin lakukan pertama?
Saya akan merekomendasikan hal mungkin Anda harus
lakukan adalah untuk mengisi pointer dari 12 simpul sebelum Anda menyentuh orang lain.
Jadi apa yang 12 akan menunjuk ke depan?
15.
Apa yang datang sebelum 12?
Tidak ada.
Sekarang kita sudah mengisi informasi tambahan dalam 12
sehingga memiliki Sebelumnya, Berikutnya, dan nilai.
>> Sekarang kita dapat memiliki 15-- ini tambahan Langkah kami berbicara about-- kami
dapat memiliki 15 titik kembali ke 12.
Dan sekarang kita bisa memindahkan kepala linked list juga menjadi 12.
Sehingga cukup mirip dengan apa yang kita lakukan dengan daftar tunggal-linked,
kecuali untuk langkah ekstra menghubungkan kepala lama daftar
kembali ke kepala baru dari daftar.
>> Sekarang mari kita akhirnya menghapus node dari linked list.
Jadi katakanlah kita memiliki beberapa fungsi lain yang
adalah menemukan simpul kita ingin menghapus dan telah memberi kita pointer ke persis
node yang ingin kita hapus.
Kami bahkan tidak need-- mengatakan kepala masih global dinyatakan.
Kita tidak perlu kepala di sini.
Semua fungsi ini lakukan adalah kita sudah menemukan pointer ke persis simpul kami
ingin menyingkirkan.
Mari kita menyingkirkan itu.
Ini jauh lebih mudah dengan daftar doubly-linked.
First-- itu sebenarnya hanya beberapa hal.
Kita hanya perlu memperbaiki sekitarnya pointer node 'sehingga mereka melompati
node kita ingin menghapus.
Dan kemudian kita dapat menghapus simpul tersebut.
Jadi sekali lagi, kita hanya akan lewat sini.
Kita tampaknya telah memutuskan bahwa kita ingin menghapus node X.
Dan lagi, apa yang saya melakukan sini-oleh way-- yang
adalah kasus umum untuk simpul yang ada di tengah.
Ada beberapa peringatan ekstra yang Anda
perlu dipertimbangkan ketika Anda menghapus awal daftar
atau akhir daftar.
Ada beberapa khusus kasus sudut untuk menangani sana.
>> Jadi ini bekerja untuk menghapus setiap node di tengah-tengah satu list-- yang
memiliki pointer yang sah ke depan dan pointer yang sah mundur,
Sebelumnya sah dan Berikutnya pointer.
Sekali lagi, jika Anda bekerja dengan ujung, Anda
perlu menangani mereka sedikit berbeda,
dan kami tidak akan berbicara tentang itu sekarang.
Tapi Anda mungkin bisa mencari tahu apa yang perlu
harus dilakukan hanya dengan menonton video ini.
>> Jadi kami telah diisolasi X. X adalah node kita ingin menghapus dari daftar.
Apa yang kita lakukan?
Pertama, kita perlu untuk mengatur ulang pointer luar.
Kita perlu untuk mengatur ulang 9 berikutnya untuk melewatkan lebih dari 13
dan arahkan ke 10-- yang adalah apa yang kita baru saja dilakukan.
Dan kita juga perlu mengatur ulang 10 ini Sebelumnya
untuk menunjuk ke 9 bukannya menunjuk ke 13.
>> Jadi sekali lagi, ini adalah diagram untuk memulai dengan.
Ini adalah rantai kami.
Kita perlu untuk melewati lebih dari 13, tapi kita perlu juga melestarikan
integritas daftar.
Kami tidak ingin kehilangan Informasi di kedua arah.
Jadi kita perlu untuk mengatur ulang pointer dengan hati-hati
jadi kami tidak memutuskan rantai sama sekali.
>> Jadi kita bisa mengatakan 9 ini pointer Berikutnya menunjuk ke tempat yang sama
bahwa tiga belas Next pointer menunjuk sekarang.
Karena kami akhirnya akan ingin melewatkan 13.
Jadi dimanapun 13 poin berikutnya, Anda ingin sembilan menunjukkan ada gantinya.
Jadi itulah yang.
Dan kemudian dimanapun 13 poin kembali untuk, apa pun yang datang sebelum 13,
kami ingin menunjukkan 10 itu bukan 13.
Sekarang perhatikan, jika Anda mengikuti panah, kita bisa drop 13
tanpa benar-benar kehilangan informasi apapun.
Kami telah terus integritas daftar, bergerak baik maju dan mundur.
Dan kemudian kita bisa hanya semacam dari membersihkannya sedikit
dengan menarik daftar bersama-sama.
Jadi kita mengatur kembali pointer di kedua sisi.
Dan kemudian kita dibebaskan X simpul yang berisi 13,
dan kami tidak melanggar rantai.
Jadi kami melakukan yang baik.
>> Catatan akhir di sini pada daftar terkait.
Jadi baik singly- dan doubly-linked daftar, seperti yang kita lihat,
dukungan penyisipan benar-benar efisien dan penghapusan elemen.
Anda dapat cukup banyak melakukan dalam waktu yang konstan.
Apa yang harus kita lakukan untuk menghapus elemen hanya detik yang lalu?
Kami pindah satu pointer.
Kami pindah pointer lain.
Kami dibebaskan X-- mengambil tiga operasi.
Ini selalu mengambil tiga operasi untuk menghapus node-- yang membebaskan node.
>> Bagaimana kita memasukkan?
Yah, kita hanya selalu memaku pada awal
jika kita memasukkan efisien.
Jadi kita perlu rearrange-- tergantung pada apakah itu
sebuah singly- atau ganda-linked daftar, kita mungkin perlu melakukan tiga
atau empat operasi max.
Tapi sekali lagi, itu selalu tiga atau empat.
Tidak peduli berapa banyak elemen dalam daftar kami,
itu selalu tiga atau empat operations-- seperti penghapusan selalu
tiga atau empat operasi.
Ini waktu yang konstan.
Jadi itu benar-benar hebat.
>> Dengan array, yang kami lakukan sesuatu seperti insertion sort.
Anda mungkin ingat bahwa penyisipan semacam ini tidak algoritma waktu yang konstan.
Ini sebenarnya cukup mahal.
Jadi ini adalah jauh lebih baik untuk memasukkan.
Tapi seperti yang saya sebutkan di tunggal-linked list video,
kita punya downside di sini juga, kan?
Kami telah kehilangan kemampuan untuk acak mengakses elemen.
Kita tidak bisa mengatakan, saya ingin nomor elemen empat atau nomor elemen 10 dari linked list
dengan cara yang sama bahwa kita bisa melakukannya dengan array
atau kita hanya bisa langsung Indeks ke elemen array kita.
>> Dan mencoba untuk menemukan elemen dalam list-- terkait
jika pencarian adalah important-- sekarang mungkin memerlukan waktu linear.
Sebagai daftar mendapat lagi, itu mungkin mengambil satu langkah tambahan
untuk setiap elemen tunggal dalam daftar di untuk menemukan apa yang kita cari.
Jadi ada trade off.
Ada sedikit pro dan elemen con di sini.
>> Dan daftar doubly-linked bukan jenis terakhir dari kombinasi struktur data
bahwa kita akan berbicara tentang, mengambil semua bangunan dasar
blok C yang menempatkan bersama-sama.
Karena pada kenyataannya, kita bisa bahkan melakukan lebih baik dari ini
untuk membuat struktur data yang Anda mungkin bisa mencari melalui
dalam waktu yang konstan juga.
Tapi lebih pada bahwa dalam video lain.
>> Aku Doug Lloyd.
Ini adalah CS50.