[Mūzikas atskaņošanai] 

Doug LLOYD: Labi, tāpēc pie šis punkts gaitā, mēs esam uz daudz pamati C. Mēs zinām daudz par mainīgo, masīvi, norādes, visu, kas labs stuff. Tie ir visu veida būvēts lai redzētu, kā pamatprincipiem, bet mēs varam izdarīt vairāk, vai ne? Mēs varam apvienot lietas kopā interesantos veidos. 

Un tāpēc pieņemsim to, ka sāksim sazaroties no kāda C dod mums, un sākt veidot savu datu struktūras, kas izmanto šīs ēkas blokus kopā kaut ko darīt tiešām vērtīgs, noderīga. Viens veids, kā mēs varam izdarīt, ir runāt par kolekcijām. Līdz Līdz šim mēs esam bija viena veida datus struktūra, kas pārstāv kolekcijas no patīk vērtības, līdzīgas vērtības. Tas būtu masīvs. Mums ir kolekcijas veselus skaitļus, vai kolekcijas burtiem un tā tālāk. 

Struktūras ir arī sava veida datu struktūru informācijas vākšanai, bet tas nav savākšanai, piemēram, vērtībām. Tas parasti maisījumi dažādu datu tipu kopā iekšpusē vienā kastē. Bet tas nav pats par sevi izmanto, lai ķēdes kopā vai savienot kopā līdzīgs priekšmeti, piemēram, masīvu. Masīvi ir liels elements uzmeklēt, bet atgādināt ka tas ir ļoti grūti ievietot masīva, ja vien mēs esam ievietojot at pašām beigām šī masīva. 

Un labākais piemērs man ir par to ir ievietošanas veida. Ja jūs atceraties mūsu video uz ievietošanas veida, tur bija daudz izdevumi iesaistīti ņemot uzņemt elementus, un novirzīt tos no tā, lai ietilptu kaut ko vērā vidū jūsu masīvs. Masīvi arī cieš no otra Problēma, kas ir neelastīgums. Kad mēs deklarēt masīvu, mēs iegūtu vienu shot pie tā. Mēs teikt, es gribu šis daudzi elementi. Varētu būt 100, tas var būt 1000, tas varētu būt x, kur x ir skaitlis, ka lietotājs sniedza mums tūlītēju vai komandu line. 

Bet mēs tikai iegūt vienu shot pie tā, mēs nesaņem tad teikt ak, patiesībā es nepieciešami 101, vai man vajadzēja x plus 20. Pārāk vēlu, mēs esam jau paziņoja, ka masīvs, un, ja mēs gribam, lai saņemtu 101 vai x plus 20, mums ir jādeklarē pavisam cits masīvs, kopēt visus elementus masīva vairāk, un tad mums ir pietiekami daudz. Un ko tad, ja mēs esam nepareizi atkal, ko ja mums tiešām ir nepieciešams 102, vai X plus 40, mums ir jādara tas vēlreiz. Tāpēc viņi ir ļoti neelastīga izmēru maiņas mūsu datus, bet, ja mēs apvienot kopā dažus no pamatiem, ko mēs jau esam uzzināja par norādes un struktūrām, jo īpaši, izmantojot dinamisko atmiņu piešķiršana ar malloc, mēs var likt šos gabalus kopā izveidot jaunu datu structure-- A atsevišķi saistīts sarakstu mēs varētu say-- kas ļauj mums augt un sarukt kolekcija vērtībām un mums nebūs nekādu izšķērdēta kosmosa. 

Tātad atkal mēs aicinām šo ideju, šis jēdziens, saistītais saraksts. Proti, šajā video mēs esam runājam par atsevišķi saistīta sarakstā, un tad vēl video mēs runājam par divkārt saistīti saraksti, kas ir tikai variācija par tēmu šeit. Bet atsevišķi saistīts saraksts sastāv no mezgliem, mezgli nav tikai abstrakts term-- tas ir tikai kaut kas es esmu aicinot tas ir sava veida struktūra, būtībā, es esmu? Tikai gatavojas to nosaukt node-- un tas mezgls ir divi locekļi vai divus laukus. Tas ir dati, parasti ir skaitlis, raksturs peldēt, vai varētu būt kāds cits datu tips ka jūs esat definēts ar tipa def. Un tas ietver rādītāju uz vēl viens mezgls tā paša tipa. 

