[Bermain muzik] 

DOUG LLOYD: OK, jadi sekurang- ketika ini dalam perjalanan, kami telah meliputi banyak asas-asas C. Kami tahu banyak tentang pembolehubah, tatasusunan, petunjuk, semua barangan yang baik. Mereka semua jenis dibina untuk melihat sebagai asas-asas, tetapi kita boleh melakukan lebih banyak, bukan? Kita boleh menggabungkan perkara-perkara bersama-sama dengan cara yang menarik. 

Dan begitu mari kita buat itu, mari kita mulakan berkembang daripada apa yang C memberikan kita, dan mula membuat data kita sendiri struktur menggunakan bangunan ini blok bersama-sama untuk melakukan sesuatu benar-benar berharga, berguna. Salah satu cara yang boleh kita lakukan ini adalah untuk bercakap tentang koleksi. Jadi setakat ini kita mempunyai satu jenis data struktur bagi mewakili koleksi daripada suka nilai, nilai-nilai yang sama. Itu akan menjadi array. Kami mempunyai koleksi integer, atau koleksi watak-watak dan sebagainya. 

Struktur juga menyusun data yang struktur bagi mengumpul maklumat, tetapi ia bukan untuk mengumpul seperti nilai-nilai. Ia biasanya menggabungkan data berlainan jenis bersama-sama di dalam kotak tunggal. Tetapi ia tidak sendiri digunakan untuk rantaian bersama-sama atau menyambung bersama-sama sama barang-barang, seperti array. Array yang besar untuk elemen mencari, tetapi ingat bahawa itu sangat sukar untuk memasukkan ke dalam array, melainkan jika kita memasukkan di akhir sangat array itu. 

Dan contoh terbaik saya kerana itu adalah jenis kemasukan. Jika anda masih ingat video kami pada jenis kemasukan, terdapat banyak perbelanjaan yang terlibat dalam mempunyai untuk mengambil elemen, dan memindahkan mereka keluar dari jalan untuk memenuhi sesuatu ke tengah-tengah lokasi anda. Tatasusunan juga mengalami satu lagi masalah, yang tidak fleksibel. Apabila kita mengisytiharkan array, kita akan mendapat satu pukulan di dalamnya. Kita dapat mengatakan, saya mahu ini banyak unsur. Mungkin 100, ia mungkin menjadi 1,000, ia mungkin menjadi x di mana x ialah nombor yang pengguna memberikan kita pada cepat atau sekurang-arahan garis. 

Tetapi kita hanya mendapat satu pukulan pada itu, kita tidak mendapat untuk kemudian berkata oh, sebenarnya saya diperlukan 101, atau saya perlu x campur 20. Terlambat, kita sudah mengisytiharkan pelbagai, dan jika kita ingin mendapatkan 101 atau x ditambah 20, kita perlu mengisytiharkan pelbagai sekali berbeza, menyalin semua elemen array lebih, dan kemudian kita mempunyai cukup. Dan bagaimana jika kita silap lagi, apa jika kita benar-benar perlu 102, atau x campur 40, yang perlu kita lakukan ini sekali lagi. Jadi mereka sangat fleksibel untuk saiz semula data kami, tetapi jika kita menggabungkan bersama-sama beberapa perkara asas yang kita ada sudah belajar tentang petunjuk dan struktur, khususnya menggunakan memori dinamik peruntukan dengan malloc, kita boleh meletakkan keping ini bersama-sama untuk mewujudkan data baru structure-- yang senarai kita mungkin iaitu- secara tunggal dikaitkan yang membolehkan kita untuk berkembang dan mengecut koleksi nilai dan kami tidak akan mempunyai ruang sia-sia. 

Jadi sekali lagi, kita panggil idea ini, idea ini, senarai berpaut. Khususnya, dalam video ini kami bercakap tentang senarai secara tunggal berkaitan, dan kemudian video lain kita akan bercakap senarai kira-kira dua kali ganda berkaitan, yang hanya variasi pada tema di sini. Tetapi senarai yang dikaitkan secara tunggal terdiri daripada nod, nod hanya menjadi satu term-- abstrak ia hanya sesuatu yang saya memanggil itu adalah satu jenis struktur, pada dasarnya, saya? Hanya akan memanggilnya node-- dan ini nod mempunyai dua ahli, atau dua bidang. Ia mempunyai data, biasanya integer, apungan watak, atau boleh menjadi beberapa jenis data lain yang anda telah ditakrifkan dengan def jenis. Dan ia mengandungi penunjuk kepada lain nod dari jenis yang sama. 

