Linked Lists

Using arrays to implement data structures has performance advantages in some cases, but this technique has its limitations. With this chapter, we begin a study of data structures that use reference types in a powerful way. Rather than forming sequences by placing data items in adjacent cells of an array, we instead use references to chain data elements together in a sequence. For some applications, this ends up being more efficient than using an array. As we will see in a later chapter, this chaining technique can be further exploited to link data items in a hierarchical way, providing even more flexible and efficient access.