Tātad mums ir divas lietas iekšpusē šis mezgls, datu un rādītāju uz citu mezglu. Un, ja jūs sākat vizualizēt tas, jūs varat domāt par to kā ķēdes mezglu, kas ir savienoti kopā. Mums ir pirmo mezglu, to satur datus un rādītāju ar otro mezglu, kas satur dati, un rādītāju uz trešo mezglu. Un tā tas ir iemesls, kāpēc mēs to saucam par saistīts saraksts, viņi savstarpēji saistīti. 

Ko dara šis īpašais mezgla struktūra izskatās? Nu, ja jūs atceraties no mūsu video definējot pasūtījuma tipus, ar tipa DEF, mēs varam definēt structure-- un ierakstiet definētu struktūru, kā šis. tyepdef struct sllist, un tad es esmu izmantojot vārdu vērtību šeit patvaļīgi lai norādītu datu tipu tiešām. Jūs varētu iet uz skaitlim vai peldēt, Jums varētu būt, ko jūs vēlaties. Tas nav tikai vienkārši veseli skaitļi, vai kaut kas tamlīdzīgs. Tātad vērtība ir tikai patvaļīgs datu tips, un pēc tam rādītājs uz citu mezglu tā paša tipa. 

Tagad tur ir maz nozvejas šeit ar definējot struktūru kad tas ir sevi godbijīgs struktūra. Man ir jābūt pagaidu nosaukt par manu struktūru. Beigās dienas I nepārprotami vēlas, lai izsauktu to SLL mezglā, tas galu galā jaunais nosaukt daļa no mana tipa definīciju, bet es nevaru izmantot SLL mezglu vidū šis. Iemesls ir, man nav izveidoja tipa sauc SLL mezglu kamēr es hit šo pēdējo punktu šeit. Līdz šo jautājumu, man ir jābūt vēl viens veids, kā atsaukties uz šo datu tipu. 

Un tas ir self godbijīgs datu tips. Tas, s datu tipam struktūra, kas satur datus, un rādītājs uz citu struktūra tā paša tipa. Tāpēc man ir nepieciešams, lai varētu atsaukties uz šī datu tips vismaz uz laiku, tā dodot tai ir pagaidu nosaukums struct sllist ļauj man tad teikt, es gribu rādītāju uz citu struct sllist, struct sllist zvaigzne, un pēc tam pēc tam, kad es esmu pabeidzis definīciju, Es tagad var zvanīt šāda veida SLL mezglā. 

Tātad, tas ir iemesls, kāpēc jūs redzēt tur ir pagaidu nosaukums šeit, bet pastāvīgs vārds šeit. Reizēm jūs varētu redzēt definīcijas struktūra, piemēram, kas ir ne sevis godbijīgs, ka nav apzīmētājs nosaukumu šeit. Tas būtu vienkārši teikt typedef struktūrai, atvērt cirtaini lencēm un tad noteikt to. Bet, ja tu esi struct ir pašnodarbināta godbijīgs, jo tas ir viens, Jums ir nepieciešams norādīt pagaidu veida nosaukums. Bet galu galā, tagad ka mēs esam izdarījuši, mēs varam tikai attiecas uz šiem mezgliem, šīs vienības, kā SLL mezgli nolūkos no pārējo šo video. 

