[MUSIC PLAYING] 

Doug LLOYD: OK, jadi pada saat ini dalam kursus, kita telah membahas banyak dasar-dasar C. Kami tahu banyak tentang variabel, array, pointer, semua hal yang baik. Mereka semua jenis dibangun untuk melihat sebagai fundamental, tapi kita bisa berbuat lebih banyak, kan? Kita bisa menggabungkan hal-hal bersama-sama dengan cara yang menarik. 

Dan jadi mari kita melakukan itu, mari kita mulai untuk cabang keluar dari apa C memberi kita, dan mulai untuk membuat data kita sendiri struktur menggunakan bangunan tersebut blok bersama-sama untuk melakukan sesuatu benar-benar berharga, berguna. Salah satu cara yang dapat kita lakukan ini untuk berbicara tentang koleksi. Jadi sejauh ini kita sudah punya satu jenis data struktur untuk mewakili koleksi dari seperti nilai-nilai, nilai-nilai yang sama. Itu akan menjadi sebuah array. Kami memiliki koleksi bilangan bulat, atau koleksi karakter dan sebagainya. 

Struktur juga mengurutkan data yang struktur untuk mengumpulkan informasi, tapi tidak untuk mengumpulkan seperti nilai-nilai. Biasanya campuran jenis data yang berbeda bersama-sama dalam satu kotak. Tapi itu tidak sendiri digunakan untuk rantai bersama-sama atau menghubungkan bersama-sama sejenis item, seperti array. Array yang besar untuk Unsur melihat ke atas, tapi ingat bahwa itu sangat sulit untuk memasukkan ke dalam sebuah array, kecuali kita memasukkan di akhir dari array. 

Dan contoh terbaik yang saya miliki untuk itu adalah insertion sort. Jika Anda ingat video kami pada insertion sort, ada banyak biaya yang terlibat dalam memiliki untuk mengambil elemen, dan pergeseran mereka keluar dari jalan untuk menyesuaikan sesuatu ke tengah array Anda. Array juga menderita lain Masalahnya, yang tidak fleksibel. Ketika kita mendeklarasikan array, kita mendapatkan satu kesempatan itu. Kita bisa mengatakan, saya ingin ini banyak unsur. Mungkin 100, itu mungkin 1.000, itu mungkin menjadi x di mana x adalah angka yang pengguna memberi kami pada prompt atau perintah line. 

Tapi kami hanya mendapatkan satu kesempatan, kita tidak bisa kemudian berkata oh, sebenarnya saya dibutuhkan 101, atau saya butuhkan x ditambah 20. Terlambat, kita sudah mendeklarasikan array, dan jika kita ingin mendapatkan 101 atau x ditambah 20, kita harus menyatakan array yang sama sekali berbeda, menyalin semua elemen array lebih, dan kemudian kita memiliki cukup. Dan bagaimana jika kita salah lagi, apa jika kita benar-benar membutuhkan 102, atau x ditambah 40, kita harus melakukan ini lagi. Jadi mereka sangat fleksibel untuk mengubah ukuran data kami, tetapi jika kita menggabungkan bersama-sama beberapa dari dasar-dasar yang kita sudah sudah belajar tentang pointer dan struktur, khususnya menggunakan memori dinamis Alokasi dengan malloc, kami dapat menempatkan potongan-potongan ini bersama-sama untuk membuat data baru structure-- sebuah tunggal linked list kita mungkin say-- yang memungkinkan kita untuk tumbuh dan menyusut koleksi nilai dan kami tidak akan memiliki ruang kosong. 

Jadi sekali lagi, kita sebut ide ini, gagasan ini, linked list. Secara khusus, dalam video ini kami berbicara tentang daftar sendiri-sendiri terkait, dan kemudian video lain kita akan bicara daftar tentang ganda terkait, yang hanya variasi pada tema di sini. Tapi daftar sendiri-sendiri terkait terdiri dari node, node hanya menjadi term-- abstrak itu hanya sesuatu yang saya menelepon itu semacam struktur, pada dasarnya, aku? Hanya akan menyebutnya node-- dan ini node memiliki dua anggota, atau dua bidang. Ini memiliki data, biasanya integer, float karakter, atau bisa beberapa jenis data lain bahwa Anda telah didefinisikan dengan tipe def. Dan berisi pointer ke node lain dari jenis yang sama. 

