forums.silverfrost.com Forum Index forums.silverfrost.com
Welcome to the Silverfrost forums
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

dangling pointers in linked lists?

 
Post new topic   Reply to topic    forums.silverfrost.com Forum Index -> General
View previous topic :: View next topic  
Author Message
Michael_Connelly



Joined: 13 Jul 2017
Posts: 10
Location: Sandusky, OH

PostPosted: Fri Jan 14, 2022 5:15 am    Post subject: dangling pointers in linked lists? Reply with quote

I am trying to understand linked lists one step at a time. I can make forward or backward linked lists okay. I can delete the first link in a linked list okay. Now I am attempting to delete a user chosen link in the middle of a linked list.

I assume the strategy is to keep track of three links, the prior link, the link to be deleted and the link following the one to be deleted? And then to do some bookkeeping to tie what remains together? I have attempted to do this but have a dangling pointer error that I cannot detect. I have tried several permutations of pointers in the subroutine shown with no success, clearly there is a conceptual error present that I cannot find. I hope someone can reveal my errors.

Code:

SUBROUTINE remove() !Subroutine to remove a user selected link in a linked list               

TYPE(link),POINTER::nextp,this,current
integer  ::  linkrem,k,j

IF(.NOT.ASSOCIATED(start)) RETURN  !checks if start is disassociated and thus is empty

call display() !Another subroutine to print the linked list

print '(a,i2,\)','Enter the link to be removed ',
read *,linkrem  !User chosen link to remove

nextp=>start  !Begin at the start of the list

do k=1,linkrem  !Count down to link linkrem, the link to be removed
     this=>start  !Begin at the start of the same linked list again
     if(k>1)then
       do j=1,k-1  !This counts down to the prior link
         prev_nextp=>this  !I am trying to point to the prior link
         this=>this%next
       end do
     end if
 
  current=>nextp  !current should point to the link to remove when k=linkrem is reached
  nextp=>nextp%next  !nextp should point to the link beyond the one that is being removed 

end do

DEALLOCATE(current)   !Deallocate the present link current

print *,'associated(nextp))= ',associated(nextp) !check that nextp is associated
print *,'associated(prev_nextp))= ',associated(prev_nextp) !check that prev_nextp is associated             

prev_nextp=>nextp  !Trying to point the prior link to nextp

END SUBROUTINE remove
Back to top
View user's profile Send private message
mecej4



Joined: 31 Oct 2006
Posts: 1692

PostPosted: Fri Jan 14, 2022 11:33 am    Post subject: Reply with quote

It seems a bit odd to specify the item to be deleted by its sequence number rather than by its stored value -- an attempt to treat the linked list as if it were an array, with the subscript of the item to be removed being specified.

What I suggest is that you work out the algorithm with pencil and paper using, say, a forward linked list with 5 items, before programming the algorithm. Verify that end cases are dealt with correctly, and that at the end of the operation you should still have an intact list. What happens if the link designated for removal is not present?

What struck me as wasteful is that your sketched algorithm would need N^2 operations to remove the N-th link.

Here is my sketch of what to do (UNTESTED!):

Code:
current => start
if (linkrem == 1) then
   start => current%next
   deallocate(current)
else
   do i = 1, linkrem-1           ! traverse first part
      prev => current
      current => current%next
   end do
   tocut => current
   prev%next => tocut%next       ! connect tail of first piece to head of second piece
   deallocate(tocut)             ! discard
endif


The variable "tocut" could be replaced by "current" and the statement "tocut => current" deleted, but I left it in the code to make things a little clearer
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    forums.silverfrost.com Forum Index -> General All times are GMT + 1 Hour
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group