Labi, tāpēc mēs zinām, kā izveidot saistīts saraksta mezglā. Mēs zinām, kā to definēt saistītais saraksts mezglu. Tagad, ja mēs ejam, lai sāktu izmantot tos, lai savāktu informāciju, tur ir pāris operācijām mēs nepieciešams saprast un strādāt. Mums ir jāzina, kā izveidot saistītais saraksts no zila gaisa. Ja tur nav saraksts jau, mēs vēlamies, lai sāktu vienu. Tāpēc mums ir jāspēj lai izveidotu saistīts sarakstu, mums ir nepieciešams, lai, iespējams, meklēt izmantojot saiti sarakstu atrast elementu mēs meklējam. Mums ir nepieciešams, lai varētu ievietot jaunas lietas fani sarakstā, mēs vēlamies, lai mūsu sarakstā, lai varētu augt. Un līdzīgi, mēs vēlamies, lai varētu izdzēst lietas no mūsu saraksta, mēs vēlamies, lai mūsu sarakstā, lai varētu sarukt. Un beigās mūsu programmas, jo īpaši Ja jūs atceraties, ka mēs esam dinamiski piešķirot atmiņu veidot šos sarakstus, parasti, mēs vēlamies, lai atbrīvotu visu šo atmiņa kad mēs esam darījuši strādāt ar to. Un tāpēc mums ir nepieciešams, lai varētu dzēst viss saistīts saraksts vienā neizdoties sagrābt. So iesim cauri daži no šiem operāciju un kā mēs varētu vizualizēt tos, runā pseudocode kodu konkrēti. Tāpēc mēs vēlamies, lai izveidotu saistīta sarakstu, tāpēc varbūt mēs vēlaties, lai noteiktu funkciju ar šo prototipu. SLL mezglā zvaigzne, radīt, un es esmu iet vienā arguments, daži patvaļīgi dati rakstīt atkal, dažu patvaļīgu datu tipu. Bet es esmu returning-- šo funkciju vajadzētu atgriezties pie manis rādītāju, līdz A atsevišķi saistīts saraksts mezglā. Atgādināsim, ka mēs cenšamies, lai radītu saistītais saraksts no zila gaisa, tāpēc man ir nepieciešams rādītāju uz šis saraksts, kad es esmu darīts. 

Tātad, kādi ir soļi šeit iesaistīti? Nu, pirmā lieta, ko es esmu gatavojas darīt, ir dinamiski piešķirt vietu jaunu mezglu. Atgādināsim, ka mēs esam veidojot to no plānas gaiss, tāpēc mums ir nepieciešams, lai malloc vietu tajā. Un, protams, nekavējoties kad mēs malloc, mēs vienmēr pārliecinieties, ka mūsu pointer-- mēs nesaņēma atpakaļ null. Jo, ja mēs mēģinātu cieņa Null rādītāju, mēs esam gatavojas ciest segfault un mēs negribam, ka. 

Tad mēs vēlamies aizpildīt jomā, mēs vēlamies, lai sāktu vērtību lauks un sāktu nākamo lauku. Un tad mēs gribam kuri paredzēti, beidzot kā funkcija prototips indicates-- mēs gribam atgriezties rādītāju uz SLL mezglā. Tātad, kas padara šo izskatās vizuāli? Nu, pirmkārt, mēs ejam, lai dinamiski piešķirt vietu jaunam SLL mezglu, tāpēc mēs malloc-- tas vizuāls attēlojums mezgla mēs tikko izveidots. Un mēs pārbaudām, lai pārliecinātos, tas nav null-- šajā gadījumā, aina nebūtu parādīts uz augšu, ja tas bija null, mēs būtu beigušies atmiņas, tāpēc mēs esam labi iet tur. Tāpēc tagad mēs esam par soli C, inicializēt mezgli vērtības laukā. Nu, pamatojoties uz šo funkciju zvaniet es esmu, izmantojot šeit, Izskatās, ka es gribu iet uz 6., tāpēc es ņemšu 6 vērtības laukā. Tagad, sāktu nākamo lauku. Nu, ko es esmu gatavojas darīt tur, nekas blakus, pa labi, tas ir vienīgais, sarakstā. Tātad, kas ir nākamā lieta sarakstā? 

Tā nedrīkst norādīt uz kaut ko, labi. Tur nekas cits tur, lai to, kas ir jēdziens mēs zinu, ka ir nothing-- norādes uz neko? Tas būtu varbūt mēs gribam likt null rādītāju tur, un es ņemšu pārstāv null rādītājs kā tikai sarkanu lodziņu, mēs nevaram iet tālāk. Kā mēs redzēsim nedaudz vēlāk, mums būs galu galā ķēdes Bultu savieno šiem mezgliem kopā, bet, kad jūs hit sarkana kaste, kas ir null, mēs nevaram iet tālāk, tas ir beigu saraksta. 

Un visbeidzot, mēs vienkārši vēlamies atgriezties rādītāju uz šo mezglu. Tāpēc mēs to saucam jauns, un atgriezīsies jauns lai to var lietot kāda funkcija izveidoja to. Tātad mēs ejam, esam izveidojuši atsevišķi saistīts saraksts mezgla no zila gaisa, un tagad mums ir saraksts, mēs varam strādāt. 

