Linked Lists in C

Linked lists are ordered collections of data where each elements stores the location of the next element. Each element therefore contains two parts, the data and the link. The link is used to chain the elements together.

A list must at least have one separate pointer to the first element in the list; the name of this pointer is synonymous with the name of the list. This pointer is known as the head pointer, as it points to the head of the list.

Linked lists are made up of nodes. A node in a linked list is a structure that should have at least two fields, one for the data and one for the link. Nodes are self-referential structures in that each instance of the node structure should have a pointer to another instance of the same type.

typedef struct aNode {
	int data;
	struct aNode *link;
} LIST_NODE;

We can define an empty linked list as a single pointer that has the value NULL.

Let’s create a function that allocates memory for the node, assigns the data, and sets the link field to NULL.

LIST_NODE *createNode(int data) {
	LIST_NODE *newNode = (LIST_NODE *)malloc(sizeof(LIST_NODE));
	newNode->data = data;
	newNode->link = NULL;
	return newNode;
}

As there is no physical relationship between the nodes in a linked list in terms of where they are placed in memory, it is vital to ensure that each node links correctly to the next. Functions that insert or delete a node should return the head of the list; if the head has not been changed, then they simply return the original head address.

We will create three functions for adding and inserting nodes. The first function will simply append one node after another. The second function will set a node as the head of the list. The third function will insert a node at a specific location in the list.

//returns location of new node added to the list
LIST_NODE *appendNode(LIST_NODE *pre, LIST_NODE *theNode) {
	if (pre != NULL) {
                //if pre is at the end of the list
                //pre->link is NULL
                theNode->link = pre->link;
		pre->link = theNode;
	}
	return theNode;
}

LIST_NODE *setHead(LIST_NODE *head, LIST_NODE *theNode) {
	if (head != NULL) {
		theNode->link = head;
	}
	return theNode;
}

LIST_NODE *insertNode(LIST_NODE *head, LIST_NODE *pre, LIST_NODE *theNode) {
	LIST_NODE *returnHead = NULL;

	//if the head is not null, set it as the default return value
	//otherwise set it to pre
	if (head != NULL) {
		returnHead = head;
	}
	else {
		returnHead = pre;
	}
	
	//if the preceding node is the start of the list
	//or both pre and head are NULL
	if (head == pre) {
		//set new node as the head of the list
		returnHead = setHead(pre, theNode);
	} else {
		//inserting at middle or end
		//leave head as it was set initially
		appendNode(pre, theNode);
	}

	return returnHead;
}

Since every new node created has its link set automatically to null by the function that creates the node, we can be sure that any node we add to the end of the list will automatically end the list.

Since the first node of the list is stored in the head pointer, it is easy to append a new node to the beginning of the list, and make it the new head pointer.

To delete a node, we must remove it from the linked list by altering the pointers and then physically removing the node from heap memory. To delete  a node, we must have its location, given by its predecessor. We can then alter the links and return the memory to the heap using free().

LIST_NODE *deleteHead(LIST_NODE *head) {
	return deleteNode(head, NULL);
}

LIST_NODE * deleteNode(LIST_NODE *head, LIST_NODE *pre) {
	LIST_NODE *target;
	//deleting first node
	if (pre == NULL) {
		target = head;
		head = head->link;
	} //deleting other nodes
	else { 
		target = pre->link;
		pre->link = target->link;
	}

	free(target);
	return head;
}

To delete or insert a node, we must first find the node that precedes it. To do so, we must find the logical predecessor of the target node. We can design a search function to find a node based on an offset number from the head of the list, or we can design a search function find the last node in the list, or we can search the list to find a node with a particular value.

//returns a pointer to the node at the 0-index offset from the head
LIST_NODE *findByIndex(LIST_NODE *head, int offset) {
	int i = 0;
	LIST_NODE *prev = head;
	LIST_NODE *current = head->link;
	while (i++ < offset && current != NULL) { 		
               prev = current; 		
               current = current->link;
	}
	//previous node always holds value at the index 
	//if it exists
	return prev;
}

//finds and returns first match for the data value
LIST_NODE *findByDataValue(LIST_NODE *head, int dValue) {
	LIST_NODE *current = head;
	bool found = false;
	do {
		if (current->data == dValue) {
			found = true;
		}
		else {
			current = current->link;
		}
	} while (current != NULL && found == false);

	return current;
}

