Linked Lists

Linked Lists Linux uses a number of software engineering techniques to link together its data structures. On a lot of occasions it uses linked or chained data structures. If each data structure describes a single instance or occurance of something, for example a process or a network device, the kernel must be able to find all of the instances. In a linked list a root pointer contains the address of the first data structure, or element, in the list, then each subsequent data structure contains a pointer to the next element in the list. The last element’s next pointer would be 0 or NULL to show that it is the end of the list. In a doubly linked list each element contains both a pointer to the next element in the list but also a pointer to the previous element in the list. Using doubly linked lists makes it easier to add or remove elements from the middle of list, although you do need more memory accesses. This is a typical operating system trade off: memory accesses versus CPU cycles.