[Muziek] DOUG LLOYD: Oké. Dus als je net klaar met dat video op enkelvoudig gelinkte lijsten spijt Ik liet je af op een beetje een cliffhanger. Maar ik ben blij dat je hier bent om te voltooien het verhaal van de dubbel-gelinkte lijsten. 

Dus als je te herinneren van die video, we praatten hoe enkelvoudig gebonden takenlijsten wonen ons vermogen te behandelen informatie waarbij het aantal elementen of het aantal items in een lijst kan groeien of krimpen. We kunnen nu behandelen iets dergelijks, waarbij We konden niet omgaan met arrays. 

Maar ze last hebben van een kritieke beperking die is dat met een enkelvoudig verbonden lijst, kunnen we alleen maar verplaatsen in één richting door de lijst. De enige situatie wanneer dat een probleem kan worden was toen we probeerden te verwijderen van een enkel element. En we hebben niet eens bespreken hoe dit te doen in een enkelvoudig gelinkte lijst in pseudocode. Het is zeker goed te doen, maar het kan een beetje een gedoe. Dus als je jezelf in een situatie waarin je probeert te verwijderen enkele elementen uit de lijst of het gaat om verplicht dat u zult verwijderen enkele elementen uit de lijst, wil je misschien te overwegen het gebruik van een dubbel-linked lijst in plaats van een enkelvoudig gelinkte lijst. Omdat de dubbel-gelinkte lijsten toestaan om voorwaarts en achterwaarts verplaatsen door de lijst in plaats van alleen vooruit door de list-- alleen door het toevoegen van een extra element onze structuurdefinitie voor de dubbel-gelinkte lijst node. 

Nogmaals, als je niet van plan om enkele elementen te verwijderen van de list-- omdat we voegen een extra veld om onze structuur definition, de knopen zelf voor dubbel-gelinkte lijsten zullen groter zijn. Ze gaan nemen up meer bytes geheugen. En dus als dit is niet iets je gaat moeten doen, je zou kunnen besluiten dat het niet de moeite waard de handel korting te hebben om de extra te besteden bytes van het geheugen vereist voor een dubbel-gelinkte lijst als je niet zal worden te verwijderen losse elementen. Maar ze zijn ook cool voor andere dingen ook. 

Dus zoals ik al zei, we moeten gewoon toe te voegen een enkel veld in onze structuur definition-- dit begrip van een Vorige pointer. Dus met een enkelvoudig gelinkte lijst, we de waarde en de Next wijzer, zodat de dubbel-gelinkte lijst heeft net een manier om terug te keren ook. 

Nu in het enkelvoudig gekoppelde lijst video, we praatten over deze vijf van de belangrijkste dingen die je moet kunnen doen om te werken met gekoppelde lijsten. En voor de meeste van deze, het feit dat het een dubbel-gelinkte lijst is niet echt een grote sprong. We kunnen nog steeds door middel van zoeken op net vooruit van begin tot eind. We kunnen nog steeds het creëren van een knooppunt uit ijle lucht, vrijwel op dezelfde manier. We kunnen lijsten behoorlijk verwijderen veel op dezelfde manier ook. De enige dingen die zijn subtiele verschillen, echt, invoegt nieuwe knooppunten in de lijst, en we zullen eindelijk praten over het verwijderen een enkel element van de lijst ook. Nogmaals, vrij veel de andere drie zijn we niet van plan om te praten over hen nu omdat ze gewoon zeer kleine aanpassingen op de ideeën besproken in het enkelvoudig gelinkte lijst video. 

