• Author / Uploaded
• AlejandroGallegos

• Categories
• Puntero (Programación de computadoras)
• Recuperación de información
• Programación de computadoras
• Informática
• Tecnología

Citation preview

ESTRUCTURAS DE DATOS

SEMANA 5

Listas enlazadas

Todos los derechos de autor son de la exclusiva propiedad de IACC o de los otorgantes de sus licencias. No está permitido copiar, reproducir, reeditar, descargar, publicar, emitir, difundir, poner a disposición del público ni ESTE LAdeSEMANA 5 utilizarDOCUMENTO los contenidos paraCONTIENE fines comerciales ninguna clase.

1

ESTE DOCUMENTO CONTIENE LA SEMANA 5

2

ÍNDICE

OBJETIVO ESPECÍFICO ......................................................................................................................... 4 INTRODUCCIÓN ................................................................................................................................... 4 1.

LISTAS ENLAZADAS ...................................................................................................................... 4 1.1.

CONCEPTO DE LISTA ENLAZADA ......................................................................................... 4

1.2.

OPERACIONES CON LISTAS ENLAZADAS.............................................................................. 5

1.2.1.

INSERTAR ..................................................................................................................... 5

1.2.2.

ELIMINAR ................................................................................................................... 11

1.2.3.

RECORRIDO ............................................................................................................... 14

1.2.4.

BÚSQUEDA ................................................................................................................ 16

1.2.5.

TAMAÑO.................................................................................................................... 17

1.3.

UTILIZACIÓN DE LISTAS ENLAZADAS ................................................................................. 18

1.3.1.

LISTAS ENLAZADAS SIMPLES ..................................................................................... 18

1.3.2.

LISTAS ENLAZADAS CIRCULARES ............................................................................... 19

1.4.

APLICACIONES CON LISTAS ENLAZADAS ........................................................................... 19

COMENTARIO FINAL.......................................................................................................................... 20 REFERENCIAS ..................................................................................................................................... 21

ESTE DOCUMENTO CONTIENE LA SEMANA 5

3

LISTA ENLAZADA

OBJETIVO ESPECÍFICO 

Analizar la utilización y las operaciones asociadas a listas enlazadas.

INTRODUCCIÓN Las listas enlazadas fueron creadas para intentar darle solución a diferentes problemas durante la década de los 50. A pesar de que fueron muy conocidas en sus inicios, en la actualidad se implementan solo en los bajos niveles informáticos de programación (a nivel de sistemas operativos), por lo cual es básico conocer su estructura y los diferentes puntos desde los cuales pueden ser operadas. A su vez, las listas enlazadas son más dinámicas que los arreglos, pero quizás se puedan notar más ventajas una vez que se profundice acerca de sus operaciones y aplicaciones dentro de la programación.

1. LISTAS ENLAZADAS 1.1. CONCEPTO DE LISTA ENLAZADA Se conoce como lista enlazada a aquella estructura de datos que es parecida a un arreglo, pero su método de acceso es a través de un puntero y no con un índice, por lo que se dice que la lista es un grupo o una secuencia de nodos conectados entre sí por medio de una dirección o enlace. Así como también es una estructura de datos que almacena la información de manera secuencial en una miniestructura conocida como nodo. Los nodos están compuestos por dos campos: en uno se almacena la información y en el otro se almacena la posición del siguiente nodo. Estos pueden estar almacenados en la memoria y no es necesario que estén uno detrás de otro, por lo que su inserción o extracción puede ser desde cualquier punto en la lista, es decir, que su almacenamiento en la memoria no necesariamente debe ser igual al orden en el que son enlazados.

ESTE DOCUMENTO CONTIENE LA SEMANA 5

4

Dentro del nodo, el campo que almacena la posición del siguiente nodo se conoce como puntero. Si el puntero contiene el valor null, significa que ese nodo no apunta hacia ningún otro elemento dentro de la lista enlazada, lo que puede implicar que la lista está vacía o que ese nodo es el último elemento de la lista.

1.2. OPERACIONES CON LISTAS ENLAZADAS A continuación se profundizará en la descripción de cada una de las operaciones con listas enlazadas:

1.2.1. INSERTAR La inserción de un elemento en las listas se realiza desde distintos puntos: al inicio, en el medio o al final. Por ejemplo, para realizar la inserción de un nuevo nodo en una lista, se debe conocer el dato a insertar, el puntero donde se desea insertar para recorrer la lista y realizar los cambios de punteros respectivos. Para controlar el acceso, la inserción y la extracción de datos de una lista es necesario conocer ciertos elementos: el nodo que ocupa la primera y la última posición y, en algunos casos, el número de nodos que contiene la lista.

