Linked lists if you need O(1) insertion at the beginning and tail(). If you don't care too much about space, you can use a doubly linked list (or, just use the xor trick).
Dynamic arrays if you need O(1) insertion at the end and random access.
Name:
Anonymous2011-04-07 21:13
The dynamic array has faster indexing - array to list, O(1) versus O(n) - but the linked list performs faster insertions at the front - array to list, O(n) versus O(1) - and insertions in the middle - array to list, search time + O(1) versus O(n). Some of these speed concerns can be mitigated by using a variant of a standard dynamic array.
As a general rule, your program should use whatever is the best implementation for your intentions.
Name:
Anonymous2011-04-07 21:47
>>2 >>3
Oh, that's logical. Thanks guys. I usually use Python so I'm not used to having to make decisions like this. C is so refreshing.
>>2,3
This assumes that allocation for a node of a linked list is a constant time operation, which many times it is not, as is the case when you malloc each node. There's a fair amount of allocation overhead.
With dynamic arrays, you can allocate the array ahead of time to meet your capacity needs, or increase the dynamic array by a fixed factor when needed, thus amortizing the allocation overhead.
Furthermore, dynamic arrays have much better cache locality than linked lists, and this alone can result in much faster code. Ignoring the importance of cache coherency on modern hardware can be dangerous to the performance of your software.
You should definitely favor dynamic arrays over linked lists where you can.
If you need to insert at the beginning or middle of a sequentially data structure, and your data structure is small (a few dozen nodes or less), you should probably prefer a dynamic array unless each node itself has quite the copy overhead.
>>11
They are also easier to deal with (in C).
The big O notation doesn't take into account ``constant'' operations (like malloc), so those are just numbers. And that's also why the O(1) fibonacci can be slower than the O(logn) one, so a small dynamic array will be faster than a linked list.
Still, if you're gonna prepend lots of stuff in an already large data structure, you don't really want to do it with an O(n) operation.
Or you can use unrolled linked lists or CDR coding (especially with immutable lists), when appropriate.
But generally, yes, just use a dynamic array.
Name:
Anonymous2011-04-08 13:46
c programmers should embed python and use its highly-optimized data structures
There is no general rule. You use what suits your needs better.
If you want a queue/stack, use a linked list. If you don't need a lot of random access, linked list. If you need random access often, use an array. If you want easy insertion, use a linked list. Of course, you should use specialized functions for each type of operation you perform on the object - what works on a linked list could work on an array, but be much slower on it, and what works on an array could be terribly inefficient when using a list.
If you understand what your data will be used for and how it will be accessed, you'll know which fits your needs better.
Name:
nambla_dot_org_rules you2011-04-08 15:22
Or you can use a real programming language like Lisp...
>>1 asked about C, and even if we may think in Lisp, we still give him the answer for what he asked. In CL this is all supported by default, but you still have to make a choice if you want a linked list or an extendable vector with fill pointer.
>>16
one could argue, that C{++|99} style comments enforce indentation YHBT
Name:
Anonymous2011-04-08 16:17
>>20
Good programmers don't comment. Why commenting when meaning is obvious from the code? So, commenting is for mediocre programmers in big teams of livestock.
>>21
This man is correct. I still use comments to document non-obvious hacks and workarounds for buggy APIs and what not, but the rest of our code at work is for the most part self-documenting.
I don't comment because I'm an asshole. Additionally, I choose misleading variable names so that the client is completely lost when, after thinking he got all the variables worked out and is ready to analyze the code, he sees something like settingsFileHandle = Color.Red.
I comment what I'm doing so people will be able to know what code does without even reading it. If you work with people who know what they're doing they usually won't give a shit about how you hacked something cleverly, they're only interested in getting it over with and move on.
Did you even read what I wrote? It's so people may just read the comments, if you block up your code and briefly note what each block is doing someone may alter (if you've written ravioli code so far) only the relevant section without ever caring about the other parts of code.
I only document the interface, not the implementation. Good code should be obvious to read and understand what it does, but an interface to a library should be well documented.
My source files looks like this:
[requires]
[long comment/protodocumentation that explains what should be explained (e.g., if a function takes a specially formatted string as argument, the formatting reference goes here)]
[comment type signatures for exported symbols in dynamic typed languages]
[the code]
[provide]
>>29 I comment what I'm doing so people will be able to know what code does without even reading `>implying reading comments doesn't require reading
In other news, a person should understand most of what a codan does and how it does it before attempting to alter anything related (i.e. in the same file). The best way of doing this is to read the code. If it's ravioli code, then that's fine, as that shit's just pillows.
Name:
Anonymous2013-03-18 18:56
>>31 '>LEEEEEEEL E/G/IN IM/G/LICATION /G/ROSKI XDDDDDDDDDD LE /G/ENTOO LEEEEL
You fucking idiot. You are what's wrong with 99% of the programmers. You think you know the problem, so you apply crappy solution. How about doing some research before
Linked lists are slow as hell. Sure they seem like O(1) but in real world conditions they are terrible. They take more memory. They destroy cache. They just suck. Dynamic arrays are always faster, if you only have to insert to the end and if you do it right.
There's even no copying of data included if you use 4k (or whatever the page size is) chunks to allocate array. The OS just creates new page and puts it after your last page and the base pointer stays the same when you "realloc()".
Name:
Anonymous2013-03-19 1:32
>>39
I was thinking the same thing. If you're using C, you care about performance, in which case, why the hell is a linked list even on the table? Ain't no bit-blaster like memcpy().
Name:
Anonymous2013-03-19 4:08
For certain information, like indexed data, which can be queried. You should use some kind of tree. Red-black binary trees are quite simple to implement and have for all operations O(log n). No a hash table won't suffice here.
Because on a tree you can also do the query: give all values between 3 and 5, which is much more natural on a tree than on a hash table.
Name:
Anonymous2013-03-19 5:56
Sure they seem like O(1) but in real world conditions they are terrible.
Insertion to the start of a linked list *is* O(1). O(1) describes a rate of growth, not a duration.
>>39 Sure they seem like O(1) but in real world conditions they are terrible. They take more memory. They destroy cache.
You might need to read this so it doesn't sound like you have absolutely no clue what you're talking about. https://en.wikipedia.org/wiki/Computational_complexity_theory
Name:
Anonymous2013-03-19 6:10
>>42
Malloc implementations under heavy fragmentation would struggle to stay close to O(1). But >>39-sama seemed to be talking about constant factors for memory use and time.
>>45
Not sure what you're on about. Are you delusional?
Meanwhile you could implement dynamic arrays as linked lists of large chunks of memory. struct dyn_arr_chunk { struct dyn_arr_chunk *next; int data[PAGESIZE - sizeof(struct dyn_arr_chunk*)]; }
Then you don't need to waste your time arguing with each other.
Name:
Anonymous2013-03-19 6:21
Just curious, would you say it's better in general to do few large allocations through malloc than many small ones?
Ideally you'd allocate in multiples of page size and make sure all your data structures neatly pack into 4K chunks.
One way to get both O(1) insertion and O(1) indexing from a linked list is to build a "dynamic" array on the first indexing operation as a cache. IIRC Firefox does this for its DOM node structures.
Maybe you should describe the use case. Basicly firefox does this for its DOM node structures isn't a use case. It sounds cool though quoting "dynamic". Like you read firefox before installing.
>>49
Yes, malloc is expensive >>53
Generally you'd want a linked list of static arrays to implement a dynamic array so (when triggering a resize) you don't have to realloc and hope for another contiguous chunk of memory that is bigger than the current one you have.
Lookup is O(n/pagesize).
>>52 One way to get both O(1) insertion and O(1) indexing from a linked list is to build a "dynamic" array on the first indexing operation as a cache. IIRC Firefox does this for its DOM node structures.
Why cant Racket or Common Lisp do that?
Name:
Anonymous2013-03-19 12:10
>>1 As a general rule, should C programs use linked lists or dynamic arrays?
How abut immutable binary trees?
>>60
I dont subject myself to such abstract bullshit that only exists at compile time
Name:
Anonymous2013-03-20 12:02
>>54 you don't have to realloc and hope for another contiguous chunk of memory that is bigger than the current one you have
You don't have to hope anything. If you realloc 4k bigger block than you had before, and your last memory chunk size was divisible by 4k, it's almost certain that realloc returns the same pointer. That's because OS can just allocate new page of memory and map it after your old memory chunk.