Jadi kita memiliki dua hal dalam node ini, data dan pointer ke node lain. Dan jika Anda mulai untuk memvisualisasikan ini, Anda dapat berpikir tentang hal ini seperti rantai node yang terhubung bersama-sama. Kami memiliki node pertama, berisi data, dan pointer ke node kedua, yang berisi data, dan pointer ke node ketiga. Dan jadi itu sebabnya kami menyebutnya linked list, mereka dihubungkan bersama. 

Apa ini khusus struktur simpul terlihat seperti? Nah, jika Anda ingat dari video kami di mendefinisikan jenis kustom, dengan tipe def, kita dapat mendefinisikan structure-- dan ketik menentukan struktur seperti ini. tyepdef struct sllist, dan kemudian aku menggunakan nilai kata di sini sewenang-wenang untuk menunjukkan jenis data yang benar-benar. Anda bisa menyampaikan integer atau float, Anda bisa memiliki apa pun yang Anda inginkan. Ini tidak terbatas hanya bilangan bulat, atau sesuatu seperti itu. Jadi nilai hanya sebuah sewenang-wenang tipe data, dan kemudian pointer ke node lain dari jenis yang sama. 

Sekarang, ada menangkap sedikit di sini dengan mendefinisikan struktur ketika itu struktur referensial diri. Saya harus memiliki sementara nama untuk struktur saya. Pada akhir hari saya jelas ingin menyebutnya sll node, yang akhirnya baru nama bagian dari jenis definisi saya, tapi saya tidak dapat menggunakan sll simpul di tengah-tengah ini. Alasannya, saya tidak menciptakan jenis yang disebut sll simpul sampai aku memukul titik akhir ini di sini. Sampai saat itu, saya harus memiliki cara lain untuk merujuk pada tipe data ini. 

Dan ini adalah diri referensial tipe data. Itu; s tipe data dari struktur yang berisi data, dan pointer ke yang lain struktur dari jenis yang sama. Jadi saya harus mampu untuk merujuk tipe data ini setidaknya untuk sementara, sehingga memberikan sebuah sementara nama struct sllist memungkinkan saya untuk kemudian mengatakan saya ingin pointer ke struct sllist lain, bintang struct sllist, dan kemudian setelah saya menyelesaikan definisi, Sekarang saya bisa menyebut jenis node sll. 

Jadi itu sebabnya Anda melihat ada nama sementara di sini, tapi nama tetap di sini. Kadang-kadang Anda mungkin melihat definisi struktur, misalnya, yang tidak referensial diri, yang tidak memiliki nama specifier sini. Itu hanya akan mengatakan typedef struct, membuka penjepit keriting dan kemudian mendefinisikannya. Tapi jika Anda struct diri referensial, seperti yang satu ini, Anda perlu menentukan nama tipe sementara. Tapi pada akhirnya, sekarang bahwa kita sudah melakukan ini, kita hanya dapat merujuk node ini, unit-unit ini, sebagai node sll untuk tujuan dari sisa video ini. 