INSERCIÓN EN LISTA SIMPLE VACÍA Se conoce que las listas enlazadas tienen una variable que se denomina primero y este valor representa el primer nodo de la lista. Ahora bien, una lista vacía tiene cero elementos dentro de sí, por lo que el puntero primero estará apuntando a un valor null. Para insertar un elemento nuevo dentro de una lista vacía, solo se debe conocer el elemento a insertar y hacer que el puntero primero apunte a este nuevo elemento insertado. A su vez, las listas tienen una variable que representa su último valor, así que si se agregó un elemento a una lista, este será el primero y el último al mismo tiempo. Al crear una instancia de tipo lista enlazada se crean dos variables con valores nulos, que indican que la lista está vacía: primero y último. El procedimiento sería más o menos este:

ESTE DOCUMENTO CONTIENE LA SEMANA 5

5

Inserción en lista simple vacía

La lista al ser inicializada, se le asignan valores null a los punteros primero y último. Al insertar un elemento este pasaría a ser el primero y último a la vez, por lo que se debe asignar la posición de las variables y, de esta manera, se inserta un elemento en una lista vacía. El nodo insertado tendrá en su puntero un valor null, lo que significa que no existe un elemento después de él. En código PHP sería así: public function InsertarPrimerovacia($elemento) { $this->head = new Nodo($elemento); $this->proximo = null; self::$count++; }

INSERCIÓN AL INICIO DE LA LISTA ENLAZADA Teniendo en cuenta la operación anterior, insertar al inicio de la lista, solo se debe hacer que el puntero del nodo nuevo apunte hacia el nodo que ocupa la primera posición de la lista y luego hacer que la variable primero apunte hacia el elemento que se desea insertar. De esta manera se desplazan los demás elementos automáticamente y el nodo que ocupaba la primera posición en la lista pasa a ser el segundo. El procedimiento sería este:

ESTE DOCUMENTO CONTIENE LA SEMANA 5

6

Inserción al inicio de una lista simple

Al insertar un elemento al inicio de la lista, posteriormente este pasaría a ser el primero, por lo que se debe asignar su posición a la variable primero. El nodo insertado tendrá en su puntero la posición del nodo que antes ocupaba la primera posición, lo que significa que existe un elemento después de él. En código PHP sería el siguiente: public function InsertarPrimero($elemento) { if ($this->head == null) { $this->head = new Nodo($elemento); } else { $aux = new Nodo($elemento); $aux->proximo = $this->head; $this->head = $aux; } self::$count++; }

ESTE DOCUMENTO CONTIENE LA SEMANA 5

7

INSERCIÓN INTERMEDIA EN LISTAS Para realizar la inserción después de cierta posición dentro de la lista, se debe tener como parámetro el elemento a insertar y la posición después de la cual se desea el nuevo elemento. Dentro del proceso, se ejecuta un ciclo que va desde el primer nodo de la lista hasta el número que se haya pasado como clave al solicitar la función. Solo se ejecuta un ciclo hasta llegar a la posición deseada y se realizan los cambios a los punteros respectivos. Aquí los punteros, primero y último, permanecen iguales a menos que alguno de los nodos que ocupan esta posición sea el que se desea eliminar. Inserción intermedia en una lista simple

ESTE DOCUMENTO CONTIENE LA SEMANA 5

8

En código PHP sería el siguiente:

public function InsertarDespues($elemento,$key){ if($key == 0){ $this->InsertarPrimero($elemento); } else{ $aux = new Nodo($elemento); $actual = $this->head; $anterior = $this->head; for($i=0;$iproximo; } $anterior->proximo = $aux; $aux->proximo = $actual; self::$count++; } }

INSERCIÓN AL FINAL DE LISTAS ENLAZADAS Para insertar un nodo al final de la lista, el puntero del nodo a insertar debe apuntar a un valor null y el puntero del nodo en la última posición debe apuntar a la posición del nuevo nodo insertado. La variable que determina la posición del último elemento de la lista ahora debe apuntar hacia el nuevo nodo insertado y, de esta manera, se inserta al final de una lista. El procedimiento sería el siguiente:

ESTE DOCUMENTO CONTIENE LA SEMANA 5

9

Inserción al final de una lista simple

En código PHP sería el siguiente: publicfunctionInsertarUltimo($elemento) { if ($this->head == null) { $this->head = new Nodo($elemento); } else { $actual = $this->head; while ($actual->proximo != null) { $actual = $actual->proximo; } $actual->proximo = new Nodo($elemento); } self::$count++; }

ESTE DOCUMENTO CONTIENE LA SEMANA 5

