C Linked Lists

« Previous Tutorial Next Tutorial »

Unlike stack or queue, a linked list can be accessed in a flexible manner, because each piece of information carries with it a link to the next data item in the chain. In addition, a linked list retrieval operation doesn't remove and destroyed an item from the list. In fact, you need to add a specific deletion operation to do this.

Linked list can be either singly or doubly linked. A singly linked list contains a link to the next data item. On the other hand, a doubly linked list contains the links to both next and previous element in the list. You will use one or the other of these linked list types, depending upon your application. Now let's discuss about singly linked lists.

Singly Linked Lists

A singly linked list requires that each item of information contain a link to the next element in list. Each data item generally consists of a structure which includes the information fields and a link pointer. Let's take a look at the following figure which represents a singly linked lists.

Basically, there are two ways to build a singly linked list. The first is simply to put each new item on the end of list. The other is to insert items into specific places in the list in ascending sorted order.

The items stored in a linked list generally consist of structures because each item must carry with it a link to the next item in the list as well as the data itself. Hence, we will need to define a structure that will be used in examples that follow. Since mailing lists are commonly stored in a linked list, an address structure makes a good choice. The data structure for each element in the mailing list is defined here:

struct address
{
	char name[30];
	char street[40];
	char city[25];
	char state[4];
	char zip[11];
	struct address *next;    // link to the next address
}info;

The function slstore() shows here builds a singly linked list by placing each new element on the end. And it must be passed a pointer to a structure of type address which contains the new entry, and a pointer to the last element in the list. In case, if the list is emply, then the pointer to the last element in the list must be null. Here is the code fragment of slstore() function:

void slstore(struct address *i, struct address **last)
{
	if(!*last) *last = i;    // first item in the list
	else (*last)->next = i;
	i->next = NULL;
	*last = i;
}

Doubly Linked Lists

The doubly linked lists consist of data plus links to the next item as well as the preceding item. Let's take a look at the following figure which represents a doubly linked lists.

Having the two links rather of one has several advantages. Perhaps the most important is that the list can be read in either direction. This simplifies the list management, making insertions and deletions much easier. It also allows us to scan the list in either the direction. Another advantage is meaningful only in the case of some type of failures. Since the entire list can be read using either forward links or backward links, should on of the links become invalid, the list could be reconstructed by using the other.

A new element can be inserted into a doubly linked list in the following three ways:

insert a new first element
insert in the middle
insert a new last element

Building a doubly linked list is similar to building a singly linked list except that two links are maintained. Hence, the structure must have room for both the links. Using mailing list example again, you can modify the structure address as shown here to accommodate both links. Here is the code fragment:

struct address
{
	char name[30];
	char street[40];
	char city[25];
	char state[4];
	char zip[11];
	struct address *next;
	struct address *prior;
}info;

Using address as basic data item, following function, dlstore(), builds a doubly linked list:

void dlstore(struct address *i, struct address **last)
{
	if(!*last)
	*last = i;   /* is first item in list */
	else
	(*last)->next = i;
	i->next = NULL;
	i->prior = *last;
	*last = i;
}

Complete Mailing List Example

Here is the complete mailing list example program. The complete list is kept in memory while in use. However, it can be stored in a disk file and loaded for later use.

/* C Linked Lists - A Complete Mailing List Example Program */

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

struct address {
	char name[40];
	char street[50];
	char city[30];
	char state[3];
	char zip[11];
	struct address *next;   // pointer to the next entry
	struct address *prior;  // pointer to the previous record
};

struct address *start;     // pointer to the first entry in the list
struct address *last;      // pointer to the last entry
struct address *find(char *);

void enter(void);
void search(void);
void save(void);
void load(void);
void list(void);
void mldelete(struct address **, struct address **);
void dls_store(struct address *i, struct address **start, struct address **last);
void inputs(char *, char *, int);
void display(struct address *);
int menu_select(void);

void main(void)
{
	clrscr();

	start = last = NULL;     // initialized start and end pointers

	for(;;)
	{
		switch(menu_select())
		{
			case 1 :
				enter();    // to enter an address
				break;
			case 2 :
				mldelete(&start, &last);     // to remove an address
				break;
			case 3 :
				list();     // to display the list
				break;
			case 4 :
				search();   // to find an address
				break;
			case 5 :
				save();     // to save the list to disk
				break;
			case 6 :
				load();     // to read from the disk
				break;
			case 7 :
				exit(0);
		}
	}

	getch();
}

// select an operation
int menu_select(void)
{
	char str[80];
	int c;

	printf("1. Enter a name\n");
	printf("2. Delete a name\n");
	printf("3. List the file\n");
	printf("4. Search\n");
	printf("5. Save the file\n");
	printf("6. Load the file\n");
	printf("7. Quit\n");

	do
	{
		printf("\nEnter your choice : ");
		gets(str);
		c = atoi(str);
	}while(c<0 || c>7);
	return c;
}

// enter the names and addresses
void enter(void)
{
	struct address *info;

	for(;;)
	{
		info = (struct address *)malloc(sizeof(struct address));
		if(!info)
		{
			printf("\nout of memory..!!");
			return;
		}

		inputs("Enter name: ", info->name, 40);
		if(!info->name[0])  break;   // stop entering
		inputs("Enter street: ", info->street, 40);
		inputs("Enter city: ", info->city, 30);
		inputs("Enter state: ", info->state, 3);
		inputs("Enter zip: ", info->zip, 10);

		dls_store(info, &start, &last);
	}  // entry loop
}

