Disposing linked lists 
Author Message
 Disposing linked lists

I understand that whenever pointers are used (eg. in a linked list)
heap space is used, and that it should be freed when finished with. In
the case of linked lists, I'm unsure how to do this.

This is the common type of list I use:

type
   nodeptr = ^node;
   node    = record
        next,prev : nodeptr;
        { other list "items" }
        end;

var
   head,tail : nodeptr;

... and then the program which uses the list.

To clear the memory used, do I just dispose "head" and "tail", or do I
have to go through and dispose every node on the list?

--

Faculty Of Science, University Of Liverpool
http://www.*-*-*.com/

--

Faculty Of Science, University Of Liverpool
http://www.*-*-*.com/

Sent via Deja.com http://www.*-*-*.com/
Before you buy.



Wed, 18 Jun 1902 08:00:00 GMT  
 Disposing linked lists


Quote:
> I understand that whenever pointers are used (eg. in a linked list)
> heap space is used, and that it should be freed when finished with.

This is probably true for your current program but there can be exceptions
to your statement. Not all pointers point to objects on the heap: you can
have a pointer to almost anything in memory, whether it is on the heap or
not. And although a simple linked list will typically be constructed on the
heap, it is possible to use linked lists to organise items which are in the
data segment, in which case they are not on the heap and should not be
freed. It is also possible to use lists to organise items which are on the
heap but which are not "owned" by the list; although these are on the heap
they should be freed by their owner, not when the list is destroyed.

Quote:
> In
> the case of linked lists, I'm unsure how to do this.

> This is the common type of list I use:

> type
>    nodeptr = ^node;
>    node    = record
>         next,prev : nodeptr;
>         { other list "items" }
>         end;

> var
>    head,tail : nodeptr;

> ... and then the program which uses the list.

> To clear the memory used, do I just dispose "head" and "tail", or do I
> have to go through and dispose every node on the list?

You do every node, by just deleting (not just disposing) "head".

Assuming items are added to the list by allocating instances of node on the
heap and then inserting them into the list, you would delete them by
unhooking them from the list and then disposing them. So what happens if you
delete the first item (head^) from the list? the second item in the list
becomes the first. If you keep doing this until the list is empty, you will
have gone through and disposed every node.

Incidentally, declaring the head and tail pointers like this makes your code
a little more complicated than it needs to be. Every time you insert or
delete an item in the list, you have to check whether you are dealing with
the first and/or last item in the list, which is treated as a special case.
If 'other list "items"' don't take up an enormous amount of space, it is
better to have an instance of Node as the head/tail pointers. Your list
becomes circular, and you lose the code which would deal with the special
cases. Condition for an empty list is that head.Next = addr(head).

If you make node an object, descended from an object type which only
consists of the next and prev pointers, you can even save yourself the space
of the 'other list "items"' in the node which holds the head & tail
pointers. And you can do other nice things too, such as having a virtual
destructor. Does 'other list "items"' include one or more pointers to other
items on the heap? Must these also be freed when the node is deleted from
the list? A virtual destructor can tidy that up for you. But if you are
using objects in this way, you will have to have to use typecasts on the
next and prev pointers to access the 'other list "items"'.

FP



Wed, 18 Jun 1902 08:00:00 GMT  
 Disposing linked lists

Iain Jones heeft geschreven in bericht

Quote:
>I understand that whenever pointers are used (eg. in a linked
list)
>heap space is used, and that it should be freed when finished
with. In
>the case of linked lists, I'm unsure how to do this.

>This is the common type of list I use:

>type
>   nodeptr = ^node;
>   node    = record
>        next,prev : nodeptr;
>        { other list "items" }
>        end;

>var
>   head,tail : nodeptr;

>... and then the program which uses the list.

>To clear the memory used, do I just dispose "head" and "tail",
or do I
>have to go through and dispose every node on the list?

>--

>Faculty Of Science, University Of Liverpool
>http://www.liv.ac.uk

>--

Yes, (in most cases) you have to delete every node.
I think in your case only the first and last nodes are
disposed of, and the rest of the nodes stay in memory
with no pointer pointing to it.

procedure destroy_list;
var cursor: nodeptr;
begin
     cursor:=head;               {first node}
     while cursor<>tail do
     begin
         cursor:=head^.next;           {link to next node}
         dispose(head);          {destroy current node}
         head:=p;                     {next node becomes first
node}
     end
end; {destroy_list}

Note: not tested. Might work.

Tip: I often draw a representation of a linked list with
squares and arrows on plain paper (with head and tail
pointing sideways to it). In this way I can see the
difference between what I want to happen and what
actually happens.

Greetings. Huub.



Wed, 18 Jun 1902 08:00:00 GMT  
 Disposing linked lists
Oops. "head:=p;" should be: "head:=cursor;"
Sorry. Huub.


Wed, 18 Jun 1902 08:00:00 GMT  
 Disposing linked lists
     Please forgive me for restricting myself to Standard Pascal here.  If
