malloc in c programming

aluser · 10-03-2004, 12:29 PM

Quote:

I am still a student.

me too

you'll get all this nonsense in whatever your data structures or algorithms course is. To summarize:

Arrays: Fast indexing, fast iteration small footprint, but slow appending, prepending, and insertion

Linked lists: Slow indexing, fast iteration, slightly larger footprint, fast appending*, prepending, and insertion

* but be sure to keep a tail pointer if you want to append quickly

mirradric · 10-03-2004, 01:05 PM

Quote:

Originally posted by aluser
me too

you'll get all this nonsense in whatever your data structures or algorithms course is. To summarize:

Arrays: Fast indexing, fast iteration small footprint, but slow appending, prepending, and insertion

Linked lists: Slow indexing, fast iteration, slightly larger footprint, fast appending*, prepending, and insertion

* but be sure to keep a tail pointer if you want to append quickly

Actually for linked lists, insertion at a random location (slow indexing remember) is slow due to the need to traverse the list, giving O(n) performance in the average case.

In addition linked list has the same problem with replacing the node at at particular position. An array can achieve it in constant time. You win some, you lose some.

aluser · 10-03-2004, 01:41 PM

true -- usually when you talk about insertion you assume you already have an iterator where you mean to insert.

Omarel · 10-04-2004, 02:00 PM

Yes, I know the times

Anyway the truth is as mirradric said, always u win smth but also u lose smth :P.