Tagad, teiksim, mēs jau ir liels ķēdi, un mēs vēlamies, lai atrastu kaut ko tajā. Un mēs gribam funkcija, kas notiek, atgriezties true vai false, atkarībā par to, vai vērtība eksistē šajā sarakstā. Funkcija prototips, vai deklarācija par šo funkciju, varētu izskatīties this-- Bool atrast, un tad mēs gribam iet uz diviem argumentiem. 

Pirmais, ir rādītājs uz no saistītā saraksta pirmais elements. Tas ir tiešām kaut kas jums vienmēr vēlas sekot, un tiešām varētu būt kaut kas jūs pat nodot globālā mainīgā. Tiklīdz jūs izveidot sarakstu, Jums vienmēr, vienmēr vēlas sekot līdzi ļoti no saraksta pirmais elements. Tādā veidā jūs varat atsaukties uz visu pārējo elementi, tikai pēc ķēdi, bez saglabātu norādes neskarts uz katru elementu. Jums tikai nepieciešams, lai sekotu pirmais vienu, ja viņi visi pieķēdēts kopā. 

Un tad otrā lieta mēs iet atkal ir patvaļīgi some-- neatkarīgi no datu tipu mēs esam meklē tur ir iekšā cerams viens no mezgliem sarakstā. Tātad, kādi ir soļi? Nu, pirmā lieta, ko mēs darām, ir mēs izveidot transversālu rādītāju norādot uz sarakstos galvu. Nu, kāpēc mēs to darām, mēs jau ir rādītāju pie saraksti galvas, kāpēc nav mēs vienkārši pārvietot, ka viens apkārt? Nu, piemēram, es tikko teicu, tas ir patiešām svarīgi, lai mums vienmēr sekot ļoti pirmais elements sarakstā. Un tā tas ir tiešām labāk izveidot dublikātu, ka, un izmantot šo, lai pārvietotos, lai mēs nekad nejauši virzīties prom, vai mēs vienmēr ir rādītāju kādā brīdī, kas ir tiesības uz saraksta pirmā elementa. Tātad, tas ir labāk, lai izveidotu Otrs, ko mēs izmantojam, lai pārvietotos. 

Tad mēs vienkārši salīdzināt, vai vērtība lauks šajā mezglā ir tas, ko mēs meklējam, un, ja tas ir nē, mēs vienkārši pāriet uz nākamo mezglu. Un mēs turpinām darām vairāk, un vairāk, un vairāk, kamēr mēs vai nu atrast elements, vai arī mēs hit null-- mēs esam sasnieguši no saraksta, un tas ir ne tur. Tas būtu cerams gredzens bell jūs kā tikko lineārs meklēšanu, mēs esam tikai atdarināt to atsevišķi saistīts saraksts struktūra nevis izmantojot masīvu, lai to izdarītu. 

Tātad, šeit ir piemērs atsevišķi saistīts saraksts. Tas viens sastāv no pieci mezgli, un mums ir rādītāju uz galvas saraksts, kas tiek saukts saraksts. Pirmā lieta, ko mēs vēlamies darīt, ir atkal, izveidot šo šķērsošana rādītāju. Tāpēc mums ir tagad ir divas norādes kas norāda uz vienu un to pašu. 

Tagad, paziņojums šeit arī, man nav ir malloc jebkuru telpu trav. Es neteicu Trav vienāds malloc kaut kas, ka mezglā jau pastāv, ka kosmosa atmiņā jau eksistē. Tāpēc es esmu patiesībā dara, ir radot vēl vienu rādītāju uz to. Es neesmu mallocing papildu telpa, tikai tagad ir divas norādes norādot uz to pašu. 

Tātad, ir 2, ko es meklēju? Nu, nē, tā vietā es esmu gatavojas pārcelties uz nākamo. Vārdu sakot, es teiktu, Trav vienāds trav nākamo. Vai 3, ko es meklēju, nē. Tāpēc es joprojām iet cauri, līdz beidzot nokļūt līdz 6., kas ir tas, ko es esmu meklē , kas balstās uz funkciju zvanu Man ir augšpusē tur, un tāpēc es esmu darīts. 

Tagad, kas notiks, ja elements es esmu meklē nav sarakstā, tas joprojām iet uz darbu? Nu, ievērosiet, ka saraksts šeit ir smalki atšķirīgs, un šī ir vēl viena lieta, kas ir svarīgi ar saistītiem sarakstiem, jums nav, lai saglabātu viņiem konkrētā secībā. Jūs varat, ja vēlaties, bet Jums var būt jau pamanījuši ka mēs neesam sekotu ko numurs elements mēs esam. 