10

Para acceder a un nodo en la lista, esta debe ser recorrida desde el inicio, y el puntero siguiente permite el enlace hasta el próximo nodo. Dicho recorrido se hace en una sola dirección, que va desde el primer elemento hasta el último.

1.2.2. ELIMINAR La eliminación de un nodo dentro de una lista consiste en redireccionar los punteros anteriores al nodo a eliminar. De esta manera, la cadena no pierde su enlace, se libera la memoria y se mantienen las conexiones entre nodos. Existen dos tipos de eliminación en una lista: al inicio o después de cierto nodo específico.

ELIMINACIÓN NODO DE INICIO Teniendo en cuenta la definición anterior, eliminar al inicio de la lista no es más que hacer que el puntero del nodo que ocupa la primera posición de la lista apunte hacia el segundo elemento. De esta forma, el nodo que ocupaba la segunda posición en la lista pasa a ser el primero. El procedimiento sería este:

ESTE DOCUMENTO CONTIENE LA SEMANA 5

11

En código PHP sería el siguiente: public function EliminarPrimero() { if ($this->head != null) { $actual = $this->head; $this->head = $actual->proximo; } self::$count--; }

ELIMINACIÓN NODO INTERMEDIO Para realizar la eliminación después de cierta posición dentro de la lista, se debe tener como parámetro la posición después de la cual se desea eliminar el elemento. Dentro del proceso, se recibe como parámetro la posición antes del nodo que se desea eliminar y se ejecuta un ciclo que va desde el primer nodo de la lista hasta el número que se haya pasado como clave al ejecutar la función. Solo se ejecuta un ciclo hasta llegar a la posición deseada y es allí donde se realizan los cambios a los punteros respectivos. El puntero en la posición recibida como parámetro ahora debe apuntar al elemento después de su siguiente posición, saltando una posición y dejando solo al nodo que se desea eliminar. Aquí los punteros primero y último permanecen iguales a menos que alguno de los nodos que ocupan esta posición sea el que se desea eliminar.

ESTE DOCUMENTO CONTIENE LA SEMANA 5

12

Eliminación intermedia en una lista simple

En código PHP sería el siguiente: public function EliminarDespues($key){ if($key == 0){ $this->EliminarPrimero($elemento); } else{ $actual = $this->head; $anterior = $this->head; for($i=0;$iproximo; } $anterior->proximo = $actual->proximo; self::$count--; } }

ESTE DOCUMENTO CONTIENE LA SEMANA 5

13

1.2.3. RECORRIDO El recorrido de una lista se hace desde el primer nodo dentro de la lista hasta el último, siempre y cuando la lista no se encuentre vacía. A continuación, se realizará la creación de una lista, se insertarán nodos y se imprimirá la lista al final con todos sus elementos, donde la función imprimir recorrerá toda la lista. En código PHP sería el siguiente:

Sea el caso de la sentencia, la salida sería la siguiente:

1.2.4. BÚSQUEDA Para realizar una búsqueda de un dato dentro de una lista, se debe recibir como parámetro el dato a buscar y comenzar a recorrer la lista desde la posición cero, que es el primer elemento de la lista, hasta el último. Esto se realiza a través de un ciclo que va desde cero hasta el contador actual de elementos de la lista que se obtiene al ejecutar la función determinada para contar los nodos. Una

ESTE DOCUMENTO CONTIENE LA SEMANA 5

16

vez que se tengan estos datos, se comparan nodo a nodo con el parámetro recibido hasta que se encuentre el nodo o hasta llegar al final de la lista y no haberlo encontrado. En código PHP sería el siguiente: publicfunctionBuscarDato($elemento) { $encontro = false; $contador = $this->ContarNodos(); $actual = $anterior = $this->head; for($i=0;$idato == $elemento) { $encontro = true; $posi = $i; break; } else { $anterior = $actual; $actual = $actual->proximo; } } if ($encontro != false){ echo "El elemento se encuentra dentro de la lista en la posicion: ".$posi; } else { echo "El elemento no se encuentra dentro de la lista."; } }

1.2.5. TAMAÑO El tamaño de la lista es dinámico debido a que va aumentando a medida que se van insertando elementos dentro de una lista. A diferencia de los arreglos, al crear una instancia de tipo lista solo se inicializan los punteros primero y último, y de ahí en adelante se agregan nodos de acuerdo a lo que necesite el usuario. Para el caso de determinar la cantidad de elementos dentro de una lista basta con contar sus elementos a través de una función incorporada en PHP conocida como count. Esta función retorna un valor de tipo entero que representa la cantidad de nodos dentro de la lista.

