Singly linked list (C)

From LiteratePrograms

Other implementations: C | C++ | Java

This is a simple implementation of a singly-linked list.

Contents 1 Creating and manipulating a list 1.1 Nodes 1.1.1 Creating a node 1.2 Inserting a node 1.3 Removing a node 2 Operating on the entire list 2.1 Traversing a list 2.2 Searching a list 2.3 Examples of user-supplied functions 3 Testing the list 3.1 Includes 3.2 The test program main function

Creating and manipulating a list

Nodes

Each node in the list contains a data pointer, and a pointer to the next element. The data pointer is of type void *, so that it could point to any data. A node with next==NULL is the last node in the list.

Any node can be viewed as representing the list beginning at that element, so we do not need a special structure to represent the whole list. The structure for a single node is:

<<structure>>=
typedef struct node_s {
	void *data;
	struct node_s *next;	
} NODE;

Creating a node

Creating a new node is simple. The memory needed to store the node is allocated, and the pointers are set up. This function leaves allocation of data to the user.

<<list_create>>=
NODE *list_create(void *data)
{
	NODE *node;
	if(!(node=malloc(sizeof(NODE)))) return NULL;
	node->data=data;
	node->next=NULL;
	return node;
}

Inserting a node

In a singly-linked list, there is no efficient way to insert a node before a given node or at the end of the list, but we can insert a node after a given node or at the beginning of the list. The following code creates and inserts a new node after an existing node.

<<list_insert>>=
NODE *list_insert_after(NODE *node, void *data)
{
	NODE *newnode;
        newnode=list_create(data);
        newnode->next = node->next;
        node->next = newnode;
	return newnode;
}

The above code cannot insert at the beginning of the list, so we have a separate function for this. This code creates and inserts the new node and returns the new head of the list:

<<list_insert>>=
NODE *list_insert_beginning(NODE *list, void *data)
{
	NODE *newnode;
        newnode=list_create(data);
        newnode->next = list;
	return newnode;
}

Removing a node

Note: This will not free the data associated with the node. Is this able to remove the head node?

<<list_remove>>=
int list_remove(NODE *list, NODE *node)
{
	while(list->next && list->next!=node) list=list->next;
	if(list->next) {
		list->next=node->next;
		free(node);
		return 0;		
	} else return -1;
}

Operating on the entire list

Traversing a list

The user-supplied function pointer will be called once for each element in the list.

<<list_foreach>>=
int list_foreach(NODE *node, int(*func)(void*))
{
	while(node) {
		if(func(node->data)!=0) return -1;
		node=node->next;
	}
	return 0;
}

Searching a list

This function will return the first node to which the supplied function pointer returns a positive number.

<<list_find>>=
NODE *list_find(NODE *node, int(*func)(void*,void*), void *data)
{
	while(node) {
		if(func(node->data, data)>0) return node;
		node=node->next;
	}
	return NULL;
}

Examples of user-supplied functions

Here are a few examples of user-supplied functions that might be used in list traversals and searches. The first function prints a value to stdout, and can be used with a traversal to print the entire contents of a list.

<<supportfunctions>>=
int printstring(void *s)
{
	printf("%s\n", (char *)s);
	return 0;
}

The second function tests to see if the value of a given node matches some string.

<<supportfunctions>>=
int findstring(void *listdata, void *searchdata)
{
	return strcmp((char*)listdata, (char*)searchdata)?0:1;
}

Testing the list

<<slist.c>>=
includes
structure
list_create
list_insert
list_remove
list_foreach
list_find
supportfunctions
main

Includes

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

The test program main function

<<main>>=
int main()
{
	NODE *list, *second, *inserted;
	NODE *match;
	/* Create initial elements of list */
	list=list_create((void*)"First");
	second=list_insert_after(list, (void*)"Second");
	list_insert_after(second, (void*)"Third");
	printf("Initial list:\n");
	list_foreach(list, printstring);
	putchar('\n');
	/* Insert 1 extra element in front */
	list=list_insert_beginning(list, "BeforeFirst");
	printf("After list_insert_beginning():\n");
	list_foreach(list, printstring);
	putchar('\n');
	/* Insert 1 extra element after second */
	inserted=list_insert_after(second, "AfterSecond");
	printf("After list_insert_after():\n");
	list_foreach(list, printstring);
	putchar('\n');
	/* Remove the element */
	list_remove(list, inserted);
	printf("After list_remove():\n");
	list_foreach(list, printstring);
	putchar('\n');
	/* Search */
	if((match=list_find(list, findstring, "Third")))
		printf("Found \"Third\"\n");
	else printf("Did not find \"Third\"\n");
	return 0;
}

Download code