Jadi kita mempunyai dua perkara di dalam nod ini, data dan penunjuk kepada nod yang lain. Dan jika anda mula untuk menggambarkan ini, anda boleh berfikir tentang hal itu seperti rangkaian nod yang disambung bersama. Kami mempunyai nod yang pertama, ia mengandungi data dan penunjuk kepada nod yang kedua, yang mengandungi data dan penunjuk kepada nod ketiga. Dan supaya sebabnya kita memanggilnya senarai berpaut, mereka dikaitkan bersama-sama. 

Apakah yang istimewa ini struktur nod kelihatan seperti? Nah, jika anda ingat dari video kami di menentukan jenis adat, dengan jenis def, kita boleh menentukan structure-- dan menaip menentukan struktur yang seperti ini. tyepdef struct sllist, dan kemudian saya menggunakan nilai perkataan di sini sewenang-wenangnya untuk menunjukkan apa-apa jenis data benar-benar. Anda boleh memindahkan integer atau terapung, anda boleh mempunyai apa sahaja yang anda mahu. Ia tidak terhad kepada hanya integer, atau apa-apa seperti itu. Jadi nilai hanya sewenang-wenangnya jenis data, dan kemudian penunjuk yang lain nod dari jenis yang sama. 

Sekarang, ada muslihat sedikit di sini dengan menentukan struktur yang apabila ia adalah satu struktur rujukan diri. Saya perlu mempunyai sementara menamakan struktur saya. Pada akhir hari, saya yang jelas mahu memanggilnya nod SLL, itu akhirnya baru menamakan sebahagian daripada definisi jenis saya, tetapi saya tidak boleh menggunakan nod SLL di pertengahan ini. Sebabnya, saya tidak mempunyai mencipta satu jenis dipanggil nod SLL sehingga saya memukul titik akhir ini di sini. Sehingga ketika itu, saya perlu mempunyai cara lain untuk merujuk kepada jenis data ini. 

Dan ini adalah diri yang jenis data rujukan. Ia; s jenis data daripada struktur yang mengandungi data, dan penunjuk yang lain struktur jenis yang sama. Jadi saya perlu berupaya untuk merujuk kepada jenis data ini sekurang-kurangnya buat sementara waktu, supaya memberikan sementara nama struct sllist membolehkan saya untuk kemudian mengatakan saya mahu penunjuk yang lain sllist struct, bintang struct sllist, dan kemudian selepas saya telah menyelesaikan definisi, Sekarang saya boleh memanggil jenis nod SLL. 

Jadi itulah sebabnya anda melihat ada nama sementara di sini, tetapi nama tetap di sini. Kadang-kadang anda mungkin melihat definisi struktur, sebagai contoh, yang tidak rujukan sendiri, yang tidak mempunyai nama specifier sini. Ia hanya akan berkata typedef struct, membuka kerinting dan kemudian menentukan ia. Tetapi jika anda struct adalah diri rujukan, yang satu ini adalah, anda perlu untuk menentukan nama jenis sementara. Tetapi akhirnya, sekarang bahawa kita telah melakukan ini, kita hanya boleh merujuk kepada nod ini, unit-unit ini, sebagai nod SLL untuk tujuan negara lain di video ini. 

