C Language

JC0133

Senior member
Nov 2, 2010
201
1
76
Does C have a pre defined linked list, double linked list or circular linked list function?

I been googling Double Linked List and Circular Linked Lists, do you guys know of any good sources(websites, youtube, etc) that do a good job explaining how these data structures work and how to build them?
 

Gryz

Golden Member
Aug 28, 2010
1,551
203
106
No.
You'll have to write code to insert, search and delete in your list yourself.

No big deal, imho. Functions that do that for you tend to hide a lot of detail. Which means you'll lose control over how much cpu-time and memory you'll spend. Sometimes that doesn't matter. Sometimes it's vital. Example: in my company we have our own libraries for things like doubly-linked lists and AVL trees. Now I don't suggest anyone writes their own AVL-tree functions (unless you do it just for fun). But our doubly-linked list library is so general purpose, it needs a lot of memory. Each linked list starts with a block of 128 bytes (with things like pointers to compare function, offset between data-structure and location of the next--pointer, etc). This makes it acceptable for some situation (few lists, but lists are big). And very inefficient for other situations (lots of small lists).

Doing list operations are not very complicated. Once you get the concept of pointers, it's just a few lines of programming.
 

Merad

Platinum Member
May 31, 2010
2,586
19
81
You should also be aware that on modern CPUs linked lists usually perform quite a bit worse than simple arrays. If you're just learning, then you of course learn about them, but in a real program most of the time you should probably just use an array (or some data structure that wraps an array, like std::vector).
 

Gryz

Golden Member
Aug 28, 2010
1,551
203
106
As always, the choice of which data-structure to use (array, list, tree, avl-tree, hash-table, etc) depends on what you're going to do with that data-structure. How many do you need ? How many elements do you put in each one of them ? How often do you insert new elements, how often do you have to search elements ? How often do you delete ? How often do you have to walk through all of them (or a subset) ? How long does your data-structure live ? How scarce is memory, how scarce is cpu-time ?

All these things matter. There is no way you can say "data structure X is always better than data structure Y".
 
Last edited:

Merad

Platinum Member
May 31, 2010
2,586
19
81
Indeed, Big O analysis tells us that arrays are superior for some operations while linked lists are superior for others. However, modern CPUs are complex beasts, and among other things they love their caching. Arrays are a very cache friendly data structure, so much so that real world testing often shows us arrays performing faster even on operations where linked lists should win. Our algorithmic analysis isn't wrong - arrays have to perform more operations, but caching makes such an extreme difference that they are still faster.

Examples:
https://www.linkedin.com/pulse/performance-array-vs-linked-list-modern-computers-dat-hoang-tien
https://kjellkod.wordpress.com/2012...ever-ever-use-linked-list-in-your-code-again/

Of course, if performance is not a significant concern to your program, none of this is extremely relevant. If you are concerned with performance and need linked list semantics, there are alternatives such as intrusive lists.