Take the 2-minute tour ×
Unix & Linux Stack Exchange is a question and answer site for users of Linux, FreeBSD and other Un*x-like operating systems.. It's 100% free, no registration required.

So the title is somewhat misleading... I'll keep this simple: I'm comparing these two data structures:

  1. An array, whereby it starts at size 1, and for each subsequent addition, there is a realloc() call to expand the memory, and then append the new (malloced) element to the n-1 position.

  2. A linked list, whereby I keep track of the head, tail, and size. And addition involves mallocing for a new element and updating the tail pointer and size.

Don't worry about any of the other details of these data structures. This is the only functionality I'm concerned with for this testing.

In theory, the LL should be performing better. However, they're near identical in time tests involving 10, 100, 1000... up to 5,000,000 elements.

My gut feeling is that the heap is large. I think the data segment defaults to 10 MB on Redhat? I could be wrong. Anyway, realloc() is first checking to see if space is available at the end of the already-allocated contiguous memory location (0-[n-1]). If the n-th position is available, there is not a relocation of the elements. Instead, realloc() just reserves the old space + the immediately following space. I'm having a hard time finding evidence of this, and I'm having a harder time proving that this array should, in practice, perform worse than the LL.

Am I wrong in my assumptions??

share|improve this question

closed as off topic by Warren Young, phunehehe, Michael Mrozek Sep 30 '10 at 8:34

Questions on Unix & Linux Stack Exchange are expected to relate to Unix or Linux within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

3  
I think you might consider posting this on Stack Overflow if you don't get an answer after a little while. –  Steven D Sep 30 '10 at 2:02
    
This relates to Unix's realloc function specifically. If I wanted performance comparisons between Arrays and Lists, I would post on Stack Exchange. –  Jmoney38 Sep 30 '10 at 12:41
    
Try doing an insertion sort of say 100,000 random words into each and compare the times. Once I reduced the time required for an operation from hours to seconds just by changing the type of list used. –  Bill K Mar 20 at 4:35

Browse other questions tagged or ask your own question.