[Zenelejátszási] DOUG LLOYD: Rendben. Tehát, ha éppen befejezte, hogy video egyszeres kapcsolt listák sajnálom Hagytam ki egy Kicsit filmsorozat. De örülök, hogy itt vagy, hogy befejezze A történet a kétszeresen láncolt listák. 

Tehát, ha visszahívja hogy a videó, beszélgettünk hogyan egyszeres kapcsolt listák nem vesz részt a képességünket, foglalkozni információk ahol az elemek száma vagy az elemek számát listáját nőhet, vagy zsugorodik. Most már foglalkozni valami ilyesmi, ahol nem tudtunk foglalkozni vele tömbök. 

De ők szenvednek az egyik kritikus határértéket, amelyet az, hogy egy egyszeresen-kapcsolt lista, csak akkor tudjuk mozgatni valaha egy irányban végig a listát. És az egyetlen valós helyzetet ha ez a probléma lehet volt, amikor megpróbáltunk törölni egy elemet. És akkor még nem is megvitassák, hogyan kell csinálni egy egyszeres láncolt lista pszeudokód. Ez minden bizonnyal megvalósítható, de ez lehet egy kis szóváltás. Tehát, ha találsz magadnak egy olyan helyzetben, ahol a akarsz törölni Egyetlen elemet a listából vagy ez lesz szükség hogy akkor kell törölni Egyetlen elemek A lista, érdemes hogy fontolják meg egy kétszeresen kötött lista helyett egy egyszeresen láncolt listával. Mivel kétszeresen láncolt listák segítségével mozogni előre és hátra Ha a listában helyett Csak előre a list-- Csak úgy, hogy egy kiegészítő elemet hogy mi szerkezete meghatározása a kétszeresen láncolt lista csomópontot. 

Ismét, ha nem fogod törlésével egyes elemeinek A list-- mert mi hozzátéve extra mezőt szerkezetünk meghatározás, a csomópontok maguk A kétszeresen láncolt listák lesznek nagyobbak. Ők fognak venni több bájt memóriát. És így, ha ez nem olyasmi fogsz kell tennie, úgy is dönthet, hogy Nem éri meg a kompromisszum hogy kell költeni az extra bájt memória szükséges Egy kétszeresen láncolt lista, ha nem lesz törlésével egyes elemek. De ők is hűvös más dolgokat is. 

Tehát mint mondtam, csak kell hozzá egyetlen mezőt szerkezetünk definition-- ezt a fogalmat Egy Előző mutató. Tehát egy egyszeres láncolt lista, mi az értéke, és a hátralévő mutatót, így a kétszeresen láncolt lista csak meg olyan módon, hogy a hátra is. 

Most az egyszeresen kötött lista video, beszélgettünk körülbelül ezek az öt legfontosabb dolog, meg kell, hogy képes megtenni dolgozni láncolt listák. És a legtöbb ilyen, az a tény, hogy ez egy kétszeresen láncolt lista nem igazán nagy ugrás. Még mindig keresgélni, egyszerűen halad előre az elejétől a végéig. Még mindig hozzon létre egy csomópont ki semmiből, nagyjából ugyanúgy. Mi lehet törölni listákat, elég ugyanúgy túl. Az egyetlen dolog, ami a finoman más, Tényleg, illeszt új csomópontokat a listából, és mi végre beszélni törlése egyetlen elem a listából is. Ismét nagyon sok A másik három vagyunk Nem fog beszélni róluk most, mert ők csak Nagyon kisebb csíp a tárgyalt javaslatokra A külön-külön kötött lista videót. 

