[Game Programming Galaxy]
                                  [Logo]
                            [Lists vs. Arrays]

                                  Preface

Linked lists are a fine thing, but sometimes the overhead introduced by
them is just not worth the effort. Searching and dereferencing linked list
items is much slower than array operations, and sometimes the array takes
less space- even if the list consits of just some view items.

                                   Arrays

We all know arrays. They consit of more or less memory aligned linarly to
store items of the same size. The drawback is, that the size of an array is
fixed. If it's full, and you want to add more data, all you can do, is to
create a larger array, then copy the items to the new array and
finally free the memory of the first one. Or, you could try to
allocate an array which is big enough to hold the maximum possible amount
of data, but if you then store just a few items, you waste memory. Take a
look the image to the right: 8 items are used, 4 still free. To insert
items in the middle of the array, you have to move forward all the
succeeding items by the amout of bytes inserted. So arrays seem to be only
practical, if you mainly add/ delete items at the end. The good thing with
arrays is, that you can access each item directly, that stepping through it
is rather simple and storing/ loading from disk is really easy.

                                Linked Lists

The linked list is made of nodes, containing the data (or a pointer to the
data) and a pointer to the next node. The end of the list is marked by a
NULL- pointer. Take a look at the image below, to get a picture :) of this
structure
                                  [Image]

Inserting new nodes to the list is quite easy, since all you have to do is
to change two pointers. To insert node B between the nodes A and C, all you
have to do is to set B's pNextNode pointer to the address of node C, and
node A's pNextNode pointer to the address of node B. Easy. Searching the
list is somewhat slow, since you have to search all node sequentially.

                            The Memory Question

Pointers need memory. In our days, this means each pointer needs 4 bytes.
Since most maps will always contain at least 1 tile, this means 8 bytes for
the pointers alone. Or, in other words: Storing 9 layers with an array
takes less memory than one layer using a linked list (8 bytes pointer, 1
byte data). Or, if you need more than 256 tiles per map, you could store 5
layers, since the 8 bytes for the pointers stay plus 1 Word for the data =
5 Words. I guess, the average map has at least 2 tiles per position, giving
you 12 bytes for pointers and 2 (or 4) bytes for data = 14 (16) bytes. This
would allow you to store 14 tile layers a 1 byte, or 8 layers of word- size
tiles. And that should be more than enough for even the very sophisticated
games.

                                 In Closing

Don't misunderstand me: Linked List are a fine thing - but they are not the
best solution for tile based maps. It could make sense to use them to store
the active (visible) sprites, or the inventory or menu structures, but it
does IMHO not make sense to use them for RPG maps.

      [Image]              [Image]              [Image]

  ------------------------------------------------------------------------
                              | What's New? |
      | Design | Tutorials | Projects | Tools | Genres | Tile based |
                               | Link Page |
  ------------------------------------------------------------------------

                Designed and maintained by Lennart Steinke
                        lennart_steinke@bigfoot.com

                            Hosted by GeoCities
                                                    [Welcome to GeoCities!]