Re: You don't have to move or free pointers, fragmenting your heap.


"Jeff?Relf" <Jeff_Relf@xxxxxxxxx> wrote in message
news:Jeff_Relf_2007_Sep_27__1_30_AH@xxxxxxxxxxxx
Has anyone ever implemented a stack using a linked list ?
Who, exactly, thinks linked-lists are faster and/or better ?

I've spent years coding ( for money ) in FORTH and PostScript,
so I'm quite familiar with indexing into the array that is the stack.

In VC++ 8.0, every local variable is
an index into " the array that is the stack ",
not a journey down a linked list, not a thread.

Only one end of a stack is dynamic.
You don't have to move or free pointers, fragmenting your heap;
instead, you can create dedicated heaps and destroy them.

With a dynamic array of pointers ( instead of a linked list )
you can do things like: copy-off a chunck of pointers,
quick-sort it any way you like and do binary searches on it.

Try doing that with linked lists !

With a linked list, you can move an arbitrary length sequence elements into
a different list (splice operation) in fixed time. Try that with your
dynamic array!

As for why you might implement a stack with a linked list, what if you had a
fixed number (or fixed maximum) of objects that would be stored on different
stacks (this could be LIFO assembly line processing)? If you use dynamic
arrays, every array needs to be large enough to accommodate the maximum
possible length. With linked lists, you need only one pool of objects and
attach and detach them from the stacks, with an extra stack for the free
pool. Zero allocation and deallocation. Much less memory used.


.

Relevant Pages

  • Re: Automatic Memory Management Question
    ... // The Stack class exists in the framework under System.Collections ... // It is a linked list because Stack doesn't contain a direct reference to any other Node. ... throw new Exception("Can't Pop from an empty Stack."); ... I have used wikipedia to explore nodes and linked lists. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Stack or Heap
    ... The combination of default low stack size ... combined with a default that puts many arrays on the stack ... programmers never use arrays prefering linked lists etc. ...
    (comp.lang.fortran)
  • You dont have to move or free pointers, fragmenting your heap.
    ... so I'm quite familiar with indexing into the array that is the stack. ... You don't have to move or free pointers, ... Try doing that with linked lists! ...
    (microsoft.public.vc.language)
  • Re: Faster than link list?
    ... I'd suggest something that has less addressing overhead: stack or array. ... linked lists are still extremely fast. ...
    (comp.graphics.algorithms)
  • Re: Lets put this to rest
    ... fundamental difference in design methodology. ... Deciding whether one needs stacks, linked lists, ... exceptions that depend on particular problem contexts that haven't been ... All the things in the *specification* for stack that you were given. ...
    (comp.object)
Quantcast