C/Traballar con listas encadeadas: Diferenzas entre revisións

É dicir, en casos en que se sabe que se van ir introducindo e borrando datos en distintas posicións que non van ser sempre a última (como se faría no caso das matrices), será máis eficiente traballar con listas encadeadas, pois este tipo de operacións con matrices resultarían, como mínimo, pouco útiles.

 

Existen distintos tipos de listas encadeadas, que fundamentalmente consisten no mesmo, pero que difiren na súa función, e por tanto tamén difiren lixeiramente na forma en que se traballa con elas. Así, segundo o que vaiamos facer con elas, falaremos de:

 

:É un contedor de datos non ordenados, que simplemente se van introducindo ao principio da pila, en lugar de ao final ─que é como se faría no caso das matrices─. É por iso que nas funcións que traballar con pilas non se fornece nunca un dato a buscar, xa que sempre se traballa co primeiro dato da pila.

:As funcións das pilas son catro:

 

;Cola

:Isto significa que para traballar con colas teremos que ter non só o enderezo en memoria do primeiro elemento, senón tamén o enderezo do último dos seus elementos. O primeiro valerá para introducir novos datos, e o segundo para traballar cos datos e borralos unha vez se utilicen.

 

Para declarar unha lista encadeada cómpre ter claro previamente o comportamento das [[{{BASEPAGENAME}}/Estruturas|estruturas]]. Cada elemento da lista ─elemento─ será unha estrutura conformada polos datos do elemento e un punteiro a unha estrutura do mesmo tipo, que será o que apunte ao seguinte elemento (salvo que se trate do último elemento da lista encadeada).

 

Por suposto, necesitaremos ademais dos elementos un punteiro solto que apunte ao primeiro elemento da lista encadeada, e en caso de que traballemos cunha cola, será necesario tamén un segundo punteiro que sinale ao último elemento. Estes punteiros serán as únicas variables locais, é dicir, as únicas que non se van reservar en memoria dinámica. Cómpre ''inicializar'' estes punteiros con valor nulo, de xeito que isto permita saber que a lista está, en principio, baleira.

 

Nos seguintes exemplos traballarase cunha estrutura chamada elemento froito do seguinte código:

<source lang=c>

Isto simplificará os exemplos, ao mesmo tempo que permitirá facilmente modificar as funcións par adaptalas a un código e unha función máis concretas.

 

Ao pasarlle unha lista a unha función que vai traballar con ela (engadir ou borrar datos), hai que pasarlle o punteiro da lista “por referencia”. Iso significa que á función se lle pasa o enderezo en memoria do punteiro que á súa vez contén o enderezo en memoria do primeiro elemento da lista, o que permitirá ao programador modificar o valor deste punteiro. Isto quedaría da seguinte forma na función que recibe a lista encadeada:

<source lang=c>

De xeito que se poida acceder a todos os elementos da lista, pero non se poida modificar o valor do punteiro da lista, é dicir, o punteiro ao primeiro elemento.

 

Antes de engadir un elemento a unha lista será necesario crealo, é dicir, facerlle espazo en memoria, xeralmente un a un a través dunha función como a seguinte:

<source lang=c>

O programa que chamase á función debería controlar o valor que devolvese a función, e en caso de ser o punteiro nulo, actuar en consecuencia.

 

O proceso para engadir un novo elemento a unha lista encadeada simple non é complicao de entender. A función recibirá a información nova que se vai engadir á lista e o enderezo do enderezo da lista (por se tiver que cambiar). Entón, a función traballará con tres punteiros, un para gardar un elemento da lista (o que se vai analizando), outro para gardar o elemento anterior (que irá mudando) e outro para gardar o novo elemento.

 

Cómpre ter en conta que este é o programa base á hora de engadir novos datos a unha lista encadeada simple e, xa que logo, pode ser que o programador queira modificalo para personalizalo. E por suposto, será necesario facer polo menos as modificacións necesarias para que a función se adapte a un tipo de elemento distinto ─cuxo contido non sexa un simple <code>signed int</code>─.

 

Imaxinemos unha pila en que os seus elementos conteñen só un dato de tipo <code>signed int</code> ─ademais de conter o punteiro que sinala ao seguinte elemento na pila─. Isto simplificará o exemplo, pero valerá para ilustrar calquera caso. Para introducir novos datos nesta pila de exemplo utilizaríase unha función como a seguinte:

<source lang=c>

Cómpre ter en conta que este é o programa base á hora de engadir novos datos a unha pila e, xa que logo, pode ser que o programador queira modificalo para personalizalo. E por suposto, será necesario facer polo menos as modificacións necesarias para que a función se adapte a un tipo de elemento distinto ─cuxo contido non sexa un simple <code>signed int</code>─.

 

Para borrar un elemento dunha lista encadeada simple, utilizarase unha función como a seguinte, sempre partindo do exemplo anterior dunha estrutura cun único dato <code>signed int</code> ─ademais do punteiro ao seguinte elemento da lista─:

<source lang=c>

</source>

 

Para sacar un elemento dunha pila, que será sempre o primeiro elemento desta dada a súa natureza, utilizarase unha función como a seguinte, sempre partindo do exemplo anterior dunha estrutura cun único dato <code>signed int</code> ─ademais do punteiro ao seguinte elemento da lista─:

<source lang=c>

Nótese que nunha pila non ten sentido borrar un elemento se non é para traballar con el e logo borralo, emporiso que a operación de borrado devolve o dato borrado en vez de recibir o dato que se quere borrar.

 

Independentemente de que se trate dunha lista encadeada simple, unha pila ou unha cola, para borrar toda unha lista encadeada utilizarase unha función como a seguinte:

<source lang=c>

</source>