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().