El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Listas Enlazadas

Siguiente ►
►

Las listas enlazadas son una estructura de datos fundamental en la programación que permite almacenar una colección de elementos de manera dinámica. A diferencia de los arreglos, las listas enlazadas no requieren un tamaño fijo y pueden crecer o reducirse según sea necesario. En Fortran, las listas enlazadas se implementan utilizando tipos derivados y punteros.

Conceptos Clave

  1. Nodo: La unidad básica de una lista enlazada, que contiene un valor y un puntero al siguiente nodo.
  2. Cabeza (Head): El primer nodo de la lista enlazada.
  3. Puntero: Una variable que almacena la dirección de memoria de otro dato.

Estructura de un Nodo

En Fortran, un nodo de una lista enlazada se puede definir utilizando un tipo derivado que contiene un valor y un puntero al siguiente nodo.

type :: Node
    integer :: value
    type(Node), pointer :: next => null()
end type Node

En este ejemplo, Node es un tipo derivado que contiene un entero value y un puntero next que apunta al siguiente nodo. El puntero se inicializa a null() para indicar que no apunta a ningún nodo inicialmente.

Creación de una Lista Enlazada

Para crear una lista enlazada, necesitamos una variable que apunte al primer nodo (cabeza) de la lista.

type(Node), pointer :: head => null()

Insertar un Nodo al Inicio

Para insertar un nodo al inicio de la lista, creamos un nuevo nodo y ajustamos los punteros adecuadamente.

subroutine insertAtBeginning(head, newValue)
    type(Node), pointer :: head
    integer, intent(in) :: newValue
    type(Node), pointer :: newNode

    allocate(newNode)
    newNode%value = newValue
    newNode%next = head
    head = newNode
end subroutine insertAtBeginning

Insertar un Nodo al Final

Para insertar un nodo al final de la lista, recorremos la lista hasta encontrar el último nodo y luego ajustamos los punteros.

subroutine insertAtEnd(head, newValue)
    type(Node), pointer :: head
    integer, intent(in) :: newValue
    type(Node), pointer :: newNode, current

    allocate(newNode)
    newNode%value = newValue
    newNode%next = null()

    if (.not. associated(head)) then
        head = newNode
    else
        current = head
        do while (associated(current%next))
            current = current%next
        end do
        current%next = newNode
    end if
end subroutine insertAtEnd

Eliminar un Nodo

Para eliminar un nodo, necesitamos ajustar los punteros para excluir el nodo deseado de la lista.

subroutine deleteNode(head, valueToDelete)
    type(Node), pointer :: head
    integer, intent(in) :: valueToDelete
    type(Node), pointer :: current, previous

    current = head
    previous => null()

    do while (associated(current) .and. current%value /= valueToDelete)
        previous = current
        current = current%next
    end do

    if (associated(current)) then
        if (associated(previous)) then
            previous%next = current%next
        else
            head = current%next
        end if
        deallocate(current)
    end if
end subroutine deleteNode

Ejercicio Práctico

Ejercicio 1: Implementar una Lista Enlazada

  1. Objetivo: Implementar una lista enlazada en Fortran que permita insertar nodos al inicio y al final, y eliminar nodos por valor.
  2. Instrucciones:
    • Define el tipo derivado Node.
    • Implementa las subrutinas insertAtBeginning, insertAtEnd y deleteNode.
    • Escribe un programa principal que pruebe estas subrutinas.

Solución

program linkedListExample
    implicit none

    type :: Node
        integer :: value
        type(Node), pointer :: next => null()
    end type Node

    type(Node), pointer :: head => null()

    call insertAtBeginning(head, 10)
    call insertAtBeginning(head, 20)
    call insertAtEnd(head, 30)
    call deleteNode(head, 20)

    call printList(head)

contains

    subroutine insertAtBeginning(head, newValue)
        type(Node), pointer :: head
        integer, intent(in) :: newValue
        type(Node), pointer :: newNode

        allocate(newNode)
        newNode%value = newValue
        newNode%next = head
        head = newNode
    end subroutine insertAtBeginning

    subroutine insertAtEnd(head, newValue)
        type(Node), pointer :: head
        integer, intent(in) :: newValue
        type(Node), pointer :: newNode, current

        allocate(newNode)
        newNode%value = newValue
        newNode%next = null()

        if (.not. associated(head)) then
            head = newNode
        else
            current = head
            do while (associated(current%next))
                current = current%next
            end do
            current%next = newNode
        end if
    end subroutine insertAtEnd

    subroutine deleteNode(head, valueToDelete)
        type(Node), pointer :: head
        integer, intent(in) :: valueToDelete
        type(Node), pointer :: current, previous

        current = head
        previous => null()

        do while (associated(current) .and. current%value /= valueToDelete)
            previous = current
            current = current%next
        end do

        if (associated(current)) then
            if (associated(previous)) then
                previous%next = current%next
            else
                head = current%next
            end if
            deallocate(current)
        end if
    end subroutine deleteNode

    subroutine printList(head)
        type(Node), pointer :: head
        type(Node), pointer :: current

        current = head
        do while (associated(current))
            print *, current%value
            current = current%next
        end do
    end subroutine printList

end program linkedListExample

Conclusión

En esta sección, hemos aprendido a implementar listas enlazadas en Fortran utilizando tipos derivados y punteros. Hemos cubierto cómo insertar nodos al inicio y al final de la lista, así como cómo eliminar nodos por valor. Estas operaciones son fundamentales para manipular listas enlazadas y son la base para estructuras de datos más complejas.

En el siguiente módulo, exploraremos el manejo de archivos en Fortran, lo que nos permitirá leer y escribir datos desde y hacia archivos, una habilidad esencial para muchos programas científicos y de ingeniería.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2024. Todos los derechos reservados