Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Linked list Fortran

  1. Aug 6, 2015 #1
    CAn anyone explain how this program in Fortran on linked lists is supposed to work. Actually it does work but I can not for the life of me follow the logic behind it or what is going on. I did some Fortran programming in F77 but now with this new 'pointer' type it is about impossible to understand. I have done assembly language programming so if one could translate how this is translated to assembly language of the microprocessor then i may be able to understand. Like what memory locations and what is being put in them and what is being read from the locations.
    Code (Fortran):

    program linkedlist
        implicit none

        type :: link
            integer :: i
            type (link), pointer :: next
        end type link

        type (link), pointer :: first, current

        integer :: number

        nullify (first)
        nullify (current)

        ! read in a number, until 0 is entered
        do
            read*, number

            if (number == 0) then
                exit
            end if

            allocate (current) ! create new link
            current%i = number
            current%next => first ! point to previous link
            first => current ! update head pointer
        end do

        ! print the contents of the list
        current => first ! point to beginning of the list

        do
            if (.not. associated (current)) then ! end of list reached
                exit
            end if

            print*, current%i

            current => current%next ! go the next link in the list
        end do

    end program linkedlist
     
    One big problem is that if i change the => to just = then it does not work ! HOw can => mean anything other than = ? And if i change the statement current%i = number to
    current%i = pointer then it does NOT work. CAn anyone explain why not ? Why does
    current%i = number work and current%i = pointer NOT work.
     
  2. jcsd
  3. Aug 6, 2015 #2

    jedishrfu

    Staff: Mentor

    I adjusted your post to use fortran syntax coloring. and some indentation for readability.

    That will help other posters with reading it.

    The statement "current => current%next" assign the value of next to the current. "current%next" contains the address of the next element in the linked and so it points to the next element of the linked list.
     
    Last edited: Aug 7, 2015
  4. Aug 7, 2015 #3

    rcgldr

    User Avatar
    Homework Helper

    It might help to compare Fortran syntax for pointer usage versus the equivalent C syntax:

    Code (Text):

        integer, pointer :: ptr0_to_int
        integer, pointer :: ptr1_to_int
        allocate (ptr0_to_int)
        ptr1_to_int => ptr0_to_int
        ptr1_to_int = 5
     
    Code (Text):

        int *ptr0_to_int;
        int *ptr1_to_int;
        ptr0_to_int = malloc(sizeof(int));
        ptr1_to_int = ptr0_to_int;
        *ptr1_to_int = 5;
     
    For pointers, Fortran a => b is like C a = b, and Fortran a = b is like C *a = b.
     
    Last edited: Aug 8, 2015
  5. Aug 7, 2015 #4
    Even if you don't know Fortran (which apparently you do not), if you know what the program does, you should be able to get the gist of it with a simple detective mind. The C comparison probably does not help, not to mention is not the same as it does not include a struct with an integer and, in turn, a pointer to the same struct.

    "type link" (notice there shouldn't be :: in between) starts a custom type definition block, basically a "struct"...it is a container for other variables and objects...in this case for an integer and a pointer which can point to "link" kind of objects (like itself)...this is how you construct the link list.

    If you are new to programming, to better understand the logic you really need to follow the loop with paper and pencil for two or three iterations and noting what is what, what stores what and what points to what...this thing about re-using a variable to store a value from the current loop for use in the next loop, makes it be the value from the "previous" loop once the "next" loop is actually the "current" loop....follow? ;-)

    Think of the "type link" as a drawer with string (rope) on one side...you can put an integer in the drawer and then you can use the string to attach it to the next drawer.

    Unlike an integer which comes already with its own memory, pointers need to be allocated.

    Hope this helps.
     
  6. Aug 7, 2015 #5
    I see the current%next in the definition though I don't understand what it means but anyway...., BUT now what about the statement current%i=number ? NOwhere in the definition do I see anything with an " i " nor %i so how is this valid ?
     
  7. Aug 7, 2015 #6

    SteamKing

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

    If you've done Fortran 77 programming, you should know how old that language version is.

    Starting with Fortran 90/95, the language standard changed quite a bit, although Fortran 77 is included as a subset language to help keep older programs written in that version from having to be re-written to remain compatible with the new standard.

    These links may help you keep up to date with the new Fortran language features:

    http://www.astro.ex.ac.uk/people/saunders/computing_tutorials/fortran.pdf

    http://www.star.le.ac.uk/~cgp/f90course/f90.html

    http://www.urz.uni-heidelberg.de/Dok/Fortran90forF77.html

    There's quite a bit of new stuff to learn, and it will take more than a couple of days to do it. Good Luck!
     
  8. Aug 7, 2015 #7
    That is right I don't understand Fortran at least as far as this part of the newer version esp 'pointer' and the => . I thought i did understand for the most part Fortran77 though a bit rusty on it. I do basically understand a 'recursive' procedure at least in the simplest most direct cases but this whole thing seems like ' black magic '.
    I have done recursive programs in Maxima . If anyone is familiar or used Maxima could you write a routine in Maxima which would accomplish the same ? Or even a routine written in Fortran 77, say in free field form for simplicity, which would accomplish the same.

    About the ' :: ' I do see it works without it also. Which brings up a new question as to what exaclty does ' :: ' mean in general ? I was able to do all my programs in Fortran 77 mostly in the '90's without having to use the " :: " .
     
  9. Aug 7, 2015 #8
    Also for example could anyone write code in F77 using ' equivalence ' which would do the same ?
     
  10. Aug 7, 2015 #9

    jedishrfu

    Staff: Mentor

    Look at the type definition earlier in your program, each node of the linked list has a field called "i" as well as a field called "next" which is a pointer to another node in the linked list:

    Code (Fortran):

       type::link
           integer::i
           type(link), pointer::next
       endtype link
     
     
  11. Aug 8, 2015 #10

    rcgldr

    User Avatar
    Homework Helper

    The pointer comes with it's own memory, but not what it points to. Based on what I've seen of Fortran examples using pointers, It's an unitialized pointer when it's declared. nullify() can be used to set a pointer to NULL (is this the same as zero in Fortran?), or allocate() can be used to allocate memory and set the pointer to point to that allocated memory.
     
  12. Aug 8, 2015 #11
    Oh ;my mistake now i do see the " i " .
     
  13. Aug 8, 2015 #12
    Does this linked list take up more memory than a conventional array with the same entries ?
     
  14. Aug 8, 2015 #13
    Well, what does an array store as its values?
    What does the linked list store as its values?
    ( for the linked list see the type :: link near the top of your program. )
     
  15. Aug 8, 2015 #14
    You are correct. What I said was within the context of storing data in the pointer itself as in the example at hand (the linked list above), in these cases, you need to allocate memory using the pointer itself. Otherwise, the pointer comes ready to point to already allocated targets...where 'target' is the attribute that needs to be given to the variable/object you want to point to.

    One interesting thing that helps performance is that pointers must have a type. In other words, if you want a pointer to point to an integer, you need to indicate so in the declaration statement for the pointer. This can clearly be seen in the linked list example above: the pointer is declared with "type(link)"...this is also why you can simply use " allocate(ptr)" on a pointer and you don't have to worry about how much memory you need for the item...the compiler already knows.

    By conventional array you mean an array of one of the native types? integer? real? Because you can just as easily have an array of a user defined type. Anyway, I don't know why you are even worried about memory if what you need cannot be done with a conventional array, it is not like you have choice.

    Also, please stop using dirty words like equivalence and, please, move up to modern Fortran, we have had it for 20 years already, it is so much more...while it may be a natural progression, you really need to read up on it.
     
  16. Aug 10, 2015 #15
    Yes i mean array of native type say of integers for example I post another more direct program and see if someone can explain some of the observations I have made about it.
    ----------------------------------------------
    integer*1 i
    type link
    integer*1 i
    type (link), pointer:: next
    end type link
    type (link), pointer :: first,current
    nullify (first)
    nullify (current)

    do i=1,11
    allocate (current)
    current%i =i
    current%next =>first
    first =>current
    end do
    current => first
    do
    if (.not. associated (current)) then
    exit
    end if
    print*, current%i
    current => current%next
    end do
    end
    ---------------------------------------------------------

    First of all the numbers are printed out in descending order - opposite to the order they were put in : as if they were pushed on to a stack or something which is
    not the case here. In the loop statement it is continuously allocated over and again without ever any statement to be deallocated. How can this be done without error?
    In the statement "if (.not. associated (current)) then.." How did it ever not get associated if it ever once was ?
     
  17. Aug 10, 2015 #16
    But it is the case...you started the list from the bottom up by starting the list with %i=1 and having %next point to the "tail" (the not associated, nullified, initial first) of the list....and THEN, you moved up to %i=2 and had that point to the link with %i=1 (the one from the previous iteration) and so on...at the very end, the last link allocated and assigned %i=11 is what you had first point to right before exiting the loop and then you had current point to that...and this is the one you start printing with...
     
  18. Aug 13, 2015 #17
     
  19. Aug 13, 2015 #18
    There is also the question of for example
    integer*1:: i
    integer*1 :: j,k

    is same as putting all together in one statement as
    integr*1 :: i,j,k

    but here has:
    type (link), pointer:: next
    end type link
    type (link), pointer :: first,current

    but if do the same there like put them all together:
    type (link), pointer:: next,first,current
    get error as do when try to change the order any other way
     
  20. Aug 13, 2015 #19

    Mark44

    Staff: Mentor

    You can't put them all together. The next variable is a member of your derived type named link. The first and current variables aren't members of your derived type, so have to be declared after the declaration of the link derived type.
     
  21. Aug 14, 2015 #20
    What is the purpose of
    nullify (first)
    nullify (current)

    and why does it not make the definitions useless or cancelled ?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Linked list Fortran
  1. Linked List (Replies: 9)

  2. Linked list (Replies: 12)

  3. Java linked list (Replies: 1)

  4. Linking Fortran (Replies: 5)

Loading...