Single Linked lists in C

What are linked lists and how do we create them?

Imagine we want to store our names in alphabetical order and maintain them in memory. We have two options, arrays or Linked Lists. In this article we will discuss linked lists and in a separate article arrays.

Types of linked list

single linked list - navigation is forward only
doubly linked list - navigation is forward and backward

What is a singly linked list? A data structure that is made up of nodes. A node is a structure with two parts (data and link(next)) and a singly linked list is made up of many nodes.

The linked lists need not be stored in sequential memory since the next part will always point us to the next node.

Creating a node of a singly linked list

In order to create a node. We need to recall what a Self-referential structure is. This is basically a structure that contains a pointer to a structure of the same type. You can read more on self-referential structure here - https://www.geeksforgeeks.org/self-referential-structures

struct abc {
int a;
struct abc *link;
};

We are using a struct data type because it can handle different data types. In this case an integer and a pointer to a struct.

practical example node.c

#include <stdio.h> /*standard input output*/
#include <stdlib.h>/*for malloc to create memory for structure*/

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

int main()
{
  struct node *head = NULL; /*pointer to access data from the node*/
  head  = malloc(sizeof(struct node));/*allocate memory for the node*/

  head->data = 45;/*head goes inside the node and intialize the data to 45*/
  head->link = NULL;/*the link part is intialized to null*/

  printf("%d\n", head->data);
  return 0;
}

Every time you create a memory for the node, you will need a pointer to access the address of that node.

To create a singly linked list we will combine a couple of nodes and use the link part to reference the next node of the list.

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

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

int main()
{
  struct node *link, *current;
  link = malloc(sizeof(struct node));

  link->data = 45;/*create first node of the linked list*/
  link->next = NULL;

  current = malloc(sizeof(struct node));
  current->data = 98;/*second node of the list*/
  current->next = NULL;
  link->next = current;/*connect the first node to second node*/

  current = malloc(sizeof(struct node));/*we can reuse this pointer because using head we can access any part of the list*/
  current->data = 3;/*third node of the list*/
  current->next = NULL;
  link->next->next = current;/* connect third node with second node*/


  return 0;
}

In the example below we will explore

Traversing a linked list
Adding a node at the beginning of the list
Adding a node at the end of the list
Adding node at position n of the list
Counting the number of nodes in the linked list

Printing data of the linked list


 #include <stdio.h>
 #include <stdlib.h>
 struct node {
   int data;
   struct node *link;
 };
 void count_nodes(struct node *head);
 void print_data(struct node *head);
 struct node *insert_begin(struct node *head, int data);
 void insert_end(struct node *head, int data);
 void insert_position(struct node *head, int data, int position);
 int main()
 {
   struct node *head, *current;
   head = malloc(sizeof(struct node));

   head->data = 45;
   head->link = NULL;

   current = malloc(sizeof(struct node));
   current->data = 98;
   current->link = NULL;
   head->link = current;

   current = malloc(sizeof(struct node));
   current->data = 3;
   current->link = NULL;
   head->link->link = current;

   head = insert_begin(head, 1);
   insert_end(head, 67);
   insert_position(head, 100, 2);
   count_nodes(head);
   print_data(head);
   return 0;
 }
 void count_nodes(struct node *head)
 {
   int count = 0;
   if (head == NULL)
       printf("Linked list is empty");

   struct node *ptr = NULL;
   ptr = head;
   while(ptr != NULL)
   {
     count++;
     ptr = ptr->link;
   }
   printf("Number of nodes are %d\n", count);
 }
 void print_data(struct node *head)
 {
   if(head == NULL)
     printf("Linked list is empty\n");
   struct node *ptr = NULL;
   ptr = head;
   while(ptr != NULL)
   {
     printf("%d\n", ptr->data);
     ptr = ptr->link;
   }
 }

 struct node *insert_begin(struct node *head, int data)
 {
   struct node *newnode;

   newnode = malloc(sizeof(struct node));
   newnode->data = data;
   newnode->link = NULL;

   newnode->link = head;
   head = newnode;
   return head;
 }

 void insert_end(struct node *head, int data)
 {
   struct node *ptr, *newnode;
   ptr = head;
   newnode = malloc(sizeof(struct node));
   newnode->data = data;
   newnode->link = NULL;

   while(ptr->link != NULL)
     ptr = ptr->link;

   ptr->link = newnode;
 }
 void insert_position(struct node *head, int data, int position)
 {
   struct node *newnode, *temp;

   temp = head;

   newnode = malloc(sizeof(char));
   newnode->data = data;
   newnode->link = NULL;

   position--;
   while (position != 1)
   {
     temp = temp->link;
     position--;
   }
   newnode->link = temp->link;
   temp->link = newnode;
 }

 output:
 Number of nodes are 6
 1
 100
 45
 98
 3
 67

I have created separate functions for each operation and called those functions in the main function.

With this article, I hope you can create now create your own linked list and add items at the beginning and at the end of your singly linked list in C.

Single Linked lists in C

Table of contents

No headings in the article.