[Muusika mängib] DOUG LLOYD: Okei. Nii et kui sa just lõpetasin selle video üksikult seotud nimekirju kahju Jätsin sulle välja lülitada natuke pinge. Aga ma olen rõõmus, et sa siin oled lõpetada lugu kahekordselt seotud nimekirju. 

Nii et kui te mäletate et video, me rääkisime kuidas üksikult seotud nimekirju teha osaleda meie võime tegelema teavet kus elementide arv või üksuste arv nimekirja võib kasvada või väheneda. Nüüd on võimalik tegeleda midagi sellist, kus me ei suutnud toime tulla massiivid. 

Aga nad ei kannata üks kriitiline piirangud, mis on, et koos ühe--aheldatud nimekirja, saame ainult kunagi liikuma ühes suunas läbi nimekirja. Ja ainus olukord kus see võib muutuda probleemiks oli, kui me püüdsime kustutada ühe elemendi. Ja me isegi ei arutada, kuidas seda teha on üksikult seotud nimekiri pseudokoodi. Kindlasti on sooritatav, kuid see võib olla veidi vaeva. Nii et kui sa leiad end olukorras, kus üritad kustutada üksikute elementide loendist või siis läheb vaja et saad kustutamine ühe elemendid nimekirja, võiksite kaaluda kahekordselt seotud nimekirja asemel üksikult seotud nimekirja. Kuna kahekordselt ahelloendid võimaldab teil liikuda nii edasi ja tagasi läbi nimekirja asemel lihtsalt edasi läbi list-- lihtsalt lisades ühe lisaelemendi meie struktuuri määratlemine eest kahekordselt seotud nimekirja sõlme. 

Jällegi, kui te ei kavatse kustutate ühe elemendid alates list-- sest me lisame Lisatasu valdkonnas meie struktuur määratlus, sõlmed ise eest kahekordselt ahelloendid hakkavad olema suuremad. Nad läheme rohkem baiti mälu. Ja kui see ei ole midagi sa lähed pead tegema, võite otsustada see on ei ole väärt kompromiss saada kulutama rohkem baiti vajatava mälu jaoks kahekordselt seotud nimekirja, kui sa ei ole hakatakse kustutamine ühe elemendid. Aga nad on ka lahe muid asju ka. 

Nii nagu ma ütlesin, me lihtsalt lisada ühe valdkonna oma struktuuri definition-- seda mõistet eelmise pointer. Nii ühekaupa seotud nimekirja, meil on väärtus ja Järgmine pointer, nii kahekordselt ahelloendid lihtsalt on viis liikuda tahapoole samuti. 

Nüüd üksikult seotud nimekirja video, me rääkisime umbes need viis Peamised asjad, mida tuleb võimeline tegema tööd ahelloendid. Ja enamik neist on asjaolu, et see on kahekordselt seotud nimekirja ei ole tõesti suur hüpe. Me saame ikka otsida lihtsalt edasiliikumist algusest lõpuni. Me saame veel luua sõlme välja õhuke õhk, päris palju sama moodi. Me ei kustuta nimekirjad päris samamoodi ka. Ainsad asjad, mis on delikaatselt erinevad, tõesti, on lisada uued tipud nimistusse, ja me lõpuks rääkida kustutamine üksikelemendi nimekirjast samuti. Jällegi päris palju Ülejäänud kolm, me oleme ei kavatse rääkida neist just nüüd, sest nad lihtsalt väga Pisimuudatused arutatud ideesid ka üksikult seotud nimekirja video. 

