Ayuda con listas enlazadas

Imaginemos un mundo libre
El blog de Ronny, dedicado a la libertad de acceso al conocimiento.
Listas enlazadas – Clase Lista,Nodo en c++
with 11 comments
Una lista es una estructura de datos que nos permite agrupar elementos de una manera organizada. Las listas al igual que los algoritmos son importantísimas en la computación y críticas en muchos programas informáticos.
Las listas estáncompuestas por nodos, estos nodos tienen un dato o valor y un puntero a otro(s) nodo(s).
Existen varios tipos de listas: Simplemente enlazada, doblemente enlazada, circular simplemente enlazada, circular doblemente enlazada.
Vamos a revisar las listas enlazadas simples, por ser el punto de partida y fundamentales para poder entender las otras.
Una lista enlazada tiene un conjunto de nodos, loscuales almacenan 2 tipos de información: El dato que contienen y un puntero al siguiente nodo en la lista. El último nodo de la lista tiene como siguiente nodo el valor NULL. Entonces las listas enlazadas simples solo pueden ser recorridas en una dirección, apuntando al nodo siguiente, mas no a un nodo anterior.
Aquí una ejemplo de un lista enlazada simple.
view source

print?
01 | Encristiano: |
02 | 55-> 60-> 31-> 5-> 4-> 51-> 9-> 27-> 68-> 62-> NULL |

03 |    |
04 | Internamente: |

05 | Nodo-> Dato: 55 Direcion: 0x3d2c00 Siguiente: 0x3d2c80 |
06 | Nodo-> Dato: 60 Direcion: 0x3d2c80 Siguiente: 0x3d2c90 |

07 | Nodo-> Dato: 31 Direcion: 0x3d2c90 Siguiente: 0x3d2ca0 |
08 | Nodo-> Dato: 5  Direcion: 0x3d2ca0 Siguiente:0x3d2cb0 |

09 | Nodo-> Dato: 4  Direcion: 0x3d2cb0 Siguiente: 0x3d2cc0 |
10 | Nodo-> Dato: 51 Direcion: 0x3d2cc0 Siguiente: 0x3d3ab8 |

11 | Nodo-> Dato: 9  Direcion: 0x3d3ab8 Siguiente: 0x3d3ac8 |
12 | Nodo-> Dato: 27 Direcion: 0x3d3ac8 Siguiente: 0x3d3ad8 |

13 | Nodo-> Dato: 68 Direcion: 0x3d3ad8 Siguiente: 0x3d3ae8 |
14 | Nodo-> Dato: 62 Direcion:0x3d3ae8 Siguiente: 0 |
Obviamente, internamente no existen las palabras nodo, dato,dirección y siguiente, es solo una representación.
Como una lista es una estructura de datos dinámica, el tamaño de la misma puede cambiar durante la ejecución del programa.
Como vimos en post anteriores, se puede generar memoria dinámicamente para un array, pero un array es una estructura estática pues su tamañotiene un limite y así creáramos array dinámicos hay que redimensionar el tamaño si es necesario, lo cual ya implica un costo de volver a generar memoria dinámica.
Entonces podemos ver una ventaja de la listas sobre los arrays: No tener que redimensionar la estructura y poder agregar elemento tras elemento indefinidamente.
Cuando uno ya ha trabajado con arrays (vectores y matrices) y empieza aestudiar las listas, se da cuenta que una restricción de las listas es el acceso a los elementos. En un vector podíamos hacer algo como v[50] y nos estábamos refiriendo al índice 50 del vector v. A esto se le conoce como acceso aleatorio.
En el caso de las listas el acceso es secuencial, es decir, para acceder a un elemento del conjunto debemos de recorrer uno por uno los elementos hasta llegar alsolicitado. Rápidamente se puede concluir que el tiempo de acceso a los elementos de un array es muchísimo más rápido que en una lista. Esta es una gran desventaja de las listas, por lo que buscar elementos por índice sería muy costoso. Esto no quiere decir que trabajar con arrays sea mejor que con listas. Las listas son muy flexibles y para muchos casos son imprescindibles.
Bueno, aquí va laprimera práctica que hice sobre listas enlazadas. Implementación de una clase Lista, clase Nodo y los siguientes métodos:
* Añadir un elemento al inicio.
* Añadir un elemento al final
* Añadir un elemento de manera ordenada
* Llenar la lista por teclado
* Llenar la lista aleatoriamente
* Imprimir la lista
* Buscar un elemento
* Eliminar un elemento por dato
*...