Un tas ir sava veida vienas tirdzniecības ka mēs ir ar saistīts saraksts vārsmas blokiem tas mums nav brīvpiekļuves vairs. Mēs nevaram vienkārši teikt, es gribu iet uz 0th elementu, vai 6. mana masīva elements ko es varu darīt masīvā. Es nevaru teikt, es gribu iet uz 0. elements, vai 6. elements, vai 25. elements mana saistīta saraksta tur nav rādītājs, kas saistītas ar tām. Un tā tas nav īsti jautājums ja mēs saglabātu mūsu sarakstu kārtībā. Ja jūs vēlaties, lai jums protams, var, bet tur ir Nav iemesla, kāpēc viņiem ir nepieciešams jāsaglabā jebkurā secībā. Tātad vēlreiz, pamēģināsim un atrast 6 šajā sarakstā. Nu, mēs sākam pie sākuma, mēs neatrodam 6, un tad mēs turpināsim neatrodot 6, kamēr mēs beidzot nokļūt šeit. Tāpēc tieši tagad Trav norāda uz mezglā kas satur 8, un seši nav tur. 

Tātad nākamais solis būtu lai dotos uz nākamo rādītāju, tā teikt Trav vienāds trav nākamo. Nu, Trav nākamais, kas apzīmēta ar sarkanā kaste tur, ir nulle. Tātad tur ir nekur citur iet, un tāpēc šajā brīdī mēs varam secināt, ka mēs esam sasnieguši beigām, kas saistīts saraksta, un 6 nav tur. Un tas būtu jāatdod viltus šajā gadījumā. 

OK, kā mēs ievietotu jaunu mezglu uz saistīts sarakstā? Tātad, mēs esam spējuši radīt saistītais saraksts no nekurienes, bet mēs, iespējams, vēlas veidot ķēdi, un nav izveidot ķekars atšķirīgas sarakstos. Mēs vēlamies, lai būtu vienu sarakstu, kas ir ķekars mezglu tā, nav ķekars sarakstu ar vienu mezglu. Tātad, mēs varam ne tikai saglabāt, izmantojot Izveidot funkcija mēs definēts agrāk, tagad mēs vēlaties ievietot par a sarakstu, kas jau pastāv. 

Tātad šajā gadījumā, mēs ejam iziet uz diviem argumentiem, rādītājs uz galvas, ka saistīts saraksts, ko mēs vēlamies pievienot. Atkal, tas ir iemesls, kāpēc tas ir tik svarīgi, ka mēs vienmēr izsekot to, jo tas ir vienīgais veids, kā mēs patiešām ir atsaukties uz visa saraksts ir tikai ar rādītāju uz pirmā elementa. Tāpēc mēs gribam iet no A rādītāju uz šo pirmo elementu, un kāda vērtība mēs vēlaties pievienot sarakstam. Un galu galā šī funkcija gatavojas atgriezties rādītāju uz jauno vadītāju saistītajā sarakstā. 

Kādi ir soļi, šeit ir iesaistītas? Nu, tāpat kā ar izveidot, mums ir dinamiski piešķirt telpa par jaunu mezglu, un pārbaudiet, Noteikti mums nav beigušies atmiņas, atkal, tāpēc, ka mēs esam izmantojot malloc. Tad mēs vēlamies aizpildīt un ievietojiet mezglu, tāpēc nodot skaitu, kāds val ir, uz mezglā. Mēs vēlamies, lai ievietotu mezglu pie sākums saistīts sarakstā. 

Tur ir iemesls, ka es gribu darīt, un tas varētu būt vērts otru lai apturētu video šeit, un domāt par to, kāpēc es gribētu ievietot sākumā saistītais saraksts. Atkal, es iepriekš minēju ka tas nav īsti svarīgi, ja mēs saglabātu to jebkurš pasūtījums, tāpēc varbūt tas ir pavediens. Un redzējāt kas notiktu, ja mēs vēlējās kuri paredzēti, vai tikai sekundi atpakaļ, kad mēs gatavojamies izmantojot meklēšanas jūs varēja redzēt, ko varētu notikt, ja mēs cenšamies ievietot beigās saraksta. Jo mums nav rādītāju uz saraksta beigām. 

