basicnumerics.com Blog

In an earlier entry, we developed a generic way of creating and looping through arrays in C. Arrays are very useful, but for some things linked lists are better. So lets develop some general tools for them.

Decisions

First, a design decision must be made. Each element in the list needs a pointer to the next element, and optionally a pointer to the previous one. Where should these pointers reside? There are a couple of options. The most obvious approach is to add next and previous pointers to whatever structure is used to store your data. This leads to a structure like the figure.

Data Structures for Linked Lists. Direct Approach.

We have a generic container (in green). It stores the number of elements in the list, along with a pointer to the first and last elements. It is up to the user to create the structure that holds the data for each element of the list. And this structure must include the prev and next pointers. This approach is conceptually simple and provides direct access to the data. However, it lacks generality. If you want to make a list containing elements based on a structure from another library, you are out of luck, unless they contain the prev and next pointers. Also, what if you want to store these data items in multiple lists? Can’t be done with a single set of next and prev pointers.

A way around this problem is to add a level of indirection to the scheme. The figure below shows the idea. We now have two predefined structures, one for the list (green) and a new one for a generic list element (blue).

Data Structures for Linked Lists. Indirect Approach.

Now a list can store items of any data type. It could even contain different structures. This generality comes at the price of more complex data access. To retrieve an item from the list, you must do something like:

mylist.pFirst->ListEl->Data1
(green) (blue) (pink)

Instead of

mylist.pFirst->Data1
(green) (pink)

This is one extra level of indirection, compared to the first scheme. It makes the code less readable, is more error prone and is probably slower as well.

Since we are going for generality, we will use the indirect approach, and see how it works.

Another design decision is should the list be linear or circular. In other words, should the next pointer in the last element be set to NULL or to the first element? We’ll keep it simple and create a linear list

Implementation

Here are what our two generic structures look like:

//Generic list Element
struct lelement {
    LElement *next;
    LElement *prev;
    void *data;
};

//Generic List Structure
struct llist {
    int NumEl;   //Number of elements in list
    LElement *pFirst;  //Ptr to first element in list
    LElement *pLast;   //Ptr to last element in list
};

The structure for a generic element in the list contains three pointers: next and prev needed for the list, and data which points to the data we are storing. The container structure holds the number of elements in the list, as well as pointers to the first and last elements.

To create an empty list, we just initialize the items in the container:

void CreateList(LList *list)
{
    list->NumEl = 0;
    list->pFirst = NULL;
    list->pLast = NULL;
}

We assume the memory was allocated elsewhere. An element can be added to the end of the list by adjusting the pointers at the end of the list and in the new element. The code below shows an implementation of this.

LElement *AddToList(void *item, LList *list)
{
    //check inputs
    assert(item!=NULL); assert(list!=NULL);
    //Create generic element to hold item ptr
    LElement *NewEl;
    NewEl = (LElement *)malloc(sizeof(NewEl));  //create generic element
    assert(NewEl != NULL);
    list->NumEl = list->NumEl + 1;
    NewEl->data = item;
    if (list->NumEl == 1)
    {
      list->pFirst = NewEl;
      NewEl->prev = NULL;
      NewEl->next = NULL;
    }
    else
    {
      NewEl->prev = list->pLast;
      NewEl->next = NULL;
      list->pLast->next = NewEl;
    }
    list->pLast = NewEl;
    return NewEl;
}

It is also to be able to add data at the beginning or middle of the list. This can be done in a similar way, although there are a few more details to worry about. To remove an item from the list you simply bypass it, then free the memory. Because we don’t know if the data is stored in multiple lists, it is never freed, only the generic list element.

Looping

To loop through a linked list, we can create a macro similar to the one for general arrays:

#define FOR_EACH(item_ptr, list) \
     for (ListEl = myList.pFirst; ListEl != NULL; ListEl=ListEl->next)

This macro creates a for loop that initializes ListEl at the first value. It then increments this value at the end of each pass through the loop until the end of the loop is reached. This makes it handy for looping through an already existing list. It is not very helpful in looping through a list under construction.

Summing up

The list code can be found here: ListType.c. It can be compiled with the command

gcc -Wall ListType.c

In creating this example, I hit many snags. It is very easy to make a mistake when rearranging the pointers for an insertion. Then the test code would try to write to a NULL pointer and crash! In comparison, the array list was much easier to develop. If I was going to use linked lists for general storage like this, I would want a well tested library, rather than just winging it.

In numerical computations, we frequently have lists of objects we must deal with. In C, there are two types of containers commonly used for holding these lists: arrays and linked lists. Arrays are good for fast, random access to the list. However, they are a few drawbacks. It is easy to write outside of array bounds and crash the code. It is hard to add elements to the middle of the list. And if you need more space than you allocated, you need to allocate a new larger block of memory and copy everything over.