Nii saab paigaldada uue tipu arvesse kahekordselt seotud nimekirja. Me rääkisime seda teed üksikult seotud nimekirjad samuti, kuid seal on paar extra saagi koos topelt-ahelloendid. Oleme [? kulgeb?] in juht siin loetleda mõned suvalise väärtuse, ja me tahame saada uue juhi nimekirja läbi selle funktsiooni. Sellepärast tagastab dllnode star. Millised on sammud? Nad on jällegi väga sarnased to üksikult seotud nimekirjad ühe ekstra lisaks. Me tahame, et eraldab ruumi uuele sõlme ja veenduge, et see on õige. Tahame täita, et sõlm üles mis tahes teavet me tahan panna seda. Viimane asi, mida me peame do-- Täiendava asi, mida me peame tegema, rather-- on määrata Eelmine pointer vana juht nimekirja. Pea meeles, et kuna on kahekordselt ahelloendid, saame edasi liikuda ja backwards-- mis tähendab, et iga sõlm tegelikult juhib kahele muude sõlmede ühe asemel. Ja nii on meil vaja määrata vana juht nimekirja punkti tahapoole uue juhi lingitud nimekirja, mis oli midagi me ei pea tegema enne. Ja nagu enne, me lihtsalt tagastada kursor uus juht nimekirja. 

Nii et siin on nimekiri. Me tahame, et lisada 12 sellesse nimekirja. Pange tähele, et skeem on veidi erinev. Iga sõlm sisaldab kolme fields-- andmed ja Järgmine kursor punaseks, ja Eelmine kursorit sinine. Miski ei tule enne 15 sõlme, nii oma Eelmine osuti on null. See on loendi alguses. Ei ole midagi enne seda. Ja midagi tuleb pärast 10 sõlme ja nii et see on Järgmine osuti on null samuti. 

Lisame 12. sellesse nimekirja. Me vajame [kuuldamatu] ruumi sõlme. Panime 12 sees on. Ja siis jälle, me peame olema väga ettevaatlik, et mitte murda kett. Tahame korrastada viiteid õiges järjekorras. Ja mõnikord, et võiks mean-- nagu me näeme eriti koos delete-- et meil on mõned koondatud suunanäitajaks, kuid see on OK. 

Mida me tahame teha esimesena? Ma soovitaks Asjad, mida peaks ilmselt teha on täita suunanäitajaks 12 sõlme, enne kui puudutada kedagi teist. Mis on 12 kavatse osutavad edasi? 15. Mis tuleb enne 12? Mitte midagi. Nüüd oleme täitnud Täiendava info 12 nii et see on Eelmine, Järgmine väärtus. 

Nüüd saame olla 15-- see extra samm rääkisime about-- me võib olla 15 punkti tagasi 12. Ja nüüd me saame liikuda juht lingitud nimekirja ka 12. Nii et see on üsna sarnane sellega, mida me tegid koos üksikult seotud nimekirju, välja arvatud ekstra sammu ühendavad vana juht nimekirja tagasi uue juhi nimekirja. 

Nüüd lõpuks kustutada sõlm on ahelloend. Ütleme, et meil on mõne muu funktsiooni, mis on leida sõlme tahame kustutada ja andnud meile viit täpselt sõlme, et me tahame kustutada. Me isegi ei need-- öelda Pea on ikka maailmas kuulutatud. Me ei pea pea siin. Kõik see funktsioon teeb on me oleme leitud kursor täpselt sõlme me tahad lahti saada. Olgem lahti saada. See on palju lihtsam kahekordselt seotud nimekirju. First-- see on tegelikult vaid paar asja. Me lihtsalt vaja parandada ümbritsevat sõlmed "viiteid, et nad vahele üle sõlme tahame kustutada. Ja siis saame kustutada selle sõlme. Nii jälle, me lihtsalt läbimas siin. Meil on ilmselt otsustanud, et tahame kustutada sõlme X. Ja jälle, mida ma olen teeme siin-- poolt way-- Üldiselt on see siis, kui sõlm, mis on keset. Seal on paar Täiendava vastuväiteid, mida sa on vaja kaaluda, kui sa kustutamine Algusest nimekirja või väga loendi lõppu. Seal on paar erilist nurgas juhtudel tegeleda seal. 

Nii käib see kustutamist sõlme keskel on list-- mis on õigustatud kursorit edasi ja õigustatud pointer tahapoole, õigustatud Eelmine ja Järgmine pointer. Jällegi, kui te töötate otstega, siis pead hakkama neid veidi erinevalt, ja me ei kavatse rääkida, et nüüd. Aga sa võid ilmselt aru saada, mis vajab tuleb teha lihtsalt vaadates seda videot. 