Tātad iemesls, ka es gribētu ievietot sākumā, ir tāpēc, ka es varu darīt to nekavējoties. Man ir rādītāju sākumā, un mēs redzēsim to vizuālais sekundē. Bet, ja es gribu, lai ievietotu beigās, Man ir jāsāk sākumā, šķērsotu visu ceļu uz gals, un pēc tam tack to. Tātad tas nozīmē, ka ievietojot beigās saraksta kļūtu par o n ekspluatācija, atgriežās mūsu diskusijā skaitļošanas sarežģītība. Tā, lūdzu kļūt par o n operācijas, kur jo saraksts got lielāks, un lielāks, un lielāks, tas būs kļuvis vairāk un grūtāk sadiegšana kaut ko uz beigās. Bet tas vienmēr ir ļoti viegli sadiegšana kaut ko sākumā, jūs vienmēr sākumā. 

Un mēs redzēsim vizuāli tas atkal. Un tad, kad mēs esam darīts, tiklīdz mēs esam iekļauj jaunu mezglu, mēs gribam atgriezties mūsu rādītāju jaunais vadītājs saistītajā sarakstā, kas jo mēs esam ievietojot pie sākumā, faktiski būs rādītāju uz mezglu mēs tikko izveidojāt. Pieņemsim vizualizēt to, jo es domāju, ka tas tev palīdzēs. 

Tātad, šeit ir mūsu sarakstā, tas sastāv no četri elementi, mezgls, kas satur 15, kas norāda uz mezglu kas satur 9, kas norāda uz mezglu, kas satur 13, kas norāda uz mezglu, kas satur 10, kas ir null rādītājs kā savu nākamo rādītājs tā, ka ir beigu sarakstā. Tāpēc mēs vēlamies, lai ievietotu jaunu mezglu ar vērtību 12 sākumā tas saraksts, ko mēs darām? Nu, vispirms mums malloc telpu, lai mezglā, un tad mēs ieliekam 12 tur. 

Tāpēc tagad mēs esam sasnieguši lēmuma pieņemšanas punkts, vai ne? Mums ir pāris norādes, ka mēs varētu pārvietot, kuriem viens mums vajadzētu virzīties vispirms? Vai mums vajadzētu veikt 12 norāda uz jaunais vadītājs list-- vai atvainojiet, mums vajadzētu darīt 12 norāda uz veco galvas sarakstā? Vai mums vajadzētu teikt, ka Tagad sarakstā sākas 12. Tur ir atšķirība tur, un mēs apskatīt to, kas notiek gan ar sekundē. 

Bet tas noved pie liels temats sānjoslas, kas ir, ka viens no sarežģītākajiem lietas ar saistītiem sarakstiem ir sakārtot norādes pareizā secībā. Ja jūs pārvietot lietas no rīkojuma, Jūs varat nonākt nejauši orphaning pārējo saraksta. Un šeit ir piemērs, ka. So iesim ar ideju of-- labi, mēs esam tikko izveidots 12. Mēs zinām, 12 būs jaunais vadītājs saraksta, un tad kāpēc nav mēs vienkārši pārvietot saraksts rādītājs norādīt tur. 

Labi, tā ka ir labi. Tāpēc tagad, kad tas 12. nākamo punktu? Es domāju, vizuāli mēs varam redzēt ka tas norāda uz 15, kā cilvēkiem tas ir patiešām skaidrs mums. Kā dators zināt? Mums nav nekas norādot uz 15 vairs, vai ne? 

Mēs esam zaudējuši jebkādu iespēju atsaukties uz 15. Mēs nevaram teikt, jauns bultiņas blakus Vienāds kaut kas, tur nekas tur. Patiesībā, mēs esam bāreņiem pārējā saraksta to darot, mēs esam nejauši sadalīti ķēdi. Un mēs noteikti nevēlamies to darīt. 

So iesim atpakaļ un mēģināt to vēlreiz. Varbūt pareizi darīt ir noteikt 12 nākamais rādītāju uz veco galvas saraksta pirmā, tad mēs varam virzīties sarakstu pāri. Un faktiski, ka ir pareizi, lai mēs nepieciešams sekot, kad mēs esam Strādājot ar atsevišķi saistīta sarakstā. Mēs vienmēr vēlamies, lai savienotu jauns elements uz sarakstā, Pirms mēs šāda veida nozīmīgs solis mainīt kur galva saistīts saraksts ir. Atkal, tas ir tik būtiska lieta, mēs negribam pazaudēt to. 