Baiklah, jadi kita tahu bagaimana membuat daftar simpul terkait. Kita tahu bagaimana mendefinisikan daftar simpul terkait. Sekarang, jika kita akan memulai menggunakan mereka untuk mengumpulkan informasi, ada beberapa operasi kami perlu memahami dan bekerja dengan. Kita perlu tahu cara membuat linked list dari udara tipis. Jika tidak ada daftar sudah, kami ingin memulai satu. Jadi kita harus mampu untuk membuat daftar link, kita perlu mencari mungkin melalui daftar link yang untuk menemukan elemen yang kita cari. Kita harus mampu memasukkan hal-hal baru ke dalam daftar, kami ingin daftar kami untuk dapat tumbuh. Dan sama, kami ingin bisa untuk menghapus hal-hal dari daftar kami, kami ingin daftar kami dapat menyusut. Dan pada akhir kami program, terutama jika Anda ingat bahwa kita dinamis mengalokasikan memori untuk membangun daftar ini biasanya, kami ingin membebaskan semua memori yang ketika kita sudah selesai bekerja dengan itu. Dan jadi kita harus mampu untuk menghapus Seluruh linked list dalam satu gagal menukik. Jadi mari kita pergi melalui beberapa operasi ini dan bagaimana kita dapat memvisualisasikan mereka, berbicara dalam kode pseudo khusus. Jadi kita ingin membuat linked list, jadi mungkin kita ingin mendefinisikan fungsi dengan prototipe ini. sll bintang node, membuat, dan aku melewati di satu argumen, beberapa data sewenang-wenang ketik lagi, beberapa tipe data yang sewenang-wenang. Tapi aku returning-- fungsi ini harus kembali ke saya pointer, untuk sendiri-sendiri linked list simpul. Sekali lagi, kami mencoba untuk membuat linked list dari udara tipis, jadi saya perlu pointer ke bahwa daftar ketika aku sudah selesai. 

Jadi apa langkah-langkah yang terlibat di sini? Nah, hal pertama yang saya akan lakukan adalah dinamis mengalokasikan ruang untuk node baru. Sekali lagi, kita sedang menciptakan keluar dari tipis udara, jadi kita perlu ruang malloc untuk itu. Dan tentu saja, segera setelah kami malloc, kami selalu memeriksa untuk memastikan bahwa kami pointer-- kami tidak mendapatkan kembali nol. Karena jika kita mencoba dan rasa hormat pointer null, kita akan menderita segfault dan kami tidak menginginkan hal itu. 

Kemudian kita ingin mengisi di lapangan, kami ingin menginisialisasi bidang nilai dan menginisialisasi kolom berikutnya. Dan kemudian kita ingin to-- akhirnya sebagai Fungsi prototipe indicates-- kita ingin untuk kembali pointer ke node sll. Jadi apa yang membuat ini terlihat seperti visual? Yah, pertama kita akan dinamis mengalokasikan ruang untuk sll node baru, jadi kami malloc-- itu representasi visual node yang baru kita buat. Dan kami periksa untuk memastikan itu tidak null-- dalam kasus ini, gambar tidak akan muncul jika itu nol, kita akan kehabisan memori, jadi kita baik untuk pergi ke sana. Jadi sekarang kita ke langkah C, menginisialisasi bidang nilai node. Nah, berdasarkan fungsi ini menelepon saya gunakan di sini, Sepertinya aku ingin lulus dalam 6, jadi saya akan 6 di bidang nilai. Sekarang, menginisialisasi kolom berikutnya. Nah, apa yang akan saya lakukan di sana, tidak ada yang berikutnya, benar, ini adalah satu-satunya hal dalam daftar. Jadi apa hal berikutnya dalam daftar? 

Tidak harus menunjuk ke sesuatu, benar. Tidak ada yang lain di sana, jadi apa konsep kita tahu itu nothing-- pointer ke apa-apa? Itu harus mungkin kita ingin untuk menempatkan pointer null ada, dan aku akan mewakili nol pointer hanya sebagai kotak merah, kita tidak bisa pergi lebih jauh. Seperti yang akan kita lihat sedikit nanti, kita akan memiliki akhirnya rantai panah menghubungkan node ini bersama-sama, tetapi ketika Anda menekan kotak merah, itu nol, kita tidak bisa pergi lebih jauh, itulah akhir dari daftar. 

Dan terakhir, kita hanya ingin kembali pointer ke node ini. Jadi kita akan menyebutnya baru, dan akan kembali baru sehingga dapat digunakan dalam Fungsi apapun menciptakannya. Jadi ada kita pergi, Kami telah menciptakan sendiri-sendiri linked list simpul dari udara tipis, dan sekarang kami memiliki daftar kami dapat bekerja dengan. 