Linked lists are good for frequently changing lists. You can easily insert an element anywhere in the list. Since memory is allocated as each element is created, there is no problem running out of room. However, cycling through the list can be slower, since the elements can be scattered all over in memory, and it is time consuming to retrieve the ith element of a list. Numerical folks tend to favor arrays, but both tools are useful.

Here we will create a general array and a macro for looping through it. This will hopefully be useful for reducing coding errors.

Array Structure

Lets begin by creating a general array structure, and some functions to access it.

A generic structure, that can hold arrays of anything might look like:

typedef struct
{
    long NumEl;      //number of elements
    size_t ElSize;   //size of each element
    void *Data;      //ptr to data
} AList;

This structure stores the size of the array, the size of each item in the array and a pointer to the first element in the array. Knowing the number of elements in the array is useful to staying in array bounds. The size is important for allocating memory and when we try looping. Notice that Data is a pointer to void. That is because we don’t know what type of array we will have. It could be intergers, floats or some arbitrary structure.

A new ArrayList could be created like so:

void CreateList(AList *list, long NumEl, size_t ElSize)
{
    list->NumEl = NumEl;
    list->ElSize = ElSize;
    list->Data = (void *)malloc((NumEl + 1) * ElSize);
    if (list->Data == NULL)
        printf ("Error in CreateList: Can't allocate memory");
}

To destroy a list, we must deallocate the memory for the data array. The DestroyList function does this:

void DestroyList(AList *list)
{
    if (list->Data != NULL)
    {
        free(list->Data);
        list->Data = NULL;
    }
}

One can access an element in the array with

void *GetItem(AList list, long index)
{
    if (index >= 0 || index < list.NumEl)
        {return list.Data + index * list.ElSize;}
    else
    {
        printf ("Wrting outside array bounds");
        return NULL;
    }
}

This may look a little strange. If Data is a pointer to an array why not access the elements in the normal fashion with [] brackets? The problem is that we don’t what ahead of time what type of data is stored in the array. For something like list.Data[5] to work, the compiler must know the size of each element, so it can calculate the distance (in memory) from the starting point. Since it doesn’t know that, we do the calculation for it.

One could also envision a SetItem routine, but this would be very dependent on the nature of the element being stored. So it is best to let the user set each element as it makes sense to do so.

For Each loop

One of the first lessons I learned in programming was: Don’t write outside array bounds! Its an important lesson, and a simple one, yet I still occasionally mess up. Why? Because its easy. Here is a very simple way to screw up in C:

int i; float myArray[10]
for i=0; i<=10; i++)
{
  //some code
}

In C, arrays start at index 0, so the above declaration runs from myArray[0] to myArray[9]. Yet our loop runs to myArray[10]. Trouble!

Some languages handle the looping details for you. Consider this equivalent code in Python:

myList = [1,4,2,3,5,6,3,8,5,9]
for each item in myList:
    #some code

The For statement knows there are ten items in myList and loops over them. Each pass through the loop, it takes the current item in the list and assigns it to Item. You can then do what you want with it.

This type of high level construct frees us to focus on the job at hand while leaving the bookkeeping to the computer. Unfortunately, in the case of Python, this comes at the cost of speed.

Lets try to emulate the For statement in Python. Consider the following macro:

#define FOR_EACH(index, item_ptr, list) \
     item_ptr=list.Data; \
     for (index=0; index

The FOR_EACH macro has three arguments: an index, a pointer to the an item in the array and the list structure. Like the Python equivalent, with each pass through the loop, the item pointer is set to point to the current position in the array. To find that position, we need to know the size of the elements, as mentioned above. With a macro like this, it is impossible to write outside array bounds. Because the compiler substitutes the code in at compile time, the performance should be the same as hand coding the loop. The best of both worlds!

Trying it out

Lets try a simple example to make sure it is working. Here is a very simple structure:

typedef struct   //toy structure to play with
{
    int val1;
    double val2;
} ElType;

To loop through a list, we first create the list, then call the FOR_EACH macro. We must declare an index variable and a pointer to an element, but don’t need to initialize these. Here is the code:

int main()
{
	int i; AList mylist;
	ElType myEl; ElType *pMyEl;

	CreateList(&mylist, 100, sizeof(myEl));
	FOR_EACH(i, pMyEl, mylist)
	{
		pMyEl->val1 = i;
		pMyEl->val2 = (double)(2.*i);
		printf("i = %d, val1 = %d, val2 = %f\n", i, pMyEl->val1, pMyEl->val2);
	}
	DestroyList(&mylist);
	return 0;
}

A nice feature of this approach is one could later change the array to be 200 elements and all the loops will still work fine.

Download code here: Array Code