//find predecessor
LIST_NODE *findPredecessor(LIST_NODE *head, LIST_NODE *target) {
	LIST_NODE *predecessor = head;
	while (predecessor->link != target) {
		predecessor = predecessor->link;
	}
	return predecessor;
}

Any application that must process the entire list will use list traversal logic. To traverse the list, we will need to start at the beginning and work with each node in succession. A simple function for printing the entire list would involve starting at the head, printing the data stored in the head, checking to see if the next node is null, and if not, setting the current node to the next node, and repeating this process until the next node is null.

//print list
void printList(LIST_NODE *head) {
	LIST_NODE *current = head;
	while (current != NULL) {
		printf("%d\t", current->data);
		current = current->link;
	}
	printf("\n\n");
}

Let’s tie it all together in the main() function.

int main()
{
	LIST_NODE *head = createNode(1138);
	LIST_NODE *current = createNode(73);
	LIST_NODE * newNode = createNode(1701);
	LIST_NODE * deleteNodePred = NULL;

	appendNode(head, current);
	appendNode(current, newNode);

	current = createNode(1999);
	appendNode(newNode, current);

	newNode = createNode(73);
	current = appendNode(current, newNode);

	current = appendNode(current, createNode(3435));

	printList(head);

	newNode = createNode(389);

	appendNode(current, newNode);

	insertNode(head, newNode, createNode(404));

	insertNode(head, current, createNode(65537));

	printList(head);

	newNode = createNode(443);

	head = setHead(head, newNode);

	head = setHead(head, createNode(118));

	printList(head);

	deleteNodePred = findByIndex(head, 2);
	head = deleteNode(head, deleteNodePred);

	printList(head);

    return 0;
}


Linked-Lists in C

Linked-lists utilize nodes of data. A node consists of two parts: a data part and a link part. The data part contains the data actually stored by the node. The link part consists of one or more pointers to other nodes. These pointers contain the addresses in memory of other nodes.

A linked list consists of a node that is the head or first node, that links to another node, that in turn links to another node, until finally the last node has a link set to NULL.

typedef struct node {
	char data; 
	struct node *link;
} NODE;

Nodes are created dynamically as needed during run time. In C, we do this using the malloc() function contained in the <stdlib.h> library. Linked-list nodes are created by dynamically allocating chunks of memory large enough to store the node. The nodes must be set to either point to another node, or else by NULL if it is at the end of the list.

void displayList(NODE *ptr);

int main()
{
	NODE *nOne, *nTwo, *nThree, *nFour;

	nOne = (NODE *)malloc(sizeof(NODE));
	nTwo = (NODE *)malloc(sizeof(NODE));
	nThree = (NODE *)malloc(sizeof(NODE));
	nFour = (NODE *)malloc(sizeof(NODE));

	nOne->data = 't';
	nOne->link = nTwo;

	nTwo->data = 'r';
	nTwo->link = nThree;

	nThree->data = 'e';
	nThree->link = nFour;

	nFour->data = 'e';
	nFour->link = NULL;


	displayList(nOne);

    return 0;
}

void displayList(NODE *ptr) {
	while (ptr != NULL) {
		printf("%c\t", ptr->data);
		ptr = ptr->link;
	}
	printf("\n\n");
}

As linked-lists are created dynamically, just adding a node isn’t just adding a node. Whenever we add a node, we have to consider several possible cases according to where in the list the node is being added and whether or not the list is empty.

The addNode() function uses a while loop to find the last node in the list before  allocating a new node and attaching it to the last node.

Adding a new node to the beginning of the list is simpler.

typedef struct node {
	int data;
	struct node *link;
} NODE;

void showList(NODE *ptr);
void addNode(NODE **ptr, int data);
void prependNode(NODE **ptr, int data);

int main() {
	
	const int buffer_size = 64;

	char buffer[buffer_size];
	NODE *n = NULL;
	int i = 0;
	int data;
	
	while (i++ < 5) { 		printf("Please enter a number: "); 		fgets(buffer, buffer_size, stdin); 		addNode(&n, atoi(buffer)); 	} 	 	printf("The link list is: \n"); 	showList(n); 	 	return 0; } void showList(NODE *ptr) { 	while (ptr != NULL) { 		printf("%d\t", ptr->data);
		ptr = ptr->link;
	}
}

