Actividad 2
Actividad 2
LISTAS DOBLEMENTE LIGADAS
1. Definir que son listas simplemente ligadas y para que se utilizan
2. Definir que son listas doblemente ligadas y para que se utilizan
3. Diferencias y similitudes entre las Listas Simplemente Ligadas y Listas Doblemente Ligadas
SOLUCION
1. Definir que son listas simplemente ligadas y para que se utilizan
1 Listas
Material multimedia recomendado:
• Listas ligadas: https://www.youtube.com/watch?v=2YPMA1p5KoM
1.1 Definici´on
En esta secci´on se presentar´a la representaci´on se secuencias por medio de listas ligadas. Podemos pensar
en una lista ligada como si fuera una cadena, donde cada eslab´on almacena un elemento, y tambi´en
tiene una referencia al siguiente eslab´on. Una lista ligadas esta compuesta de nodos los cuales almacenan
alg´un elemento de inter´es, que pod´ıan ser n´umeros enteros, caracteres, estructuras, u objetos. Para
efectos pr´acticos en este cap´ıtulo utilizaremos listas ligadas compuestas de nodos que almacenan n´umeros
enteros. Las listas ligadas pueden clasificarse en listas ligadas simples y listas doblemente ligadas, las
cuales estudiaremos m´as adelante. Otra variante de las listas ligadas son las listas circulares.
Una posible definici´on de lista ligadas es la siguiente:
Lista ligada: Secuencia finita y ordenada de datos conocidos como elementos o nodos. Ordenada en el
sentido de que cada elemento tiene una posici´on (´ındice) en la lista.
Notaci´on: < a0, a1, · · · , an−1 > para los n elementos de la lista A.
Las siguientes definiciones nos ayudar´an a tener una mejor representaci´on clara de listas ligadas:
Lista vacia: Cuando no tiene elementos.
Longitud ´o lenght: Se refiere al n´umero de elementos en la lista.
Head: Se refiere al primer elemento de la lista.
Tail: Se refiere al ´ultimo elemento de la lista.
Puede o no haber relaci´on entre el valor de un elemento y su posici´on en la lista (listas ordenadas o
no ordenadas).
Para indicar la posici´on actual en la que nos encontramos dentro de la lista podemos utilizar el operador | (indicador de posici´on). Por ejemplo:
Sea la lista: < 20, 23|12, 15 >
La posici´on en la cual estamos trabajando es entre el par de nodos 2 y 3, los cuales almacenan
los valores 23 y 12 respectivamente. No hay que confundir los nodos con los elementos (valores) que
almacenan. Los accesos a los datos de la lista se realizan con base en la posici´on de —. El s´ımbolo |
divide a la lista en una partici´on derecha y una izquierda. La longitud de la partici´on izquierda crece
conforme el indicador se mueve hacia la derecha. A continuaci´on se presentan las operaciones que se
pueden realizar sobre una lista.
Aporte personal : Las listas ligadas son estructuras de datos donde cada "nodo" almacena un valor y una referencia al siguiente nodo. Imagina una cadena donde cada eslabón tiene un dato y apunta al siguiente eslabón. En este capítulo, nos enfocaremos en listas ligadas que solo guardan números enteros. Existen listas ligadas simples, doblemente ligadas y circulares.
Una lista ligada puede estar vacía o tener una longitud que indica cuántos elementos tiene. El primer nodo se llama "head" y el último "tail". La posición en la lista se puede marcar con el símbolo "|". Por ejemplo, en la lista <20, 23|12, 15>, el indicador está entre los valores 23 y 12. Es importante distinguir entre los nodos y los valores que contienen. Las operaciones en listas ligadas se basan en la posición de los nodos.
Fuente: https://technodyan.com/wp-content/uploads/2018/01/lista.png
Chio Code. (2023, 25 mayo). ¡Aprende Paso a Paso Como Usar Listas Enlazadas! [Vídeo]. YouTube. https://www.youtube.com/watch?v=qk67wS7WYxo
2. Definir que son listas doblemente ligadas y para que se utilizan
En ciencias de la computación, una lista doblemente enlazada es una estructura de datos que consiste en un conjunto de nodos enlazados secuencialmente. Cada nodo contiene tres campos, dos para los llamados enlaces, que son referencias al nodo siguiente y al anterior en la secuencia de nodos, y otro más para el almacenamiento de la información (en este caso un entero). El enlace al nodo anterior del primer nodo y el enlace al nodo siguiente del último nodo, apuntan a un tipo de nodo que marca el final de la lista, normalmente un nodo centinela o puntero null, para facilitar el recorrido de la lista. Si existe un único nodo centinela, entonces la lista es circular a través del nodo centinela.
El doble enlace de los nodos permite recorrer la lista en cualquier dirección. Mientras que agregar o eliminar un nodo en una lista doblemente enlazada requiere cambiar más enlaces que en estas mismas operaciones en una lista enlazada simple, las operaciones son más simples porque no hay necesidad de mantener guardado el nodo anterior durante el recorrido, ni necesidad de recorrer la lista para hallar el nodo anterior, la referencia al nodo que se quiere eliminar o insertar es lo único necesario.
colaboradores de Wikipedia. (s. f.). Wikipedia, la enciclopedia libre. https://es.wikipedia.org/wiki/Wikipedia:Portada
Aporte personal : En informática, una lista doblemente enlazada es una estructura de datos formada por nodos conectados entre sí. Cada nodo tiene tres partes: una que apunta al siguiente nodo, otra que apunta al nodo anterior, y una tercera que guarda un dato, en este caso un número entero. El primer y el último nodo apuntan a un nodo especial (o "nulo") que indica el final de la lista. Si solo hay un nodo especial, la lista es circular.
Gracias a los enlaces dobles, se puede recorrer la lista en ambas direcciones. Aunque agregar o eliminar nodos puede ser más complicado porque se deben actualizar más enlaces que en una lista simple, es más fácil trabajar con ella porque no es necesario buscar el nodo anterior; solo se necesita la referencia al nodo que se va a modificar.
Pozo, S. (s. f.). Estructuras de datos: Doblemente enlazadas. © 2000 Salvador Pozo. https://conclase.net/c/edd/cap5
MonitoresUCaldas. (2013, 7 octubre). lista doblemente enlazada [Vídeo]. YouTube. https://www.youtube.com/watch?v=QecAjGZhAM8
3. Diferencias y similitudes entre las Listas Simplemente Ligadas y Listas Doblemente Ligadas
Las listas se clasifican en: Lista de enlace simple: cada nodo contiene una sola parte de enlace. Lista de enlace doble: cada nodo contiene dos partes de enlace al siguiente nodo y al anterior nodo.
La lista enlazada individualmente contiene datos y un enlace al siguiente componente. Mientras que en una lista doblemente enlazada, cada nodo incluye un enlace al nodo anterior .
Admin. (2023, 31 marzo). Difference between Singly Linked List and Doubly Linked List. BYJUS. https://byjus.com/gate/difference-between-singly-linked-list-doubly-linked-list/
Admin. (2023b, marzo 31). Difference between Singly Linked List and Doubly Linked List. BYJUS. https://byjus.com/gate/difference-between-singly-linked-list-doubly-linked-list/