Introduction to C-Programming: As seen in ENGS 20

So far we have used arrays to store multiple items of the same data type. For example, we could use an array of characters to store the characters ’E’, ’N’, ’G’, ’S’, ’2’, ’0’ as depicted in the illustration below.

Note that this is simply an illustration for the purpose of creating a conceptual understanding. Above the memory cells are the addresses of the memory locations - these are fictitious of course. In reality, memory addresses look a bit more complicated, for example something like 0x7ffcce3fe0a0 (which is just hexadecimal for a pretty large number).

When the elements of our array are stored right next to each other (as they are in the case of an array) then all the computer needs to find all of these elements is the address of the first element (and its datatype). With that information and the knowledge of how much room each element of this datatype takes up, the computer can calculate the address of subsequent elements and thereby access all of them (while it’s the programmers job to keep track of the length of the array).

Suppose now that for some reason the elements of the array were not stored right next to each other in memory but rather scattered about as in the following illustration:

Without knowing all of the locations of the stored elements it would be impossible to know what (and where) the elements of the list are. This is where the idea of a linked list comes in. In a linked list it is the job of each element to keep track of the location of the next element in the list. Thus, if you know where the first element is located you can again traverse the entire list by asking the first element for the address of the second, the second element for the address of the third, and so forth. This idea is depicted in the next image:

It is our job to keep track of the start, that is, the address of the first element of the list (in the image it is stored in a variable named start). Each element knows where the next element is stored, and the last element knows that it is last. This is all the information needed to access the entire list. We’ll therefore group together whatever it is we’d like to store along with an additional address field which is there to store the location of the next element. We’ll typically use a structure for this purpose as is depicted in the following image:

The following video presents a first example of a linked list. Just as we did previously in class with arrays, we’ll be storing coordinates of points in this example, but unlike the arrays we used in class for this purpose, this time around each individual point will be stored at some place assigned to it during run-time, and each point will keep track of the location of the subsequent point in order to maintain the ordering.

In order to do so, we need to store the address of a point (the next point in the list) as part of (so as a member of) the structure that holds the coordinates of the point. We’ll therefore work with the following structure in this example (note that we are switching coordinates to integers just to make the memory view nicer):

struct point{
  int x;
  int y;
  struct point * next;
};