|
forums.silverfrost.com Welcome to the Silverfrost forums
|
View previous topic :: View next topic |
Author |
Message |
Michael_Connelly
Joined: 13 Jul 2017 Posts: 10 Location: Sandusky, OH
|
Posted: Fri Jan 14, 2022 5:15 am Post subject: dangling pointers in linked lists? |
|
|
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 |
|
|
mecej4
Joined: 31 Oct 2006 Posts: 1886
|
Posted: Fri Jan 14, 2022 11:33 am Post subject: |
|
|
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 |
|
|
|
|
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
|