Logo
Posts

How to Create a Linked List in C

How to Create a Linked List in C

Lets start by explaining what is a linked list and why we even use it.

What is a Linked List?

To understand what a linked list is, let's start by defining what a traditional array is.
An array is a data structure where each element is stored in a linear fashion. Here is a representation of what an array looks like in memory:

Representation of how an array looks like in memory

In the diagram above, each array element is stored in contiguous memory. You can also think of it as a collection of elements (in our case, 7 integer elements) that are tied together. One advantage of using an array is fast access. Accessing an element in an array has a time complexity of O(1), making it really fast. In most programming languages, you can do this by writing something like arr[2] to get the 3rd item in the array (note that array indexing starts from '0'). Here's another way of doing the same thing in C:"

int arr[5] = {10, 12, 6, 7, 9}; 
int *p = &arr[0] + 2;

printf("\The third element is: %d", *p);

This is a great way to understand how it works. Here, we can see that we first get the address of the first item in the array, and then we simply move two steps forward to access the 3rd item. This works because the addresses of the values in the array are stored in a single memory block arranged linearly.

Alright, enough about arrays. The real question here is: what is a linked list, and why would we use it instead of an array?

A linked list is a linear collection of nodes, where each node points to the next one. Think of it like a chain: there is a head and a tail, and each part of the node is connected to another node. Here’s a diagram representing how it looks:

Diagram of how a linked list looks like

In the diagram above, we can see that the node with the value 8 points to 6, 6 points to 11, and so on, until 13 points to 4. The value 4 is the last node, so it points to NULL, meaning it doesn't reference any data in memory.

Now back to our original question: why should we use a linked list over an array? Remember when I mentioned that arrays are really fast at accessing data? That’s true, but the problem with arrays is that they are slow when it comes to insertion or deletion. If you look at the array diagram, now imagine I ask you how to insert the value 10 between 11 and 5. What would your answer be? The solution is to set the 3rd index to 5 and shift all the values after it by one position. The same applies to deletion, except the values afterward would shift backward by one. You can see how this could take longer, especially with a large array. This process takes O(n) time in the worst case.

Now, look at the linked list diagram. How do you think insertion and deletion work here? To insert a new node, I would make 11 point to 10 (the new node) and 10 point to 5. Notice that we didn’t have to rearrange the list. If it’s still unclear, think of it like a chain with 5 links connected to each other, and you want to add one link in the middle. You would simply open the chain in the middle, insert the new link, and then reconnect the other part of the chain. No need for rearranging. The same logic applies to deletion—this time, you’re removing a node and connecting the two ends together. This process takes O(1) time in the worst case.

However, accessing a node in a linked list is more time-consuming. Unlike arrays, linked lists are not stored in contiguous memory blocks. Each node contains a pointer to the next node. To access an element in a linked list, you have to move through each node sequentially until you reach the desired element, which takes O(n) time in the worst case.

In contrast, elements in arrays are stored in contiguous memory. This means that to access an element in an array, you simply get the address of the first element and add the index value to it (see the code above to see this implemented in C).

Coding Starts Here

Now it's time to start coding our linked list in C.

I like to start with the objectives we want our code to accomplish:

  • Create a student struct that includes the student's name, age, grade, and subjects taken.
  • This is a linked list, so each student should point to the next student.
  • Print out the list in the console.
  • Create new nodes using a function.
  • Retrieve a student from the list using their name.
  • Insert a new node into the list.
  • Delete a node from the list.
  • BONUS: Reverse the linked list.

Creating the Student struct

#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
  
typedef struct Student {  
  char* name;  
  char* subject;  
  unsigned int age;  
  char grade[3];  
  struct Student* next; // Points to the next student
} Student;

Printing our list

void printList(Student* student) {  
  if (student == NULL) {  
    fprintf(stderr, "Empty student data in printList\n");  
    return;  
 }  
  Student* tmp = student;  
  
  while (tmp->next != NULL) {  
    printf("(%s, %s, %s, %d)->", tmp->name, tmp->subject, tmp->grade, tmp->age);  
    tmp = tmp->next;  
 }  
  printf("(%s, %s, %s, %d)", tmp->name, tmp->subject, tmp->grade, tmp->age);  
}

The tmp variable starts by being equal to the head of the list. After that, we check if the next node is NULL (which would indicate the tail node, since it doesn’t point to any other node). Inside the while loop, on each iteration, we set the tmp variable to be equal to the next node.

At the end of the while loop, tmp will be equal to the tail node, and then we print it out. Notice that in the printf function inside the loop, we end with ->, but we don’t do this for the one outside the loop. This is for formatting purposes, since the tail node doesn’t point to any other node.

Create a new nodes using a function.