Baiklah, jadi kita tahu bagaimana untuk mewujudkan nod senarai berkaitan. Kita tahu bagaimana untuk menentukan nod senarai berkaitan. Sekarang, jika kita akan mula menggunakan mereka untuk mengumpul maklumat, ada beberapa operasi kami perlu memahami dan bekerja dengan. Kita perlu tahu bagaimana untuk membuat senarai berpaut dari udara tipis. Jika tiada senarai sudah, kita mahu memulakan satu. Oleh itu, kita perlu berupaya untuk membuat senarai berpaut, kita perlu mungkin mencari melalui senarai link untuk mencari elemen yang kami cari. Kita perlu dapat memasukkan perkara-perkara baru ke dalam senarai, kita mahu senarai kami dapat berkembang. Begitu juga, kita mahu dapat untuk memadam perkara dari senarai kami, kita mahu senarai kami dapat mengecut. Dan pada akhir kami program, terutamanya jika anda masih ingat bahawa kita dinamik memperuntukkan memori untuk membina senarai ini biasanya, kita mahu membebaskan kesemua memori yang apabila kami sudah selesai bekerja dengannya. Dan dengan itu kita perlu berupaya untuk memadam senarai keseluruhan dikaitkan dalam satu kali kejadian gagal. Jadi mari kita pergi melalui beberapa operasi ini dan bagaimana kita boleh menggambarkan mereka, bercakap kod pseudo secara khusus. Oleh itu, kita ingin membuat senarai bersambung, jadi mungkin kita hendak menentukan fungsi dengan prototaip ini. SLL nod bintang, buat dan saya lulus dalam satu hujah, beberapa data yang sewenang-wenangnya menaip lagi, beberapa sewenang-wenangnya jenis data. Tetapi saya returning-- fungsi ini perlu kembali kepadaku penunjuk, kepada secara tunggal dikaitkan nod senarai. Sekali lagi, kita cuba untuk mewujudkan senarai berpaut dari udara tipis, jadi saya perlu penunjuk kepada senarai itu apabila aku selesai. 

Jadi apakah langkah-langkah yang terlibat di sini? Nah, perkara pertama saya akan lakukan adalah dinamik memperuntukkan ruang untuk nod baru. Sekali lagi, kami mewujudkan ia keluar dari nipis udara, jadi kita perlu ruang malloc untuk itu. Dan sudah tentu, dengan serta-merta selepas kami malloc, kita sentiasa periksa untuk memastikan bahawa kami pointer-- kita tidak kembali null. Kerana jika kita cuba rasa hormat penunjuk null, kita akan mengalami segfault dan kita tidak mahu itu. 

Kemudian kita mahu mengisi dalam bidang ini, kita mahu memulakan bidang nilai dan memulakan medan seterusnya. Dan kemudian kita mahu supaya- akhirnya sebagai fungsi prototaip indicates-- kita mahu untuk kembali penunjuk kepada nod SLL. Jadi apa yang membuat ini kelihatan seperti cacat? Well, pertama kita akan secara dinamik memperuntukkan ruang untuk nod SLL baru, jadi kami malloc-- itulah representasi visual nod yang kita buat. Dan kita periksa untuk memastikan ia tidak null-- dalam kes ini, gambar tidak akan mempunyai ditunjukkan jika ia adalah tidak sah, kita akan kehabisan memori, supaya kita baik untuk pergi ke sana. Jadi sekarang kita ke langkah C, memulakan bidang nilai nod. Nah, berdasarkan fungsi ini memanggil saya menggunakan di sini, kelihatan seperti saya mahu lulus di 6, jadi saya akan 6 dalam bidang nilai. Sekarang, memulakan medan seterusnya. Nah, apa yang saya akan lakukan di sana, tiada apa yang akan datang, betul, ini adalah satu-satunya perkara dalam senarai. Jadi apa perkara yang akan datang dalam senarai? 

Ia tidak seharusnya menunjukkan apa-apa, betul. Ada apa-apa lagi di sana, jadi apa yang konsep yang kita tahu itulah nothing-- petunjuk untuk apa-apa? Ia harus menjadi mungkin kita mahu untuk meletakkan penunjuk null sana, dan saya akan mewakili null penunjuk sebagai hanya sebuah kotak merah, kita tidak boleh pergi mana-mana lagi. Seperti yang kita akan melihat sedikit di kemudian hari, kita akan mempunyai akhirnya rantaian anak panah yang menghubungkan nod ini bersama-sama, tetapi apabila anda melanda kotak merah, itu batal, kita tidak boleh pergi mana-mana lagi, itulah akhir senarai. 

Dan akhir sekali, kami hanya mahu kembali penunjuk kepada nod ini. Oleh itu, kita akan memanggilnya baru, dan akan kembali baru supaya ia boleh digunakan dalam apa fungsi menciptakannya. Jadi ada kita pergi, Kami telah mencipta satu secara tunggal dikaitkan nod senarai dari udara tipis, dan sekarang kita mempunyai senarai yang kami boleh bekerja dengan. 

Sekarang, mari kita mengatakan bahawa kita sudah mempunyai rangkaian yang besar, dan kami ingin mencari sesuatu di dalamnya. Dan kita mahu satu fungsi yang akan untuk kembali benar atau salah, bergantung sama ada nilai yang wujud dalam senarai itu. Satu prototaip fungsi, atau penerangan bagi fungsi itu, mungkin kelihatan seperti this-- bool mencari, dan maka kita mahu lulus dalam dua hujah. 

