1 00:00:00,000 --> 00:00:03,381 >> [MUSIC PLAYING] 2 00:00:03,381 --> 00:00:04,604 3 00:00:04,604 --> 00:00:05,520 Doug LLOYD: Baiklah. 4 00:00:05,520 --> 00:00:07,860 Jadi jika Anda baru saja selesai yang video pada daftar tunggal-linked maaf 5 00:00:07,860 --> 00:00:09,568 Saya meninggalkan Anda off pada sedikit cliffhanger. 6 00:00:09,568 --> 00:00:12,790 Tapi aku senang kau di sini untuk menyelesaikan kisah daftar doubly-linked. 7 00:00:12,790 --> 00:00:15,250 >> Jadi, jika Anda ingat dari video yang, kita berbicara 8 00:00:15,250 --> 00:00:18,500 tentang bagaimana secara tunggal-linked daftar lakukan menghadiri kemampuan kita 9 00:00:18,500 --> 00:00:22,090 untuk menangani informasi di mana jumlah elemen 10 00:00:22,090 --> 00:00:24,442 atau jumlah item di daftar dapat tumbuh atau menyusut. 11 00:00:24,442 --> 00:00:26,400 Kita sekarang dapat menangani sesuatu seperti itu, di mana 12 00:00:26,400 --> 00:00:28,310 kita tidak bisa menghadapinya dengan array. 13 00:00:28,310 --> 00:00:30,560 >> Tapi mereka menderita satu batasan kritis yang 14 00:00:30,560 --> 00:00:33,790 adalah bahwa dengan tunggal-linked daftar, kita dapat hanya pernah bergerak 15 00:00:33,790 --> 00:00:36,200 dalam satu arah melalui daftar. 16 00:00:36,200 --> 00:00:39,010 Dan satu-satunya situasi nyata mana yang bisa menjadi masalah 17 00:00:39,010 --> 00:00:41,250 adalah ketika kita mencoba untuk menghapus satu elemen. 18 00:00:41,250 --> 00:00:46,000 Dan kita bahkan tidak membahas bagaimana melakukannya dalam daftar sendiri-sendiri-linked di pseudocode. 19 00:00:46,000 --> 00:00:48,797 Hal ini tentu bisa dilakukan, tapi itu bisa menjadi sedikit merepotkan. 20 00:00:48,797 --> 00:00:50,630 Jadi jika Anda menemukan diri Anda dalam situasi di mana 21 00:00:50,630 --> 00:00:53,175 Anda mencoba untuk menghapus elemen tunggal dari daftar 22 00:00:53,175 --> 00:00:55,430 atau itu akan diperlukan bahwa Anda akan menghapus 23 00:00:55,430 --> 00:00:57,970 elemen tunggal dari daftar, Anda mungkin ingin 24 00:00:57,970 --> 00:01:02,090 untuk mempertimbangkan menggunakan doubly-linked daftar bukannya daftar tunggal-linked. 25 00:01:02,090 --> 00:01:06,320 Karena daftar doubly-linked memungkinkan Anda untuk bergerak maju dan mundur baik 26 00:01:06,320 --> 00:01:09,340 melalui daftar bukannya hanya maju melalui list-- yang 27 00:01:09,340 --> 00:01:13,950 hanya dengan menambahkan satu elemen tambahan definisi struktur kami 28 00:01:13,950 --> 00:01:16,690 untuk daftar node doubly-linked. 29 00:01:16,690 --> 00:01:19,770 >> Sekali lagi, jika Anda tidak akan akan menghapus elemen tunggal 30 00:01:19,770 --> 00:01:24,810 dari list-- karena kami menambahkan bidang ekstra untuk struktur kami 31 00:01:24,810 --> 00:01:28,340 definisi, node sendiri untuk daftar doubly-linked 32 00:01:28,340 --> 00:01:29,550 akan menjadi lebih besar. 33 00:01:29,550 --> 00:01:31,600 Mereka akan mengambil up byte lagi memori. 34 00:01:31,600 --> 00:01:34,160 Dan jadi jika ini bukan sesuatu yang Anda akan perlu melakukan, 35 00:01:34,160 --> 00:01:36,300 Anda mungkin memutuskan itu tidak layak trade off 36 00:01:36,300 --> 00:01:39,360 harus menghabiskan ekstra byte memori yang dibutuhkan 37 00:01:39,360 --> 00:01:43,940 untuk daftar ganda-linked jika Anda tidak akan menghapus elemen tunggal. 38 00:01:43,940 --> 00:01:46,760 Tapi mereka juga keren untuk hal-hal lain juga. 39 00:01:46,760 --> 00:01:51,260 >> Jadi seperti yang saya katakan, kita hanya perlu menambahkan satu bidang tunggal untuk struktur kami 40 00:01:51,260 --> 00:01:55,360 definition-- gagasan ini dari pointer Sebelumnya. 41 00:01:55,360 --> 00:01:58,620 Jadi dengan daftar sendiri-linked, kami memiliki nilai dan pointer berikutnya, 42 00:01:58,620 --> 00:02:02,850 sehingga doubly-linked list hanya memiliki cara untuk bergerak mundur juga. 43 00:02:02,850 --> 00:02:04,960 >> Sekarang di-linked sendiri-sendiri Daftar video, kami berbicara 44 00:02:04,960 --> 00:02:07,210 tentang ini adalah lima dari hal utama yang harus 45 00:02:07,210 --> 00:02:09,449 mampu lakukan untuk bekerja dengan daftar terkait. 46 00:02:09,449 --> 00:02:12,880 Dan untuk sebagian besar, kenyataan bahwa itu daftar ganda-linked 47 00:02:12,880 --> 00:02:14,130 tidak benar-benar sebuah lompatan besar. 48 00:02:14,130 --> 00:02:17,936 Kita masih bisa mencari melalui dengan hanya bergerak maju dari awal sampai akhir. 49 00:02:17,936 --> 00:02:20,810 Kita masih bisa membuat simpul dari udara tipis, cukup banyak dengan cara yang sama. 50 00:02:20,810 --> 00:02:23,591 Kita bisa menghapus daftar cukup banyak cara yang sama juga. 51 00:02:23,591 --> 00:02:25,340 Satu-satunya hal yang yang agak berbeda, 52 00:02:25,340 --> 00:02:28,970 benar-benar, yang memasukkan node baru ke dalam daftar, 53 00:02:28,970 --> 00:02:33,722 dan kami akhirnya akan berbicara tentang menghapus satu elemen dari daftar juga. 54 00:02:33,722 --> 00:02:35,430 Sekali lagi, cukup banyak tiga lainnya, kami 55 00:02:35,430 --> 00:02:37,888 tidak akan berbicara tentang mereka sekarang karena mereka hanya 56 00:02:37,888 --> 00:02:43,920 tweak sangat kecil pada ide-ide yang dibahas dalam daftar video yang tunggal-linked. 57 00:02:43,920 --> 00:02:46,292 >> Jadi mari kita menyisipkan node baru ke dalam daftar doubly-linked. 58 00:02:46,292 --> 00:02:48,750 Kami berbicara tentang melakukan hal ini untuk daftar tunggal terkait juga, 59 00:02:48,750 --> 00:02:52,020 tapi ada beberapa tambahan menangkap dengan daftar doubly-linked. 60 00:02:52,020 --> 00:02:55,280 Kami [? lewat?] di kepala daftar di sini dan beberapa nilai sewenang-wenang, 61 00:02:55,280 --> 00:02:58,600 dan kami ingin mendapatkan kepala baru daftar dari fungsi ini. 62 00:02:58,600 --> 00:03:01,414 Itu sebabnya ia mengembalikan bintang dllnode. 63 00:03:01,414 --> 00:03:02,330 Jadi apa langkah-langkah? 64 00:03:02,330 --> 00:03:04,496 Mereka adalah, sekali lagi, sangat mirip untuk daftar sendiri-linked 65 00:03:04,496 --> 00:03:05,670 dengan satu tambahan ekstra. 66 00:03:05,670 --> 00:03:08,900 Kami ingin mengalokasikan ruang untuk baru node dan cek untuk memastikan itu berlaku. 67 00:03:08,900 --> 00:03:11,510 Kami ingin mengisi simpul yang up dengan informasi apapun yang kita 68 00:03:11,510 --> 00:03:12,564 ingin menempatkan di dalamnya. 69 00:03:12,564 --> 00:03:15,480 Hal terakhir yang perlu kita do-- yang hal ekstra yang perlu kita lakukan, rather-- 70 00:03:15,480 --> 00:03:19,435 adalah untuk memperbaiki pointer Sebelumnya kepala lama daftar. 71 00:03:19,435 --> 00:03:21,310 Ingat bahwa karena daftar doubly-linked, 72 00:03:21,310 --> 00:03:23,110 kita dapat bergerak maju dan backwards-- yang 73 00:03:23,110 --> 00:03:27,080 berarti bahwa setiap node sebenarnya poin dua node lain, bukan hanya satu. 74 00:03:27,080 --> 00:03:29,110 Dan jadi kita harus memperbaiki kepala lama daftar 75 00:03:29,110 --> 00:03:32,151 untuk menunjuk ke belakang untuk kepala baru dari linked list, yang adalah sesuatu yang 76 00:03:32,151 --> 00:03:33,990 kita tidak perlu melakukan sebelumnya. 77 00:03:33,990 --> 00:03:37,420 Dan seperti sebelumnya, kami hanya mengembalikan pointer ke kepala baru dari daftar. 78 00:03:37,420 --> 00:03:38,220 >> Jadi, inilah daftar. 79 00:03:38,220 --> 00:03:40,144 Kami ingin memasukkan 12 ke daftar ini. 80 00:03:40,144 --> 00:03:42,060 Perhatikan bahwa diagram sedikit berbeda. 81 00:03:42,060 --> 00:03:47,710 Setiap node berisi tiga fields-- data, dan pointer Berikutnya merah, 82 00:03:47,710 --> 00:03:50,170 dan pointer Sebelumnya biru. 83 00:03:50,170 --> 00:03:54,059 Tidak ada yang datang sebelum 15 node, sehingga pointer Sebelumnya adalah nol. 84 00:03:54,059 --> 00:03:55,350 Ini adalah awal dari daftar. 85 00:03:55,350 --> 00:03:56,560 Tidak ada sebelum. 86 00:03:56,560 --> 00:04:03,350 Dan tidak ada yang datang setelah 10 node, dan jadi pointer Berikutnya adalah null juga. 87 00:04:03,350 --> 00:04:05,616 >> Jadi mari kita tambahkan 12 ke daftar ini. 88 00:04:05,616 --> 00:04:08,070 Kita perlu [tidak terdengar] ruang untuk node. 89 00:04:08,070 --> 00:04:11,480 Kami menempatkan 12 di dalamnya. 90 00:04:11,480 --> 00:04:14,840 Dan sekali lagi, kita harus benar-benar hati untuk tidak melanggar rantai. 91 00:04:14,840 --> 00:04:17,144 Kami ingin mengatur ulang pointer dalam urutan yang benar. 92 00:04:17,144 --> 00:04:19,519 Dan kadang-kadang yang mungkin mean-- seperti yang kita akan melihat sangat 93 00:04:19,519 --> 00:04:24,120 dengan delete-- bahwa kita memiliki beberapa pointer berlebihan, tapi itu OK. 94 00:04:24,120 --> 00:04:25,750 >> Jadi apa yang kita ingin lakukan pertama? 95 00:04:25,750 --> 00:04:28,290 Saya akan merekomendasikan hal mungkin Anda harus 96 00:04:28,290 --> 00:04:35,350 lakukan adalah untuk mengisi pointer dari 12 simpul sebelum Anda menyentuh orang lain. 97 00:04:35,350 --> 00:04:38,640 Jadi apa yang 12 akan menunjuk ke depan? 98 00:04:38,640 --> 00:04:39,860 15. 99 00:04:39,860 --> 00:04:42,430 Apa yang datang sebelum 12? 100 00:04:42,430 --> 00:04:43,640 Tidak ada. 101 00:04:43,640 --> 00:04:46,280 Sekarang kita sudah mengisi informasi tambahan dalam 12 102 00:04:46,280 --> 00:04:49,320 sehingga memiliki Sebelumnya, Berikutnya, dan nilai. 103 00:04:49,320 --> 00:04:53,505 >> Sekarang kita dapat memiliki 15-- ini tambahan Langkah kami berbicara about-- kami 104 00:04:53,505 --> 00:04:56,590 dapat memiliki 15 titik kembali ke 12. 105 00:04:56,590 --> 00:04:59,634 Dan sekarang kita bisa memindahkan kepala linked list juga menjadi 12. 106 00:04:59,634 --> 00:05:02,550 Sehingga cukup mirip dengan apa yang kita lakukan dengan daftar tunggal-linked, 107 00:05:02,550 --> 00:05:06,940 kecuali untuk langkah ekstra menghubungkan kepala lama daftar 108 00:05:06,940 --> 00:05:09,810 kembali ke kepala baru dari daftar. 109 00:05:09,810 --> 00:05:12,170 >> Sekarang mari kita akhirnya menghapus node dari linked list. 110 00:05:12,170 --> 00:05:14,350 Jadi katakanlah kita memiliki beberapa fungsi lain yang 111 00:05:14,350 --> 00:05:18,080 adalah menemukan simpul kita ingin menghapus dan telah memberi kita pointer ke persis 112 00:05:18,080 --> 00:05:19,710 node yang ingin kita hapus. 113 00:05:19,710 --> 00:05:22,360 Kami bahkan tidak need-- mengatakan kepala masih global dinyatakan. 114 00:05:22,360 --> 00:05:23,590 Kita tidak perlu kepala di sini. 115 00:05:23,590 --> 00:05:26,830 Semua fungsi ini lakukan adalah kita sudah menemukan pointer ke persis simpul kami 116 00:05:26,830 --> 00:05:28,090 ingin menyingkirkan. 117 00:05:28,090 --> 00:05:28,940 Mari kita menyingkirkan itu. 118 00:05:28,940 --> 00:05:31,859 Ini jauh lebih mudah dengan daftar doubly-linked. 119 00:05:31,859 --> 00:05:33,650 First-- itu sebenarnya hanya beberapa hal. 120 00:05:33,650 --> 00:05:38,760 Kita hanya perlu memperbaiki sekitarnya pointer node 'sehingga mereka melompati 121 00:05:38,760 --> 00:05:40,240 node kita ingin menghapus. 122 00:05:40,240 --> 00:05:43,484 Dan kemudian kita dapat menghapus simpul tersebut. 123 00:05:43,484 --> 00:05:45,150 Jadi sekali lagi, kita hanya akan lewat sini. 124 00:05:45,150 --> 00:05:49,625 Kita tampaknya telah memutuskan bahwa kita ingin menghapus node X. 125 00:05:49,625 --> 00:05:51,500 Dan lagi, apa yang saya melakukan sini-oleh way-- yang 126 00:05:51,500 --> 00:05:54,580 adalah kasus umum untuk simpul yang ada di tengah. 127 00:05:54,580 --> 00:05:56,547 Ada beberapa peringatan ekstra yang Anda 128 00:05:56,547 --> 00:05:59,380 perlu dipertimbangkan ketika Anda menghapus awal daftar 129 00:05:59,380 --> 00:06:01,040 atau akhir daftar. 130 00:06:01,040 --> 00:06:03,730 Ada beberapa khusus kasus sudut untuk menangani sana. 131 00:06:03,730 --> 00:06:07,960 >> Jadi ini bekerja untuk menghapus setiap node di tengah-tengah satu list-- yang 132 00:06:07,960 --> 00:06:11,550 memiliki pointer yang sah ke depan dan pointer yang sah mundur, 133 00:06:11,550 --> 00:06:14,460 Sebelumnya sah dan Berikutnya pointer. 134 00:06:14,460 --> 00:06:16,530 Sekali lagi, jika Anda bekerja dengan ujung, Anda 135 00:06:16,530 --> 00:06:18,500 perlu menangani mereka sedikit berbeda, 136 00:06:18,500 --> 00:06:19,570 dan kami tidak akan berbicara tentang itu sekarang. 137 00:06:19,570 --> 00:06:21,319 Tapi Anda mungkin bisa mencari tahu apa yang perlu 138 00:06:21,319 --> 00:06:24,610 harus dilakukan hanya dengan menonton video ini. 139 00:06:24,610 --> 00:06:28,910 >> Jadi kami telah diisolasi X. X adalah node kita ingin menghapus dari daftar. 140 00:06:28,910 --> 00:06:30,140 Apa yang kita lakukan? 141 00:06:30,140 --> 00:06:32,800 Pertama, kita perlu untuk mengatur ulang pointer luar. 142 00:06:32,800 --> 00:06:35,815 Kita perlu untuk mengatur ulang 9 berikutnya untuk melewatkan lebih dari 13 143 00:06:35,815 --> 00:06:38,030 dan arahkan ke 10-- yang adalah apa yang kita baru saja dilakukan. 144 00:06:38,030 --> 00:06:41,180 Dan kita juga perlu mengatur ulang 10 ini Sebelumnya 145 00:06:41,180 --> 00:06:44,610 untuk menunjuk ke 9 bukannya menunjuk ke 13. 146 00:06:44,610 --> 00:06:46,490 >> Jadi sekali lagi, ini adalah diagram untuk memulai dengan. 147 00:06:46,490 --> 00:06:47,730 Ini adalah rantai kami. 148 00:06:47,730 --> 00:06:51,027 Kita perlu untuk melewati lebih dari 13, tapi kita perlu juga melestarikan 149 00:06:51,027 --> 00:06:52,110 integritas daftar. 150 00:06:52,110 --> 00:06:54,680 Kami tidak ingin kehilangan Informasi di kedua arah. 151 00:06:54,680 --> 00:06:59,620 Jadi kita perlu untuk mengatur ulang pointer dengan hati-hati 152 00:06:59,620 --> 00:07:02,240 jadi kami tidak memutuskan rantai sama sekali. 153 00:07:02,240 --> 00:07:05,710 >> Jadi kita bisa mengatakan 9 ini pointer Berikutnya menunjuk ke tempat yang sama 154 00:07:05,710 --> 00:07:08,040 bahwa tiga belas Next pointer menunjuk sekarang. 155 00:07:08,040 --> 00:07:10,331 Karena kami akhirnya akan ingin melewatkan 13. 156 00:07:10,331 --> 00:07:13,750 Jadi dimanapun 13 poin berikutnya, Anda ingin sembilan menunjukkan ada gantinya. 157 00:07:13,750 --> 00:07:15,200 Jadi itulah yang. 158 00:07:15,200 --> 00:07:20,370 Dan kemudian dimanapun 13 poin kembali untuk, apa pun yang datang sebelum 13, 159 00:07:20,370 --> 00:07:24,800 kami ingin menunjukkan 10 itu bukan 13. 160 00:07:24,800 --> 00:07:29,290 Sekarang perhatikan, jika Anda mengikuti panah, kita bisa drop 13 161 00:07:29,290 --> 00:07:32,380 tanpa benar-benar kehilangan informasi apapun. 162 00:07:32,380 --> 00:07:36,002 Kami telah terus integritas daftar, bergerak baik maju dan mundur. 163 00:07:36,002 --> 00:07:38,210 Dan kemudian kita bisa hanya semacam dari membersihkannya sedikit 164 00:07:38,210 --> 00:07:40,930 dengan menarik daftar bersama-sama. 165 00:07:40,930 --> 00:07:43,270 Jadi kita mengatur kembali pointer di kedua sisi. 166 00:07:43,270 --> 00:07:46,231 Dan kemudian kita dibebaskan X simpul yang berisi 13, 167 00:07:46,231 --> 00:07:47,480 dan kami tidak melanggar rantai. 168 00:07:47,480 --> 00:07:50,980 Jadi kami melakukan yang baik. 169 00:07:50,980 --> 00:07:53,000 >> Catatan akhir di sini pada daftar terkait. 170 00:07:53,000 --> 00:07:55,990 Jadi baik singly- dan doubly-linked daftar, seperti yang kita lihat, 171 00:07:55,990 --> 00:07:58,959 dukungan penyisipan benar-benar efisien dan penghapusan elemen. 172 00:07:58,959 --> 00:08:00,750 Anda dapat cukup banyak melakukan dalam waktu yang konstan. 173 00:08:00,750 --> 00:08:03,333 Apa yang harus kita lakukan untuk menghapus elemen hanya detik yang lalu? 174 00:08:03,333 --> 00:08:04,440 Kami pindah satu pointer. 175 00:08:04,440 --> 00:08:05,920 Kami pindah pointer lain. 176 00:08:05,920 --> 00:08:07,915 Kami dibebaskan X-- mengambil tiga operasi. 177 00:08:07,915 --> 00:08:14,500 Ini selalu mengambil tiga operasi untuk menghapus node-- yang membebaskan node. 178 00:08:14,500 --> 00:08:15,280 >> Bagaimana kita memasukkan? 179 00:08:15,280 --> 00:08:17,280 Yah, kita hanya selalu memaku pada awal 180 00:08:17,280 --> 00:08:19,400 jika kita memasukkan efisien. 181 00:08:19,400 --> 00:08:21,964 Jadi kita perlu rearrange-- tergantung pada apakah itu 182 00:08:21,964 --> 00:08:24,380 sebuah singly- atau ganda-linked daftar, kita mungkin perlu melakukan tiga 183 00:08:24,380 --> 00:08:26,824 atau empat operasi max. 184 00:08:26,824 --> 00:08:28,365 Tapi sekali lagi, itu selalu tiga atau empat. 185 00:08:28,365 --> 00:08:30,531 Tidak peduli berapa banyak elemen dalam daftar kami, 186 00:08:30,531 --> 00:08:33,549 itu selalu tiga atau empat operations-- seperti penghapusan selalu 187 00:08:33,549 --> 00:08:35,320 tiga atau empat operasi. 188 00:08:35,320 --> 00:08:36,919 Ini waktu yang konstan. 189 00:08:36,919 --> 00:08:38,169 Jadi itu benar-benar hebat. 190 00:08:38,169 --> 00:08:40,620 >> Dengan array, yang kami lakukan sesuatu seperti insertion sort. 191 00:08:40,620 --> 00:08:44,739 Anda mungkin ingat bahwa penyisipan semacam ini tidak algoritma waktu yang konstan. 192 00:08:44,739 --> 00:08:46,030 Ini sebenarnya cukup mahal. 193 00:08:46,030 --> 00:08:48,840 Jadi ini adalah jauh lebih baik untuk memasukkan. 194 00:08:48,840 --> 00:08:51,840 Tapi seperti yang saya sebutkan di tunggal-linked list video, 195 00:08:51,840 --> 00:08:54,030 kita punya downside di sini juga, kan? 196 00:08:54,030 --> 00:08:57,580 Kami telah kehilangan kemampuan untuk acak mengakses elemen. 197 00:08:57,580 --> 00:09:02,310 Kita tidak bisa mengatakan, saya ingin nomor elemen empat atau nomor elemen 10 dari linked list 198 00:09:02,310 --> 00:09:04,990 dengan cara yang sama bahwa kita bisa melakukannya dengan array 199 00:09:04,990 --> 00:09:08,630 atau kita hanya bisa langsung Indeks ke elemen array kita. 200 00:09:08,630 --> 00:09:10,930 >> Dan mencoba untuk menemukan elemen dalam list-- terkait 201 00:09:10,930 --> 00:09:15,880 jika pencarian adalah important-- sekarang mungkin memerlukan waktu linear. 202 00:09:15,880 --> 00:09:18,330 Sebagai daftar mendapat lagi, itu mungkin mengambil satu langkah tambahan 203 00:09:18,330 --> 00:09:22,644 untuk setiap elemen tunggal dalam daftar di untuk menemukan apa yang kita cari. 204 00:09:22,644 --> 00:09:23,560 Jadi ada trade off. 205 00:09:23,560 --> 00:09:25,780 Ada sedikit pro dan elemen con di sini. 206 00:09:25,780 --> 00:09:29,110 >> Dan daftar doubly-linked bukan jenis terakhir dari kombinasi struktur data 207 00:09:29,110 --> 00:09:32,840 bahwa kita akan berbicara tentang, mengambil semua bangunan dasar 208 00:09:32,840 --> 00:09:34,865 blok C yang menempatkan bersama-sama. 209 00:09:34,865 --> 00:09:37,900 Karena pada kenyataannya, kita bisa bahkan melakukan lebih baik dari ini 210 00:09:37,900 --> 00:09:41,970 untuk membuat struktur data yang Anda mungkin bisa mencari melalui 211 00:09:41,970 --> 00:09:43,360 dalam waktu yang konstan juga. 212 00:09:43,360 --> 00:09:46,080 Tapi lebih pada bahwa dalam video lain. 213 00:09:46,080 --> 00:09:47,150 >> Aku Doug Lloyd. 214 00:09:47,150 --> 00:09:49,050 Ini adalah CS50. 215 00:09:49,050 --> 00:09:50,877