Dus laten plaatst u een nieuw knooppunt in een dubbel-gelinkte lijst. We spraken over dit voor het doen enkelvoudig gelinkte lijsten als goed, maar er zijn een paar extra vangt met dubbel-gelinkte lijsten. We zijn [? passeren?] in de kop van de hier op te noemen en een aantal willekeurige waarde, en we willen het nieuwe hoofd krijgen van de lijst van deze functie. Dat is waarom het geeft een dllnode ster. Dus wat zijn de stappen? Ze zijn weer vergelijkbaar naar enkelvoudig-gekoppelde lijsten met een extra toevoeging. Wij willen ruimte toewijst voor een nieuwe knooppunt en controleren om ervoor te zorgen dat het geldig is. We willen dat knooppunt vullen met alle informatie die we wil in te zetten. Het laatste wat we moeten de doen-- extra wat we moeten doen, rather-- is om de vorige pointer fix van de oude kop van de lijst. Vergeet niet dat, omdat van dubbel gelinkte lijsten, kunnen we vooruit en backwards-- die betekent dat elk knooppunt in feite wijst twee andere knooppunten in plaats van slechts één. En dus moeten we op te lossen de oude kop van de lijst om terug te verwijzen naar het nieuwe hoofd van de gelinkte lijst, waarin iets was we hoefden niet te doen voordat. En als voorheen, we gewoon terug een Pointer naar het nieuwe hoofd van de lijst. 

Dus hier is een lijst. We willen invoegen 12 in deze lijst. Merk op dat het diagram is iets anders. Elk knooppunt drie fields-- bevat data, en de Next wijzer in het rood, en een Vorige pointer in blauw. Niets komt voor de 15-knooppunt, zodat de vorige pointer nul. Het is het begin van de lijst. Er is niets voor het. En niets komt na de 10 knooppunt, en dus het is Volgende pointer nul ook. 

Dus laten we toe 12 aan deze lijst. We moeten [onverstaanbaar] ruimte voor het knooppunt. We zetten 12 binnenkant van het. En nogmaals, we moeten echt Pas op dat u de ketting te breken. We willen het herschikken wijzers in de juiste volgorde. En soms is dat misschien mean-- zoals we in het bijzonder zullen zien met delete-- dat we hebben een aantal redundant pointers, maar dat is OK. 

Dus wat willen we eerst doen? Ik zou aanraden het Dingen die je moet waarschijnlijk doen zijn om de wijzers van de 12 te vullen knooppunt voordat u aanraakt iemand anders. Dus wat is 12 gaan naar de volgende wijzen? 15. Wat komt voor 12? Niets. Nu hebben we vulden de extra informatie in 12 dus het heeft Vorige, Volgende, en waarde. 

Nu kunnen we 15-- dit extra stap die we kregen about-- we praten kan 15 punt terug tot 12 hebben. En nu kunnen we het hoofd van bewegen de gekoppelde lijst met eveneens 12. Dus het is vrij vergelijkbaar met wat we deden met enkelvoudig gelinkte lijsten, met uitzondering van de extra stap van het aansluiten van de oude kop van de lijst terug naar het nieuwe hoofd van de lijst. 

Laten we nu eens eindelijk verwijderen een knooppunt van een gekoppelde lijst. Dus laten we zeggen dat we hebben een andere functie die is het vinden van een knooppunt we willen verwijderen en heeft ons een aanwijzing gegeven om precies te het knooppunt dat we willen verwijderen. We weten niet eens need-- zeggen dat de hoofd is nog steeds wereldwijd verklaard. We hebben het hoofd hier niet nodig. Alle deze functie doet is we hebben vond een pointer precies knooppunt we wil om zich te ontdoen van te krijgen. Laten we van af. Het is een stuk makkelijker met dubbel-gelinkte lijsten. First-- het is eigenlijk slechts een paar dingen. We hoeven alleen maar te bevestigen de omringende pointers nodes ', zodat ze over te slaan het knooppunt we willen verwijderen. En dan kunnen we dat knooppunt te verwijderen. Dus nogmaals, we gewoon door hier. We hebben blijkbaar besloten we willen het knooppunt X. schrappen En nogmaals, wat ik ben doet hier-- door de way-- is een algemeen geval voor een knooppunt, dat is in het midden. Er zijn een paar van extra waarschuwingen dat u moet overwegen wanneer u het verwijderen het begin van de lijst of het einde van de lijst. Er zijn een paar van de speciale grensgevallen te behandelen zijn. 

Dus dit werkt voor het verwijderen van elk knooppunt in het midden van de list-- die heeft een legitieme pointer vooruit en een legitieme wijzer achteruit, legitieme vorige en volgende pointer. Nogmaals, als je werkt met de uiteinden, u moeten die verwerken iets anders, en we zijn niet van plan om over praten nu. Maar je kan waarschijnlijk erachter te komen wat er moet gewoon gedaan worden door te kijken naar deze video. 