Sekarang, katakanlah kita sudah memiliki rantai besar, dan kita ingin mencari sesuatu di dalamnya. Dan kami ingin fungsi yang akan untuk kembali benar atau salah, tergantung apakah suatu nilai ada dalam daftar itu. Sebuah prototipe fungsi, atau deklarasi untuk fungsi itu, mungkin terlihat seperti this-- Bool menemukan, dan maka kita ingin lulus dalam dua argumen. 

Yang pertama, adalah pointer ke elemen pertama dari linked list. Ini sebenarnya sesuatu yang Anda akan selalu ingin melacak, dan benar-benar mungkin sesuatu yang Anda bahkan dimasukkan ke dalam variabel global. Setelah Anda membuat daftar, Anda selalu, selalu ingin melacak sangat elemen pertama dari daftar. Dengan cara itu Anda dapat merujuk ke semua lainnya elemen dengan hanya mengikuti rantai, tanpa harus menjaga pointer utuh untuk setiap elemen tunggal. Anda hanya perlu untuk melacak pertama satu jika mereka semua dirantai bersama-sama. 

Dan kemudian hal yang kedua kita melewati lagi adalah sewenang-wenang some-- apapun jenis data yang kami mencari ada dalam mudah-mudahan salah satu node dalam daftar. Jadi apa langkah-langkah? Nah, hal pertama yang kami lakukan adalah kami membuat pointer transversal menunjuk ke kepala daftar. Nah, mengapa kita melakukan itu, kita sudah memiliki pointer di kepala daftar, kenapa tidak kita hanya bergerak satu bahwa sekitar? Nah, seperti saya hanya berkata, itu benar-benar penting bagi kami untuk selalu melacak Unsur pertama dalam daftar. Dan itu benar-benar baik untuk membuat duplikat dari itu, dan menggunakannya untuk bergerak sehingga kita tidak pernah sengaja menjauh, atau kita selalu memiliki pointer di beberapa titik yang tepat pada elemen pertama dari daftar. Jadi lebih baik untuk membuat kedua satu yang kita gunakan untuk bergerak. 

Kemudian kita hanya membandingkan apakah bidang nilai pada node yang adalah apa yang kita cari, dan jika itu tidak, kita hanya pindah ke node berikutnya. Dan kami terus melakukan itu lebih, dan lebih, dan lebih, sampai kita baik menemukan elemen, atau kita memukul null-- kita telah mencapai akhir dari daftar dan tidak ada. Ini harus mudah-mudahan membunyikan lonceng Anda hanya sebagai pencarian linear, kami hanya mereplikasi dalam struktur daftar sendiri-sendiri terkait alih-alih menggunakan array untuk melakukannya. 

Jadi di sini adalah contoh daftar sendiri-sendiri terkait. Yang satu ini terdiri dari lima node, dan kami memiliki pointer ke kepala daftar, yang disebut daftar. Hal pertama yang kami ingin lakukan adalah lagi, buat yang traversal pointer. Jadi kita miliki sekarang dua pointer saat itu untuk hal yang sama. 

Sekarang, perhatikan di sini juga, saya tidak harus malloc ada ruang untuk trav. Saya tidak mengatakan trav sama malloc sesuatu, simpul yang sudah ada, bahwa ruang dalam memori sudah ada. Jadi semua aku benar-benar lakukan adalah menciptakan pointer lain untuk itu. Saya tidak mallocing tambahan ruang, hanya sekarang dua pointer menunjuk ke hal yang sama. 

Jadi adalah 2 apa yang saya cari? Nah, tidak ada, jadi bukan aku akan pindah ke yang berikutnya. Jadi pada dasarnya saya akan mengatakan, trav sama trav berikutnya. Apakah 3 apa yang saya cari, tidak ada. Jadi saya terus pergi melalui, sampai akhirnya sampai ke 6 yang merupakan apa yang saya cari untuk didasarkan pada fungsi panggilan Saya memiliki di atas ada, dan jadi saya sudah selesai. 

