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