This is the eighth tutorial in the series Online C Tutorials for beginners and is about pointer variables. These are single page bite size tutorials which can usually be run on either codepad.org or ideone.com.

Building Data Structures with Pointers

Other computer languages has lists and dictionaries available either in the language (Python) or as a separate library (C++ and C#). In C we have to build our own. That said there are some excellent open source (and probably commercial as well) libraries out there but you should know the principle behind them and they all use pointers.

All the data structures use some combination of structs and pointers. Here’s some simple ones.

• Forward List (Single Linked List)
• Two Way List (Double Linked List)

Single Linked List

In this you have a list of structs and each struct contains a pointer to the next struct in the list. The last struct in the list has a null pointer (the value 0). If you want to add another item to the list you create a struct using malloc and then set the pointer at the end of the list to point to this new struct.

You can either store the data in the struct or keep it simple and just store a second pointer to the data. That’s slightly slower as you have to allocate two structs for each data item. One for the list struct and one for the data.

Let’s see this in action with some example code I’ll have a simple struct holding a 5 char id (4 chars + \0) and a double being the account balance. Here’s what the struct looks like.

struct accountrec {
  char id[5];
  double balance;
  struct accountrec * next;
};

If you prefer to simplify the code, you can use a typedef ptraccountrec like this.


typedef struct accountrec * ptraccountrec;


Declare this before the struct and the last line of the struct becomes ptraccountrec next;

I call this “no star” programming and if you are new to pointers it can make reading programs a lot easier as there are no *, but you should make sure that typedefs which are pointers are named accordingly. I tend to prefix types and variables with p or better still ptr.

/* simplell.c : Simple Linked List code by D. Bolton (C)    */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct accountrec * ptraccountrec;

struct accountrec {
    char id[5]; 
	double balance;
	ptraccountrec next;
};

ptraccountrec list=0;

ptraccountrec newaccount(char * newid,double newbalance) {

    ptraccountrec newrec = (ptraccountrec)malloc(sizeof(struct accountrec));
	ptraccountrec listptr = list;
	newrec->balance= newbalance;
	strcpy(newrec->id,newid);
	newrec->next = 0;

	if (list== 0) {
		list = newrec; /* list was empty but now points to new item */
	}
	else /* go from start to end until reach end struct and set its next ptr*/
	{
		while ( listptr->next != 0) {
			listptr = listptr->next;
		}
		listptr->next = newrec;	
		
	}
  return newrec;    
}

void showaccounts() {
	ptraccountrec listptr = list;
	while (listptr !=0 ) {
		printf("Account %s has $%f\n\r",listptr->id,listptr->balance);
		listptr= listptr->next;
	}
}

void freelist() {
	ptraccountrec tempptr;
	while (list != 0) {
		tempptr= list->next;
		free(list);
		list = tempptr;
	}
}

int main(int argc, char * argv[])
{
	newaccount("REC1",10000.0);
	newaccount("REC2",500.0);
	newaccount("REC3",-500.0);
	showaccounts();
	freelist();
	return 0;
}

Running this example above on ideone.com gives this:

Account REC1 has $10000.000000
Account REC2 has $500.000000
Account REC3 has $-500.000000


It adds three items to the list, prints the list and then frees up the memory. You should always free up any memory allocated with malloc.

This starts with an empty list. The global variable list has a value of 0. The new account function calls malloc() to allocate enough room for an accountrec struct and stores a pointer to this in the variable newrec and initializes the fields in that.

This struct will always be added to the end of the list so the next field will always be set to 0. Another pointer is initialized as once we have a value for list we must never change it.

If the list is empty then we set list to point to the new struct. Otherwise we use the listptr variable to access each struct in the list, looking for the one at the end. All it takes to go from struct to struct is this statement.

listptr = listptr->next;


Once the list end is found (with listptr -> next == 0 ) then the address of the new struct is assigned to listptr-> next and that completes it.

The function returns the address of the new struct which can be handy if further processing is needed. In this case it’s not.

Showaccounts() just walks the list, printing out the values of the fields in each struct. Finally freelist() frees everything and it does change list. When it finishes all the structs allocated memory have been returned to the operating system and list has the value 0.

Double Linked List

This is like a single linked list except each struct has two pointers, prev and next. The prev pointer points to the struct before. The first struct has a prev value of 0.

This allows you to write code that can traverse a list in either direction but you will need to store a listend pointer, so you can process the list backwards using the prev pointer.

Pros and Cons

Linked lists have the advantage that you can add new structs anywhere in the list or delete them fairly quickly. Searches though require a linear search and so take O(n) for n structs.

Searches can be improved if you add an index, but that requires extra code to maintain the index when structs are added or removed.

In the next tutorial, I’ll cover function pointers.

Link to previous tutorial.

Link to Next Tutorial