Dus we hebben geïsoleerd X. X is het knooppunt we willen verwijderen uit de lijst. Wat doen we? Eerst moeten we te herschikken buiten pointers. We moeten herschikken 9's volgende over te slaan 13 en wijzen op 10-- die is wat we net hebben gedaan. En we moeten ook herschikken 10's Vorige te wijzen op 9 in plaats van naar een 13. 

Dus nogmaals, dit was de diagram te beginnen. Dit was onze keten. We moeten overslaan 13, maar we moeten ook behouden de integriteit van de lijst. We willen niet elke verliezen informatie in beide richtingen. Dus moeten we herschikken de wijzers zorgvuldig zodat we niet de ketting breekt helemaal. 

Dus we kunnen 9's Next wijzer zeggen naar dezelfde plaats dat dertien's Next pointer wijst nu. Omdat we uiteindelijk gaat te willen overslaan 13. Dus waar 13 punten naast u wil negen wijzen er in plaats. Dus dat is dat. En dan waar 13 punten terug aan, wat komt vóór 13, we willen 10 wijzen dat in plaats van 13. Nu merken, als je de volgende de pijlen, kunnen we laten vallen 13 zonder enige informatie daadwerkelijk te verliezen. We hebben de integriteit van de lijst gehouden, bewegen zowel vooruit als achteruit. En dan kunnen we gewoon soort van opruimen een beetje door samen te trekken van de lijst. Dus we herschikt de wijzers aan beide zijden. En dan hebben we bevrijd van de X knooppunt 13 bevatte, en we niet breken de keten. Dus hebben we goed. 

Laatste opmerking hier op gelinkte lijsten. Dus zowel singly- en dubbel-linked lijsten, zoals we hebben gezien, ondersteuning echt efficiënt inbrengen en verwijderen van elementen. U kunt vrij veel doen in constante tijd. Wat hebben we moeten doen om te verwijderen een element slechts een seconde geleden? Verhuisden we een pointer. We verhuisden een andere pointer. We bevrijd x-- duurde drie operaties. Het duurt altijd drie operaties aan dat node-- verwijderen om een ​​knoop te bevrijden. 

Hoe kunnen we voegen? Nou, we zijn gewoon altijd hechten aan het begin als we efficiënt inbrengen. Dus moeten we rearrange-- afhankelijk van of het een singly- of dubbel-linked lijst, zouden we moeten doen drie of vier operaties max. Maar nogmaals, het is altijd drie of vier. Het maakt niet uit hoeveel elementen zijn in onze lijst, het is altijd drie of vier operations-- net zoals verwijdering is altijd drie of vier operaties. Het is een constante tijd. Dus dat is echt geweldig. 

Met arrays, we deden zoiets als insertion sort. Herinnert u zich waarschijnlijk dat het inbrengen sorteren is geen constante tijd algoritme. Het is eigenlijk vrij duur. Dus dit is veel beter voor invoegen. Maar zoals ik in de genoemde enkelvoudig gelinkte lijst video, we hebben ook een keerzijde hebben hier ook, toch? We hebben de mogelijkheid om verloren willekeurige toegang elementen. We kunnen niet zeggen, ik wil element nummer vier of element nummer 10 van een gekoppelde lijst Net zoals we kunnen die met een array of we kunnen gewoon rechtstreeks index element in ons aanbod is. 

En zo proberen om een ​​te vinden element in een gekoppelde list-- Als zoeken is important-- kan nu nemen lineaire tijd. Aangezien de lijst wordt langer het misschien een extra stap te zetten voor elk element in de lijst Om te vinden wat we zoeken. Dus er is de handel offs. Er is een beetje een pro en con element hier. 

En dubbel-gelinkte lijsten zijn niet de laatste soort gegevens structuur combinatie dat we praten over, het nemen van alle fundamentele gebouw blokken van C een samenstellen. Want in feite, kunnen we zelfs beter dan dit een data structuur te creëren dat je zou in staat zijn om door middel van in constante tijd ook. Maar meer daarover in een andere video. 

Ik ben Doug Lloyd. Dit is CS50.