From: erc@netcom.com (Eric Smith)
Subject: Re: What is Object Oriented Programming? Is C doomed?
Organization: Netcom - Online Communication Services (408 241-9760 guest)
Date: Wed, 16 Dec 1992 21:52:51 GMT

In article <1992Dec16.145444.2130@nastar.uucp> phardie@nastar.uucp (Pete Hardie) writes:
>In article <1992Dec15.172057.6793@borland.com> pete@borland.com (Pete Becker) writes:
>>	That's certainly true, but I don't think it's a good thing.  It seems
>>to me that the important factor in using a container is understanding its
>>behavior.  A Queue and a Stack differ significantly, in that a Queue is
>>FIFO and a Stack is LIFO. You pick which one to use based on what your
>>current program requires.  Replacing a Queue with a Stack will change the
>>behavior of the program.  So I don't want them to have the same interface.
>
>By coincidence, I am working on a list-management module, that includes
>Lists, Queues, Stacks, and several other types.
>
>I am using a linked-list as the base structure, with auxiliary pointers to
>allow circular access, size limits, etc.  To make the list a Stack, I
>simply do this:
>
>#define Push(list,element) AddElementToEnd(list,element)
>#define Pop(list) RemoveElementFromEnd(list)
>
>where AddElement... and RemoveElement... are generic linked-list functions.
>
>For a Queue, I do this:
>
>#define Enqueue(list,element) AddElementToEnd(list,element)
>#define Dequeue(list) RemoveElementFromFront(list)
>
>Thus, they have the 'same' interface, in the generic functions, using the same
>data structure(s), and if I decide that the program need a queue instead of
>a stack, all I need to do is change the Push() calls to Enqueue() calls, and
>so on.
>
>If I need a fixed-size container, mimicking an array, I have functions to
>treat a linked-list as a fixed length container, with all the same data
>structures, and minimal changes need to be made to the surrounding code
>to dal with the possible error conditions that a fixed size container will
>cause over a dynamic one.
>
>-- 
>Pete Hardie:  phardie@nastar  (voice) (404) 497-0101
>Digital Transmission Systems, Inc., Duluth GA
>Member, DTS Dart Team           |  cat * | egrep -v "signature virus|infection" 
>Position:  Goalie               |


There are two major problems with doing it that way.  First, it uses
more memory than it needs to, and in some cases that can be very
costly.  For example, a stack of one million 4-byte integers using a
bidirectional linked list would take 12 megabytes or more, but could be
made to take 4 megabytes using an array, or 8 megabytes using a
unidirectional linked list.  The 2nd problem is when you use a linked
list to mimick an array.  One important use for arrays is random
access.  You can't do random access in a linked list.  (By random
access I mean the speed of accessing an element can't depend on which
element it is.)  Some applications need bidirectional random access,
i.e., random access on both putting data in the container and getting
data out of it.  But most applications that need random access only
need it on getting data out of the container.  For those applications,
you can use an array that reallocates itself when it needs to grow.
But if you need bidirectional random access, you have to allocate the
entire maximum size in advance.

To summarize, linked lists have their limits, and you can't use
bidirectional linked lists as a single catch-all implementation of
container classes for widely varied high quality software.  Instead,
the container classes should use different implementations for
different purposes, and those implementations should include linked
lists, both bidirectional and unidirectional, and various kinds of
arrays, and maybe some other structures besides linked lists and
arrays, depending on what kinds of containers you provide.
Xref: sparky alt.amateur-comp:370 comp.lang.c:18545 comp.lang.c++:18138 comp.misc:4630