Yang pertama, adalah penunjuk kepada Elemen pertama dalam senarai yang dipautkan. Ini sebenarnya adalah sesuatu yang anda akan sentiasa mahu untuk mengesan, dan sebenarnya mungkin menjadi sesuatu yang anda juga dimasukkan ke dalam pembolehubah global. Sebaik sahaja anda membuat senarai, anda sentiasa, sentiasa mahu untuk mengesan yang Elemen pertama dalam senarai itu. Dengan cara itu anda boleh merujuk kepada semua yang lain unsur-unsur dengan hanya mengikuti rantai, tanpa perlu menyimpan petunjuk utuh kepada setiap elemen tunggal. Anda hanya perlu untuk mengesan satu yang pertama satu jika mereka semua dirantai bersama-sama. 

Kemudian perkara yang kedua kita lulus dalam lagi adalah sewenang-wenangnya some-- apa sahaja jenis data kami cari ada di dalam mudah-mudahan salah satu daripada nod dalam senarai. Jadi apakah langkah-langkah? Nah, perkara pertama yang kami lakukan adalah kita mewujudkan penunjuk melintang menunjuk ke kepala menyenaraikan. Nah, mengapa kita berbuat demikian, kita sudah mempunyai penunjuk di kepala menyenaraikan, mengapa tidak kita hanya bergerak satu yang di sekeliling? Well, seperti saya hanya berkata, ia benar-benar penting untuk kita untuk sentiasa mengesan elemen yang pertama dalam senarai. Dan supaya ia sebenarnya lebih baik untuk membuat pendua itu, dan menggunakannya untuk bergerak jadi kami tidak pernah sengaja bergerak, atau kita sentiasa mempunyai penunjuk pada satu ketika yang kanan pada elemen pertama dalam senarai itu. Jadi ia adalah lebih baik untuk mewujudkan satu saat yang kita gunakan untuk bergerak. 

Maka kita hanya membandingkan sama ada bidang nilai pada nod yang adalah apa yang kita cari, dan jika ia tidak, kita hanya bergerak ke nod seterusnya. Dan kita terus melakukan itu ke atas, dan ke atas, dan ke atas, sehingga kita sama ada mencari unsur, atau kita mencapai null-- kami telah mencapai akhir senarai dan ia tidak ada. Ini diharapkan dapat berdering loceng kepada anda sebagai hanya carian linear, kami hanya mereplikasi dalam struktur senarai secara tunggal dikaitkan bukannya menggunakan array untuk melakukannya. 

Jadi di sini adalah satu contoh senarai secara tunggal berkaitan. Yang ini terdiri daripada lima nod, dan kami mempunyai penunjuk kepada ketua senarai, yang dipanggil senarai. Perkara pertama yang kita mahu lakukan adalah lagi, buat bahawa penunjuk penyusuran. Oleh itu, kita kini mempunyai dua petunjuk ketika itu kepada perkara yang sama. 

Sekarang, perhatikan di sini juga, saya tidak perlu malloc mana-mana ruang untuk trav. Saya tidak mengatakan trav sama malloc sesuatu, nod tersebut telah ada ruang yang di dalam memori telah wujud. Jadi semua Saya sebenarnya lakukan adalah mewujudkan satu lagi penunjuk kepadanya. Saya tidak mallocing tambahan ruang, hanya ada sekarang dua petunjuk menunjuk kepada perkara yang sama. 

Jadi adalah 2 apa yang saya cari? Well, tidak, jadi bukannya Saya akan bergerak ke satu depan. Jadi, pada asasnya saya akan berkata, trav sama trav depan. Adalah 3 apa yang saya cari, tidak. Jadi saya terus pergi melalui, sehingga akhirnya mendapatkan hingga 6 yang merupakan apa yang saya cari berasaskan kepada panggilan fungsi Saya mempunyai di bahagian atas di sana, dan supaya aku selesai. 

Sekarang, bagaimana jika unsur Saya cari tidak dalam senarai, ia masih akan bekerja? Nah, perhatikan bahawa senarai di sini adalah secara halus berbeza, dan ini adalah satu lagi perkara itu penting dengan senarai berkaitan, anda tidak perlu untuk memelihara mereka dalam mana-mana perintah tertentu. Anda boleh jika anda mahu, tetapi anda mungkin perasan bahawa kita tidak mengesan apa elemen nombor kita berada di. 

