>> [Música tocando]
>> Doug LLOYD: OK, entón a Neste punto do curso,
nós Cubrimos unha morea de conceptos básicos de C. Sabemos moito sobre variables, arrays,
punteiros, todas esas cousas boas.
Aqueles son todo tipo de construción para ver como os fundamentos,
pero podemos facer máis, non?
Podemos combinar as cousas en conxunto de formas interesantes.
>> E así imos facelo, imos comezar a ramifican-se que C nos dá,
e comezar a crear os nosos propios datos Usando estas estruturas edificio
bloques xuntos para facer algo realmente valioso, útil.
Unha forma de facelo é para falar coleccións.
Entón, por agora tivemos un tipo de datos estrutura para representar as coleccións
quere valores, valores semellantes.
Iso sería unha matriz.
Temos coleccións de enteiros, ou coleccións de personaxes e así por diante.
>> Estruturas tamén son un tipo de datos estrutura para a obtención de información,
pero non é para recoller como valores.
Xeralmente mestura diferentes tipos de datos xuntos dentro dunha única caixa.
Pero non é en si usado para encadear
ou conectar xuntos semellante elementos, como unha matriz.
Arrays son grandes para elemento de mirar para arriba, pero recordo
que é moi difícil para introducir unha matriz,
a non ser que estamos introducindo no o final desa matriz.
>> E o mellor exemplo que eu teño para iso é a ordenación por inserción.
Se ben se lembran o noso vídeo na ordenación por inserción,
había unha morea de gasto parte en ter
para incorporarse elementos, e transferir-los fóra do camiño para caber algo
no medio da súa matriz.
Arrays tamén sofren doutro problema, que é a inflexibilidade.
Cando declaramos unha matriz, obtemos un tiro nel.
Comezamos a dicir, quero este moitos elementos.
Pode ser de 100, pode ser 1000, pode
ser X, onde X é un número que o usuario deunos nun ventá de consola ou no
liña.
>> Pero nós só temos unha oportunidade para el, nós non pode, entón, dicir oh, de feito eu
precisaba de 101, ou eu precisaba x máis 20.
Demasiado tarde, que xa declarou o array, e se queremos obter 101 ou x
engade 20, temos a declarar unha matriz totalmente diferente,
copiar todos os elementos da matriz sobre, e entón temos o suficiente.
E se estamos errados de novo, o que se realmente necesitamos 102, ou x máis 40,
temos que facelo de novo.
Entón, eles están moi inflexíbel para cambiar o tamaño os nosos datos,
pero se combinan algúns dos principios básicos que xa
Aprende sobre punteiros e estruturas, en especial a través de memoria dinámica
distribución con malloc, nós pode pór estes anacos xuntos
para crear un novo dado un structure-- illadamente lista poderiamos dizer-- conectado
que nos permite crecer e encoller unha colección de valores
e non teremos ningún espazo desperdiçado.
>> Entón, de novo, chamamos esa idea, esa noción, unha lista ligada.
En particular, neste video que estamos falando lista vinculada illadamente,
e, a continuación, outro vídeo imos falar listas sobre dobremente ligadas, que
é só unha variación sobre un tema aquí.
Pero unha lista vinculada illadamente está composto por nós,
nós só ser un term-- abstracto é só algo que eu estou chamando
que é unha especie de estrutura, basicamente, eu son?
Só tes que ir a chamalo dun node-- e este nó ten dous membros, ou dous campos.
Ten de datos, xeralmente un enteiro, un personaxe float,
ou podería ser algún outro tipo de datos que teña definido cun tipo def.
E que contén unha ligazón para outro nó do mesmo tipo.
>> Polo tanto, temos dúas cousas dentro ese nó, de datos e un punteiro
a outro nodo.
E se comezar a ver iso, pode pensar sobre iso
como unha cadea de nós que están ligados entre si.
Temos o primeiro nodo, el contén os datos, e un punteiro
para o segundo no, a cal contén de datos, e un punteiro para o terceiro nó.
E é por iso que chamamos lista ligada, están unidos entre si.
>> O que fai este especial estrutura de nó parece?
Ben, se se lembra do noso vídeo sobre definir tipos personalizados, co tipo de definición,
podemos definir unha structure-- e escriba definir unha estrutura como esta.
tyepdef struct sllist, e entón eu son usando a palabra valor arbitrariamente aquí
para indicar calquera tipo de datos realmente.
Podería pasar un enteiro ou float, pode que o que quere.
Non hai restricións para só enteiros, ou algo así.
Así, o valor é só unha arbitraria Tipo de datos e, a continuación, un punteiro
a outro nodo do mesmo tipo.
>> Agora, hai un pouco de captura aquí cunha estrutura que define
cando é unha estrutura auto referencial.
Eu teño que ter un temporal nomear a miña estrutura.
Ao final do día, claramente queren chamalo
SLL nó, que é en definitiva, o novo nomear parte da miña definición de tipo,
pero eu non podo usar nó SLL no medio deste.
A razón de ser, eu non teño creou un tipo chamado nó SLL
ata que eu bati ese punto final aquí.
Até aquel momento, eu teño que ter outra forma de referirse a este tipo de datos.
>> E esta é unha auto- tipo de datos referencial.
; S un tipo de datos que contén unha estrutura de datos,
e un punteiro a outra estrutura do mesmo tipo.
Entón eu teño poder referirse a este tipo de datos, polo menos temporalmente,
así dándolle un temporal nome struct sllist
permíteme, a continuación, dicir que eu quero un punteiro a outro sllist struct,
unha estrela struct sllist, e, a continuación, despois de que eu feitas as definición,
Agora podo chamar este tipo de un nó de SLL.
>> É por iso que ve que hai un nome temporal aquí,
pero un nome permanente aquí.
Ás veces podes ver definicións de estrutura,
por exemplo, que non son auto referencial, que
non ten un nome especificador aquí.
El só diría typedef struct, abrir chaveta e, a continuación, define-lo.
Pero se é struct é auto- referencial, como este é,
precisa especificar un nome do tipo temporal.
Pero, ao final, agora que fixemos iso,
podemos só referirse a eses nós, estas unidades,
como nodos SLL con fins do resto deste vídeo.
>> Todo ben, entón sabemos como crear un nó lista ligada.
Sabemos como configurar un nó de lista ligada.
Agora, se nós estamos indo para comezar usando os para recoller información,
hai un par de operacións que necesitan entender e traballar con el.
Necesitamos saber como crear unha lista ligada fóra do ar.
Se non hai ningunha lista xa, queremos comezar un.
Entón, necesitamos ser capaces para crear unha lista ligada,
necesitamos probablemente buscar a través da lista de ligazóns
para atopar un elemento que estamos buscando.
Necesitamos ser capaces de inserir cousas novas para a lista,
queremos que a nosa lista para poder crecer.
E do mesmo xeito, queremos ser capaces para borrar as cousas da nosa lista,
queremos que a nosa lista para poder encoller.
E ao final da nosa programas, especialmente
se recorda que somos reservar dinamicamente a memoria
para construír estas listas normalmente, queremos liberar toda a memoria que
cando terminarmos de traballar con el.
E por iso temos que ser capaces de borrar un Toda lista ligada nunha rusga falla.
Entón, imos pasar por Algunhas destas tarefas
e como podemos visualiza-los, falando en código pseudocódigo especificamente.
Por iso, queremos crear unha lista ligada, entón quizais nós
quere definir unha función con este prototipo.
SLL estrela no, crear, e eu estou pasando nun argumento, algúns datos arbitrarios
escriba de novo, de calquera tipo de datos arbitrario.
Pero eu estou returning-- esta función debe volver para min un punteiro, a un illadamente
nó lista ligada.
Unha vez máis, estamos intentando crear unha lista ligada fóra do ar,
entón eu teño un punteiro para esa lista cando rematar.
>> Entón, cales son os pasos implicadas aquí?
Ben, o primeiro que eu son vai facer é dinámicamente
reservar espazo para un novo nodo.
Unha vez máis, estamos creando-o para fora da fina aire, polo que necesitamos espazo malloc para el.
E, por suposto, inmediatamente despois que malloc,
sempre asegúrese de que o noso pointer-- non volver nulo.
Porque se nós intentamos e deferencia un punteiro nulo,
imos sufrir un segfault e nós non queremos iso.
>> Entón, nós queremos encher o campo, queremos iniciar o campo de valor
e iniciar o próximo campo.
E entón nós queremos a--, finalmente, como o función prototipo indicates-- queremos
para voltar un punteiro para un nó SLL.
Entón, o que facer este ollar como visualmente?
Ben, primeiro imos dinamicamente reservar espazo para un novo nodo SLL,
por iso, que é malloc-- unha representación visual
do nodo que acabamos de crear.
E nós comproba se non é null-- neste caso
a imaxe non tería aparecido se era nulo,
teriamos quedar sen memoria, polo que é bo para ir alí.
Entón, agora estamos a paso C, iniciar o campo nodos valor.
Ben, con base nesa función chamar que está a usar aquí,
parece que quero pasar en 6, entón eu vou 6 no campo de valor.
Agora, iniciar o próximo campo.
Ben, o que eu vou facer alí, non hai nada ao lado, á dereita,
esta é a única cousa na lista.
Entón, cal é a seguinte cousa na lista?
>> Non debe apuntar para calquera cousa, certo.
Non hai máis nada alí, entón o que é o concepto sabemos de que se nothing--
punteiros para nada?
Debe ser posible queremos para poñer un punteiro nulo alí,
e eu vou representar o nulo punteiro como só unha caixa vermella,
non podemos ir máis lonxe.
Como veremos un pouco máis tarde, imos ter finalmente cadeas
de frechas que ligan destes nós, en conxunto
pero cando bate a caixa vermella, que é nula,
non podemos ir máis lonxe, ese é o fin da lista.
>> E, finalmente, nós só queremos voltar un punteiro para ese nó.
Entón, imos chamalo de novo, e volverá novo
de xeito que se pode empregar en calquera función creou.
Entón alí imos nós, Creamos un illadamente nó lista ligada fóra do ar,
e agora temos unha lista podemos traballar con.
>> Agora, imos dicir que xa ten unha gran cadea,
e queremos atopar algo nel.
E queremos unha función que está a suceder para volver verdadeiro ou falso, dependendo
sobre se existe un valor da lista.
Un prototipo de función, ou declaración para esa función,
pode parecer isto-- bool atopar, e entón queremos pasar en dous argumentos.
>> O primeiro, é un punteiro para o primeiro elemento da lista ligada.
Isto é realmente algo que vai sempre quere seguir,
e, de feito, pode ser algo que vostede mesmo poñer nunha variable global.
Despois de crear unha lista, sempre, sempre
quere manter o control do propio primeiro elemento da lista.
Desta forma, pode referirse a todos os outros elementos por só seguindo a cadea,
sen ter que manter punteiros intacta para cada elemento.
Só ten manter o control do primeiro un, se eles están todos encadeados.
>> E, a continuación, a segunda cousa estamos pasando de novo
é arbitrariamente some-- calquera que sexa o tipo de datos que estamos
buscando existe dentro espero que un dos nós da lista.
Entón, cales son os pasos?
Ben, o primeiro que facemos é creamos un punteiro transversal
apuntando á cabeza listas.
Ben, por que facemos iso, nós xa ter un punteiro na cabeza listas,
por que non imos só mover dun en torno a?
Ben, como dixen, que é realmente importante para nós
manter sempre o control do primeiro elemento da lista.
E por iso é realmente mellor para crear un duplicado de que,
e usar isto para moverse, polo que nunca accidentalmente afastarse, ou sempre
ter un punteiro nalgún punto que é dereito sobre o primeiro elemento da lista.
Polo tanto, é mellor crear un un segundo que usan para mover.
>> A continuación, pode comparar se O campo de valor en que nodo
é o que estamos a buscar, e se é Non, só pasar ao seguinte nodo.
E nós continuar facendo iso máis, e máis, e máis,
ata que quere atopar o elemento, ou se loita
null-- chegamos á final da lista e non está alí.
Este debe esperamos tocar unha campá para ti como só busca lineal,
estamos só réplica-lo unha estrutura de lista vinculada illadamente
en vez de usar unha matriz para facelo.
>> Entón aquí está un exemplo de unha lista vinculada illadamente.
Este consiste cinco nós, e temos
un punteiro para a cabeza do lista, que se chama lista.
O primeiro que quero facer é de novo, crear ese punteiro travesía.
Polo tanto, temos agora dous punteiros que ligan con o mesmo.
>> Agora, observe aquí tamén, eu non fixen ten que malloc calquera espazo para Trav.
Eu non dixen trav igual malloc algo, ese nó xa existe,
ese espazo na memoria xa existe.
Entón, todo o que eu estou facendo realmente é creando un outro punteiro para el.
Non estou mallocing un adicional espazo, só ten agora dous punteiros
apuntando para o mesmo.
>> Entón é 2 o que estou buscando?
Ben, non, en vez eu son vai pasar á seguinte.
Entón, basicamente, eu diría, trav igual trav seguinte.
3 é o que eu estou buscando, non.
Entón eu continuar a ir través, ata que finalmente
chegar a 6, que é o que estou buscando para con base na chamada de función
Teño na parte superior alí, e así que eu son feito.
>> Agora, e se o elemento que eu son buscar non está na lista,
é que aínda vai funcionar?
Ben, teña en conta que a lista aquí é sutilmente diferente,
e esta é outra cousa que é importante con listas ligadas,
non ten que preservar los en calquera orde particular.
Vostede pode, se quere, pero xa debe ter notado
que non estamos mantendo o control de o elemento de número estamos.
>> E iso é un tipo de comercio que ten con lista ligada versos arrays,
é que non temos acceso aleatorio máis.
Non podemos só dicir, quero para ir ao elemento 0,
ou o elemento sexto da miña matriz, que podo facer nunha matriz.
Non podo dicir que eu quero ir ao Elemento 0, ou o elemento 6,
ou o elemento 25 da miña lista ligada, non hai ningún índice asociado con eles.
E por iso realmente non importa preservarse nosa lista en orde.
Se quere vostede certamente poden, pero hai
ningunha razón para que precisan ser preservados en calquera orde.
Entón, de novo, imos tratar 6 atopar nesta lista.
Ben, imos comezar con comezando, non atopamos 6,
e entón non seguir a atopar 6, ata que, finalmente, chegar a aquí.
Tan seguro puntos agora trav para o no contendo 8, e seis non está alí.
>> Así, o seguinte paso sería para ir ao seguinte punteiro,
así din trav igual trav seguinte.
Ben, Trav seguinte, indicada pola a caixa vermella alí, é nulo.
Polo tanto, non hai ningún outro lugar para ir, e por iso neste momento
podemos concluír que chegamos o fin da lista ligada,
e 6 non está alí.
E iso sería devolto false neste caso.
>> OK, como é que imos introducir unha nova nó na lista vinculada?
Entón, nós temos sido capaces de crear unha lista vinculada da nada,
pero probablemente quere construír unha cadea e non
crear un grupo de listas distintas.
Queremos ter unha lista que ten unha morea de nós na mesma,
non unha morea de listas cun único nodo.
Polo tanto, non podemos só seguir usando o Crear función que definimos anteriormente, agora nós
quere inserir un lista que xa existe.
>> Entón, neste caso, imos para pasar en dous argumentos,
o punteiro para a cabeza do que lista que quere engadir á conectados.
De novo, é por iso que é tan importante que sempre
seguir, porque é a única forma de realmente
ten que referirse a toda a lista é só por un punteiro para o primeiro elemento.
Por iso, queremos pasar nun punteiro para ese primeiro elemento,
e calquera valor que quere engadir á lista.
E, finalmente, esta función vai voltar un punteiro
ao novo xefe dunha lista ligada.
>> Cales son os pasos implicadas aquí?
Ben, así como coa crear, necesitamos reservar dinamicamente
espazo para un novo nodo, e asegúrese garantir que non quede sen memoria, outra vez,
porque estamos usando malloc.
Entón, nós queremos encher e introducir o no,
de xeito que o número, o que quere val é, para o no.
Queremos introducir o no en o inicio da lista encadeada.
>> Hai unha razón para que eu quero facer iso, e
pode valer a pena tomar un segundo para deter o vídeo aquí,
e pensar por que eu ía querer introducir no inicio dun conectado
lista.
Unha vez máis, eu mencionen anteriormente que realmente non
importa si preservalo-lo en calquera orde, polo tanto, é posible que unha pista.
E viu o que acontecería se nós quería a-- ou só un segundo
atrás, cando estabamos indo a través de busca vostede
podía ver o que pode deberse estabamos intentando
para introducir no fin da lista.
Porque non temos un punteiro para o fin da lista.
>> Polo tanto, a razón que me gustaría para introducir no inicio,
é porque eu podo facelo inmediatamente.
Eu teño un punteiro en principio, e imos ver iso nun visual nun segundo.
Pero se eu queira inserir o final, Teño que comezar de inicio,
percorrer todo o camiño para a final, e despois predica-la por diante.
Entón, iso significaría que introducir no fin da lista
se tornaría un o de n operación, volvendo
para a nosa discusión de complexidade computacional.
El tiña se tornado un o de n operación, onde como a lista quedou maior e máis grande,
e máis grande, que vai facer máis e máis difícil para alinhavar algo
en ao final.
Pero sempre moi doado alinhavar algo en en principio,
está sempre no inicio.
>> E nós imos ver un visual desta novo.
E, a continuación, xa que estamos a facer, xa temos Insírese o novo nó,
queremos volver noso punteiro para o novo xefe dunha lista ligada, o que
xa que estamos introducindo no comezando, vai ser realmente
un punteiro para o no que acabamos de crear.
Imos ver esta, porque eu creo que vai axudar.
>> Entón aquí está a nosa lista, que consiste en catro elementos, contendo un nó 15,
o que apunta a un nodo contén 9, que
apunta a un nodo que contén 13, o que apunta a un nodo que conteña
10, que ten o nulo punteiro como o seu próximo punteiro
de xeito que é o final da lista.
Por iso, queremos introducir un novo nodo co valor 12
a comezos do presente lista, o que imos facer?
Ben, primeiro nós malloc espazo para a no, e, a continuación, imos poñer 12 en alí.
>> Entón, agora chegamos a un punto de decisión, non?
Temos un par de punteiros que puidésemos
mover, que debemos avanzar en primeiro lugar?
Temos que facer 12 puntos para o novo xefe da lista--
ou me desculpar, temos que facer 12 apuntar ao antigo xefe da lista?
Ou deberiamos dicir que o lista agora comeza a 12.
Hai unha distinción alí, e nós ollaremos
o que pasa con ambos nun segundo.
>> Pero isto conduce a un gran tema para a barra lateral,
que é un dos que o as cousas máis complicadas con listas ligadas
é organizar os punteiros na orde correcta.
Se mover as cousas fóra de orde, pode acabar accidentalmente
orphaning resto da lista.
E aquí está un exemplo diso.
Entón, imos ir coa idea de-- ben, que acabamos de crear 12.
Sabemos 12 será o novo xefe da lista,
e así por que non imos só mover o punteiro lista para apuntar alí.
>> OK, entón iso é bo.
Entón, agora onde é que 12 seguinte punto?
Quero dicir, visualmente vemos que apuntar para 15,
como seres humanos é moi evidente para nós.
Como o ordenador sabe?
Non temos nada apuntando a máis 15, non?
>> Perdemos calquera capacidade de referirse a 15.
Non podemos dicir nova frecha ao lado equals algo, non hai nada alí.
De feito, temos orfos resto da lista
ao facelo, temos accidentalmente rompe a cadea.
E nós certamente non queremos facelo.
>> Entón, imos volver e tentar de novo.
Quizais a cousa ben a facer está situado á beira do punteiro 12
ao antigo xefe da primeira lista, entón podemos mover a lista máis.
E, de feito, que é o orde correcta que
necesitamos seguir cando estamos Traballando con unha lista vinculada illadamente.
Sempre queremos conectar o novo elemento da lista,
antes de tomar este tipo de importante paso de modificación
onde a cabeza da lista ligada é.
De novo, iso é unha cousa tan fundamental, nós non queremos perder o control dela.
>> Entón, nós queremos estar seguro de que todo é encadenados,
antes de pasar ese punteiro.
E así esta sería a orde correcta, o cal é para chamar á súa lista 12,
a continuación, dicir que a lista comeza a 12.
Se dixo que a lista comeza o 12 e a continuación, intentou conectar 12 da lista,
xa vimos o que pasa.
Perdemos a lista por erro.
>> OK, entón unha cousa para falar.
E se a xente quere se librar de toda unha lista ligada dunha vez?
Unha vez máis, estamos mallocing todo este espazo, e por iso,
que liberalo la cando estamos a facer.
Entón, agora queremos eliminar a listaxe ligada.
Ben, o que queremos facer?
>> Se nós alcanzamos o punteiro nulo, nós quere parar, se non, pode borrar
resto da lista e, a continuación, me liberar.
Eliminar o resto da lista, e, a continuación, liberar o no actual.
O que significa que o son como, cal técnica falamos
sobre anteriormente é que o son como?
Eliminar todos os outros, a continuación, volver e me eliminar.
>> Isto é recursão, fixemos o problema un pouco menor,
estamos dicindo eliminar todos máis, entón podes me eliminar.
E máis abaixo na estrada, ese nó vai dicir, eliminar todos os outros.
Pero finalmente imos chegar ao momento en que a lista é nulo,
e este é o noso caso base.
>> Entón, imos dar un ollo niso, e como iso pode funcionar.
Entón aquí está a nosa lista, é o mesmo lista que estaban falando sobre,
e hai os pasos.
Hai unha morea de texto aquí, pero espero que a visualización vai axudar.
>> Entón, nós have-- e eu tamén tirou a nosa pila de cadros ilustración
do noso vídeo sobre pilas de chamadas, e espero que todo isto
xuntos ha amosar-lle o que está pasando.
Entón aquí está o noso código pseudocódigo.
Se chegamos a un valor nulo punteiro, parar, se non,
eliminar o resto da lista, logo liberar o no actual.
Entón, agora, lista-- o punteiro do que somos
pasando para destruír a 12 puntos.
12 non é un punteiro nulo, polo que estamos indo para eliminar o resto da lista.
>> ¿Que é a exclusión do resto de nós implicados?
Ben, iso significa facer unha chamar para destruír, dicindo
15 é que o inicio do resto da lista queremos destruír.
E así a chamada para destruír 12 é unha especie de en espera.
Está conxelado alí, esperando o chamar para destruír 15, para rematar o seu traballo.
>> Ben, 15 non é un punteiro nulo, e polo que vai dicir, todo ben,
ben, elimine o resto da lista.
O resto da lista comeza ás 9, e por iso imos só
espera ata que exclúa todo o que material, a continuación, volver e borrar min.
Ben 9 vai dicir, ben, Eu non son un punteiro nulo,
así eliminar o resto da lista a partir de aquí.
E así intentar destruír 13.
13 di: Non son punteiro nulo, mesmo, el pasa o buck.
10 non é punteiro nulo, 10 contén un punteiro nulo,
10, pero non é ela mesma unha Punteiro Nulo agora,
e así que pasa o balón tamén.
>> E agora incluír puntos alí, realmente chama a atención sobre some--
se eu tivese máis espazo na imaxe, el chama a atención sobre un espazo chou
que non sabemos o que é.
É o punteiro nulo, porén, a lista é, literalmente, agora defínese valores nulos.
El está a apuntar cara a dereita dentro desa caixa vermella.
Chegamos a un punteiro nulo, polo podemos parar, e estamos a facer.
>> E así que cadro vermello é agora-- no parte superior da stack-- ese é o cadro activo,
pero está feito.
Se chegamos a un punteiro nulo, pare.
Nós non facemos nada, nós non pode liberar un punteiro nulo,
non malloc calquera espazo, e por iso estamos a facer.
Entón, ese cadro función é destruído, e nós
resume-- nós incorporarse onde paramos fóra co máis elevado seguinte, que
é este cadro azul escuro aquí.
Entón, nós incorporarse exactamente onde paramos.
Nós excluído o resto do lista xa, entón agora estamos
vai liberar os nós actuais.
Entón agora podemos liberar este nodo, e agora chegamos ao final da función.
E así que o cadro función é destruído, e nós incorporarse na unha luz azul.
>> Por iso, says-- Xa done-- a exclusión do resto da lista, para
liberar o no actual.
E agora o marco amarela é de volta ao principio da pila.
E así como se pode ver, estamos agora destruíndo a lista da dereita á esquerda.
>> Que acontecería, porén, se tivésemos feito as cousas de forma incorrecta?
Así como cando tentamos engadir un elemento.
Se errei a cadea, se non conectar os punteiros
na orde correcta, se nós só liberado o primeiro elemento,
se nós só liberou o cabeza da lista, agora nós
non teñen ningunha maneira para referirse a resto da lista.
E por iso, tería orfas todo,
teriamos que é chamado de fuga de memoria.
Se se lembrar do noso vídeo na distribución dinámica de memoria,
iso non é cousa moi boa.
>> Entón, como dixen, hai varias operacións
que necesitamos usar para traballar con lista ligada de forma eficaz.
E pode notar que omitido nun, excluíndo un único elemento a partir dun conectado
lista.
A razón pola que eu fixen iso é que é realmente tipo de
complicado para pensar sobre como eliminar un único elemento dunha illadamente
lista ligada.
Necesitamos ser capaces de pasar por riba algo na lista, que
Significa chegar a un que ponto-- quere borrar este node--
pero, a fin de facelo así que non perda ningunha información,
necesitamos conectar este nó aquí, aquí.
>> Entón eu probablemente fixen iso mal a partir dunha perspectiva visual.
Entón, estamos no inicio da nosa lista, estamos a proceder a través de,
que quere eliminar este nodo.
Se nós só excluílo, nós quebramos a corrente.
Este nodo aquí refírese a todo o demais,
contén a cadea de agora en diante.
>> Entón, o que necesitamos facer, de feito, despois de chegar a este punto,
é que necesitamos dar un paso atrás un, e conectar ese nó durante a ese nó,
para que poidamos, a continuación, eliminar o un no medio.
Pero as listas vinculada illadamente non facer nos ofrecer unha forma de ir cara atrás.
Entón, necesitamos quere manter dous punteiros, e mover los
especie de off paso, un detrás do outros como nós imos, ou chegar a un punto
e, a continuación, enviar outro punteiro completamente.
E como se pode ver, pode ser un pouco confuso.
Afortunadamente, temos outra forma de resolver isto,
cando falamos de listas dobremente ligadas.
>> Eu son Doug Lloyd, este é CS50.