Sekarang, bagaimana jika elemen aku cari tidak dalam daftar, apakah masih akan bekerja? Nah, perhatikan bahwa daftar di sini adalah agak berbeda, dan ini adalah hal lain yang penting dengan daftar terkait, Anda tidak perlu melestarikan mereka dalam urutan tertentu. Anda dapat jika Anda inginkan, tetapi Anda mungkin sudah menyadari bahwa kita tidak melacak apa elemen nomor kita di. 

Dan itu semacam salah satu perdagangan yang kita memiliki dengan linked list ayat array, apakah kita tidak memiliki akses acak lagi. Kita tidak bisa hanya mengatakan, saya ingin untuk pergi ke elemen 0, atau elemen 6 dari array saya, yang bisa saya lakukan dalam array. Saya tidak bisa mengatakan saya ingin pergi ke Elemen 0, atau elemen 6, atau elemen-25 daftar link saya, tidak ada indeks yang terkait dengan mereka. Dan sehingga tidak terlalu penting jika kita melestarikan daftar kami dalam rangka. Jika Anda ingin Anda pasti bisa, tapi ada tidak ada alasan mengapa mereka perlu dipertahankan dalam urutan apapun. Jadi sekali lagi, mari kita coba dan menemukan 6 dalam daftar ini. Nah, kita mulai di mulai, kita tidak menemukan 6, dan kemudian kita terus tidak menemukan 6, sampai kita akhirnya sampai ke sini. Jadi sekarang trav poin ke node mengandung 8, dan enam tidak di sana. 

Jadi langkah berikutnya akan untuk pergi ke pointer berikutnya, sehingga mengatakan trav sama trav berikutnya. Nah, trav berikutnya, ditandai dengan kotak merah ada, adalah null. Jadi ada tempat lain untuk pergi, dan pada titik ini kita dapat menyimpulkan bahwa kami telah mencapai akhir linked list, dan 6 tidak di sana. Dan itu akan dikembalikan palsu dalam kasus ini. 

OK, bagaimana kita memasukkan baru simpul ke dalam linked list? Jadi kita sudah mampu menciptakan linked list entah dari mana, tapi kami mungkin ingin membangun rantai dan tidak membuat sekelompok daftar yang berbeda. Kami ingin memiliki satu daftar yang memiliki banyak node di dalamnya, tidak banyak daftar dengan node tunggal. Jadi kita tidak bisa terus menggunakan Buat Fungsi kita ditetapkan sebelumnya, sekarang kita ingin memasukkan ke dalam daftar yang sudah ada. 

Jadi hal ini, kita akan untuk lulus dalam dua argumen, pointer ke kepala yang linked list yang ingin kita tambahkan ke. Sekali lagi, itu mengapa begitu penting bahwa kita selalu melacak, karena itu satu-satunya cara kita benar-benar harus mengacu pada seluruh daftar adalah hanya dengan pointer ke elemen pertama. Jadi kami ingin lulus dalam pointer ke elemen pertama, dan nilai yang kita apa pun ingin menambah daftar. Dan akhirnya fungsi ini akan kembali pointer dengan kepala baru dari linked list. 

Apa langkah-langkah yang terlibat di sini? Nah, seperti dengan membuat, kita perlu mengalokasikan secara dinamis ruang untuk node baru, dan periksa untuk memastikan yakin kita tidak kehabisan memori, sekali lagi, karena kita menggunakan malloc. Kemudian kita ingin mengisi dan masukkan node, sehingga menempatkan angka, apa pun val adalah, dalam node. Kami ingin memasukkan node di awal linked list. 

Ada alasan bahwa saya ingin melakukan ini, dan itu mungkin layak mengambil kedua untuk menghentikan video di sini, dan berpikir tentang mengapa saya ingin masukkan pada awal terkait daftar. Sekali lagi, saya sebutkan sebelumnya bahwa itu tidak benar-benar masalah jika kita melestarikannya dalam order, jadi mungkin itu petunjuk. Dan Anda melihat apa yang akan terjadi jika kita ingin to-- atau dari hanya satu detik lalu ketika kami akan melalui pencarian Anda bisa melihat apa yang mungkin terjadi jika kita mencoba untuk menyisipkan pada akhir daftar. Karena kita tidak memiliki pointer ke akhir daftar. 

