C Tutorial: Basics

Linked Lists

There are only a few data structures and algorithms that you need to keep fresh in your mind because they are used over and over again. The simple singly-linked list is one of these.

What's a linked list and when do you use it?

A linked list is useful when you need to read, keep track of, and process arbitrary amount of information. There are variations on the linked list: singly-linked, doubly-linked, and circular lists. This set of tutorials focuses on the basics so well look at how you program and use a singly-linked list in C. Besides, you'll use a singly-linked list at least a hundred times more than all of the other types combined.

Implementation

A linked list data structure contains whatever data we want to store in the list along with a pointer to the next element of the list. All we need to keep track of is the head of the list. Whenever we want to add a new element to the list, we simply allocate the memory for the new element, set its pointer to point to the contents of the current head of the list and then set the head of the list to point to this new element. Hence, the new element becomes the head of the list.

Example 1: adding elements

Here's a simple example. We'll write a program that reads lines from the standard input. Each line gets entered as an element on the list. When we enter a line containing just a period, we'll stop reading lines and iterate through the list, printing out each one of the strings. Since each successive item goes to the head of the list, we'll be printing the last items first.

/* list: linked list example */
/* Paul Krzyzanowski */

#include <stdlib.h>	/* needed to define malloc() */
#include <string.h>	/* needed to define strdup() */
#include <stdio.h>	/* needed for printf() */
#define MAXLEN 128

struct list_entry {
	char *data;
	struct list_entry *next;
} *list = (struct list_entry *)0;

int
main(int argc, char **argv) {
	void dump(void);
	char *s, line[MAXLEN];
	struct list_entry *item;

	while (fgets(line, MAXLEN, stdin) != 0) {	/* read until eof or . */
		/* fgets reads in a \n - strip it */
		if ((s = strchr(line, '\n')) != 0)
			*s = 0;

		if (strcmp(line, ".") == 0) 	/* we have a line with just "." */
			break;

		/* allocate a new list element */
		item = malloc(sizeof(struct list_entry));
		if (item == 0) {
			fprintf(stderr, "malloc failed\n");
			exit(1);
		}
		/* set the data in the list element */
		item->data = strdup(line);	/* copy the string */
		item->next = list;

		/* we have a new head of the list */
		list = item;
	}
	dump();
	exit(0);
}

/* dump: dump the list */

void
dump(void) 
{
	struct list_entry *lp;
	
	for (lp = list; lp != 0; lp=lp->next)
		printf("item: \"%s\"\n", lp->data);	
}

Download this file

Save this file by control-clicking or right clicking the download link and then saving it as list1.c.

Compile this program via:

gcc -o list1 list1.c

If you don't have gcc, You may need to substitute the gcc command with cc or another name of your compiler.

Run the program:

./list1

Now enter a bunch of stuff on multiple lines and then terminate with a line containing a single period.

Example 2: deleting elements

Let's expand on the above example. Now, after we enter the line containing just a period, we will be asked to enter more test. Each time we enter a line, we will search through the list. If we find a match then we will state so and delete the list entry. A line with just a period will signify the end of this second phase.

Deleting is straightforward. We just need to keep track of the prevous item we found. When we find the entry that we want to delete, we update the next pointer of the previous item to point to the next item instead of the current one. Then we free whatever space we allocated for the item:

last->next = current->next;
free(current);

The special case that we have to handle is if we need to delete the first item on the list. In this case, we update the head of the list to point to the next item on the list:

if (last != 0)
	last->next = current->next;
else
	list = current->next;
free(current);

Here's the code.. I moved the code read lines and create the list as well as the code to read lines and delete items from the list into separate functions to keep all functions short and to the point.:

/* list: linked list example */
/* Paul Krzyzanowski */

#include <stdlib.h>	/* needed to define malloc() */
#include <string.h>	/* needed to define strdup() */
#include <stdio.h>	/* needed for printf() */
#define MAXLEN 128

struct list_entry {
	char *data;
	struct list_entry *next;
} *list = (struct list_entry *)0;

int genlist(void);

int
main(int argc, char **argv) {
	int genlist(void);
	void read_delete(void);

	if (genlist()) {
		/* phase 2 - delete */
		printf("enter words to delete\n");
		read_delete();
	}
	exit(0);
}

/* read in list contents from stdin */
/* return zero if we didn't read an end of file */

int
genlist()
{
	char *s, line[MAXLEN];
	struct list_entry *item;

	while (fgets(line, MAXLEN, stdin) != 0) {	/* read until eof or . */
		/* fgets reads in a \n - strip it */
		if ((s = strchr(line, '\n')) != 0)
			*s = 0;

		if (strcmp(line, ".") == 0)  	/* we have a line with just "." */
			return 1;

		/* allocate a new list element */
		item = malloc(sizeof(struct list_entry));
		if (item == 0) {
			fprintf(stderr, "malloc failed\n");
			exit(1);
		}
		/* set the data in the list element */
		item->data = strdup(line);	/* copy the string */
		item->next = list;

		/* we have a new head of the list */
		list = item;
	}
	return 0;	/* we reached the end of input! */
}

/* read in words from stdin and delete them from the list */

void
read_delete()
{
	void delete(char *s);
	char *s, line[MAXLEN];

	while (fgets(line, MAXLEN, stdin) != 0) {	/* read until eof or . */
		if ((s = strchr(line, '\n')) != 0)	/* strip \n at end */
			*s = 0;

		if (strcmp(line, ".") == 0) 	/* we have a line with just "." */
			break;
		delete(line);
	}
}

/* delete: delete an entry from the list */

void
delete(char *s) 
{
	struct list_entry *current, *last = 0;
	
	for (current = list; current != 0; last = current, current=current->next)
		if (strcmp(current->data, s) == 0) {
			printf("deleting \"%s\"\n", s);
			if (last != 0) /* not the first entry */
				last->next = current->next;
			else
				list = current->next; /* change head of list */
			free(current->data);
			free(current);
			return;
		}
	printf("\"%s\" not found\n", s);
}

Download this file

Save this file by control-clicking or right clicking the download link and then saving it as list2.c.c.

Compile this program via:

gcc -o list2.c TEST.c

If you don't have gcc, You may need to substitute the gcc command with cc or another name of your compiler.

Run the program:

./list2.c

Now enter a bunch of text, such as a word per line. Then enter a line with just a period on it. You will be prompted to enter more words and they will either be found and deleted from the list or not found in the list.

C Tutorial: Basics

Linked Lists

What's a linked list and when do you use it?

Implementation

Example 1: adding elements

Example 2: deleting elements

Contents

CS 416

Tutorials

C Tutorials

Processes

I/O and IPC

Timing

Basics

Recommended