Dan itu semacam satu perdagangan yang kita mempunyai dengan senarai dikaitkan ayat tatasusunan, adakah ia kita tidak mempunyai capaian rawak lagi. Kita tidak boleh hanya berkata, saya mahu untuk pergi ke unsur 0, atau unsur ke-6 daripada pelbagai saya, yang boleh saya lakukan dalam array. Saya tidak boleh mengatakan saya mahu pergi ke Unsur 0, atau unsur ke-6, atau unsur ke-25 senarai dikaitkan saya, tidak ada indeks yang berkaitan dengan mereka. Dan supaya ia tidak benar-benar perkara jika kita memelihara senarai kami teratur. Jika anda mahu anda pasti boleh, tetapi ada ada sebab mengapa mereka perlu dikekalkan dalam mana-mana perintah. Jadi sekali lagi, mari kita cuba dan mencari 6 dalam senarai ini. Nah, kita bermula pada bermula, kita tidak mencari 6, dan kemudian kita terus tidak mencari 6, sehingga kita akhirnya sampai ke sini. Jadi betul mata sekarang trav kepada nod mengandungi 8, dan enam tidak ada di dalam sana. 

Jadi, langkah seterusnya adalah untuk pergi ke penunjuk yang akan datang, jadi berkata trav sama trav depan. Nah, trav depan, ditunjukkan oleh kotak merah di sana, adalah batal. Jadi ada tempat lain untuk pergi, dan sebagainya pada ketika ini kita boleh menyimpulkan bahawa kita telah mencapai akhir senarai berkaitan, dan 6 tidak ada di sana. Dan ia akan dikembalikan palsu dalam kes ini. 

OK, bagaimana kita memasukkan baru nod dalam senarai berpaut? Oleh itu, kita telah dapat mewujudkan senarai berpaut entah dari mana, tetapi kita mungkin mahu membina rantai dan tidak mewujudkan sekumpulan senarai berbeza. Kami mahu mempunyai satu senarai yang mempunyai sekumpulan nod di dalamnya, bukan sekumpulan senarai dengan nod tunggal. Oleh itu, kita tidak boleh hanya terus menggunakan Cipta fungsi kita ditakrifkan sebelum ini, sekarang kita mahu masukkan ke dalam senarai itu telah wujud. 

Jadi kes ini, kita akan lulus dalam dua hujah, penunjuk kepada ketua yang senarai yang kita mahu untuk menambah berkaitan. Sekali lagi, itulah sebabnya ia begitu penting untuk kita sentiasa mengesan, kerana ia adalah satu-satunya cara kita benar-benar perlu merujuk kepada keseluruhan senarai adalah hanya dengan penunjuk kepada elemen pertama. Oleh itu, kita mahu lulus dalam penunjuk kepada elemen pertama, dan apa sahaja yang kita nilai ingin menambah kepada senarai. Dan akhirnya fungsi ini akan kembali penunjuk kepada ketua baru senarai berpaut. 

Apakah langkah-langkah yang terlibat di sini? Nah, sama seperti dengan membuat, kita perlu dinamik memperuntukkan ruang untuk nod baru, dan periksa untuk memastikan kita tidak kehabisan memori, sekali lagi, kerana kita menggunakan malloc. Maka kita mahu untuk mengisi dan masukkan nod, jadi meletakkan jumlah itu, apa sahaja yang val adalah, ke dalam nod. Kami mahu memasukkan nod di permulaan senarai yang dipautkan. 

Ada sebab yang saya mahu melakukan ini, dan ia mungkin bernilai mengambil kedua untuk menjedakan video di sini, dan berfikir tentang mengapa saya mahu memasukkan pada awal berpaut senarai. Sekali lagi, saya nyatakan sebelum ini bahawa ia tidak benar-benar kira jika kita mengekalkan ia dalam mana-mana perintah, jadi mungkin itulah petunjuk. Dan anda melihat apa yang akan berlaku jika kita mahu supaya- atau daripada hanya sesaat lalu apabila kami pergi melalui carian anda dapat melihat apa yang mungkin berlaku jika kita cuba untuk memasukkan pada akhir senarai. Kerana kita tidak mempunyai penunjuk kepada akhir senarai. 