ESTE DOCUMENTO CONTIENE LA SEMANA 5

17

En código PHP sería: public function ContarNodos() { return self::$count; }

Para conocer más funciones disponibles en PHP, puede revisar el siguiente enlace. Funciones de arrays

1.3.UTILIZACIÓN DE LISTAS ENLAZADAS Existen dos tipos de listas: las simples y las circulares. Dependiendo de su uso y de la disponibilidad de memoria para su implementación se utiliza la que mejor se ajuste a lo que se requiera.

1.3.1. LISTAS ENLAZADAS SIMPLES Una lista enlazada simple representa una estructura de datos lineal, pero el orden de sus nodos no es necesariamente igual al espacio que ocupan en memoria. Además es dinámica, pues va creciendo dependiendo de lo que se vaya necesitando. Se puede insertar o eliminar un elemento desde cualquier punto de la lista, pero de igual manera consume recursos debido a que, para realizar alguna operación con ella, se debe recorrer la lista hasta llegar al punto de inserción, búsqueda o eliminación, el cual puede estar al inicio, centro o final de la lista. Mantiene dos valores importantes que son: primero y último, los que representan respectivamente al primer y al último nodo de la lista. Su utilización dependerá de si se necesita controlar el inicio y fin de la lista, y este tipo de lista lo permite gracias a los valores anteriormente mencionados.

ESTE DOCUMENTO CONTIENE LA SEMANA 5

18

Ejemplo: Lista enlazada simple

1.3.2. LISTAS ENLAZADAS CIRCULARES Una lista enlazada circular generalmente se implementa cuando se dispone de poca memoria y no se necesita una estructura lineal para su implementación. Los nodos primero y último están enlazados debido a que el último no apunta hacia un valor null, sino hacia el primero. Para recorrer este tipo de lista se puede comenzar desde cualquier nodo y regresar al mismo, al terminar el recorrido. Se puede decir que la lista circular no tiene un inicio y un fin. Ejemplo: Lista enlazada circular

1.4. APLICACIONES CON LISTAS ENLAZADAS Las aplicaciones de las listas van a depender de lo que se necesite y de los recursos que se dispongan. Por ejemplo, si se necesita control sobre los últimos elementos insertados y además tener un inicio y un fin, se debe usar una lista enlazada simple. Si, por el contrario, se necesita accesar una lista desde cualquier nodo y no es necesario tener un inicio y un fin, se puede implementar una lista enlazada circular. En ambos casos sus implementaciones van más allá de su estructura, pues se puede implementar muy bien un arreglo o una cola utilizando una lista, siempre y cuando se conozcan y se diferencien sus operaciones y limitaciones. En la actualidad no se encuentran muchas aplicaciones que utilicen las listas enlazadas como tipo de estructura de datos, debido a su alto consumo de memoria y su alto costo de recorrido. Sin embargo, se utilizan en los buffers de los servidores, para consumir datos y, a su vez, recuperar memoria utilizada, o en la distribución y organización de los ficheros de un sistema operativo.

ESTE DOCUMENTO CONTIENE LA SEMANA 5

19

COMENTARIO FINAL Las listas enlazadas tienen un beneficio con respecto a los arreglos y es que el orden de sus elementos, los cuales permanecen enlazados a través de punteros, puede ser diferente al orden en el que son almacenados en memoria. Esto permite que su recorrido sea diferente al de su almacenamiento. Se pueden insertar o eliminar elementos desde cualquier punto de la lista, pero su acceso no es igual debido a que se debe recorrer toda o parte de la lista para realizar alguna operación. A pesar de que son muy útiles y de fácil implementación, pueden llegar a consumir muchos más recursos de los necesarios, por ejemplo, a la hora de ejecutar una búsqueda. Es por ello que se debe tener en cuenta el uso de recursos a la hora de una implementación eficiente.

ESTE DOCUMENTO CONTIENE LA SEMANA 5

20

REFERENCIAS Campos, J. (1995). Estructuras de datos y algoritmos. 1.ª edición. España: Prensas Universitarias de Zaragoza. Franch, X. (1999). Estructuras de datos. Especificación, diseño e implementación. 3.ª edición. España: Ediciones UPC. Hernández, R.; Lázaro, J.; Dormido, R. y Ros, S. (2001). Estructuras de datos y algoritmos. España: Prentice-Hall.

PARA REFERENCIAR ESTE DOCUMENTO, CONSIDERE: IACC (2016). Listas enlazadas. Estructuras de Datos. Semana 5.

ESTE DOCUMENTO CONTIENE LA SEMANA 5

21

ESTE DOCUMENTO CONTIENE LA SEMANA 5

22