3 ms·

Who used linked lists in practice anyway?

betterunix 13y ago
The Linux kernel, among other things.
cnvogel 13y ago
It's heavily used in the Linux kernel, for example: http://kernelnewbies.org/FAQ/LinkedLists http://kernelnewbies.org/FAQ/LinkedLists [fbsd /home/chris/linux-tegra (master)] $ git grep LIST_HEAD|wc 5939 12872 372136
GnarfGnarf 13y ago
LIBXML uses them for in-memory representation of DOM parsed XML. They are also very effective in Trie node structures (http://en.wikipedia.org/wiki/Trie http://en.wikipedia.org/wiki/Trie). They provide super-fast searching of large texts. I prefer arrays. I experimented with linked lists in my early C days, and this code turned about to be the most bug-prone and hard to maintain. They have their place, but given a choice, arrays are simpler, and faster to code for.
- gizmo686 13y ago
  >I experimented with linked lists in my early C days, and this code turned about to be the most bug-prone and hard to maintain. I had almost the exact opposite experience. Arrays always felt like I was shuffling indexes around, and needed to do extra bookkeeping to keep track of where I was. Linked-lists seemed more explicit. Granted, I have had times where arrays produced easier code. These tended to be when I need random access (or to backtrack n-elements or such). Furtuantly, these cases also (normally) coincide with the cases where arrays are the more (asymptotically) performant data-structure.
gizmo686 13y ago
Kernels, embeded, games come to mind. For all of them, a major advantage of linked-lists is that they really are constant time. For example, if you are programming a game, you gennerally do not want to use a vector. Even though vectors amoratize to O(1), and may be, on average, faster, they occasionally take a long time. Switching to a linked list could be the difference from going from 100FPS with an occasional 1FPS, to going at a constant 80FPS. Also, linked lists can (counterintuitivly) often make better use of a low memory environment. This is because they do not require a continuous block of ram, so they can fill in free memory that has become fragmented. Also, in many cases linked-lists produce very clear and understandable code. And functional programming.
com2kid 13y ago
Anyone who needs an unbounded list of stuff and who cannot afford the memory to over allocate. At least that is my biased opinion coming from embedded! (No STL, everything done from scratch)

The Linux kernel, among other things.

It's heavily used in the Linux kernel, for example: http://kernelnewbies.org/FAQ/LinkedLists http://kernelnewbies.org/FAQ/LinkedLists [fbsd /home/chris/linux-tegra (master)] $ git grep LIST_HEAD|wc 5939 12872 372136

GnarfGnarf 13y ago

LIBXML uses them for in-memory representation of DOM parsed XML. They are also very effective in Trie node structures (http://en.wikipedia.org/wiki/Trie http://en.wikipedia.org/wiki/Trie). They provide super-fast searching of large texts. I prefer arrays. I experimented with linked lists in my early C days, and this code turned about to be the most bug-prone and hard to maintain. They have their place, but given a choice, arrays are simpler, and faster to code for.

gizmo686 13y ago
>I experimented with linked lists in my early C days, and this code turned about to be the most bug-prone and hard to maintain. I had almost the exact opposite experience. Arrays always felt like I was shuffling indexes around, and needed to do extra bookkeeping to keep track of where I was. Linked-lists seemed more explicit. Granted, I have had times where arrays produced easier code. These tended to be when I need random access (or to backtrack n-elements or such). Furtuantly, these cases also (normally) coincide with the cases where arrays are the more (asymptotically) performant data-structure.

gizmo686 13y ago

Kernels, embeded, games come to mind. For all of them, a major advantage of linked-lists is that they really are constant time. For example, if you are programming a game, you gennerally do not want to use a vector. Even though vectors amoratize to O(1), and may be, on average, faster, they occasionally take a long time. Switching to a linked list could be the difference from going from 100FPS with an occasional 1FPS, to going at a constant 80FPS. Also, linked lists can (counterintuitivly) often make better use of a low memory environment. This is because they do not require a continuous block of ram, so they can fill in free memory that has become fragmented. Also, in many cases linked-lists produce very clear and understandable code. And functional programming.

com2kid 13y ago

Anyone who needs an unbounded list of stuff and who cannot afford the memory to over allocate. At least that is my biased opinion coming from embedded! (No STL, everything done from scratch)