Jadi sebab itu saya mahu untuk memasukkan pada permulaan, kerana saya boleh melakukannya dengan segera. Saya mempunyai penunjuk pada permulaan, dan kita akan melihat ini dalam visual dalam satu saat. Tetapi jika saya mahu memasukkan pada akhirnya, Saya perlu bermula pada awal, merentasi semua jalan ke akhir, dan kemudian jelujur ia. Supaya bermakna memasukkan di akhir senarai akan menjadi o n operasi, akan kembali untuk perbincangan kita tentang kerumitan pengiraan. Ia akan menjadi o n operasi, di mana sebagai senarai yang mendapat lebih besar, dan lebih besar, dan lebih besar, ia akan menjadi lebih dan lebih sukar untuk jelujur sesuatu pada pada akhir. Tetapi ia sentiasa benar-benar mudah untuk jelujur sesuatu pada pada permulaan, anda sentiasa pada permulaan. 

Dan kita akan melihat visual ini lagi. Dan kemudian sebaik sahaja kami selesai, sebaik sahaja kami telah dimasukkan nod baru, kita mahu kembali penunjuk kami untuk ketua baru senarai berpaut, yang kerana kita memasukkan di permulaan, benar-benar akan menjadi penunjuk kepada nod yang kita buat. Mari kita menggambarkan hal ini, kerana saya fikir ia akan membantu. 

Jadi di sini adalah senarai kami, ia terdiri daripada empat elemen, nod yang mengandungi 15, yang menunjuk kepada nod mengandungi 9, yang menunjuk kepada nod yang mengandungi 13, yang menunjuk kepada nod yang mengandungi 10, yang mempunyai null penunjuk sebagai penunjuk seterusnya jadi itulah akhir senarai. Oleh itu, kita mahu untuk memasukkan nod baru dengan nilai 12 pada awal ini senarai, apa yang kita lakukan? Well, pertama kita malloc ruang untuk nod, dan kemudian kita masukkan ke 12 di sana. 

Jadi sekarang kita telah mencapai titik keputusan, bukan? Kami mempunyai beberapa petunjuk yang kita boleh bergerak, yang mana satu yang patut kita bergerak dahulu? Sekiranya kita membuat 12 mata untuk ketua baru list-- yang atau maafkan saya, kita perlu membuat 12 menunjukkan kepala lama senarai? Atau kita tidak mengatakan bahawa Senarai kini bermula pada 12. Ada perbezaan yang di sana, dan kita akan melihat apa yang berlaku dengan kedua-dua dalam satu saat. 

Tetapi ini membawa kepada topik yang besar untuk bar sisi, yang adalah bahawa salah satu daripada perkara yang paling sukar dengan senarai berkaitan adalah untuk menyusun petunjuk dalam susunan yang betul. Jika anda bergerak perkara daripada perintah, anda boleh berakhir tidak sengaja anak yatim yang lain dalam senarai itu. Dan di sini adalah satu contoh itu. Jadi mari kita pergi dengan idea daripada- baik, kami telah membina 12. Kita tahu 12 akan menjadi ketua baru senarai, dan jadi mengapa tidak kita hanya bergerak penunjuk senarai untuk menunjukkan di sana. 

OK, jadi itulah yang baik. Jadi sekarang di mana tidak 12 Fakta yang seterusnya? Maksud saya, visual yang kita dapat lihat supaya ia menunjuk kepada 15, sebagai manusia ia benar-benar jelas kepada kami. Bagaimana komputer tahu? Kami tidak mempunyai apa-apa menunjuk ke 15 lagi, bukan? 

Kami telah kehilangan apa-apa keupayaan untuk merujuk kepada 15. Kita tidak boleh mengatakan anak panah baru setaraf seterusnya sesuatu, tiada apa-apa di sana. Malah, kami telah yatim yang lain dalam senarai dengan berbuat demikian, kami telah sengaja rosak rantai. Dan kami tidak mahu berbuat demikian. 

Oleh itu, marilah kita kembali dan cuba ini lagi. Mungkin perkara yang betul untuk melakukan adalah untuk menetapkan penunjuk tempoh 12 ini kepala lama dalam senarai yang pertama, maka kita boleh menggerakkan senarai lebih. Dan sebenarnya, iaitu susunan yang betul yang kita perlu mengikuti apabila kami bekerja dengan senarai secara tunggal berkaitan. Kami sentiasa mahu menyambung elemen baru ke dalam senarai, sebelum kita mengambil yang jenis langkah yang penting untuk mengubah di mana ketua senarai berkaitan adalah. Sekali lagi, itu satu perkara yang asas, kita tidak mahu untuk mengesan kehilangan ia. 

