The last data structure we'll cover in this chapter is the linked list. A linked list is an ordered set of elements where each element contains a link to its successor.
Linked list data structure
Linked lists and arrays are similar; they both contain a set of elements. Arrays are allocated in a contiguous range of memory, whereas linked lists are not. This can be an advantage if you have a large dataset you need to work with but you do not know its size ahead of time. Because linked list nodes are allocated individually, they do not allow random access to the elements they contain. If you need to access the fifth element of a linked list, you need to start at the beginning and follow the next pointer of each node until you reach it. Linked lists do support fast insertion and deletion though, O(1).
There are additional linked list types that are useful for different requirements:
Doubly linked list - When you want to be able to walk up and down a linked list. Each node contains two...