void prependNode(NODE **ptr, int data) {
	NODE *nOne = (NODE *)malloc(sizeof(NODE));
	if (nOne != NULL) {
		nOne->data = data;
		nOne->link = *ptr;
		*ptr = nOne;
	}
}

void addNode(NODE **ptr, int data) {
	NODE *pOne, *pTwo;

	pOne = *ptr;
	if (pOne == NULL) {
		//empty list
		pOne = (NODE *)malloc(sizeof(NODE));
		if (pOne != NULL) {
			pOne->data = data;
			pOne->link = NULL;
			*ptr = pOne;
		}
	}
	else {
		while (pOne->link != NULL) {
			pOne = pOne->link;
		}
		pTwo = (NODE *)malloc(sizeof(NODE));
		if (pTwo != NULL) {
			pTwo->data = data;
			pTwo->link = NULL;
			pOne->link = pTwo;
		}
	}
}

Sometimes we may need to delete a node from a linked list. We can delete a node from the beginning of the linked list, from the end of the list, or from somewhere in the middle. We use the free() function to return the memory back to the heap.

void deleteFromHead(NODE **ptr) {
	NODE *head;
	head = *ptr;
	if (head != NULL) {
		head = head->link;
		free(*ptr);
	}
	*ptr = head;
}

To delete the node from the tail of a linked list we search to find the last node in the list.

typedef struct node {
	double data;
	struct node *link;
} NODE;

void viewList(NODE *ptr);
void deleteTail(NODE **ptr);

int main() {
	
	NODE *nOne, *nTwo, *nThree, *nFour;

	nOne = (NODE *)malloc(sizeof(NODE));
	nTwo = (NODE *)malloc(sizeof(NODE));
	nThree = (NODE *)malloc(sizeof(NODE));
	nFour = (NODE *)malloc(sizeof(NODE));

	nOne->data = 2.718;
	nOne->link = nTwo;

	nTwo->data = 1.491625;
	nTwo->link = nThree;

	nThree->data = 169.254;
	nThree->link = nFour;

	nFour->data = 0.57721;
	nFour->link = NULL;

	viewList(nOne);

	deleteTail(&nOne);

	viewList(nOne);

	return 0;
}

void viewList(NODE *ptr) {
	printf("\n");
	while (ptr != NULL) {
		printf("%f\t", ptr->data);
		ptr = ptr->link;
	}
	printf("\n");
}

void deleteTail(NODE **ptr) {
	NODE *nOne, *nTwo;

	nOne = *ptr;
	if (nOne != NULL)
	{
		if (nOne->link == NULL) {
			free(*ptr);
			*ptr = NULL;
		}
		else {
			nTwo = nOne;
			while (nOne->link != NULL) {
				nTwo = nOne;
				nOne = nOne->link;
			}
			nTwo->link = NULL;
			free(nOne);
		}
	}
}

 

Allocating and Freeing Dynamic Variables in C

We create a pointer variable to an integer with the declaration int *p; Having declared a variable p as a pointer to a specific type, it is possible to dynamically create an object of that type and assign its address to p.

We do this by calling the standard library function malloc(), which dynamically allocates a portion of memory of a specified size and returns  a pointer to it.

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

int main(void){

    int *i, *j;

    int x;

    i = (int *) malloc(sizeof(int));

    *i = 1138;

    j = i;

    printf("%d %d\n", *i, *j);

    x = 73;

    *i = x;

    printf("%d %d\n", *i, *j);

    *i = 5;

    printf("%d %d\n", *i, *j);

    return 0;

}

The sizeof operator returns the size, in bytes, of its operand.  We can use sizeof in conjunction with malloc() to get an object of the proper size.

The free() function is used to return allocated storage. Calling free() on a pointer makes the memory pointed to by the pointer available for reuse.  While most operating systems “clean up” memory after a program exits, it’s still really a good idea to explicitly clean up any dynamically allocated memory ourselves.

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

