      module city_list
      type river
         type(river),  pointer:: upstream 
         character (len=25):: city
         type(river),  pointer:: downstream 
      end type
      type(river),  pointer:: finish 
      type(river),  pointer:: start 
      type(river),  pointer:: travel 
      end module


      program detour
      use city_list
      character (len=25):: city_input
      type(river),  pointer:: temp 
      allocate(start)
      nullify(start%upstream)
      start%city = ' '
      nullify(start%downstream)
      travel=>start
      print *, " "
      print *, "Enter cities ..."
      do  
         read (unit=*,fmt=100,end=200) city_input
100         format (A25)
         temp=>travel
         travel%city = city_input
         allocate(travel%downstream)
         travel=>travel%downstream
         travel%upstream=>temp
      enddo

200      continue
      finish=>temp
      nullify(travel%downstream)
      print *, " "
      print *, "All city names have been read ..."
      print *, " "
      print *, "LIST the original tour"
      print *, "======================"
      call droute ()
      print *, " "
      print *, "REPLACE Davenport with Dubuque"
      print *, "=============================="
      travel=>start
      do  
         if (travel%city(1:4) .eq. 'Dave') then 
             travel%city = 'Dubuque, Iowa'
            exit 
           else
            travel=>travel%downstream
            if (.not. (associated (travel%downstream)))            exit 


         endif
      enddo

      call uroute ()
      print *, " "
      print *, "INSERT Hannibal between Rock Island and St. Louis"
      print *, "================================================="
      travel=>start
      do  
         if (travel%city(1:11) .eq. 'Rock Island') then 
             call city_insert ("Hannibal, Missouri       ")
            exit 
           else
            travel=>travel%downstream
            if (.not. (associated (travel%downstream)))            exit 


         endif
      enddo

      call droute ()
      print *, " "
      print *, "DELETE Vicksburg from between Memphis and Natchez"
      print *, "================================================="
      travel=>start
      do  
         if (travel%city(1:9) .eq. 'Vicksburg') then 
             temp=>travel%downstream
            travel=>travel%upstream
            deallocate(travel%downstream)
            travel%downstream=>temp
            temp%upstream=>travel
            nullify(temp)
            exit 
           else
            travel=>travel%downstream
            if (.not. (associated (travel%downstream)))            exit 


         endif
      enddo

      call uroute ()
      print *, " "
      print *, "DEALLOCATE the linked list"
      print *, "=========================="
      print *, " "
      print *, "     Cities deallocated going downstream ..."
      travel=>start
      do  
         print *, "     ",travel%city
         temp=>travel%downstream
         deallocate(travel)
         if (.not. (associated (temp%downstream)))         exit 

         travel=>temp
      enddo

      nullify(finish)
      nullify(start)
      nullify(temp)
      print *, " "
      end program


      subroutine droute()
      use city_list
      print *, " "
      print *, "     Cities passed going downstream ..."
      travel=>start
      do  
         print *, "     ",travel%city
         travel=>travel%downstream
         if (.not. (associated (travel%downstream)))         exit 

      enddo

      end subroutine

      subroutine uroute()
      use city_list
      print *, " "
      print *, "     Cities passed going upstream ..."
      travel=>finish
      do  
         print *, "     ",travel%city
         if (.not. (associated (travel%upstream)))         exit 

         travel=>travel%upstream
      enddo

      end subroutine

      subroutine city_insert(city_input)
      use city_list
      character (len=25):: city_input
      type(river),  pointer:: down,temp 
      down=>travel%downstream
      allocate(temp)
      temp%city = city_input
      temp%upstream=>travel
      temp%downstream=>travel%downstream
      travel%downstream=>temp
      down%upstream=>temp
      nullify(down,temp)
      end subroutine

