An Overview on Singly-Linked Lists in C

Introduction

While arrays do have their virtues in areas like sorting and lookup, they can sometimes lack in element insertion, which requires lots of shifting around, and resizing, which calls for lots of dynamic memory allocation.

Luckily, another data structure in C is particularly good in these areas, being able to grow and shrink as well as insert values as the program runs.

Here is everything you should know about singly-linked lists.

Nodes

Linked lists are made up of nodes, which is just a fancy name for a custom structure consisting of some data and a pointer to another node.

This ability for one element to point to the next help creates a chain, which can be added to or subtracted from as you go.

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

*Here, struct node is a temporary name for our data type so that we can refer to it within itself, before it is formally renamed from 'struct node' to 'node' by our typedef.

Filling Linked Lists

• create a header

• dynamically allocate memory of size node to a new node

• exit if node is NULL

• fill data field using -> operator

• fill next field using -> operator to point to the list header

• make sure the header always points to the first node

• repeat for any number of nodes

// header
node *list;

// first node
node *n = malloc(sizeof(node));
if (n == NULL) 
{
	// exit program
	return 1;
}

n->data = 15;
n->next = NULL;

// header now points to first node
list = n;

// second node
// inserted at the beginning of the list
n = malloc(sizeof(node));
n->data = 4;
n->next = list;
list = n;

To create a linked list efficiently, we can use a for loop:

#define LEN = 12;

node *list = NULL;

for (int i = 0; i < LEN; i++)
{
	node *n = malloc(sizeof(node));
	if (n == NULL)
		return 1;

	n->data = 12;
	n->next = list;
	
	list = n;
}

Things to Remember

• unlike with arrays, order does not play a role in linked lists

  • no indices

  • easy to insert elements to the beginning of the list

  • difficult to insert elements to the end of the list

    • we only have access to the header pointer, so we'd need to iterate through the list linearly to reach the end, which is inefficient

• important never to sever the header's connection with the rest of list

  • ex: If these lines were reversed, and list was set to n prematurely, the node storing 1 in the diagram would have been lost, as there would be nothing pointing to it.

n->next = list;  

list = n; 

• we can search for a specific value in a linked list by creating a new pointer, pointing to the first node

  • we do this to ensure that the header pointer remains intact

  • we can loop over the list until NULL is reached (found in the next field), checking the data field for the specific value we're searching for

  • to move to the next element, simply set your pointer to the next field of the current pointer

• to delete a list

  • we must recursively call a delete function that checks until the end of the list is reached and frees the node, eventually freeing all nodes

  • we need to start at the end because destroying any of the first nodes would sever our connection with the rest, meaning that memory is never freed

Final Thoughts

Hopefully you've got a basic idea of what a singly-linked list is, when to use them, and how to implement them. Thanks for reading!