>> [REPRODUCCIÓ DE MÚSICA]
>> DOUG LLOYD: OK, així que al aquest punt en el curs,
hem cobert molts dels conceptes bàsics de la C. Sabem molt sobre variables, matrius,
punters, totes aquestes coses bones.
Aquests són tot tipus de construït per veure com els fonaments,
però podem fer més, no?
Podem combinar coses junts en formes interessants.
>> I així anem a fer això, anem a començar diversificar del que C ens dóna,
i començar a crear les nostres pròpies dades estructures que utilitzen aquests edificis
blocs junts per fer alguna cosa realment valuós, útil.
Una manera de fer-ho és per parlar sobre les col·leccions.
Així que fins ara hem tingut un tipus de dades estructura per representar col·leccions
de rebre els valors, valors similars.
Això seria una matriu.
Disposem de col·leccions de nombres sencers, o col·leccions de personatges i així successivament.
>> Estructures també una mena de dades estructura per a la recopilació d'informació,
però no ho és per recollir com a valors.
En general, es barreja diferents tipus de dades junts dins d'una sola caixa.
Però no és en si utilitzat per encadenar
o connecti juntes similars articles, com una matriu.
Les matrius són grans per element de mirar cap amunt, però el record
que és molt difícil per inserir en una matriu,
llevat que estem inserint en al final d'aquesta matriu.
>> I el millor exemple que té per això és l'ordenació per inserció.
Si vostè recorda el nostre vídeo d'ordenació per inserció,
hi havia una gran quantitat de despeses involucrats en tenir
per recollir elements, i desplaçar-los fora del camí per adaptar-se a alguna cosa
al centre de la seva matriu.
Les matrius també pateixen d'una altra problema, que és la inflexibilitat.
Quan declarem una matriu, tenim una oportunitat en ell.
Hem de dir, vull aquesta quantitat d'elements.
Podria ser 100, podria ser 1000, podria
ser x, on x és un nombre que l'usuari ens va donar en el símbol o en la comanda
la línia.
>> Però només tenim una oportunitat per ella, no arribo a dir a continuació, oh, en realitat jo
necessitava 101, o que necessitava x més 20.
Massa tard, ja hem declarat la matriu, i si volem obtenir 101 o x
més 20, hem de declarar un conjunt completament diferent,
copiar tots els elements de la matriu acabat, i llavors tenim prou.
¿I si ens equivoquem de nou, el que si en realitat necessitem 102, o x més de 40 anys,
hem de fer això de nou.
Així que són molt inflexibles per canviar la mida de les nostres dades,
però si combinem a alguns dels conceptes bàsics que ja hem
après sobre els punters i estructures, en particular, l'ús de memòria dinàmica
assignació amb malloc, que pot posar aquestes peces juntes
per crear un una nova dada structure-- llista podríem dir-- enllaçada
que ens permet créixer i reduir una col·lecció de valors
i no tindrem cap espai perdut.
>> Així que de nou, cridem a aquesta idea, aquesta noció, una llista enllaçada.
En particular, en aquest vídeo estem parlant de llista enllaçada,
i després un altre vídeo parlarem llistes sobre doblement enllaçades, que
és només una variació sobre un tema aquí.
No obstant això, una llista enllaçada es compon de nodes,
nodes només ser un term-- abstracta és només una cosa que estic trucant
això és una mena de estructura, bàsicament, estic?
Només va a trucar a un node-- i això node té dos membres, o dos camps.
Té dades, en general una nombre enter, un flotador caràcter,
o podria ser algun altre tipus de dades que ha definit amb un tipus def.
I conté un punter a un altre node del mateix tipus.
>> Així que tenim dues coses a l'interior de aquest node, les dades i un punter
a un altre node.
I si vostè comença a visualitzar això, es pot pensar-hi
com una cadena de nodes que estan connectats entre si.
Tenim el primer node, conté dades, i un punter
al segon node, que conté de dades, i un punter a la tercera node.
I per això en diem un llista enllaçada, estan units entre si.
>> Què fa aquest especial estructura de nodes sembla?
Bé, si vostè recorda del nostre vídeo en la definició de tipus personalitzats, amb el tipus de definició,
podem definir un structure-- i escrigui definir una estructura com aquesta.
tyepdef struct sllist, i llavors estic utilitzant el valor de la paraula aquí arbitràriament
per indicar qualsevol tipus de dades realment.
Vostè podria passar un sencer o flotant, vostè podria tenir el que vulguis.
No està restringit només sencers, ni res d'això.
Així que el valor és només una arbitrària tipus de dades, i després un punter
a un altre node del mateix tipus.
>> Ara, hi ha una mica de captures aquí amb la definició d'una estructura de
quan és una estructura auto referencial.
He de tenir un temporal nomenar per la meva estructura.
Al final del dia I clarament volen dir-
node sll, que és en última instància, el nou nomenar part de la meva tipus de definició,
però no puc utilitzar el node sll en el medi d'això.
La raó és que no ho he fet creat un node SLL tipus anomenat
fins que vaig arribar a aquest punt final aquí.
Fins a aquest moment, he de tenir una altra manera de referir-se a aquest tipus de dades.
>> I aquest és un acte tipus de dades referencial.
És, és un tipus de dades d'un estructura que conté una dada,
i un punter a un altre estructura del mateix tipus.
Així que he de ser capaç de referir-se a aquest tipus de dades almenys temporalment,
per la qual cosa li dóna un temporal nom del struct sllist
em permet llavors dic que vull un punter a una altra estructura sllist,
un estel struct sllist, i després després d'haver completat la definició,
Ara puc cridar a aquest tipus d'un node sll.
>> Així que per això es veu que hi ha un nom temporal aquí,
sinó un nom permanent aquí.
A vegades és possible que vegi les definicions de l'estructura,
per exemple, que no són acte referencial, que
no tenen un nom especificador aquí.
Simplement diria typedef struct, obrir claudàtor i després definir-lo.
Però si vostè és struct és acte referencial, com aquesta és,
cal especificar un nom de tipus temporal.
Però en última instància, ara que hem fet això,
acabem de fer referència a aquests nodes, aquestes unitats,
com a nodes SLL propòsits de la resta d'aquest vídeo.
>> Molt bé, així que sabem com crear un node de llista enllaçada.
Sabem com definir un node de llista enllaçada.
Ara, si anem a començar usar-les per recopilar informació,
hi ha un parell d'operacions que necessitat d'entendre i treballar amb ells.
Hem de saber com crear una llista enllaçada del no-res.
Si no hi ha cap llista ja, volem començar un.
Així que hem de ser capaços de per crear una llista enllaçada,
hem de probablement buscar a través de la llista d'enllaços
per trobar un element que estem buscant.
Hem de ser capaços d'inserir noves coses a la llista,
volem que la nostra llista per poder créixer.
I de la mateixa manera, volem ser capaços eliminar coses de la nostra llista,
volem que la nostra llista per ser capaç de reduir la mida.
I al final de la nostra programes, especialment
si vostè recorda que som assignació dinàmica de memòria
per construir aquestes llistes normalment, volem alliberar tota la que la memòria
quan hàgim acabat de treballar amb ell.
I així hem de ser capaços d'esborrar 01:00 tota llista enllaçada en un error de la batuda.
Així que anem a anar a través algunes d'aquestes operacions
i com podem visualitzar-los, parlant en codi pseudocodi específicament.
Així que volem crear un llista enllaçada, així que potser
voleu definir una funció amb aquest prototip.
sll estrelles node, creu, i jo estic passant en un argument, algunes dades arbitraris
escrigui de nou, d'algun tipus de dades arbitrari.
Però estic returning-- aquesta funció hauria tornarà a mi un punter, a un solitari
node de llista enllaçada.
Un cop més, estem tractant de crear una llista enllaçada del no-res,
així que necessito un punter a aquesta llista quan he acabat.
>> Quins són els passos a seguir aquí?
Bé, primer que estic farem és dinàmicament
assignar espai per a un nou node.
Un cop més, estem creant fora de fina aire, de manera que necessitem l'espai malloc per a això.
I, per descomptat, immediatament després que malloc,
sempre comprovar per assegurar-se que la nostra pointer-- no aconseguim tornar nul.
Perquè si tractem de deferència un punter nul,
anem a patir un violació de segment i no volem això.
>> Llavors volem omplir el camp, volem inicialitzar el camp de valor
i inicialitzar el següent camp.
I després volem A-- finalment com el prototip de funció indicates-- volem
per tornar un punter a un node sll.
Llavors, què fa aquest parer visualment?
Bé, primer anem a dinàmicament assignar espai per a un nou node SLL,
així que això és malloc-- una representació visual
del node que acabem de crear.
I vam comprovar que assegurar no és null-- en aquest cas,
la imatge no tindria aparegut si era nul,
ens hauríem quedat sense memòria, així que estem bé per anar-hi.
Així que ara estem en el pas C, inicialitzar el camp de valor nodes.
Doncs bé, en base a aquesta funció dic estic fent servir aquí,
sembla que vull passar a 6, Així que vaig a 6 al camp de valor.
Ara, inicialitzar el següent camp.
Bé, què faré allà, no hi ha res al costat, a la dreta,
aquesta és l'única cosa a la llista.
Llavors, ¿què és el proper a la llista?
>> No ha d'apuntar a res, és clar.
No hi ha res més allà, així que el que és el concepte que coneixem que és nothing--
punters a res?
Ha de ser tal que volem posar un punter nul allà,
i vaig a representar la nul·la punter només com una caixa vermella,
no podem anar més enllà.
Com veurem una mica més endavant, tindrem eventualment cadenes
de fletxes que connecten aquests nodes junts,
però quan es prem el caixa vermella, que és nul·la,
no podem anar més lluny, aquest és el final de la llista.
>> I finalment, només volem retornar un punter a aquest node.
Així que ho anem a cridar nova, i tornarà nova
per la qual cosa es pot utilitzar en qualsevol funció va crear.
Així que aquí anem, Hem creat una individualment node de llista enllaçada del no-res,
i ara tenim una llista que podem treballar.
>> Ara, anem a dir que ja tenen una gran cadena,
i volem trobar alguna cosa en ella.
I volem una funció que està passant per tornar veritable o fals, depenent
sobre si hi ha un valor en aquesta llista.
Un prototip de funció, o declaració per a aquesta funció,
podria semblar esto-- Bool trobar, i llavors volem passar en dos arguments.
>> El primer, és un punter a la primer element de la llista enllaçada.
Això és realment una cosa que vostè sempre volen perdre de vista,
i en realitat podria ser una cosa que fins i tot es posa en una variable global.
Un cop creada una llista, sempre, sempre
vull fer un seguiment de la mateixa primer element de la llista.
D'aquesta manera vostè pot fer referència a tots els altres elements per només seguint la cadena,
sense haver de mantenir punters intacte per a cada element.
Només cal fer un seguiment de la primera un si tots estan encadenats junts.
>> I després la segona cosa estem passant de nou
és some-- arbitràriament qualsevol que sigui el tipus de dades que estem
buscant que hi ha dins de amb sort un dels nodes de la llista.
Quins són els passos?
Bé, el primer que fem és vam crear un punter transversal
apuntant al capdavant de les llistes.
Bé, per què ho fem, ja tenir un punter al capdavant llistes,
¿Per què no simplement movem que ningú al voltant?
Bé, com acabo de dir, que és molt important per a nosaltres
sempre mantenir un seguiment de la molt primer element a la llista.
I el que és en realitat millor per crear un duplicat que,
i l'ús que per moure de manera que mai moure accidentalment de distància, o sempre
tenir un punter en algun moment que és a la dreta en el primer element de la llista.
Així que és millor crear un segon que fem servir per moure.
>> Llavors només si comparem el camp de valor en aquest node
és el que estem buscant, i si és No, simplement movem al següent node.
I seguim fent això una altra vegada, i una altra, i una altra,
fins que ens trobem, ja sigui l'element, o colpegem
null-- que hem arribat al final de la llista i no hi és.
Això hauria de sonar una campana a vostè com acaba de recerca lineal,
només estem replicant en una estructura de llista enllaçada
en lloc d'utilitzar una matriu per fer-ho.
>> Així que aquí està un exemple de una llista simplement enllaçada.
Aquest consisteix en 5 nodes, i tenim
un punter al capdavant de la llista, que es diu llista.
El primer que volem fer és de nou, crear aquest punter recorregut.
Així que tenim ara dos punters que apunten al mateix.
>> Ara, noti aquí també, no ho vaig fer que malloc qualsevol espai per trav.
Jo no he dit trav és igual a malloc alguna cosa, aquest node ja existeix,
que l'espai en la memòria ja existeix.
Així que tot el que en realitat estic fent és creant un altre punter a ell.
No estic mallocing addicionals espai, només hi ha ara dos punters
apuntant a la mateixa cosa.
>> Així és 2 el que estic buscant?
Bé, no, així que en comptes estic passarà a la següent.
Així que, bàsicament, jo diria, trav és igual a trav següent.
És de 3 el que estic buscant, no.
Així que segueixo anar a través, fins que al final
arribo a 6 que és el que estic buscant per a la base de la crida a la funció
Tinc a la part superior allà, i l'he acabat.
>> Ara, què passa si l'element que sóc buscant no està a la llista,
està encara funcionarà?
Bé, notarà que la llista aquí és subtilment diferent,
i això és una altra cosa que és important amb llistes enllaçades,
vostè no ha de preservar en qualsevol ordre particular.
Vostè pot si ho desitja, però és possible que ja hagi notat
que no estem fer el seguiment de el que l'element nombre estem.
>> I això és una espècie d'un comerç que tenir amb llista enllaçada versos matrius,
és que no tenim accés aleatori més.
No podem dir, que vull per anar a l'element 0 ª,
o el sisè element de la meva matriu, que puc fer en una matriu.
No puc dir que em vull anar a la Element 0 ª, o el sisè element,
o l'element 25a de la cistella enllaçada, no hi ha índex associat amb ells.
I pel que en realitat no importa si preservem la nostra llista en ordre.
Si desitja vostè certament pot, però hi ha
cap raó per la qual necessiten per preservar en qualsevol ordre.
Així que de nou, tractarem de trobar 6 en aquesta llista.
Bé, comencem pel començant, no trobem 6,
i llavors no seguim trobant 6, fins que finalment vam arribar a aquí.
Així correctes punts ara trav al node conté 8, i sis no hi és.
>> Així que el següent pas seria per anar al següent punter,
ho diuen trav és igual a trav següent.
Bé, trav següent, indicat per la caixa vermella allà, és nul.
Així que no hi ha cap altre lloc a anar, i el que en aquest punt
podem concloure que hem arribat al final de la llista enllaçada,
i 6 no hi és.
I seria retornat falsa en aquest cas.
>> OK, com ens inserim una nova node en la llista enllaçada?
Així que hem estat capaços de crear una llista enllaçada del no-res,
però probablement volem construir una cadena i no
crear un munt de llistes diferents.
Volem tenir una sola llista que té un grup de nodes al mateix,
no un munt de llistes amb un únic node.
Així no podem seguir utilitzant el Crear funció que definim abans, ara ens
vol inserir en un llista que ja existeix.
>> Així que aquest cas, anem Va esdevenir en dos arguments,
el punter al capdavant d'aquest llista que volem afegir a la vinculada.
Un cop més, és per això que és tan important que sempre
no perdre de vista, perquè és l'única manera en què realment
que es refereixen a tota la llista és amb només un punter al primer element.
Així que volem transmetre en un punter a aquest primer element,
i qualsevol que sigui el valor que que voleu afegir a la llista.
I, finalment, aquesta funció va retornar un punter
a la nova cap d'una llista enllaçada.
>> Quins són els passos a seguir aquí?
Bé, igual que amb crear, hem d'assignar dinàmicament
espai per a un nou node, i comprovar per assegurar-se que no es quedi sense memòria, de nou,
perquè estem usant malloc.
Llavors volem poblar i inserir el node,
a fi de posar el nombre, el que sigui val és, en el node.
Volem inserir el node en l'inici de la llista enllaçada.
>> Hi ha una raó per la qual voler fer això, i
valdria la pena prendre un segon per aturar el vídeo aquí,
i pensar sobre per què voldria inserir al començament d'una lligat
llista.
Un cop més, he esmentat abans que en realitat no
importa si preservem en qualsevol ordre, així que potser això és una pista.
I vas veure el que passaria si ens volgut A-- o des d'un segon
fa quan ens anàvem a través de cerca
podria veure el que podria passaria si tractàvem
per inserir al final de la llista.
Perquè no tenim un punter al final de la llista.
>> Així que la raó per la qual jo voldria per inserir al principi,
és perquè puc fer-ho immediatament.
Tinc un punter al començament, i anem a veure això en un visual en un segon.
Però si vull inserir al final, He de començar pel principi,
recórrer tot el camí fins a la final, i després virar a engegar.
Així que això significaria que inserir al final de la llista
es convertiria en un o de n operació, que es remunta
a la nostra discussió de complexitat computacional.
S'havia convertit en un o de l'operació n, on com la llista es va fer més gran i més gran,
i més gran, que serà més i més difícil de virar una mica
en al final.
Però sempre és molt fàcil virar alguna cosa en al principi,
sempre estàs al principi.
>> I anem a veure una representació visual d'aquest nou.
I després, un cop que haguem acabat, un cop hem inserit el nou node,
volem tornar la nostra punter a el nou cap d'una llista enllaçada, que
ja que estem inserint en el començant, serà realment
un punter al node que acabem de crear.
Anem a visualitzar això, perquè crec que va a ajudar.
>> Així que aquí està la nostra llista, que consisteix en quatre elements, un node que conté 15,
el que apunta a un node que conté 9, que
apunta a un node que conté 13, que apunta a un node que conté
10, que té la hipòtesi nul·la punter com a pròxim punter
de manera que és el final de la llista.
Així que volem inserir un nou node amb el valor 12
a l'inici d'aquesta llista, què fem?
Bé, primer que malloc espai per al node, i després posem 12 en aquest país.
>> Així que ara hem arribat a un punt de decisió, no?
Tenim un parell de punters que vam poder
movem, quina hem de passar primer?
Cal fer 12 punts per el nou cap de la pel·lícules--
o perdó, hem de fer 12 apuntar a la vella cap de la llista?
O hauríem de dir que la llista ara comença a les 12.
Hi ha una distinció allà, i anem a veure
al que succeeix amb els dos en un segon.
>> Però això condueix a una gran tema de la barra lateral,
que és que una de les les coses més difícils amb llistes enllaçades
és el d'organitzar els punters en l'ordre correcte.
Si mou les coses fora d'ordre, vostè pot acabar accidentalment
orfandat la resta de la llista.
I aquí és un exemple d'això.
Així que anirem amb la idea de-- així, hem acabem de crear 12.
Sabem 12 serà el nou cap de la llista,
i així que per què no ens movem el punter de la llista perquè apunti allà.
>> OK, així que això és bo.
Així que ara, on 12 següent punt?
Vull dir, visualment podem veure que apuntarà a 15,
com a éssers humans és molt obvi per a nosaltres.
Com sap l'equip?
Nosaltres no tenim res assenyalant a 15 més, no?
>> Hem perdut tota capacitat per fer referència a 15.
No podem dir nova fletxa propers iguals alguna cosa, no hi ha res allà.
De fet, hem orfes la resta de la llista
en fer-ho, tenim trencat accidentalment la cadena.
I certament no volem fer això.
>> Així que anem a tornar i provar de nou.
Potser el que cal fer és establir de 12 següent punter
l'antic cap de la primera llista, llavors podem moure la llista més.
I de fet, aquest és el ordre correcte que nosaltres
ha de seguir quan estem treballar amb llista enllaçada.
Sempre volem connectar el nou element a la llista,
abans de prendre aquest tipus de important pas de canviar
on el cap de la llista enllaçada és.
Un cop més, això és una cosa tan fonamental, no volem perdre la pista d'ell.
>> Així que volem assegurar-nos que tot està encadenat junts,
abans de passar aquest punter.
I pel que aquest seria l'ordre correcte, que és connectar 12 a la llista,
després dir que la llista comença 1 des.
Si ens va dir que la llista comença a les 12 i després va tractar de connectar 12 a la llista,
ja hem vist el que passa.
Perdem la llista per error.
>> OK, així que una cosa més que parlar.
Què passa si volem desfer-nos d' tota una llista lligada a la vegada?
Un cop més, estem mallocing tot aquest espai, de manera que
necessari per alliberar quan hàgim acabat.
Així que ara volem eliminar la llista enllaçada sencer.
Bé, què és el que volem fer?
>> Si hem arribat al punter nul, ens vol deixar, en cas contrari, simplement esborri
la resta de la llista i després em allibera.
Elimineu la resta de la llista, i després alliberar el node actual.
El que fa que el so com, quina tècnica hem de parlar
sobre prèviament sona això?
Eliminar tots els altres, a continuació, tornar i em eliminar.
>> Aquesta és la recursivitat, hem fet la problema una mica més petit,
estem dient esborrar tot el món persona, llavors vostè em pot eliminar.
I més pel camí, aquest node diran, esborrar tots els altres.
Però amb el temps arribarem a la punt en el qual la llista és nul,
i aquest és el nostre cas base.
>> Així que anem a fer una ullada a això, i com això podria funcionar.
Així que aquí està la nostra llista, que és el mateix Enumerem només estàvem parlant,
i hi ha els passos.
Hi ha una gran quantitat de text aquí, però esperem que la visualització l'ajudarà.
>> Així que tener-- i també vam aturar la nostra marcs de pila il·lustració
del nostre vídeo en piles de trucades, i espero que tot això
junts li mostrarà el que està passant.
Així que aquí està el nostre codi pseudocodi.
Si arribem a un nul punter, parada, en cas contrari,
eliminar la resta de la llista, a continuació, alliberar el node actual.
Així que ara mateix, pel·lícules-- el punter que estem
passant per destruir punts a 12.
12 no és un punter nul, així que estem va a eliminar la resta de la llista.
>> El que està esborrant el resta de nosaltres involucrats?
Bé, significa fer una trucar per destruir, dient:
15 que és el començament de la resta de la llista que volem destruir.
I així la crida a destruir 12 és tipus d'en espera.
Ha congelat allà, esperant el cridar per destruir 15, per acabar la seva feina.
>> Bé, 15 no és un punter nul, i pel que dirà, està bé,
així, elimini la resta de la llista.
La resta de la llista comença a les 9, de manera que només haurem de
espereu fins que s'elimini tot el que coses, i després tornar i em eliminar.
Bé setembre que dirà, bé, Jo no sóc un punter nul,
així eliminar la resta de la llista d'aquí.
I així tractar de destruir 13.
13 diu: Jo no sóc punter nul, el mateix, passa la pilota.
10 no és punter nul, 10 conté un punter nul,
però 10 no és en si mateixa una punter nul en aquest moment,
i pel que passa els diners també.
>> I ara una llista dels punts allà, Realment seria apuntar a some--
si tingués més espai en la imatge, seria apuntar a un cert espai a l'atzar
que no sabem el que és.
És el punter nul, però, la llista s'estableix ara, literalment, és valors nuls.
S'assenyala a la dreta dins d'aquesta caixa vermella.
Arribem a un punter nul, de manera que podem aturar, i estem fet.
>> I perquè el marc porpra és ara-- al part superior de stack-- que és el marc actiu,
però es fa.
Si hem arribat a un punter nul, per.
Nosaltres no fem res, no es pot alliberar un punter nul,
que no malloc qualsevol espai, i així hem acabat.
Així que marc de funció es destrueix, i nosaltres
resume-- recollim on ho vam deixar amb la següent més alta, la qual cosa
És aquest marc blau fosc aquí.
Així que prenem just on ho vam deixar.
Hem suprimit la resta de la llista ja, de manera que ara estem
va alliberar els nodes actuals.
Així que ara podem alliberar aquest node, i ara hem arribat al final de la funció.
I perquè marc de funció es destrueix, i nosaltres recollim en el blau clar.
>> Així que says-- ja he done-- suprimir la resta de la llista, per la qual
alliberar el node actual.
I ara el quadre groc és tornar al cim de la pila.
I així com veus, ara estem la destrucció de la llista de dreta a esquerra.
>> ¿Què hauria passat, però, si haguéssim fet les coses de manera equivocada?
Igual que quan intentem per afegir un element.
Si mal estat de la cadena, en cas no ens connectem els punters
en l'ordre correcte, si alliberat al primer element,
si ens alliberem de la cap de la llista, ara
no hi ha manera de referir-se a la resta de la llista.
I així tindríem tot orfes,
haguéssim tingut el que hi ha diu una pèrdua de memòria.
Si vostè recorda del nostre vídeo en l'assignació de memòria dinàmica,
això no és molt bo.
>> Així que com ja he dit, hi ha són diverses operacions
que hem de fer servir per treballar amb llista vinculada efectivament.
I t'hauràs adonat vaig ometre un, l'eliminació d'un sol element d'una lligat
llista.
La raó per la qual vaig fer és que és en realitat una mica
difícil de pensar sobre com eliminar un sol element d'una individualment
llista enllaçada.
Hem de ser capaços de passar per alt alguna cosa a la llista, que
vol dir que arribem a un nosaltres point-- vols eliminar aquest node--
però per tal que sigui així que no perdi cap informació,
hem de connectar aquest node d'aquí, aquí.
>> Així que probablement vaig fer malament des d'una perspectiva visual.
Així que estem en el començament de la nostra llista, estem procedint a través,
volem eliminar aquest node.
Si ens limitem a esborrar-ho, hem trencat la cadena.
Aquest node aquí es refereix a tota la resta,
que conté la cadena d'ara endavant.
>> Així que el que hem de fer realitat després d'arribar a aquest punt,
és que hem de donar un pas enrere un, i connectar aquest node a través d'aquest node,
així llavors podem eliminar l'un al centre.
Però les llistes per separat enllaçats no fan ens proporcionen una manera d'anar cap enrere.
Així que hem de mantenir qualsevol dos punters, i moure'ls
espècie de pas fora, una darrere de l' altra mesura que avancem, o arribar a un punt
i després enviar un altre punter a través.
I com es pot veure, pot ser una mica desordenat.
Afortunadament, tenim una altra manera de resoldre això,
quan parlem de llistes doblement enllaçades.
>> Sóc Doug Lloyd, això és CS50.