Jadi alasan bahwa saya ingin untuk menyisipkan di awal, adalah karena saya bisa melakukannya segera. Saya memiliki pointer di awal, dan kita akan melihat ini dalam visual dalam satu detik. Tapi jika saya ingin memasukkan di akhir, Saya harus mulai dari awal, melintasi semua jalan ke akhir, dan kemudian taktik pada. Jadi itu berarti bahwa memasukkan pada akhir daftar akan menjadi o n operasi, akan kembali diskusi kami kompleksitas komputasi. Ini akan menjadi o operasi n, di mana sebagai daftar menjadi lebih besar, dan lebih besar, dan lebih besar, itu akan menjadi lebih dan lebih sulit untuk memakukan sesuatu pada di akhir. Tapi selalu benar-benar mudah untuk taktik sesuatu di di awal, Anda selalu di awal. 

Dan kita akan melihat visual ini lagi. Dan kemudian setelah kami selesai, setelah kami telah dimasukkan node baru, kami ingin kembali pointer untuk kepala baru dari linked list, yang karena kita sedang memasukkan di mulai, akan benar-benar pointer ke node yang baru kita buat. Mari kita memvisualisasikan ini, karena saya pikir itu akan membantu. 

Jadi, inilah daftar kami, terdiri dari empat unsur, node yang mengandung 15, yang menunjuk ke node mengandung 9, yang menunjuk ke node yang mengandung 13, yang menunjuk ke node yang mengandung 10, yang memiliki nol pointer sebagai pointer berikutnya jadi itu akhir daftar. Jadi kita ingin menyisipkan node baru dengan nilai 12 pada awal ini daftar, apa yang kita lakukan? Yah, pertama kita malloc ruang untuk node, dan kemudian kami menempatkan 12 di sana. 

Jadi sekarang kita sudah mencapai titik keputusan, kan? Kami memiliki beberapa pointer yang kita bisa bergerak, mana yang harus kita bergerak pertama? Haruskah kita membuat 12 poin untuk kepala baru list-- yang atau permisi, kita harus membuat 12 menunjuk ke kepala lama daftar? Atau harus kita katakan bahwa daftar sekarang dimulai pada 12. Ada perbedaan ada, dan kita akan melihat apa yang terjadi dengan kedua dalam detik. 

Tapi ini mengarah ke topik besar untuk sidebar, yaitu bahwa salah satu hal paling sulit dengan daftar terkait adalah untuk mengatur pointer dalam urutan yang benar. Jika Anda memindahkan barang-barang rusak, Anda dapat berakhir sengaja orphaning sisa daftar. Dan inilah contoh dari itu. Jadi mari kita pergi dengan ide of-- baik, kita baru saja membuat 12. Kita tahu 12 akan menjadi kepala baru dari daftar, dan jadi mengapa tidak kita hanya bergerak daftar pointer ke titik di sana. 

OK, jadi itu bagus. Jadi sekarang di mana tidak 12 titik berikutnya? Maksudku, secara visual kita dapat melihat bahwa ia akan menunjuk ke 15, sebagai manusia itu benar-benar jelas bagi kita. Bagaimana komputer tahu? Kami tidak punya apa-apa menunjuk ke 15 lagi, kan? 

Kami telah kehilangan setiap kemampuan untuk merujuk ke 15. Kita tidak bisa mengatakan panah baru equals berikutnya sesuatu, tidak ada ada. Bahkan, kami sudah yatim sisa daftar dengan demikian, kami telah sengaja rusak rantai. Dan kita tentu tidak ingin melakukan itu. 

Jadi mari kita kembali dan mencoba lagi ini. Mungkin hal yang benar untuk dilakukan adalah untuk mengatur 12 ini pointer berikutnya kepala lama daftar pertama, maka kita dapat memindahkan daftar lebih. Dan pada kenyataannya, itu adalah urutan yang benar bahwa kita harus mengikuti ketika kita bekerja dengan daftar sendiri-sendiri terkait. Kami selalu ingin menghubungkan elemen baru ke dalam daftar, sebelum kita mengambil semacam langkah penting untuk mengubah di mana kepala linked list adalah. Sekali lagi, itu suatu hal yang mendasar, kita tidak ingin kehilangan jejak itu. 