Oleh itu, kita mahu memastikan bahawa semuanya dirantai bersama-sama, sebelum kita gerakkan penuding itu. Dan sebagainya ini akan menjadi susunan yang betul, iaitu untuk menyambung 12 ke dalam senarai, kemudian mengatakan bahawa senarai itu bermula 12. Jika kita berkata senarai itu bermula pada 12 dan kemudian cuba untuk menyambung 12 ke dalam senarai, kita telah pun melihat apa yang berlaku. Kita kehilangan senarai dengan sengaja. 

OK, jadi satu perkara lagi untuk bercakap tentang. Bagaimana jika kita mahu untuk menghilangkan keseluruhan senarai dikaitkan sekaligus? Sekali lagi, kami mallocing semua ruang ini, dan dengan itu kita perlu untuk membebaskan apabila kita selesai. Jadi sekarang kita mahu memadam senarai dikaitkan keseluruhan. Well, apa yang kita mahu lakukan? 

Jika kita telah mencapai penunjuk nol, kita mahu berhenti, jika tidak, hanya memadam yang lain dalam senarai dan kemudian membebaskan saya. Padam selebihnya senarai, dan kemudian membebaskan nod semasa. Apakah bunyi yang seperti, apa teknik perlu kita bercakap tentang sebelum adakah itu bunyi seperti? Memadam semua orang lain, maka kembali dan memadam saya. 

Itulah rekursi, kami telah membuat masalah sedikit lebih kecil, kita katakan memadam semua orang lain, maka anda boleh memadam saya. Dan lebih bawah jalan, nod yang akan berkata, memadam orang lain. Tetapi akhirnya kita akan sampai ke titik di mana senarai itu adalah batal, dan itulah kes asas kami. 

Jadi mari kita lihat ini, dan bagaimana ini mungkin bekerja. Jadi di sini adalah senarai kami, ia adalah sama senarai kami hanya bercakap tentang, dan ada langkah-langkah. Ada banyak teks di sini, tetapi mudah-mudahan visualisasi akan membantu. 

Oleh itu, kita ada-- dan saya juga ditarik sehingga ilustrasi bingkai tindanan kami dari video kami pada susunan panggilan, dan mudah-mudahan semua ini bersama-sama akan menunjukkan kepada anda apa yang sedang berlaku. Jadi di sini adalah kod kod pseudo kami. Jika kita mencapai null yang penunjuk, berhenti, jika tidak, memadam selebihnya senarai, kemudian membebaskan nod semasa. Jadi sekarang, list-- penunjuk bahawa kita lulus dalam untuk memusnahkan mata kepada 12. 12 bukan penunjuk null, jadi kami akan memadam yang lain dalam senarai itu. 

Apa yang memotong lain daripada kita yang terlibat? Nah, ia bermakna membuat memanggil untuk memusnahkan, berkata yang 15 adalah permulaan lain dalam senarai yang kita mahu untuk memusnahkan. Dan sebagainya panggilan untuk memusnahkan 12 adalah jenis ditahan. Ia beku di sana, menunggu memanggil untuk memusnahkan 15, untuk menyelesaikan tugasnya. 

Well, 15 bukan penunjuk null, dan jadi ia akan berkata, semua hak, baik, memadam seluruh senarai. Selebihnya senarai bermula pada 9, dan dengan itu kita akan hanya tunggu sehingga anda memadam semua yang barangan, kemudian kembali dan memadam saya. Well 9 akan berkata, baik, Saya bukan penunjuk null, supaya memadam selebihnya senarai dari sini. Dan jadi cuba dan memusnahkan 13. 13 berkata, saya tidak penunjuk null, Perkara yang sama, ia pas tanggungjawab itu. 10 tidak penunjuk null, 10 mengandungi penunjuk null, tetapi 10 tidak sendiri adalah null penunjuk sekarang, dan oleh itu pas tanggungjawab itu juga. 

