A linked list is an alternate way to collect together a number of instances of a given data type. Compared to arrays, linked lists offer the advantages of not requiring contiguous memory for the collection and an easy way to re-order the collection by simply swapping pointers. As we shall see later, linked lists are also very flexible when it comes to adding or deleting items to the collection. On the downside, linked lists require somewhat more memory than arrays (since space for pointers must be included), and arrays offer consistent fast access to any member of the array (linked lists require that the list be "walked along" in order to get to a given member). To create a linked list, a pointer to the structure type is included in the definition of the structure. Once the instances of the structure type are created, they are strung together by placing appropriate addresses in the pointer field.
A graphical example is shown below with four instances of some structure:
Imagine that each structure is 100 bytes in size. Further, assume that
A is located at memory address 1000 (spanning 1000 to 1099),
B is a located at address 2000,
C at 3000, and
D at 4000. Each structure contains a pointer to the next one in the list.
A contains a pointer to the address of
C, and so forth. For example, the value of
A’s pointer is 2000 (the memory address of
B), while the value of
C’s pointer is 4000 (the address of
&A is the top of the list, and that the last item signifies that no items remain by having its pointer set to 0. Further, these four items could be linked in any manner by simply changing the pointer values. Finally, items
D may reside anywhere in the memory map; they need not be contiguous. In contrast, if we were to make an array out of these structures, they would need to be packed into memory in sequence in order to be indexed properly. That is, if
A were located at address 1000,
B would have to be at 1100,
C at 1200, and
D at 1300, as they are each 100 bytes in size1. If you wanted to rearrange the structures (e.g., to sort them), add new ones or delete existing ones, this would require quite a bit of work with an array. These tasks are much easier with a linked list because the structures themselves aren’t manipulated, only the associated pointers.
- Array indexing works by simply multiplying the index value by the size of the arrayed item, and then using this value as an offset from the starting address. Thus, in this example, item (i.e.,
C) is found by multiplying the index of 2 by the size of 100 bytes to achieve a 200 offset from the starting location of address 1000, or 1200. Remember, item is
A, while item is
B, and item is