void inserNodeToHead(Student** head, Student* newNode) {  
  if (newNode == NULL) return;  
  
  newNode->next = *head;  
  *head = newNode;  
}

Our list is designed so that nodes are inserted at the head. This function is meant to handle that. The head argument is a double pointer because we need to update the head node variable within the main function.

Student* createNode(char* name, char* subject, char grade[3], const int age) {  
  Student* student = malloc(sizeof(*student));  
  student->name = name;  
  student->subject = subject;  
  student->age = age;  
  snprintf(student->grade, sizeof(student->grade), "%s", grade);  
  student->next = NULL;  
  
  return student;  
}

We create our node using this function. Notice how we are using malloc here; this helps us dynamically allocate memory for our list as it grows. So, if we have one node, we ensure we are only allocating memory for that node, and if we decide to add another node, we allocate memory for that one as well. This approach is better because it ensures we are only using what we need. For now, we will set student->next to NULL, and later in the main function, after creating our node, we will pass it to the insertNodeToHead function.

Retrieve a student from the list using their name.

Student* getNode(Student* head, const char* name) {  
  Student* tmp = head;  
  
  while (tmp != NULL && strcmp(tmp->name, name) != 0) {  
	  tmp = tmp->next;  
 }  
  return tmp;  
}

To retrieve a student, we first set the tmp variable to the head node and loop until tmp->name matches our desired name. Once found, we return the node.

Insert a new node into the list.

void insertNode(Student* nodeToInsertAt, Student* newNode) {  
  if (newNode == NULL) return;  
  
  newNode->next = nodeToInsertAt->next;  
  nodeToInsertAt->next = newNode;  
}

This can be confusing, so I will explain what is happening here as clearly as I can.
The newNode we created is pointing to the next node of nodeToInsertAt, and then we set nodeToInsertAt->next (which is the next node) to point to our newNode. Here’s a diagram representing what this code is doing:

A Diagram representation of how a node is inserted in a linked list

Deleting a node from the list.

void deleteNode(Student** head, const char* name) {  
  Student* tmp = *head;  
  Student* prev = NULL;  
  
  while (tmp->next != NULL && tmp->name != name) {  
	  prev = tmp;  
	  tmp = tmp->next;  
  }  
  if (prev != NULL) {  
	  prev->next = tmp->next;  
  } else {  
	  // This means the node to delete is the head node
	  *head = tmp->next;  
  }
 }

This is somewhat similar to the insertion; the only difference here is that we have a prev variable to track our previous node. The reason for having the prev variable is that once we find the node we want to delete, we simply set the next node for prev to be equal to the next node of the node we want to delete. Think back to the chain example— all we are doing is removing a link and joining the two disconnected ends.

Lets create our main function

typedef struct studentData {  
  char* name;  
  char* subject;  
  char grade[3];  
  unsigned int age;  
} studentData;

int main(void) {  
  studentData data[10] = {  
  {"Mark", "Science", "B", 11},  
  {"Jeff", "English", "C+", 12},  
  {"Sam", "History", "A", 10},  
  {"Clifford", "Maths", "A+", 10},  
  {"Alex", "Geography", "B+", 11},  
  {"James", "Maths", "D", 13},  
  {"Tom", "Science", "C", 12},  
  {"Peter", "English", "B", 11},  
  {"John", "History", "A", 10},  
  {"Steve", "Geography", "C+", 12}  
  };  
  
  Student* head = NULL;  
  
  const int studentDataLen = sizeof(data) / sizeof(data[0]);  
  
  for (int i = 0; i < studentDataLen; i++) {  
	  Student* newNode = createNode(data[i].name, data[i].subject, data[i].grade, data[i].age);  
	  inserNodeToHead(&head, newNode);  
 }  
  Student* nodeToInsertAt = getNode(head, "Clifford");  
  
  Student* newNode = createNode("Cassie", "Science", "A+", 7);  
  
  insertNode(nodeToInsertAt, newNode);  
  
  deleteNode(&head, "James");  
  
  printList(head);  
  
  return 0;  
}

First, we create a studentData struct to help us generate some dummy data. Inside our for loop, we create a new node for each piece of data and insert it at the head. The remaining lines of code simply call the functions we created earlier.

Run the function to see the printed output. If you don’t know C and just want to run the program, you can check out the Hello World tutorial I wrote - Hello world

BONUS: Reverse the linked list.

I’m going to make this an assignment for you to try your hand at: reverse the returned linked list. You can check out my solution here once you're done: Reverse Linked List.

Also, try to clean up the linked list from memory if you can. I will include the solution for this in the GitHub code. Happy coding! 🎉

You can find the full code here:
https://github.com/cliffordaustin/LinkedList/blob/5761a7e71b2956d236899ae4d1e66a6d9116b1b5/main.c.