las wikis

Listas enlazadas
Definición: Las listas enlazadas son estructuras de datos semejantes a los array (arreglos) salvo que el acceso a un elemento no se hace mediante un índice sino mediante un puntero. 
La asignación de memoria es hecha durante la ejecución. 
En una lista los elementos son contiguos en lo que concierne al enlazado. 


Aplicaciones de las listas enlazadas
Las listasenlazadas son usadas como módulos para otras muchas estructuras de datos, tales como pilas, colas y sus variaciones. El campo de datos de un nodo puede ser otra lista enlazada. Mediante este mecanismo, podemos construir muchas estructuras de datos enlazadas con listas; esta práctica tiene su origen en el lenguaje de programación Lisp, donde las listas enlazadas son una estructura de datos primaria (aunqueno la única), y ahora es una característica común en el estilo de programación funcional.
Definición y declaración de Punteros.

 Un puntero es una variable que contiene la dirección de otra variable. 
 
 También podríamos decir que un puntero es una variable que representa la posición (más que el valor) de otro dato, tal como una variable o un elemento de un array. 
 
 Cuando una variablepuntero es definida, el nombre de la variable debe ir precedido de un asterisco (*). Este identifica que la variable es un puntero. Por tanto, una declaración de puntero puede ser escrita en téminos generales como:

 es cualquier tipo de variable en C. 

 es el nombre del puntero. El tipo o tipo base, indica el tipo de variables que se podrán manipular a través del puntero. Es importanteconocer el tipo base de un puntero, puesto que toda la aritmética de punteros se realiza con relación a la base. (Luego lo veremos más claro en los ejemplos).  
 

& Devuelve la dirección de memoria del operando.

* Devuelve el valor almacenado en la dirección de memoria que determina el operando.

  

Clasificación de las Listas Enlazadas
•Las listas simples están formadas por nodos conun solo enlace. Este enlace hace referencia al siguiente nodo de la lista o a NULL si es el ultimo nodo. NULL es un valor que representa que la referencia esta vacía. Debido a que poseen una sola referencia el recorrido de las listas simples es en una sola dirección: del primero hacia el ultimo. No es posible ir de un nodo al nodo anterior.




Implementación de una Lista Simple
Paraimplementar una lista primero debemos definir su nodo. Podemos definir el nodo como una estructura con dos campos: uno para almacenar el valor o la data del nodo y el otro para almacenar la dirección del siguiente nodo. El primer campo puede ser un tipo de dato elemental o una estructura. El segundo debe ser un puntero a una estructura nodo. Veamos:



En Código:
1
2
3
4
struct nodo {
 intdata; //almacena la data (un entero en este caso)
 nodo *sgte; //almacena la dirección de otro nodo
};

Una lista se maneja mediante un puntero al primer nodo de la lista. A este puntero se le conoce como cabecera y se declara en la función principal (main). Inicialmente, cuando la lista esta vacía, la cabecera debe de tener el valor NULL. Veamos:
1
2
3
4
int main() {
 nodo *cab = NULL;//declaración de la cabecera de la lista
 return 0;
}

Por medio de la cabecera podemos acceder a todos los nodos de la lista de la siguiente manera: como la cabecera apunta al primer elemento, accedemos su campo sgte y encontramos la dirección del segundo elemento luego accedemos al campo sgte del segundo elemento y encontramos la dirección del tercero. Así sucesivamente hasta que el campo sgtede un elemento sea igual a NULL entonces diremos que este es el ultimo elemento y que la lista ha terminado.

Operaciones sobre una Lista Simple
Las operaciones sobre una lista las implementamos mediante funciones que reciben como parámetro la cabecera de la lista sobre la que queremos trabajar entre otros parámetros dependiendo de la operación. Ahora veamos las operaciones básicas que se...