Jadi kami ingin memastikan bahwa semuanya dirantai bersama-sama, sebelum kita bergerak pointer itu. Dan jadi ini akan menjadi urutan yang benar, yang menghubungkan 12 ke dalam daftar, kemudian mengatakan bahwa daftar dimulai 12. Jika kita mengatakan daftar dimulai pada 12 dan kemudian mencoba untuk menghubungkan 12 ke dalam daftar, yang telah kita lihat apa yang terjadi. Kami kehilangan daftar dengan kesalahan. 

OK, jadi satu hal lagi untuk dibicarakan. Bagaimana jika kita ingin menyingkirkan seluruh linked list sekaligus? Sekali lagi, kita mallocing semua ruang ini, dan jadi kami perlu membebaskan ketika kita sudah selesai. Jadi sekarang kita ingin menghapus seluruh linked list. Nah, apa yang kita ingin lakukan? 

Jika kita sudah mencapai pointer null, kita ingin berhenti, jika tidak, hapus saja sisa daftar, kemudian membebaskan saya. Hapus sisanya dari daftar, dan kemudian membebaskan node saat. Apa yang terdengar seperti, Teknik apa yang harus kita berbicara tentang sebelumnya apakah itu terdengar seperti? Hapus orang lain, maka kembali dan menghapus saya. 

Itu rekursi, kami telah membuat masalah sedikit lebih kecil, kita mengatakan menghapus semua lain, maka Anda dapat menghapus saya. Dan lebih lanjut di jalan, node yang akan mengatakan, menghapus orang lain. Tapi akhirnya kita akan sampai ke titik di mana daftar adalah null, dan itulah kasus dasar kami. 

Jadi mari kita lihat ini, dan bagaimana ini bisa bekerja. Jadi, inilah daftar kami, itu sama daftar kami hanya berbicara tentang, dan ada langkah-langkah. Ada banyak teks di sini, tapi mudah-mudahan visualisasi akan membantu. 

Jadi kita have-- dan saya juga ditarik up kami tumpukan frame ilustrasi dari video kami pada tumpukan panggilan, dan mudah-mudahan semua ini bersama-sama akan menunjukkan apa yang terjadi. Jadi, inilah kode pseudo kami. Jika kita mencapai null pointer, berhenti, jika tidak, menghapus sisanya dari daftar, kemudian membebaskan node saat ini. Jadi sekarang, list-- pointer yang kami lewat di untuk menghancurkan poin ke 12. 12 tidak pointer nol, jadi kita akan menghapus sisa daftar. 

Apa yang menghapus sisa dari kita yang terlibat? Nah, itu berarti membuat panggilan untuk menghancurkan, mengatakan bahwa 15 adalah awal dari sisa daftar kami ingin menghancurkan. Dan panggilan untuk menghancurkan 12 adalah jenis ditahan. Ini beku di sana, menunggu panggilan untuk menghancurkan 15, untuk menyelesaikan tugasnya. 

Nah, 15 tidak null pointer, dan sehingga akan mengatakan, baiklah, baik, menghapus sisa daftar. Sisa daftar dimulai di 9, dan jadi kami hanya akan tunggu sampai Anda menghapus semua yang hal, kemudian kembali dan menghapus saya. Nah 9 akan mengatakan, baik, Aku bukan pointer null, sehingga menghapus sisanya daftar dari sini. Dan jadi coba dan menghancurkan 13. 13 kata, aku tidak null pointer, Hal yang sama, melewati buck. 10 tidak null pointer, 10 mengandung pointer null, tapi 10 tidak sendiri merupakan nol pointer sekarang, dan melewati uang juga. 