you are using the function new() to create nodes, then you should use
dispose() to dispose of them.

     If "head" is a pointer to a (correctly-) linked list, then one can
discard an entire list using the following (recursive) procedure -- if the
list is empty, do nothing;
otherwise, discard the rest of the list, and then dispose of its head.  To
be "nice", you
can even have this function return a value showing what results when you
are done (it should return NIL, which you can use to conveniently "wipe
out" the pointer to the list you are discarding).

   head := discard (head);

 FUNCTION discard (headoflist : nodeptr);

 BEGIN   { discard }
   IF headoflist = NIL
    THEN discard := headoflist  { end of recursion, return NIL }
    ELSE WITH headoflist^ DO
      BEGIN
       discard := discard (next);
       dispose (headoflist)
      END
   END;

Note that if you have a doubly-linked list (as in your example), you only
need to traverse it once (in one direction).  If your list is circular,
then you can write a function "discardring" that first "breaks" the ring
(by setting an "end" pointer to NIL) and then calling "discard" with the
resulting "linear" linked list.

Bob Schor
Pascal Enthusiast

Quote:

> I understand that whenever pointers are used (eg. in a linked list)
> heap space is used, and that it should be freed when finished with. In
> the case of linked lists, I'm unsure how to do this.

> This is the common type of list I use:

> type
>    nodeptr = ^node;
>    node    = record
>         next,prev : nodeptr;
>         { other list "items" }
>         end;

> var
>    head,tail : nodeptr;

> ... and then the program which uses the list.

> To clear the memory used, do I just dispose "head" and "tail", or do I
> have to go through and dispose every node on the list?

> --

> Faculty Of Science, University Of Liverpool
> http://www.liv.ac.uk

> --

> Faculty Of Science, University Of Liverpool
> http://www.liv.ac.uk

> Sent via Deja.com http://www.deja.com/
> Before you buy.



Wed, 18 Jun 1902 08:00:00 GMT  
 Disposing linked lists


Quote:
>To clear the memory used, do I just dispose "head" and "tail", or do I
>have to go through and dispose every node on the list?

>--

>Faculty Of Science, University Of Liverpool
>http://www.liv.ac.uk

If you are using Borland/Turbo and clearing the entire list, it is
much faster to use MARK and RELEASE. THESE SHOULD NOT BE USED WITH
DISPOSE!!

You will find an example in the online HELP file.



Wed, 18 Jun 1902 08:00:00 GMT  
 Disposing linked lists

Quote:
>     Please forgive me for restricting myself to Standard Pascal here.  If
>you are using the function new() to create nodes, then you should use
>dispose() to dispose of them.

>     If "head" is a pointer to a (correctly-) linked list, then one can
>discard an entire list using the following (recursive) procedure -- if the
>list is empty, do nothing;
>otherwise, discard the rest of the list, and then dispose of its head.  To
>be "nice", you
>can even have this function return a value showing what results when you
>are done (it should return NIL, which you can use to conveniently "wipe
>out" the pointer to the list you are discarding).

>   head := discard (head);

> FUNCTION discard (headoflist : nodeptr);

> BEGIN   { discard }
>   IF headoflist = NIL
>    THEN discard := headoflist  { end of recursion, return NIL }
>    ELSE WITH headoflist^ DO
>      BEGIN
>       discard := discard (next);
>       dispose (headoflist)
>      END
>   END;

That is a very bad solution as it uses lots and lost of stack. In It
has linear stack use. When implemented with TP each call takes 10 bytes
from the stack. Since the default stack is 16K, it is limited to lists
under 1600 elements.

Recursion is a nice technique when one uses trees but with lists it is
not that useful. Same applies to other tasks like reversing list: Do
not use recursion with linked lists.

Osmo



Wed, 18 Jun 1902 08:00:00 GMT  
 Disposing linked lists


Quote:


>>To clear the memory used, do I just dispose "head" and "tail", or do I
>>have to go through and dispose every node on the list?

>>--

>>Faculty Of Science, University Of Liverpool
>>http://www.liv.ac.uk

>If you are using Borland/Turbo and clearing the entire list, it is
>much faster to use MARK and RELEASE. THESE SHOULD NOT BE USED WITH
>DISPOSE!!

No, no no. Stay away from those. They do not take any consideration what
they release. Some routines (like opening graphics) do their own
allocations. Release causes havoc on those.

Mark/release is for compatibility with implementations that do not have
dispose and instead offer this very primitive method of releasing
memory.

Nobody has such hurry that he cannot release the lists properly. If
you constantly allocate and free fixed size nodes, instead of disposing
nodes, you could put them in your own free list. That is fast.
Const freenodes:pnode=nil;

Function Freenode(p:pnode);
Begin
  p^.next:=freenodes;
  freenodes:=p;
End;

{ heap error handler }
Procedure HeapProc(x:word):integer; far;
Begin
   heapProc:=1;
End;

Function AllocNode:pnode;
var heapsave:pointer;
    p:pnode;
Begin
  if freenodes<>nil then begin
     AllocNode:=freenode;
     freenode:=freenode^.next;
     exit;
  End;
  heapsave:=heaperror;

  new(p);
  AllocNode:=p;
  heaperror:=heapsave;
End;

This also shows how to return nil when one is out of memory (instead of
RTE 203).

You could even "free" a whole list with

Procedure Freelist(first,last:pnode);
Begin
  last^.next:=freenodes;
  freenodes:=first;
End;

If one then needs to free the memory for other use (note it is not
necessary to free memory on exit)  the one could dispose the freenodes
and set it nil.

Osmo



Wed, 18 Jun 1902 08:00:00 GMT  
 Disposing linked lists


Quote:


>>To clear the memory used, do I just dispose "head" and "tail", or do I
>>have to go through and dispose every node on the list?

>>--

>>Faculty Of Science, University Of Liverpool
>>http://www.liv.ac.uk

>If you are using Borland/Turbo and clearing the entire list, it is
>much faster to use MARK and RELEASE. THESE SHOULD NOT BE USED WITH
>DISPOSE!!

>You will find an example in the online HELP file.

DISPOSE is the original WIRTH PASCAL method of recovering the heap
with linked lists. MARK/RELEASE IS NEWER AND FAR FASTER THAN THE OLDER
DISPOSE. SINCE YOU ARE TALKING ABOUT LINKED LISTS AND NOT GRAPHICS
THIS IS THE BEST WAY TO DO IT AND THERE HAVE NEVER BEEN ANY PROBLEMS
WITH USING IT WITH CONVENTIONAL LINKED LISTS BY ME ARE ANY OF MY
FRIENDS SINCE IT WAS ADDED TO BORLAND/TURBO PASCAL. WE USE IT JUST AS
THE HELP INSTRUCTS AND WILL CONTINUE TO DO SO. The qualification is
"linked lists" and "clearing the entire list." Do your own test.


Wed, 18 Jun 1902 08:00:00 GMT  
 Disposing linked lists


Quote:




>>>To clear the memory used, do I just dispose "head" and "tail", or do I
>>>have to go through and dispose every node on the list?

>>>--

>>>Faculty Of Science, University Of Liverpool
>>>http://www.liv.ac.uk

>>If you are using Borland/Turbo and clearing the entire list, it is
>>much faster to use MARK and RELEASE. THESE SHOULD NOT BE USED WITH
>>DISPOSE!!

>>You will find an example in the online HELP file.

>DISPOSE is the original WIRTH PASCAL method of recovering the heap
>with linked lists. MARK/RELEASE IS NEWER AND FAR FASTER THAN THE OLDER
>DISPOSE. SINCE YOU ARE TALKING ABOUT LINKED LISTS AND NOT GRAPHICS
>THIS IS THE BEST WAY TO DO IT AND THERE HAVE NEVER BEEN ANY PROBLEMS
>WITH USING IT WITH CONVENTIONAL LINKED LISTS BY ME ARE ANY OF MY
>FRIENDS SINCE IT WAS ADDED TO BORLAND/TURBO PASCAL. WE USE IT JUST AS
>THE HELP INSTRUCTS AND WILL CONTINUE TO DO SO. The qualification is
>"linked lists" and "clearing the entire list." Do your own test.

First: Why do you write a followup to your own message?

Second: Why do you shout?

Mark/release is a far more primitive method than dispose. Dispose
requires memory management i.e. keeping track of free blocks. This can
cause problems in implementation. In TP 5.x releasing memory could
actually decrease the amount of free heap for example. because Dispose
is so hard to implement some implementations of Pascal cut corners and
dropped dispose and instead used mark/release. TP has mark/release for
compatibility with those inferior implementations.

Mark and release work if you use the heap in a stack like manner., What
is last allocated is first released. However, many programs do not work
that way. Mark/release does not work well with those kind of programs.

Also a program,m should never use both mark/release and dispose. This
could cause serious problems.

Is there some rule that linked lists can be used only on text based
programs?

If one writes very simple programs then maybe one can get away with
Mark and release but how about writing for example a text editor with
them. What would you do when you delete a line and free, say, 57 bytes
to the heap.

Osmo



Wed, 18 Jun 1902 08:00:00 GMT  
 
 [ 10 post ] 

 Relevant Pages 

1. Help Link List, Reverse Print List Node

2. Link List , use recursive routine to reverse print the node of the list

3. Doubly Linked List problem

4. Linked Lists

5. Sorting a linked list by multiple criteria

6. Linked Lists and Pointers

7. Linked List

8. Writting and Reading a linked list from/to a file

9. Record Link List Help please

10. Linked Lists Beyond the 640kb Limit

11. delete from end of linked list

12. Student help--records, linked lists, sorting

 

 
Powered by phpBB® Forum Software