5: Linked Lists

The main structured data type we have seen so far is the array. Arrays consist of homogeneous data (i.e. data that is all of the same type) in contiguous memory locations, along with a value for the length of them. An array may be created dynamically, at run-time, with the new operator. Once an array has been made in memory, though, we cannot change its size. What if, suddenly, at run-time, we find we need to store more items than for which we requested space? The array cannot be made bigger. Often this means that we over-estimate the amount of space we will require but this is not a perfect solution as then more memory than may be necessary is being hogged, and there might still be more entries than will fit into the (big) allocated space.

The solution we want is to be able to grow our data structure at run-time. One way to do this is with linked lists. Like arrays, linked lists also contain homogeneous data; unlike arrays, linked lists can change in size during run-time.