Nii oleme isoleeritud X. X on sõlm tahame kustutada loendist. Mida me siis teeme? Esiteks, me peame ümber väljastpoolt suunanäitajaks. Me peame ümber 9 järgmiseks vahele üle 13 ja punkt 10-- mis on see, mida me oleme lihtsalt teha. Ja me peame ka ümber 10 aasta Eelmine punkti 9 asemel osutades 13. 

Nii jälle, see oli diagrammil alustada. See oli meie kett. Me peame vahele üle 13, kuid me peame ka säilitada terviklikkuse nimekirja. Me ei taha kaotada mis tahes andmed ühes või teises suunas. Seega peame ümber vihjeid hoolikalt nii et me ei riku kett üldse. 

Nii võime öelda, 9 järgmiseks pointer juhib samas kohas et kolmteist järgmiseks pointer juhib praegu. Sest me oleme lõpuks lähed tahan vahele üle 13. Nii kõikjal 13 punkti kõrval, siis tahan üheksa punkti seal asemel. Nii et see, et. Ja siis seal, kus 13 punkti tagasi et olenemata tuleb enne 13, tahame 10 punkti selle asemel 13. Nüüd märgata, kui te järgite nooled, me võib langeda 13 ilma tegelikult kaotada mis tahes teavet. Me oleme hoidnud terviklikkuse nimekirja, liikudes nii edasi ja tagasi. Ja siis me saame lihtsalt omamoodi ja puhastan natuke tõmmates nimekirja koos. Nii me paigutas ümber osuti mõlemale küljele. Ja siis me vabanenud X sõlm, mis sisaldas 13 ja me ei kaotanud kett. Nii me tegime hea. 

Lõpetuseks siin ahelloendid. Nii nii singly- ja kahekordselt seotud nimekirjad, nagu me oleme näinud, toetust tõesti tõhus sisestamise ja väljajätmist. Võite päris palju teha see konstantse ajaga. Mida me peame tegema, et kustutada element vaid sekund tagasi? Kolisime üks pointer. Kolisime teise kursorit. Meil vabanes x-ist võttis kolm operatsiooni. See võtab alati kolm toimingud kustutada node-- vaba sõlme. 

Kuidas lisada? Noh, me oleme lihtsalt alati laveerimine alguses kui me sisestamist tõhusalt. Seega peame rearrange-- sõltuvalt sellest, kas see on singly- või kahekordselt seotud nimekirja, meil võib olla vaja teha kolm või neli tegevust max. Aga jälle, see on alati kolm või neli. See ei ole tähtis, kui palju elemendid on meie nimekirjas, see on alati kolm või neli operations-- nagu kustutamine on alati kolm või neli operatsioone. See on pidev aega. Nii see on tõesti suur. 

Mis massiivid, me teeme midagi sisestamise omamoodi. Sa ilmselt meelde tuletada, et sisestamise Sorteeri ei ole pidev algoritm. See on tegelikult päris kallis. Nii et see on palju parem sisestamist. Aga nagu ma mainisin üksikult seotud nimekirja video, meil ka varjukülg ka siin, eks? Me oleme kaotanud võime juhuslikult juurde elemente. Me ei saa öelda, ma tahan element number neli või element number 10 ahelloend Samamoodi, et suudame teha, et massiivi või saame lihtsalt otse indeks meie massiiv on element. 

Ja nii püüab leida element seotud list-- Kui otsing ei important-- võib nüüd võtta lineaarne aeg. Nagu nimekirjast muutub pikemaks, siis võib võtta veel üks samm iga üksiku elemendi nimekiri Selleks, et leida, mida me otsime. Nii et kompromisse. Seal on natuke pro ja con element siin. 

Ja kahekordselt ahelloendid ei ole Viimast liiki andmete struktuuri kombinatsioon et me räägime, võttes kõik põhilised ehitusplokid plokid C puhul koondades. Sest tegelikult suudame isegi parem kui see luua andmestruktuur, et sa võiksid otsida pidevas aega ka. Aga rohkem, et teise video. 

Ma olen Doug Lloyd. See on CS50.