Tāpēc mēs vēlamies, lai pārliecinātos, ka viss ir chained kopā, Pirms mēs virzāmies šo rādītāju. Un tā tas būtu pareizā secībā, kas ir savienojumu 12, lai saraksta, tad saka, ka saraksts sāk 12. Ja mēs teicām saraksts sākas 12. un tad mēģināju savienot 12 sarakstā, mēs jau esam redzējuši, kas notiek. Mēs zaudējam sarakstu kļūdas. 

Labi, tāpēc vēl viena lieta runāt. Ko darīt, ja mēs gribam, lai atbrīvotos no vesela saistīta sarakstu uzreiz? Atgādināsim, ka mēs esam mallocing visu šo vietu, un tāpēc mēs ir nepieciešams, lai atbrīvotu to, kad mēs esam darījuši. Tāpēc tagad mēs vēlamies, lai izdzēstu viss saistīts saraksts. Nu, ko mēs vēlamies darīt? 

Ja mēs esam sasnieguši null rādītāju, mēs vēlaties pārtraukt, citādi, tāpat izdzēst pārējā saraksta un pēc tam atbrīvot mani. Dzēst pārējā saraksta un pēc tam atbrīvot pašreizējo mezglā. Ko nozīmē, ka skaņas, piemēram, ko paņēmiens ir mēs runājām par iepriekš dara, ka skaņas, piemēram? Dzēst ikviens cits, tad atgriezties un dzēst mani. 

Tas ir rekursijas, mēs esam padarījuši Problēma mazliet mazāks, mēs esam sakot dzēst visiem cits, tad jūs varat izdzēst mani. Un tālāk pa ceļu, kas mezgls teiks, dzēst ikviens cits. Bet galu galā mēs nokļūt uz punkts, kurā saraksts ir spēkā, un tas ir mūsu bāze gadījums. 

Tātad, pieņemsim to apskatīt to, un kā tas varētu darboties. Tātad, šeit ir mūsu sarakstā, tas ir tas pats uzskaitīt mēs bijām tikai runā par, un tur ir soļi. Tur ir daudz tekstu šeit, bet cerams, ka vizualizācija palīdzēs. 

Tātad mēs have-- un es arī velk up mūsu kaudze rāmji ilustrācija no mūsu video zvanu skursteņi, un cerams, ka tas viss kopā jums parādīs to, kas notiek. Tātad, šeit ir mūsu pseudocode kods. Ja mēs sasniedzam null rādītājs, stop, pretējā gadījumā, izdzēst pārējā saraksta tad bez pašreizējo mezglā. Tāpēc tieši tagad, list-- rādītājs, ka mēs esam iet, lai iznīcinātu punktus 12. 12 nav spēkā rādītājs, tāpēc mēs esam gatavojas dzēst pārējo saraksta. 

Kas ir izdzēšot mums pārējiem iesaistīti? Nu, tas nozīmē, padarot zvanīt, lai iznīcinātu, sakot ka 15 ir sākums pārējā saraksta mēs vēlamies, lai iznīcinātu. Un tā aicinājums iznīcināt 12 ir veida aizturēts. Tas ir iesaldēti tur, gaida zvanīt, lai iznīcinātu 15, lai pabeigtu savu darbu. 

Nu, 15 nav spēkā rādītājs, un tā tas notiek, lai teikt, labi, labi, dzēst pārējo saraksta. No saraksta pārējais sākas 9, un tāpēc mēs vienkārši gaidīt, kamēr jūs izdzēst visu, kas sīkumi, pēc tam nāk atpakaļ un dzēst mani. Nu 9 gatavojas teikt, labi, Es neesmu Null rādītājs, lai dzēstu pārējo sarakstu no šejienes. Un tā mēģinātu iznīcināt 13. 13 saka, es neesmu null rādītājs, tas pats, tas iet buks. 10 nav spēkā rādītājs, 10 satur Null rādītāju, bet 10 ir pati nav null rādītāju tieši tagad, un tā tas iet buks too. 