/* this function will input a string up to the
 * length in count and will prevent the string
 * from being overrun. It will also display a
 * prompting message
 */
void inputs(char *prompt, char *s, int count)
{
	char p[255];

	do
	{
		printf(prompt);
		fgets(p, 254, stdin);
		if(strlen(p) > count)
		{
			printf("\nToo Long..!!\n");
		}
	}while(strlen(p) > count);

	p[strlen(p)-1] = 0;   // remove newline character
	strcpy(s, p);
}

// now create a doubly linked list in the sorted order
void dls_store(struct address *i, struct address **start, struct address **last)
{
	struct address *old;
	struct address *p;

	if(*last == NULL)
	{
		i->next = NULL;
		i->prior = NULL;
		*last = i;
		*start = i;
		return;
	}
	p = *start;    // start at top of the list

	old = NULL;
	while(p)
	{
		if(strcmp(p->name, i->name)<0)
		{
			old = p;
			p = p->next;
		}
		else
		{
			if(p->prior)
			{
				p->prior->next = i;
				i->next = p;
				i->prior = p->prior;
				p->prior = i;
				return;
			}
			i->next = p;     // new first element
			i->prior = NULL;
			p->prior = i;
			*start = i;
			return;
		}
	}
	old->next = i;    // put on end
	i->next = NULL;
	i->prior = old;
	*last = i;
}

// remove an element from the list
void mldelete(struct address **start, struct address **last)
{
	struct address *info;
	char str[80];

	inputs("Enter name: ", str, 40);
	info = find(str);
	if(info)
	{
		if(*start==info)
		{
			*start=info->next;
			if(*start)
			{
				(*start)->prior = NULL;
			}
			else
			{
				*last = NULL;
			}
		}
		else
		{
			info->prior->next = info->next;
			if(info!=*last)
			{
				info->next->prior = info->prior;
			}
			else
			{
				*last = info->prior;
			}
		}
		free(info);    // returned memory to system
	}
}

// find an address
struct address *find(char *name)
{
	struct address *info;

	info = start;
	while(info)
	{
		if(!strcmp(name, info->name)) return info;
		info = info->next;   // get next address
	}
	printf("Name not found..!!\n");
	return NULL;    // not found
}

// display the complete list
void list(void)
{
	struct address *info;

	info = start;
	while(info)
	{
		display(info);
		info = info->next;   // get next address
	}
	printf("\n\n");
}

// now this function prints the fields in each address
void display(struct address *info)
{
	printf("%s\n", info->name);
	printf("%s\n", info->street);
	printf("%s\n", info->city);
	printf("%s\n", info->state);
	printf("%s\n", info->zip);
	printf("\n\n");
}
// look or search for a name in the list
void search(void)
{
	char name[40];
	struct address *info;

	printf("Enter name to find: ");
	gets(name);
	info = find(name);
	if(!info)
	{
		printf("Not found..!!\n");
	}
	else
	{
		display(info);
	}
}

// now save the file to the disk
void save(void)
{
	struct address *info;
	FILE *fp;

	fp = fopen("mlist", "wb");
	if(!fp)
	{
		printf("Cannot open file..!!\n");
		exit(1);
	}
	printf("\nSaving File..\n");

	info = start;
	while(info)
	{
		fwrite(info, sizeof(struct address), 1, fp);
		info = info->next;      // get next address
	}
	fclose(fp);
}

// load the address file
void load()
{
	struct address *info;
	FILE *fp;

	fp = fopen("mlist", "rb");
	if(!fp)
	{
		printf("Cannot open file..!!\n");
		exit(1);
	}

	// now free any previously allocated memory
	while(start)
	{
		info = start->next;
		free(info);
		start = info;
	}

	// reset top and bottom pointers
	start = last = NULL;

	printf("\nLoading file..\n");
	while(!feof(fp))
	{
		info = (struct address *) malloc(sizeof(struct address));
		if(!info)
		{
			printf("Out of Memory..!!");
			return;
		}
		if(1 != fread(info, sizeof(struct address), 1, fp)) break;
		dls_store(info, &start, &last);
	}
	fclose(fp);
}

This program saves your input data in the file. Here are some sample outputs, just concentrate on it:

After entering the two record, just press enter. After pressing the ENTER key, you will get this output:

Now press 3 and then press enter key to display the file. Here is the sample output after pressing the key 3 then ENTER:

As you can see, after pressing the 3 then ENTER key, you will see the entered record on the output screen. Now press 2 to delete a record from the list. Enter the name which you want to delete from the list, here we will enter Alok Kumar Singh. After entering the name which is going to delete, just press enter to perform the deletion of this name from the list. After doing this, here is the sample output :

To check, whether the required record is deleted or not from the list, just press 3 to display the entire list and check whether the name is present in the list or not, which was performed for deletion previously. Here is the sample output:

As you can see, the deletion was performed successfully i.e., Alok Kumar Singh is not in the list now. Now to search any record, just enter 4, and then enter the name to be search. Here is the sample output of the search operation.

To save the file (record), just press 5 to save. Here is the sample output:

You can do any action accordingly as you saw. To quit the program just enter 7, but before quitting the program, press 5 to save your entered record, for the further use.

C Online Test

« Previous Tutorial Next Tutorial »