One example would be timers. Timers are often arranged as linked lists.
That way, only one value has to be decremented under a clock interrupt.
For example, if you have timers due to expire in 10, 30 and 100 seconds, you will have
3 values in a linked list, which looks like this:
10, 20 and 70.
This means: first timer expires in 10 seconds, second timer in 20 seconds after that, and the third one in 70 seconds after the second one.
If you then want to add another one expiring in 25 seconds, you will insert it in the appropriate position (#2) in the list, adjust the next element (from 20 to 5) and the list will look like this:
10, 15, 5, 70
When a clock ticks, you only decrement the head value, e.g:
9, 15, 5, 70
A bit more processing when inserting and removing but is worth it - read below.
If, as opposed to the linked list, you keep them in an array, you would have to decrement each and every running timer, every time the clock interrupt occurs. If you have lots of timers, it can be very substantial.
I am not making it up, by the way, this is how most RTOS-es that I have seen do it .
Updated 29-Oct-12 14:54pm
v2
maybe it needs to be reentrant or points to read only memory structures..
in general, unless the list is very large or has many insertions/deletions at random locations, a dynamic array (or stl vector) is MUCH more efficient.
Sure, unless you want to limit yourself to the number of processes that you can keep track of at once (i.e the number that are running) you'll need to either
(a) Set aside a fixed quantity of memory exclusively for this task or
(b) implement a linked list, that creates new nodes from the kernel's pool of memory.
That's how windows does it, you get a list to iterate throught, with the option of a callback at each node - you don't get the process list as an array - though you could build one from the list if it floated your boat.
Can't think of another just this moment, but it's a matter of efficient memory use.