Úgyhogy be egy új csomópont egy kétszeresen láncolt listával. Beszéltünk csinálom ezt egyszeres kapcsolt listák is, de van egy-két extra elkapja a kétszeresen láncolt listák. Mi vagyunk [? halad?] a fejét a felsorolni és néhány tetszőleges értéket, és azt akarjuk, hogy az új vezetője A lista ki ezt a funkciót. Ez miért ad vissza dllnode csillag. Tehát mi a lépések? Ezek, ismét nagyon hasonló hogy egyszeres láncolt listák egy extra felül. Azt akarjuk, hogy foglalja le a helyet az új csomópontot, és győződjön meg róla, hogy érvényes-e. Azt akarjuk, hogy töltse ki, hogy node-ig mindazt az információt, amit kívánja helyezni azt. Az utolsó dolog, amit meg kell do-- a extra dolog, amit tennie kell, rather-- meg kell határoznia Előző mutatót A régi lista élére. Ne feledje, hogy azért, mert A kétszeresen láncolt listák, tudunk előrelépni és backwards-- amely azt jelenti, hogy minden csomópont valóban emlékeztet a másik két csomópont helyett csak egy. És így kell rögzíteni A régi lista élére hogy pont hátra az új vezetője A listába, ami valami nem kellett tennie, mielőtt. És mint korábban, csak vissza mutatót a lista élére. 

Tehát itt egy lista. Azt akarjuk, hogy helyezze be a 12. a listán. Figyeljük meg, hogy a rajz kicsit más. Minden csomópont három fields-- adatokat, és egy Következő mutató piros, és az előző mutató kék. Semmi nem jön, mielőtt a 15 csomópont, így a korábbi mutató null. Ez a lista elején. Semmi sem előtte. És semmi nem jön, miután a 10 csomópontot, így Következő mutató null is. 

Tehát tegyük hozzá 12 ehhez a listához. Szükségünk [hallhatatlan] helyet a csomópontot. Azt hogy 12 belsejébe. És akkor megint, mi kell igazán Vigyázzon, hogy ne megtörni a láncot. Azt akarjuk, hogy átrendezéséhez mutatók a megfelelő sorrendben. És néha, hogy talán értem-- mint látni fogjuk, különösen A delete--, hogy mi van néhány redundáns mutatók, de ez rendben van. 

Szóval mit akarunk csinálni először? Azt ajánlom a dolgok akkor valószínűleg nem kell kitölteni a mutató a 12 node, mielőtt megérintené bárki más. Tehát mi 12 fog mutatni a következő lépés? 15. Mi jön 12-e előtt? Semmi. Most már betöltötte a Extra információk 12 ezért az előző, következő, és az érték. 

Most mi lehet 15-- ezt a plusz lépésben beszéltünk about-- vagyunk lehet 15 pontot vissza 12. És most már tudjuk mozgatni a fejét A listába, hogy szintén 12. Szóval ez elég hasonló ahhoz, amit csinált a egyszeres láncolt listák, kivéve a további lépést, a összekötő régi lista élére vissza az új lista élére. 

Most végre törölni Egy csomópont egy láncolt lista. Tehát mondjuk van Néhány más, megtalálni egy csomópont akarunk törölni és adott nekünk egy mutatót pontosan A csomópont, hogy szeretnénk törölni. Még csak nem is need-- mondani a feje még mindig globálisan deklarált. Nem kell a fejét itt. Minden ezt a funkciót tesz, mi már Találtam egy mutatót pontosan csúcsba akar megszabadulni. Nézzük megszabadulni tőle. Ez egy sokkal könnyebb kétszeresen láncolt listák. First-- ez valójában csak egy pár dolgot. Csak meg kell kijavítani a környező csomópontok "mutatókat úgy, hogy átugorják A csomópont akarunk törölni. És akkor törölheti a csomóponton. Tehát újra, csak most megy keresztül itt. Mi már nyilvánvalóan úgy döntött, hogy akarjuk törölni a csomópont X. És ismét, milyen vagyok Ennek here-- a way-- Általános esetben egy csomóponton, amely a közepén. Van egy pár extra kikötéssel, hogy kell szem előtt tartania törlése A legelején a listát vagy a legvégén a lista. Van egy pár speciális sarok megoldandó eset van. 

Így működik ez a megsemmisítését csomópont a közepén a list-- egyik, hogy jogos mutatót előre és jogos mutató hátra, jogos Előző és Következő mutatót. Ismét ha dolgozik A végén, akkor kell kezelni azokat kicsit másképp, és mi nem fogunk beszélni, hogy most. De akkor talán kitalálni, mit kell meg kell tenni csak nézi ezt a videót. 

