Linked list is one of the most simplest and most common data structures out there. Implementing linked lists in C is easy by using structs and pointers.

What is a linked list?

A linked list is a linear data structure that contains data elements called nodes. Each node points to the next node. Order of nodes is not necessarily the same as the order they are stored in the memory.

How to implement a linked list in C?

The most common way to implement a linked list in C is by using structs and pointers.

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

In the code above we define a struct called node. This struct contains integer data and then a pointer to another struct node.

Let's see how it works in real life...

/* Define a struct that represents a person */
struct person {
  int age;
  struct person *next;
};

/* Initialize structs for three persons */
struct node *person1 = malloc(sizeof(struct person));
struct node *person2 = malloc(sizeof(struct person));
struct node *person3 = malloc(sizeof(struct person));

/* Assign data values for each person */
person1->age = 25;
person2->age = 46;
person3->age = 68;

/* Connect persons */
person1->next = person2;
person2->next = person3;
person3->next = NULL;

Defining variable names like person1..person3 is not necessary at all. In many cases you would iterate through some data and create the linked list in that way. For example...

/* Initialize a pointer that points to the current node */
struct person *current = NULL;

/* Create persons with ages 20, 35, 50, 65, 80 and 95 */
for (int i = 20; i < 100; i = i + 15) {
  struct person *p = malloc(sizeof(struct person));
  p->age = i;
  p->next = current;
  current = p;
}

/* After this we could iterate through our linked list */
while (current != NULL) {
  printf("%d\n", current->age);
  current = current->next;
}

Why use linked lists instead of arrays for example?

The most significant advantage of linked lists is that they are dynamic in nature, allowing memory allocation only when required. Moreover, linked lists allow removing and adding nodes from the middle of the list, without shifting other elements in the memory at all.