The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Linked Lists

Next ►
►

Linked lists are a fundamental data structure in computer science, used to store a collection of elements. Unlike arrays, linked lists allow for efficient insertion and deletion of elements. In Fortran, linked lists can be implemented using derived types and pointers.

Key Concepts

  1. Node Structure: Each element in a linked list is called a node. A node contains data and a pointer to the next node.
  2. Head Pointer: A pointer that points to the first node in the linked list.
  3. Traversal: The process of visiting each node in the linked list.
  4. Insertion: Adding a new node to the linked list.
  5. Deletion: Removing a node from the linked list.

Node Structure

In Fortran, we define a node using a derived type. Each node will contain an integer data field and a pointer to the next node.

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

Head Pointer

The head pointer is a pointer to the first node in the linked list. Initially, it is set to null().

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

Traversal

Traversal involves visiting each node in the linked list. We start from the head and follow the next pointers until we reach the end of the list.

subroutine traverse(head)
    type(Node), pointer :: head, current
    current => head
    do while (associated(current))
        print *, current%data
        current => current%next
    end do
end subroutine traverse

Insertion

Inserting at the Beginning

To insert a new node at the beginning of the linked list, we create a new node and set its next pointer to the current head. Then, we update the head to point to the new node.

subroutine insert_at_beginning(head, value)
    type(Node), pointer :: head, new_node
    integer :: value

    allocate(new_node)
    new_node%data = value
    new_node%next => head
    head => new_node
end subroutine insert_at_beginning

Inserting at the End

To insert a new node at the end of the linked list, we traverse to the last node and set its next pointer to the new node.

subroutine insert_at_end(head, value)
    type(Node), pointer :: head, new_node, current
    integer :: value

    allocate(new_node)
    new_node%data = value
    new_node%next => null()

    if (.not. associated(head)) then
        head => new_node
    else
        current => head
        do while (associated(current%next))
            current => current%next
        end do
        current%next => new_node
    end if
end subroutine insert_at_end

Deletion

Deleting a Node

To delete a node, we need to find the node to be deleted and update the next pointer of the previous node to skip the deleted node.

subroutine delete_node(head, value)
    type(Node), pointer :: head, current, previous
    integer :: value

    current => head
    previous => null()

    do while (associated(current) .and. current%data /= value)
        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 delete_node

Practical Exercise

Exercise: Implement a Linked List

  1. Define a derived type Node with an integer data field and a pointer to the next node.
  2. Write a subroutine insert_at_beginning to insert a new node at the beginning of the linked list.
  3. Write a subroutine insert_at_end to insert a new node at the end of the linked list.
  4. Write a subroutine delete_node to delete a node with a given value.
  5. Write a subroutine traverse to print all the elements in the linked list.

Solution

module linked_list_module
    implicit none

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

contains

    subroutine insert_at_beginning(head, value)
        type(Node), pointer :: head, new_node
        integer :: value

        allocate(new_node)
        new_node%data = value
        new_node%next => head
        head => new_node
    end subroutine insert_at_beginning

    subroutine insert_at_end(head, value)
        type(Node), pointer :: head, new_node, current
        integer :: value

        allocate(new_node)
        new_node%data = value
        new_node%next => null()

        if (.not. associated(head)) then
            head => new_node
        else
            current => head
            do while (associated(current%next))
                current => current%next
            end do
            current%next => new_node
        end if
    end subroutine insert_at_end

    subroutine delete_node(head, value)
        type(Node), pointer :: head, current, previous
        integer :: value

        current => head
        previous => null()

        do while (associated(current) .and. current%data /= value)
            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 delete_node

    subroutine traverse(head)
        type(Node), pointer :: head, current
        current => head
        do while (associated(current))
            print *, current%data
            current => current%next
        end do
    end subroutine traverse

end module linked_list_module

program test_linked_list
    use linked_list_module
    implicit none

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

    call insert_at_beginning(head, 10)
    call insert_at_beginning(head, 20)
    call insert_at_end(head, 30)
    call traverse(head)

    call delete_node(head, 20)
    call traverse(head)
end program test_linked_list

Summary

In this section, we covered the basics of linked lists in Fortran, including:

  • Defining a node structure using derived types.
  • Implementing head pointers.
  • Traversing the linked list.
  • Inserting nodes at the beginning and end of the list.
  • Deleting nodes from the list.

Understanding linked lists is crucial for mastering more complex data structures and algorithms. In the next module, we will explore file handling in Fortran, which is essential for reading and writing data to files.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2024. All rights reserved