using arrays vs using lists

Hello, I am probably in the process of starting to use object orientation, since it finally convinced me that it can be helpful, and I want to write decent code without having to pass and get back tons of stuff into functions (my hacking approach recently was not using functions at all, but it lead to some admittedly awful stuff).


I was wondering what were the advantages of using lists (which I'm not familiar with and that look a bit dodgy to me...) versus using arrays. It looks that you can do everything you do with lists also with arrays (of objects) without too many problems.

If I understand correctly, lists are good because you can change their sizes dynamically through the addition and removal of elements, unlike arrays which are of fixed length. However, arrays allow you to access any element within them via their indices, whereas with lists, you must iterate through the elements until you find the one you want.

Can someone confirm this?

Ryan

My own preferences on what to use are :

1. When the data is fairly constant and I need quick access to individual elements I use arrays. eg. Storing the map data for a game level. This data doesnt need to change but I need to access specific tiles for a given x,y co-ordindate all the time.

2. Where I just need to store a group of things. Just a collection if 'things' and the contents of the group changes a lot and the only processing I perform is done to the whole group I will use a list. So.. for example shots/bombs etc. When the player fires a shot I add an entry to the shots list. Each game cycle I go through each shot and update it / check for collisions. If I need to destroy it I just remove it from the list. When updating the screen I need to display them all. I am never interested in keeping track of individual shots. My player just fires them and they do thier own thing.

@Ryan
i thought that with arrys you could sclice* them i.e. copy parts of an arry but i tink you can resize them doing this as well.

It depends on what you want to put in the lists. If you need to alter or sort your contents alot then a list is the way to go. Also lists make it easier to add items to it especialy at the beginning of the list.

Arrays are better for tasks that require accessing arbitrary elements quickly. There a little quicker to loop through because linked lists always have a little overhead, but it's quite small. They are also dynamic and easily resized using slices. It has to be done manually however.

Local array:Int[]
Repeat
	array=array[..array.length+1]
	array[array.length-1]=New Int
	array[array.length-1]=Rand(1,100)
Forever

I've always prefered using arrays, but it always depends on what you want to use it for.

I'd imagine adding/removing items in a list would be faster than slicing an array.

A list is a good datastructure for any ammounts data where the ammount is difficult to predict. They are most suitable for sequential access (constant time) to data that you cannot say with any degree of certainty how much storage you'll need in advance. Random access however is in linear time.

Manipulating items, by sorting and such is also done in constant time, because you're only changing the individual links, and theres no need to copy any data back and forth.

Arrays on the other hand are good for itams that you know for a fact the maximum number of objects you'll ever have in play. They are also good because sequential and random access can both be done in constant time. However manipulating objects, sorting, compressing, moving and so on is rather expensive - at best linear time.

So you would pick the type of data structure that most closely matches what you're trying to acheive. Any LISP programmer will tell you the list is better - all problems can be solved using lists. And while that is technically true - it's not always fastest.

It looks to me that by using arrays you are avoiding memory leaks at all

I was wondering: is it possible to make a memory leak without using lists?

Neither give memory leaks. Arrays will reserve a set ammount of memory (and that's all you get). Lists reserve memory as nessecary.

It is generally not possible to make a memory leak at all in a garbage collected language, unless doing so intentionally.

In BlitzMAX the only memoryleak gotchas is cyclic data structures, and not properly releaseing non-typesafe handles.

This is how I visualise them.



Also notice the hashtable which is a combination of an array & linked lists.
It use the array as an index for the linked lists which makes searching in linked lists ALOT faster.

You sure about that?
I belive there is currently a memory leak issue related to *when* you call flushmem. i.e. call it in the wrong place and it will never free certain objects.

It's not a memory leak as such, but rather a limitation in the design of the garbage collector. The BlitzMAX garbage collector does not find root objects like traditional garbage collectors do. Instead it works by counting references.

They way I understand it is, when you invoke flushmem the garbage collector will not be able to tell if references above it in the heap represent alive or dead objects, so will simply assume that they're alive, only collecting dead references below it.