in spite of having so many efficient data structures, why is only linked list used so heavily in systems programming? Is it because it allows least usage of heap/less buggy code?
Regards, Pwn
-
This is not quite an exact duplicate, but it is quite relevant: Under what circumstances are lined lists useful?James McNellis– James McNellis2010-05-31 19:23:27 +00:00Commented May 31, 2010 at 19:23
-
Interesting question. Your statement seems quite valid for some branches of systems programming. But you're likely to encounter tree data structures as soon as you get to e.g. file systems. And I wonder if linked lists are sufficient for an efficient OS memory management core; I'd guess not.stakx - no longer contributing– stakx - no longer contributing2010-05-31 19:26:17 +00:00Commented May 31, 2010 at 19:26
Add a comment
|
8 Answers
Linked List is a very efficient data structure to use for something like a queue or stack where you want to add something at the end or remove it from the beginning. Systems programming deals a lot with queues and stacks.
Comments
I'm guessing because it's just extremely simple to implement and understand. And it has an extremely small overhead.
The kernel has access to copious amounts of memory (it's in charge of it, after all) and mainly has to control lists of things (rather than associative structures that connect one thing with another).
So it's just a good match. There is no (or rarely) any need to complicate it further.
2 Comments
stakx - no longer contributing
(If you look at the number of linked list related questions here on SO, I doubt they're really that easy to get your head around. ;-) But they're definitely easier than e.g. red-black trees.)
David Roberts
You can definitely do some bizarre (confusing) things with them - but in general, traversing them and doing basic operations on them (add/remove) is extremely simple and fast. Also, I probably should have put this in my answer - but I suppose they're good for immediately detecting corruption. The kernel knows valid regions of mem. Wonky pointer = bad list
Linked lists are quite efficient for many systems-level tasks:
- Queues (for scheduling)
- Collections where your main operation is to visit every single thing in the collection, e.g., gather information about every active process
- Memory blocks (for first-fit allocation)
- Collections where you add or remove one element at a time
It's quite rare in systems programming to have a collection where you have to look things up by key, or to have to take the union of two sets. Except of course in filesystems, where you will find that more sophisticated data structures are used.
Is it because it allows least usage of heap/less buggy code?
No. In many cases, a linked list is the most appropriate data structure for the job.
Comments
Linked lists provide an easy implementation for several important abstract data structures, including stacks, queues, hash tables, symbolic expressions, and skip lists.
Comments
Its partly because efficent datastructures tend to have overheads that are relatively large when dealing with small numbers of entries, and partly because a lot of OS data-structures are FIFOs which linked-lists are good for.
Comments
Usually it is because you need a list of stuff - that is, you often pretty much just need something you can add/remove easily at either end or remove/insert at a node pointer you already have and iterate over.
There's plenty of areas where you don't need random access or search capabilities - or the space you need to search is so small that a linked list is anyway faster than more "fancy" data structures.
Sometimes though, it's also because linked lists are easiy to implement.
Comments
There's no good answer, because you're making wrong assumptions. It's not true that only linked list is used heavily. It's used when there are many things which need to be traversed in sequence - like free memory segments list, queue-like structures, etc.
There are many places where you need exactly such structure. There are other places where you don't need it.
Comments
Linked lists can easily be tied-in with other data-structures, (such as hash-tables for example). Also they can be translated easily to arrays and there are different ways of implementing them, for example one or two way linked list.
