forums.silverfrost.com
Welcome to the Silverfrost forums

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.

mecej4

Joined: 31 Oct 2006
Posts: 1682

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
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 All times are GMT + 1 Hour Page 1 of 1