Dan sekarang daftar poin di sana, itu benar-benar akan menunjuk ke some-- jika saya memiliki lebih banyak ruang dalam gambar, itu akan menunjuk ke beberapa ruang acak bahwa kita tidak tahu apa itu. Ini adalah pointer nol meskipun, daftar secara harfiah sekarang ditetapkan itu nilai null. Itu menunjuk tepat di dalam kotak merah. Kami mencapai pointer nol, sehingga kita bisa berhenti, dan kami sudah selesai. 

Dan sehingga bingkai ungu adalah sekarang-- di atas stack-- itu frame aktif, tapi itu dilakukan. Jika kita sudah mencapai null pointer, berhenti. Kami tidak melakukan apa-apa, kita tidak bisa membebaskan pointer null, kami tidak malloc apapun ruang, dan jadi kita sudah selesai. Sehingga bingkai fungsi hancur, dan kami resume-- kami mengambil tempat kami meninggalkan off dengan yang berikutnya tertinggi, yang adalah ini bingkai biru tua di sini. Jadi kami mengambil tepat di mana kita tinggalkan. Kami menghapus sisa daftar sudah, jadi sekarang kita akan membebaskan node saat ini. Jadi sekarang kita bisa bebas node ini, dan sekarang kita telah mencapai akhir dari fungsi. Dan sehingga bingkai fungsi hancur, dan kami menjemput di satu biru muda. 

Jadi says-- saya sudah done-- menghapus sisa daftar, sehingga membebaskan node saat ini. Dan sekarang bingkai kuning kembali di atas tumpukan. Dan seperti yang Anda lihat, kami sekarang menghancurkan daftar dari kanan ke kiri. 

Apa yang akan terjadi, meskipun, jika kita telah melakukan hal-hal dengan cara yang salah? Sama seperti ketika kita mencoba untuk menambahkan elemen. Jika kita kacau rantai, jika kami tidak menghubungkan pointer dalam urutan yang benar, jika kita hanya dibebaskan elemen pertama, jika kita hanya membebaskan Kepala daftar, sekarang kita tidak memiliki cara untuk merujuk sisa daftar. Dan sehingga kita akan memiliki semuanya yatim, kita akan memiliki apa yang disebut kebocoran memori. Jika Anda ingat dari video kami alokasi memori dinamis, itu tidak hal yang sangat baik. 

Jadi seperti yang saya katakan, ada beberapa operasi bahwa kita perlu menggunakan untuk bekerja dengan linked list efektif. Dan Anda mungkin telah memperhatikan saya dihilangkan satu, menghapus satu elemen dari linked daftar. Alasan saya melakukan itu itu sebenarnya semacam sulit untuk berpikir tentang bagaimana untuk menghapus satu elemen dari sendiri-sendiri linked list. Kita harus mampu untuk melewatkan sesuatu dalam daftar, yang berarti kita bisa kita point-- ingin menghapus node-- ini tetapi untuk membuatnya jadi kita tidak kehilangan informasi apapun, kita perlu menghubungkan ini simpul di sini, di sini. 

Jadi saya mungkin melakukan itu salah dari perspektif visual. Jadi kita di awal kami daftar, kita melanjutkan melalui, kita ingin menghapus node ini. Jika kita hanya menghapusnya, kami telah rusak rantai. Simpul ini di sini mengacu pada segala sesuatu yang lain, mengandung rantai pada keluar dari sini. 

Jadi apa yang perlu kita lakukan benar-benar setelah kami sampai ke titik ini, adalah kita harus melangkah mundur satu, dan menghubungkan node ini ke node ini, sehingga kita kemudian dapat menghapus satu di tengah. Tapi daftar tunggal terkait tidak memberikan kami cara untuk pergi ke belakang. Jadi kita perlu menjaga baik dua pointer, dan memindahkan mereka semacam off langkah, satu di belakang lain seperti yang kita pergi, atau sampai ke titik dan kemudian mengirim pointer lain melalui. Dan seperti yang Anda lihat, itu bisa mendapatkan sedikit berantakan. Untungnya, kita memiliki cara lain untuk menyelesaikan itu, ketika kita berbicara tentang daftar ganda terkait. 

Aku Doug Lloyd, ini CS50.