Így már elszigetelt X. X a csomópont szeretnénk törölni a listáról. Mit csináljunk? Először is meg kell átrendezni a külső mutatók. Meg kell átrendezni 9-es melletti átugorják 13 és pont 10-- amely az, amit éppen most történik. És azt is meg kell átrendezheti 10 korábbi hogy pont 9 helyett mutató 13. 

Tehát újra, ez volt az rajz kezdeni. Ez volt a lánc. Meg kell, hogy átugorja a 13, de meg kell is megőrizheti a integritását a listán. Nem akarjuk elveszíteni bármilyen információ mindkét irányban. Tehát meg kell átrendezni A mutatók gondosan így nem megtörni a láncot egyáltalán. 

Így elmondhatjuk, 9 Next mutató rámutat, hogy ugyanazon a helyen A tizenhárom Next mutató most. Mert mi vagyunk végül szeretne majd átugorják 13. Így bárhol 13 pont következő, akkor szeretnénk kilenc pontra van helyette. Szóval ennyi. És akkor bárhol 13 pont vissza az, bármi is jön, mielőtt 13, akarunk 10 pontra hogy hogy ahelyett, hogy 13. Most észre, ha követi A nyilak, levehetjük 13 anélkül, hogy elveszítené minden információt. Úgy írtuk meg a integritását a listán, mozgó előre és hátra. És akkor mi is csak amolyan A tiszta fel egy kicsit húzva a listáról össze. Tehát átrendezték a pointerek mindkét oldalán. És akkor felszabadul X a csomópont, amely tartalmazott 13, és mi nem megtörni a láncot. Szóval mi a jó. 

Utolsó megjegyzés itt láncolt listák. Így mindkét singly- és kétszeresen kötött listákat, mint láttuk, támogatást valóban hatékony beillesztés és törlésére vonatkozó elemeket. Akkor elég sok ez állandó időt. Mit kell tennünk, hogy törölje egy elem csak egy perce? Azért költöztünk egy mutatóval. Elköltöztünk egy másik mutatót. Mi szabadult X- vett három művelet. Mindig úgy három műveletek törölni, hogy node-- kiszabadítani egy csomópont. 

Hogyan írjunk? Nos, mi csak mindig tacking a kezdet ha már behelyezése hatékonyan. Tehát meg kell rearrange-- attól függően, hogy ha ez Egy singly- vagy kétszeresen kötött listáját, szükségünk lehet, hogy nem három vagy négy műveletek max. De ismétlem, ez mindig három vagy négy. Nem számít, hogy hány elemek vannak a listán, ez mindig három-négy operations-- mint törlés mindig három vagy négy műveletet. Ez folyamatos időben. Szóval ez tényleg jó. 

A tömbök, csinálunk valami, mint az elhelyezési sorrend. Valószínűleg emlékeztetni arra, hogy behelyezés A rendezés nem állandó algoritmust. Valójában nagyon drága. Tehát ez egy sokkal jobb behelyezésére. De ahogy már említettem az egyszeres láncolt lista video, megvan a hátránya is itt, igaz? Elvesztettük a képességét, hogy véletlenszerűen elemeinek elérésére. Nem mondhatjuk, szeretnék eleme a négyes vagy elem száma 10 egy láncolt lista Ugyanúgy, ahogy csak tudunk Ehhez egy sor vagy mi csak közvetlenül index a mi tömb eleme. 

És így próbál találni eleme a kapcsolódó list-- Ha keresés important-- Most már a lineáris idő. Mivel a lista egyre hosszabb, akkor Lehet, hogy egy további lépés minden egyes eleme a lista annak érdekében, hogy megtalálja, amit keres. Szóval van kompromisszumokra. Van egy kis pro és con eleme van. 

És kétszeresen kapcsolt listák nem az Utolsó féle adat struktúra kombinációja hogy fogunk beszélni, figyelembe az összes alapvető építési blokkok C egy összerakva. Mert valójában tudjuk még jobban, mint ez a hogy hozzon létre egy adatstruktúrát, amely akkor lehet, hogy keresni állandó időt is. De még az, hogy egy másik videó. 

Én Doug Lloyd. Ez CS50.