# 11.1: Introduction

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 B, B to 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 D).

Note that &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 A, B, C, and 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.

1. 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[2] (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[0] is A, while item[1] is B, and item[2] is C.