C++ Footprint and Performance Optimization

Linked Lists

Another fairly straightforward storage structure is the linked list. A linked list is in fact a set of data elements that are chained together by pointers. Each element contains a pointer to the next element in the list, or a NULL pointer in case there are no further elements in the list. Figure 11.1 shows a linked list.

Figure 11.1. A linked list.

How you link list elements together is of course entirely up to you. One type of linked list that is often used is the double linked list, in which elements contain pointers to the next list element as well as to the previous element. The advantage of this is that you can navigate through ...