Listas enlazadas 


Una lista enlazada es un conjunto de elementos llamados nodos en los que cada uno de ellos contiene un dato y también la dirección del siguiente nodo,donde el orden de los mismos se establece mediante punteros.

La idea básica es que cada componente de la lista incluya un puntero que indique donde puede encontrarse el siguiente componente por lo que el orden relativo de estos puede ser fácilmente alterado modificando los punteros lo que permite, a su vez, añadir o suprimir elementos de la lista. El primer elemento de la lista es la cabecera, que sólo contiene un puntero que señala el primer elemento de la lista.
El último nodo de la lista apunta a NULL (nulo) porque no hay más nodos en la lista. Se usará el término NULL para designar el final de la lista.




Comentarios

Publicar un comentario

Entradas populares de este blog

Imagen
Tipos de listas enlazadas  Listas doblemente enlazadas : Un tipo de lista enlazada más sofisticado es la lista doblemente enlazada o lista enlazadas de dos vías. Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL si es el primer nodo; y otro que apunta al nodo siguiente, o apunta al valor NULL si es el último nodo. En algún lenguaje de muy bajo nivel, XOR-Linking ofrece una vía para implementar listas doblemente enlazadas, usando una sola palabra para ambos enlaces, aunque esta técnica no se suele utilizar. Listas enlazadas circulares: En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas ...
Leer más
 Ventajas y desventajas de las listas enlazadas  Ventajas  Es muy sencillo implementar pilas y  colas  usando listas enlazadas. Las  tablas hash  (usadas en diccionarios o mapas) tienen sus elementos distribuidos en un array gigante, donde los elementos colisionados pueden estar almacenados en una lista enlazada. Podrían estar almacenados en un array dinámico, pero el proceso de rehashing (cuando cambian las dimensiones del array gigante de la tabla hash) es más eficiente reusando los nodos de la lista enlazada. Cuando tienes un conjunto de elementos del que quieres remover algunos elementos dependiendo de alguna condición. Removerlos de una lista enlazada consiste simplemente en destruir el elemento preciso y actualizar los enlaces de sus nodos siguiente y anterior adecuadamente. Removerlos de un array dinámico implicaría recorrer todos los elementos siguientes en cada eliminación, mucho menos eficiente. Desventajas  Utilizan más memoria que los ...
Leer más