>> [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.