Re: arrays vs linked lists

From: Patrick Dughi (
Date: 01/05/99

> i'm wondering if anybody has undertaken converting the whole
> info_storage scheme into linked lists.  or for some of you more advanced
> C coders out there, are the some advantages to the array implementation
> of which i am not aware.  with linked lists, its so much easier and
> quicker to add and delete records.  you can more easily utilize faster
> search routines(BST's etc; i realize you can implement a bst with an
> array but its really really nasty)

        Actually, its much easier to make arrays rather then linked lists,
for just about anything.  The only real downside to arrays is that
normally, they're statically allocated, so usually you make them bigger
than you could ever want, because otherwise, you could overrun them.

        Linked lists are usually dynamic - you can keep adding, and
adding.  As far as beginners are concerned, I'd say its rather easy to
create memory leaks with linked lists.  Of course, if you build up some
control functions like 'remove from list' or 'add to list', a linked list
is as simple (at the programming level) as the array.  It just takes a bit
more work to make it work as easily.

        Both of the types above can be put into any sorting algorithm
rather easily.  BST's are simple with arrays.. Incredibly easy as a matter
of fact.  Once you've written your control functions, they're just as easy
with linked lists...
        The only advantage in this situation is lookup time - arrays have
a lookup time less than or equal to linked lists... Think about it this
way, if you have all the mobs in the game, and you want to load up a mob
with a rnum of 700, you would have to go through a linked list structure
700 times before you reach your mob.  With an array, it would be
mob=mob_list[700]; (well, sorta).  Of course, searching would take the
same time, but I'd think incrementing an integer would be easier to
understand than using control functions - to a new programmer..


     | Ensure that you have read the CircleMUD Mailing List FAQ:  |
     |  |

This archive was generated by hypermail 2b30 : 12/15/00 PST