4 ms·

Yeah you do - the kernel uses linked lists to store everything from running tasks to memory pages. Insertion and deletion of entries are much faster in a linked

• Dylan16807 6y ago
  > Insertion and deletion of entries are much faster in a linked list than in an array That's a really broad statement. Arrays can get surprisingly big while being faster. Performance-wise, you'd usually want to use arrays up to a certain size and then link between entire arrays. I'd say the biggest advantage of a standard linked list is that it can be intrusive.
  • dr_zoidberg 6y ago
    > I'd say the biggest advantage of a standard linked list is that it can be intrusive. That's one big benefit. I teach operating systems and, when the semester has been good, we dig into physical memory dumps with a few python scripts, and show the students how to parse Windows process list following _EPROCESS structures. That's one of the big things they find themselves surprised every year: that the process list is a chain of LIST_ENTRY structures embedded within the _EPROCESSes[0] (or any other structure that is doubly-linked in memory). And LIST_ENTRY is just 2 pointers going hand in hand with list_entry->flink and list_entry->blink attributes and nothing more. [0] You can read some about this structures here https://www.nirsoft.net/kernel_struct/vista/index.html https://www.nirsoft.net/kernel_struct/vista/index.html but beware this is based on Vista and a bit old. Kernel data structures vary with versions of the OS (and not even major versions at that) and target processor (x86, x86-64, ARM too would be reasonable).