Dan kini senarai mata di sana, ia benar-benar akan menunjukkan some-- jika saya mempunyai lebih banyak ruang dalam imej, ia akan menunjukkan beberapa ruang rawak bahawa kita tidak tahu apa yang ada. Ia adalah penunjuk nol walaupun, senarai secara literal kini ditetapkan itu nilai-nilai null. Ia menunjuk betul di dalam kotak yang merah. Kami sampai penunjuk batal, jadi kita boleh berhenti, dan kami sudah selesai. 

Dan supaya rangka ungu adalah sekarang-- di atas stack-- itulah bingkai aktif, tetapi ia dilakukan. Jika kita telah mencapai penunjuk null, berhenti. Kami tidak berbuat apa-apa, kita tidak boleh membebaskan penunjuk null, kami tidak malloc apa-apa ruang, dan dengan itu kita selesai. Supaya rangka fungsi dimusnahkan, dan kami resume-- kami mengambil mana kita mati dengan yang paling tinggi yang seterusnya, yang adalah tempoh yang gelap biru di sini. Oleh itu, kita mengambil hak mana kita berhenti. Kami telah membuang yang lain daripada senarai sudah, jadi sekarang kita akan membebaskan nod semasa. Jadi sekarang kita boleh bebas nod ini, dan kini kami telah sampai ke penghujung majlis itu. Dan supaya rangka fungsi dimusnahkan, dan kami menjemput di satu biru cahaya. 

Jadi ia says-- saya telah done-- memotong yang lain dalam senarai ini, jadi membebaskan nod semasa. Dan sekarang bingkai kuning adalah kembali di atas timbunan. Dan sebagainya seperti yang anda lihat, kami sekarang memusnahkan senarai dari kanan ke kiri. 

Apa yang akan berlaku, walaupun, jika kita telah melakukan sesuatu dengan cara yang salah? Sama seperti apabila kita cuba untuk menambah unsur. Jika kita sehingga merosakkan rantai, jika kami tidak menyambung petunjuk dalam susunan yang betul, jika kita hanya dibebaskan elemen pertama, jika kita hanya dibebaskan ketua senarai, sekarang kita tidak mempunyai cara untuk merujuk kepada seluruh senarai. Dan dengan itu kita akan mempunyai segala-galanya yatim, kita akan mempunyai apa yang dipanggil kebocoran memori. Jika anda ingat dari video kami mengenai peruntukan memori dinamik, itu bukan perkara yang sangat baik. 

Jadi seperti yang saya katakan, terdapat beberapa operasi yang perlu kita gunakan untuk bekerja dengan senarai dikaitkan dengan berkesan. Dan anda mungkin perasan saya ditinggalkan satu, memotong satu unsur dari berpaut senarai. Alasan saya berbuat demikian adalah ia sebenarnya sejenis sukar untuk berfikir tentang bagaimana untuk memadam satu unsur dari secara tunggal senarai berkaitan. Kita perlu dapat melangkau lebih sesuatu dalam senarai, yang ertinya kita dapat, kita point-- mahu memadam node-- ini tetapi untuk membuat ia supaya kita tidak kehilangan apa-apa maklumat, kita perlu menyambungkan ini nod di sini, di sini. 

Jadi saya mungkin melakukan yang salah dari perspektif yang dengar. Oleh itu, kita berada pada awal kami senarai, kami meneruskan perjalanan melalui, kami mahu memadam nod ini. Jika kita hanya memadamnya, kami telah rosak rantai. Nod ini di sini merujuk kepada segala-galanya, ia mengandungi rantai dari sini pada keluar. 

Jadi apa yang perlu kita lakukan sebenarnya selepas kita sampai ke tahap ini, adalah kita perlu untuk langkah ke belakang satu, dan menyambung nod ini ke nod ini, jadi kami boleh memadam yang di tengah-tengah. Tetapi senarai secara tunggal berkaitan tidak memberikan kita satu cara untuk pergi ke belakang. Oleh itu, kita perlu sama ada untuk menyimpan dua petunjuk, dan memindahkan mereka semacam langkah di luar, satu di belakang yang lain seperti yang kita pergi, atau mendapatkan ke satu tahap dan kemudian menghantar penunjuk lain melalui. Dan seperti yang anda boleh lihat, ia boleh mendapatkan kemas sedikit. Mujurlah, kami mempunyai cara lain untuk menyelesaikan itu, apabila kita bercakap mengenai senarai duanya adalah terpakai dikaitkan. 

Saya Doug Lloyd, ini adalah CS50.