Un tagad uzskaitīt punktus tur, to tiešām norāda uz some-- ja man būtu vairāk vietas attēlā, tas norāda uz kādu izlases vietu ka mēs nezinām, kas tas ir. Tas ir null rādītājs gan, saraksts ir burtiski tagad ir noteikts tā vērtības Null. Tas norāda tieši no šī sarkanā kastē. Mēs sasnieguši null rādītāju, tāpēc mēs varam apturēt, un mēs esam darījuši. 

Un tā, ka purpursarkana rāmis ir now-- pie top stack-- kas ir aktīvā rāmis, bet tas ir darīts. Ja mēs esam sasnieguši null rādītāju, apstāties. Mēs nedarām neko, mēs nevar atbrīvoties Null rādītāju, mēs neesam malloc jebkurš telpu, un tāpēc mēs esam darījuši. Tātad šī funkcija rāmis tiek iznīcināta, un mēs resume-- mēs uzņemt kur mēs pa kreisi off ar nākamo augstāko vienu, kas tas ir tumši zils rāmis šeit. Tāpēc mēs uzņemt tieši tur, kur mēs left off. Mēs svītrots pārējā saraksts jau, tāpēc tagad mēs esam gatavojas atbrīvot pašreizējās mezgliem. Tāpēc tagad mēs varam atbrīvot šo mezglu, un tagad mēs esam sasnieguši funkciju. Un tā, ka funkcija rāmis ir iznīcināta, un mēs uzņemt pie gaiši zilu. 

Tātad tas says-- es esmu jau done-- svītrojot pārējo saraksta, tāpēc atbrīvotu pašreizējo mezglā. Un tagad dzeltens rāmis ir atpakaļ uz augšu kaudze. Un tā kā jūs redzat, mēs esam tagad iznīcinot sarakstu no labās uz kreiso pusi. 

Kas būtu noticis, lai gan, ja mēs būtu darījuši lietas nepareizi? Tāpat kā tad, kad mēs mēģinājām pievienot elementu. Ja mēs messed up ķēdi, ja mēs neesam savienot norādes pareizā secībā, ja mēs tikai atbrīvoja pirmo elementu, ja mēs vienkārši viņus atlaida vadītājs saraksta, tagad mēs nav veids, kā atsaukties uz pārējā sarakstā. Un tā mēs būtu bāreņiem viss, mēs būtu to, kas ir sauc par atmiņas noplūde. Ja jūs atceraties no mūsu video uz dinamisku atmiņas sadalījumu, tas nav ļoti laba lieta. 

Tā kā es teicu, ka Ir vairākas operācijas ka mums ir nepieciešams izmantot, lai strādātu ar saistīts saraksts efektīvi. Un jums var būt ievērojuši, es izlaist vienu, izdzēšot vienu elementu no saistītais saraksts. Iemesls, kāpēc es to izdarīju tas ir faktiski sava veida grūts domāt par to, kā izdzēst viens elements no A atsevišķi saistīts saraksts. Mums ir nepieciešams, lai varētu izlaist kaut kas sarakstā, kas nozīmē, ka mēs nokļūt point-- mēs vēlies dzēst šo node-- bet, lai padarītu to, lai mēs nezaudē nekādu informāciju, mums ir nepieciešams, lai savienotu šo mezglu nekā šeit, šeit. 

Tāpēc es droši vien bija, ka nepareizi no vizuālā viedokļa. Tātad mēs esam sākumā mūsu saraksts, mēs esam visnotaļ cauri, mēs vēlamies, lai izdzēstu šo mezglu. Ja mēs vienkārši izdzēst to, mēs esam sadalīti ķēdi. Šis mezgls tieši šeit attiecas uz visu citu, tas satur ķēdi no šejienes uz out. 

Tātad, kas mums jādara, faktiski kad mēs nokļūt uz šo punktu, ir mums soli atpakaļ vienu, un savienot šo mezglu pār šo mezglu, lai mēs varētu pēc tam izdzēsiet viens vidū. Bet atsevišķi saistīti saraksti nav sniedz mums ceļš ejams atpakaļ. Tāpēc mums ir nepieciešams paturēt divas norādes, un pārvietot tos veida off soli, viens aiz cits, kā mums iet, vai nokļūt līdz punktam un pēc tam nosūtīt citu rādītāju cauri. Un, kā jūs varat redzēt, tas var iegūt mazliet netīrs. Par laimi, mums ir vēl viens veids, kā atrisināt ka, kad mēs runājam par divkārt saistītas sarakstiem. 

Es esmu Doug Lloyd, tas ir CS50.