Node-based data structures
Node-based data structures do not necessarily take contiguous blocks of memory. They mainly allocate nodes in memory that are connected. In this case, logically, there is no need to allocate a block of memory when nodes can occupy node-size spaces and be connected in some way. This means that nodes might be spread randomly in memory.
The linked list is the most often used and most basic node-based data structure. A visual representation of a doubly linked list is shown in the following diagram:
Figure 6.9: Illustration of a doubly linked list
Apart from the structural differences, the way that operations run on node-based data structures also differs from that of sequential data structures. Some of the operations are faster, while some are slower. For example, if we compare an array and a list, the time complexity of reading an element will be O(1) for an array and O(n) for a list. Here, the insertion will be O(n) for an array...