PureBasic Forums - English

Hi

can someone explain ( in simple terms ) the benefit of linked lists over Arrays. Is it the advantage in the fact that linked lists dont need to be dimensioned?

thanks

yep, and you can insert stuff anywhere without having to move elements of the arrays (as pb is doing that for you)

personally i often end up using arrays instead of linked lists despite the dimensioning...

With an array, the nedded memory will be located at the start of the application. With a linked list, no memory is needed first when 0 elements are added. And even if you add an element, only the memory needed for this one element is now in use. So it's more flexibel and more dynamically as an array. But if you anyway need a fix number of elements, an array is the better choice because it's faster.

Linked list implemented IN AN ARRAY is typically IMHO a (or "the") most practical solution.

spongehammer wrote:Hi

can someone explain ( in simple terms ) the benefit of linked lists over Arrays. Is it the advantage in the fact that linked lists dont need to be dimensioned?

thanks

cant explain right now.. too tired.. but linked lists are easier to work
with, actually quite fun ..

[edited until further notice]

- np

Hi NoahPhense,

and if you'd like, i have read/write speed tests to prove that linked lists
are a lot faster..

It would be neat if you could show us some tips and tricks with getting speed up on linked lists, as they are great.

But everything I have done with linked lists (and volumes of data) has proved to be slower than arrays or memory/structure approaches.

Thanks.

Dare2 wrote:Hi NoahPhense,

It would be neat if you could show us some tips and tricks with getting speed up on linked lists, as they are great.

But everything I have done with linked lists (and volumes of data) has proved to be slower than arrays or memory/structure approaches.

Thanks.

Hey D2,

I think I might have made a mistake. The tests I ran, compared the
speeds of linked-lists and arrays against another basic language.

My apologies. But now that you mention speed issues, I will look into
expanding my tests to possibly speed up lists.

- np

thanks all for the response.

my needs are pretty simple as far as data manipulation goes, and if linked lists are slower then i will probably stick with arrays.

Suitably sized array's avoid dynamic alloc/dealloc which saves some time but you may find this is insignificant compared to the efficiency of your own code. Memory is another concern: LL's can obviously grow and shrink but may fragment memory over time (making it difficult/impossible to allocate large chunks). PB arrays don't appear to be re-dim'able without losing contents but 2 secs thinking and the solution is obvious and easily implemented: copy array mem to temp mem bank, redim and copy back... now you have the best of both worlds Final tip: arrays are easy to spool to a file (auxillary data aside).

i think arrays are always faster, i'm quite interested in dare2's example...

One thing to consider is that a linkedlist which stores only small amounts of
data per item (for example just "NewList MyList.l()" are not good, because
each item requires 8bytes of extra space.
An Array (in PB) also needs a few extra bytes, but only once per array, not
once per item.

When you need to access items by their index, LinkedLists are horribly
slow, because they need to count throug all items to get to the one you want.
An array can directly index each item.

Timo

freak wrote: When you need to access items by their index, LinkedLists are horribly
slow, because they need to count throug all items to get to the one you want.
An array can directly index each item.
Timo

Are you saying that PureBasic's command:

SelectElement(LinkedList(), Position)

is doing just that

And I thought Fred is setting an index...

variables, arrays, structures, linked lists... All have their pros & cons.

Don't think there is a general rule, to be able to say one is better than the other.

If my program needs to access all elements I would favour linked lists, if I only need to access random/selected elements I would use arrays or structs

If you need to sort often, arrays are easier and much faster. On the other hand if you don't know before hand the number of elements you'll need linked lists seems a better option.

So the best option is to use whatever best suits your program.

If you are planning on using strings, stay far away from Linked Lists as possible, unless you like memory leaks

fsw wrote:

freak wrote: When you need to access items by their index, LinkedLists are horribly
slow, because they need to count throug all items to get to the one you want.
An array can directly index each item.
Timo

Are you saying that PureBasic's command:

SelectElement(LinkedList(), Position)

is doing just that

And I thought Fred is setting an index...

Yes, it does exactly that.
The list is linked together dinamically, which means, there is no way to
tell where in memory Item number x is located, unless you have the
previous or the next element. So the only way to find item number x
is to start at the first one, and do a 'NextItem' x times.

There was a speed test somewhere in the forum about this not long
ago i think.

In an array, you can directly calculate the memory position at position x,
because they are all stored one after another.

Timo