Computational Physics, 1B, Term 2

Using pointers for making interesting data-structures

Insertion-sort using a linked list

We are going to create a linked list, a data structure in which each item in the list points to the next item in the list. Such a structure can be used, for example, to store and update an ordered list of things. Here, we'll imagine we are sorting the integers {152, 7, 34, 19}. We define a structure: typedef struct item { int value ; item *next ; }; The first image shows a single 'item'. The contents of the item are a value (such as the integer 152), and a pointer, 'next', which points to the next item (or, if there is no next item, indicates this by taking a special null value). Shown in a yellow plaque is the address of the pigeonhole in memory where the item is located. These yellow plaques can't be edited. They just note factual statements about addresses, like the fixed numbers on houses in a street.

Now we show a picture of the list assuming the numbers 7, 34, and 152 have already been put in order. Notice how each 'next' contains the address of the next item - except in the case of the last 'next', which is set to the special value zero to indicate that the item in address EFEFEF is currently the last in the list.

We now discuss the next step where the number 19 is added to the list.
One thing that must happen is a new piece of memory must be found somewhere to contain this new item. In the figure above, we've just received this memory, at address F0F0F0, from the memory manager, and we've written in the new value, 19; but we haven't sorted out the pointers yet.

The final figure shows the pointers pointing correctly.
Notice that the pointer in the preceding item ('7') has to change to point to the new piece of memory. The address that used to be in that location is now moved into the 'next' slot in the newly created item.

This discussion has shown how to insert an item into an existing list, but it hasn't described how to get the list started. In an elegant implementation, this special case is handled by the general code. That is, we can ask our software to insert an item into a list that is actually empty, and the software will do the right thing. The task "insertion sort with linked lists" is the task of making software that can take an array of unsorted integers and create a sorted linked list.