Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!iuvax!purdue!decwrl!hplabs!hpfcdc!marc
From: marc@hpfcdc.HP.COM (Marc 'Sphere' Sabatella)
Newsgroups: comp.lang.misc
Subject: Re: flexible arrays
Message-ID: <5160013@hpfcdc.HP.COM>
Date: 1 Feb 89 00:20:11 GMT
References: <21@euteal.UUCP>
Organization: HP Ft. Collins, Co.
Lines: 28

/ hpfcdc:comp.lang.misc / mart@euteal.UUCP (Mart van Stiphout) / 10:57 am  Jan 30, 1989 /

>What I really like are arrays. They have numerous advantages:
>1. they can be processed easily.

This is subjective.

>2. elements can be accessed randomly in a cheap manner.

This is not always a necessity - for many applications, sequential access is
sufficient.

>3. you don't have to mess around with pointers.
>4. you don't have to allocate memory.

There are disadvantages too.  Say you have an array of 1000 elements, and you
want to insert a new one at position 10.  You have to copy 990 elements to
do this (OK, you could move the first 10 down, if your language supports the
memory management necessary).  Unless you use pointers, this means moving 990
objects which may be of arbitrary size.

Even appending to an array via realloc() may be expensive if it has to copy the
old data into the new block.

The pain of using linked lists is lessened by Lisp, which does all the right
allocation, 'next' (cdr) pointer, etc. for you.  However, you can right a
fairly nice linked list manager in C, Pascal, or Ada that will make them
almost as painless, and certainly more efficient than arrays for many tasks.