linklist implementation ITS 116

Using Pointers
Aside from using pointers to access functions, they can be very useful in creating dynamic data structures, such as arrays, stacks and lists. A Linked List, for example, uses pointers to each node in order to dynamically allocate the memory and retain a reference to it.
We can also use pointers in preference to arrays (otherwise known as dynamic arrays). This can be useful to build arrays that are larger than the stack size allowed by the language (a common problem in Modula-2), or to create arrays where we do not know the size at the start of the program.
Most languages also support pointer arithmetic, required if we wish to access the elements in the block of memory as if it were an array. Pointer arithmetic allows us to step through the elements by a given amount : the amount being equal to the size of the element being referenced. This automatic feature in C allows us to declare a user-defined type (such as a structure), allocate a block of memory to store a collection of them in, and then step through the array by incrementing the pointer.
If we rewrite the code, and make the struct bigger, then the code to allocate the memory, and the pointer arithmetic will still work, because it is a feature of the C language. This memory handling trick means that, if we use pointers, much of the data processing code that we need for an application can be re-used even if we change the nature of the data being stored.

15.5: Linked Data Structures
[This section corresponds to K&R Sec. 6.5]
One reason that pointers to structures are useful and common is that they can be used to build linked data structures, in which a structure contains a pointer to another instance of the same structure (or perhaps a different structure). The simplest example is a singly-linked list, which we might declare like this: struct listnode
{
char *item;
struct listnode *next;
};
This structure describes one node in a list; a list may consist of many nodes, one for each item in the list. Here, each item in the list (the field we've named item) will be a string, represented (i.e. pointed to) by a char *. Each node in the list is linked to its successor by its next field, which is a pointer to another struct listnode. (The compiler is perfectly happy to place a pointer to a structure inside that very same structure; it would only complain if you tried to stuff an entire struct listnode into a struct listnode, which would tend to make the struct listnode explode.) We'll use a null pointer as the next field of the last node in the list, since by definition a null pointer doesn't point anywhere.
We could set up a tiny list with these declarations: struct listnode node2 = {"world", NULL};
struct listnode node1 = {"hello", &node2};
struct listnode *head = &node1;
A box-and-arrows picture of the resulting list would look like this:
The list has two nodes, allocated by the compiler in response to the first two declarations we gave. We've also allocated a pointer variable, head, which points at the ``head'' of the list.
Once we've built a list, we'll naturally want to do things with it. One of the simplest operations is to print the list back out. The code to do so is very simple. We declare another list pointer lp and then cause it to step over each node in the list, in turn: struct listnode *lp;
for(lp = head; lp != NULL; lp = lp->next)
printf("%s\n", lp->item);
This for loop deserves some attention, especially if you haven't seen one like it before. Many for loops step an int variable (often called i) through a series of integer values. However, the three controlling expressions of a for loop are not limited to that pattern; you may in fact use any expressions at all, although it's best if they conform to the expected initialize;test;increment pattern. The list-printing loop above certainly does: the expression lp = head initializes lp to point to the head of the loop; the expression lp != NULL tests whether lp still points to a real node (or whether it has reached the null pointer which marks the end of the list); and the expression lp = lp->next sets lp to point to the next node in the list, one past where it did before.