Subscribe:

miércoles, 6 de abril de 2016

Listas enlazadas en C++

Hace una semana, después de acabar con la práctica de programación competitiva, noté que aun había dos alumnos de segundo semestre sentados frente a una computadora. Como soy muy metiche curioso, fui a preguntar qué estaban haciendo. Su respuesta fue "Tenemos que entregar un programa de listas enlazadas".

Después de que me dijeron esto y de que los vi batallando para poder eliminar un nodo por su índice, decidí darles un tip, no decirles la respuesta como tal, pero sí ayudarlos.

Justo hace unos minutos recordé que cuando me tocó ver este tema también tuve unos problemas para entenderlo, así que en este post intentaré aportar mi granito de arena por si alguien está viendo este tema y no le queda muy claro.

De Wikipedia "...una lista enlazada es una colección lineal de elementos, llamados nodos, donde cada uno de estos apunta a otro nodo mediante un apuntador...". Cada nodo, tiene al menos dos partes: un dato y un apuntador. Dependiendo de la implementación, puede tener un apuntador más (lista doblemente enlazada).

El dato es la información que deseamos guardar en el nodo, y el apuntador es el enlace al siguiente nodo. Una lista tiene ventajas y desventajas frente a los arrays, la principal ventaja es que eliminar o insertar nodos en cualquier parte de la lista se realiza de manera muy sencilla, sin necesidad de reasignar o reorganizar la memoria. Sin embargo, como las listas son una estructura secuencial, para acceder al i-ésimo elemento de la lista, tenemos que recorrer todos los nodos desde 0 hasta i-1, por lo que para consulta de información no es una estructura que se recomiende.

Ahora, ¿cómo está compuesta una lista enlazada? La implementación más sencilla sólamente incluye la cabeza/inicio de la lista (un apuntador al primer nodo) y los nodos de la misma. Así mismo, también se incluyen las funciones para insertar y eliminar los nodos. En otras implementaciones y con motivo de mejorar el desempeño se incluye un final (apuntador al último nodo de la lista) y el tamaño de la misma.

A continuación muestro la implementación de una lista enlazada simple en C++.

Lo primero es definir nuestra estructura nodo, esta puede ser definida con un struct o con una clase. Por conveniencia usaré un struct. Para eliminar nodos, en lugar de usar delete (y por comodidad) solamente se desenlazarán estos nodos. Sin más que comentar, aquí se muestra la implementación.

Comenté lo suficiente del código como para ser entendible (según mis nervios), sin embargo, cualquier duda, comentario, queja o sugerencia pueden dejarla en los comentarios o enviarla por correo. Como siempre quiero dejar en claro que la implementación puede mejorarse.

Hasta luego.

0 Comentarios:

Publicar un comentario