int main(void){

    int *p = (int *)malloc(sizeof(int));
    int *q = (int *)malloc(sizeof(int));
    double *d = (double *)malloc(sizeof(double));
    double *e = (double *)malloc(sizeof(double));

    *p = 404;
    *q = 711;
    free(p);    
    p = q;
    printf("%d %d\n", *p, *q);
    
    *d = 0.57721;
    *e = 1.12358;

    printf("%f %f\n", *d, *e);

    free(e);
    e = d;
    *d += 7.11;

    printf("%f %f\n", *d, *e);

    //clean up time
    free(d);
    free(q);
        
    return 0;

}

As we have seen in these past two programs, if two pointers point at the same variable, they are functionally identical. Thus, an assignment to one changes the value of the other.

Next, let’s take a look at creating a linked list using dynamic variables. A linked list consists of a set of nodes, each of which has two fields: an information field and a pointer to the next node in the list. In addition, we have an external pointer that points to the first node in the list.

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

struct node * getNode();

struct node{
    int data;
    struct node *next;
};

int main(void){

    struct node *begin, *temp;    
    struct node *nodePtr;

    temp = getNode();
    temp->data = 42;
    
    begin = temp;
    nodePtr = temp;
    
    nodePtr->next = getNode();
    temp = nodePtr->next;

    temp->data = 73;
    nodePtr = temp;
    nodePtr->next = getNode();

    temp = nodePtr->next;
    temp->data = 1999;
    temp->next = NULL;

    nodePtr = begin;

    while(1){
        printf("%d\n", nodePtr->data);
        if(nodePtr->next==NULL){
            break;
        } else {
            nodePtr = nodePtr->next;
        }
    }
    
    return 0;

}

struct node * getNode(){
    struct node *p;
    p = (struct node *)malloc(sizeof(struct node));
    return p;
}

When looking at the above code, we should ask ourselves how we would go about returning all of the nodes’ memory to the heap.

Note that the getnode() function could as well be implemented via a macro.

Next, let’s look at implementing a list as a queue. A queue follows the first in, first out principle – the first item to be inserted into a queue, will also be the first to be taken out. To do this, we will create a second structure, known as a queue. This structure will have two fields; the first field will be a node pointer to the first node in the list, and the second pointer will be a pointer to the last node in the list.

Our function for getting a queue will initialize both of these fields to NULL. We will then implement two functions, pop() and push(). The pop() function takes a node out out of the queue, frees it in memory, and then returns the value it was storing. The push() function creates a new node, assigns its data field a value, and then assigns it to the end of the queue.

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

struct node *getNode();
struct queue * getQueue();
int empty(struct queue *q);
void push(struct queue *q, int x);
int pop(struct queue *q);

struct node{
    int data;
    struct node *next;
};

struct queue{
    struct node *first;
    struct node *last;
};

int main(void){
    struct queue *q = getQueue();
    printf("queue allocated.");
    if(empty(q)){
        printf("queue is empty.\n");
    }

    push(q, 2001);
    push(q, 2600);
    push(q, 80);
    push(q, 1970);
    push(q, 1701);

    while(empty(q)==0){
        printf("%d\n", pop(q));
    }


    return 0;    
}




struct node * getNode(){
    struct node *p;
    p = (struct node *)malloc(sizeof(struct node));
    return p;
}

struct queue * getQueue(){
    struct queue *q;
    q = (struct  queue*)malloc(sizeof(struct queue));
    q->first=NULL;
    q->last=NULL;
    return q;
}    

int empty(struct queue *q){
    if(q->first==NULL){
        return 1;
    } else {
        return 0;
    }
}

void push(struct queue *q, int x){
    struct node *n = getNode();
    n->data = x;
    n->next = NULL;
    if(q->last!=NULL){
        (q->last)->next = n;    
    } else {
        q->first = n;
    }
    q->last = n;
}

int pop(struct queue *q){
    int x;
    struct node *n = q->first;
    q->first = n->next;
    if(q->first==NULL){
        q->last=NULL;
    }
    x = n->data;
    free(n);
    return x;
}

One of the nice things about working with higher level languages such as C# is that data structures such as linked lists are already implemented for us in the language.

To learn more about C, take a look at my book at http://www.amazon.com/Big-Als-C-Standard-ebook/dp/B00A4JGE0M/