Link list usage in system programming

Question

Hi, 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

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

Linked lists provide an easy implementation for several important abstract data structures, including stacks, queues, hash tables, symbolic expressions, and skip lists.

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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.