Getting Started with Data Structures in C

What are Data Structures in C?

Have you begun to learn C Programming? Are you aware of the data structures used in C language? Data Structures in C provide a method for storing and organizing data in the computer memory. A data structure is a fundamental building block for all critical operations performed on data. Effective utilization of the data structures leads to program efficiency.

In this C tutorial, we'll delve deep into the data structures used in the C language. We'll understand various types of data structures with examples. At the end of the tutorial, you'll differentiate different data structures based on their characteristics. Let's get started.

Types of Data Structures in C

1. Primitive Data Structures: These data types are predefined in the C programming language. They store the data of only one type. Data types like short,integer, float, character, and double comes in this category.

   Read More: Data Types in C Programming

2. Non-Primitive Data Structures: They can store data of more than one type. They are derived from the built-in or the primitive data types and are called derived data types. Data types like arrays, linked lists, trees, etc. come in this category. Non-Primitive Data Structures are also known as user-defined data types.

   Based on the structure and arrangement of data, these data structures are further classified into two categories

   1. Linear Data Structures: The data in this data structure is arranged in a sequence, one after the other i.e. each element appears to be connected linearly.

      Based on the memory allocation, the Linear Data Structures are again classified into two types:

      1. Static Data Structures: They have a fixed size. The memory is allocated at the compile time, and the user cannot change its size after being compiled; however, the data can be modified. e.g. array
      2. Dynamic Data Structures: They don't have a fixed size. The memory is allocated at the run time, and its size varies during the program execution. Moreover, the user can modify the size as well as the data elements stored at the run time. e.g. linked list, stack, queue
   2. Non-Linear Data Structures: The elements in this data structure are not arranged sequentially. They form a hierarchy i.e. the data elements have multiple ways to connect to other elements. e.g. tree and graph

Types of Linear Data Structures in C

1. Arrays

An Array in the C programming language is a powerful data structure that allows users to store and manipulate a collection of elements, all of the same data types in a single variable. In simple words, an array is a collection of elements of the same data type. The values get stored at contagious memory locations that can be accessed with their index number.

Syntax

dataType arrayName[arraySize];

Example of Arrays in C

#include <stdio.h>
int main(){
int i=0;
int marks[5];//declaration of array
marks[0]=90;//initialization of array
marks[1]=80;
marks[2]=75;
marks[3]=95;
marks[4]=85;

//traversal of array
for(i=0;i<5;i++){
printf("%d \n",marks[i]);
}//end of for loop
return 0;
}

In this example, an integer array named "marks" of size 5 is declared and initialized with predetermined values, with each element's index denoting a different integer value.

Output

90
80
75
95
85

There are two types of arrays in the C language:

1. Single-dimensional arrays: Here the elements are stored in a single row in contiguous memory locations. They are also known as 1D arrays.
2. Multi-dimensional arrays: They contain one or more arrays as their elements. They are known as arrays of arrays. Examples are 2D and 3D arrays.

   Read More: Multidimensional Arrays in C: 2D and 3D Arrays

2. Linked Lists

A Linked List is a linear data structure consisting of a series of connected nodes randomly stored in the memory. Here, each node consists of two parts, the first part is the data and the second part contains the pointer to the address of the next node. The pointer of the last node of the linked list consists of a null pointer, as it points to nothing. The elements are stored dynamically in the linked list.

Syntax to Declare Linked Lists in C

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

Example of Linked Lists in C Compiler

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

// Define the structure for a node
struct Node {
    int data;
    struct Node* next;
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("Memory error\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to traverse and print the linked list
void traversal(struct Node* head) {
    struct Node* itr = head;
    while (itr != NULL) {
        printf("%d\n", itr->data);
        itr = itr->next;
    }
}

// Function to insert a new node after a given previous node
void insertion(struct Node* prevNode, struct Node* newNode) {
    if (prevNode == NULL) {
        printf("The given previous node cannot be NULL\n");
        return;
    }
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

int main() {
    struct Node* head = createNode(1);
    struct Node* second = createNode(2);
    struct Node* third = createNode(3);

    head->next = second;
    second->next = third;

    // Print the initial linked list
    printf("Initial Linked List:\n");
    traversal(head);

    // Insert a new node (4) after the second node
    struct Node* newNode = createNode(4);
    insertion(second, newNode);

    // Print the linked list after insertion
    printf("\nLinked List after Insertion:\n");
    traversal(head);
}

In the above code, a linked list is created and traversed. Afterward, we insert a new node in the linked list. Again it's traversed and printed with new values.

Output

Initial Linked List:
1
2
3

Linked List after Insertion:
1
2
4
3

There are three types of Linked Lists used in C language:

1. Singly-linked list: Here, each node has dataand a pointer that contains a reference to the next node in the list. This means that we can traverse in only one direction, from the head to the tail. It is the most common linked list.
2. Doubly linked list: In this type of linked list, each interconnected node contains three fields that contain references to both the next and previous nodes in the list along with the data. This allows traversal in both directions, making it easier to insert or delete nodes at any point in the list.
3. Circular linked list: Here, the last node in the list contains a reference to the first node instead of NULL, creating a loop. This means that traversal can continue indefinitely, until the program crashes.

3. Stack

A stack is an ordered list or a container in which insertion and deletion can be done from one end known as the top of the stack. The last inserted element is available first and is the first one to be deleted. Hence, it is known as Last In, First Out LIFO, or First In, Last Out FILO. Stacks do not have a fixed size and their size can be increased or decreased depending on the number of elements.

Basic Operations on Stack

• push: It is inserting an element at the top of the stack. If the stack is full, it is said to be an Overflow condition.
• pop: It removes the topmost element of the stack and returns its value.
• peek: It returns the value of the topmost element of the stack without modifying the stack.
• isFull: It determines if the stack is full or not.
• isEmpty: It checks if the stack is empty or not

Syntax to Define a Stack in C

struct stack
{
   int myStack[capacity];
   int top;
};

Example of Stack in C

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

#define capacity 20

int count = 0;

struct STACK
{
   int myStack[capacity];
   int top;
};

void buildStack(struct STACK *stack)
{
   stack->top = -1;
}

int isStackFull(struct STACK *stack)
{
   if (stack->top == capacity - 1)
      return 1;
   else
      return 0;
}

int isEmpty(struct STACK *stack)
{
   if (stack->top == -1)
      return 1;

   else
      return 0;
}

void push(struct STACK *stack, int dataValue)
{
   if (isStackFull(stack))
   {
      printf("Overflow! The stack is full.");
   }
   else
   {
      stack->top++;
      stack->myStack[stack->top] = dataValue;
   }
   count++;
}

void pop(struct STACK *stack)
{
   if (isEmpty(stack))
   {
    printf("\nUnderflow! The stack is empty. \n");
   }
   else
   {
      printf("The deleted value is: %d\n", stack->myStack[stack->top]);
      stack->top--;
   }
   count--;
}

void printValues(struct STACK *stack)
{
   printf("The elements of the stack are:\n");
   for (int i = 0; i < count; i++)
   {
      printf("%d \n", stack->myStack[i]);
   }
}

int main()
{
   struct STACK *stack = (struct STACK *)malloc(sizeof(struct STACK));
   
   // create a stack.
   buildStack(stack);

   // insert data values into the stack.
   push(stack, 150);
   push(stack, 270);
   push(stack, 330);
   push(stack, 400);

   // print the stack elements.
   printValues(stack);

   // delete an item at the top.
   pop(stack);

   // print the stack elements after performing the pop operation.
   printf("\nThe stack elements after the pop operation: \n");

   printValues(stack);
}

The above program in the C Editor demonstrates the creation of a Stack and its associated operations.

Output

The elements of the stack are:
150 
270 
330 
400 
The deleted value is: 400

The stack elements after the pop operation: 
The elements of the stack are:
150 
270 
330

3. Queue

A queue is an ordered list in which insertion is done at one end called REAR and deletion at another end called FRONT. The first inserted element is available first for the operations to be performed and is the first one to be deleted. Hence, it is known as First In First Out, FIFO, or Last In Last Out, LILO.

Basic Operations on Queue

• enqueue: It is used to insert an element at the back of a queue or to the end or the rear end of the queue.
• dequeue: It removes and returns the element from the front of a queue.
• peek: It returns the value at the front end of the queue without removing it.
• isFull: It determines if the queue is full or not.
• isEmpty: check if the queue is empty or not. It returns a boolean value, true when the queue is empty, otherwise false.

Syntax to define a Queue in C

struct Queue {
   int myQueue[capacity]; 
   int front, rear;
};

Example of Queue in C

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

#define capacity 15

struct QUEUE
{
    int front, rear, size;
    int myQueue[capacity];
};

void buildQueue(struct QUEUE *queue)
{
    queue->front = -1;
    queue->rear = -1;
} 

int isFull(struct QUEUE *queue)
{
    if (queue->front == 0 && queue->rear == capacity - 1)
        return 1; 
    else
        return 0;
}

int isEmpty(struct QUEUE *queue)
{
    if (queue->front == -1)
        return 1;
    else
        return 0;
}

void enqueue(struct QUEUE *queue, int item)
{
    if (isFull(queue))
        return;
    else
    {
        if (queue->front == -1)
            queue->front = 0;

        queue->rear++;

        queue->myQueue[queue->rear] = item;
    }
}

void dequeue(struct QUEUE *queue)
{
    if (isEmpty(queue))
    {
        printf("The queue is empty.\n");
        return;
    }

    else
    {
        int deletedValue = queue->myQueue[queue->front];
        if (queue->front >= queue->rear)
        {
            queue->front = -1;
            queue->rear = -1;
        }
        else
        {
            queue->front++;
        }
        printf("The deleted value is: %d\n", deletedValue);
    }
}

void printValues(struct QUEUE *queue)
{
    printf("The elements of the queue are:\n");
    for (int i = queue->front; i <= queue->rear; i++)
    {
        printf("%d \n", queue->myQueue[i]);
    }
}

int main()
{
    struct QUEUE *queue = (struct QUEUE *)malloc(sizeof(struct QUEUE)); 

    // create a queue.
    buildQueue(queue); 
    enqueue(queue, 160);
    enqueue(queue, 208);
    enqueue(queue, 390);
    enqueue(queue, 450); 

    // print the queue elements.
    printValues(queue); 

    // delete an item from the queue.
    dequeue(queue);

     // print the queue elements after performing the dequeue operation.
    printf("\nThe queue elements after the queue operation: \n");
    printValues(queue);

   printf("\n\n");
}

In the above code, we defined a queue. After that, we perform insertion, deletion, and print operations on the queue.

Output

The elements of the queue are:
160 
208 
390 
450 
The deleted value is: 160

The queue elements after the queue operation: 
The elements of the queue are:
208 
390 
450

Types of Non-Linear Data Structures in C

1. Graphs

A graph is a collection of nodes that consist of data and are connected to other nodes of the graph. Formally a Graph is composed of a set of vertices( V ) and a set of edges( E ). The graph is denoted by G(V, E). In a graph, each entity is symbolized by a vertex, while edges denote the connections or associations between entities.

There are two ways to represent a graph in C:

1. Adjacency Matrix: It's a 2D array of size V x V where V is the number of nodes in a graph. It represents a finite graph, with 0's and 1's. It is a square matrix since it's a V x V matrix. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph i.e. if there is any edge connecting a pair of nodes in the graph.

   Example of Adjacency Matrix Representation of Graph in C

   
   #include <stdio.h>
   #include <stdlib.h>
   
   #define MAX_VERTICES 10
   
   void initializeMatrix(int matrix[MAX_VERTICES][MAX_VERTICES], int numVertices) {
       for (int i = 0; i < numVertices; i++) {
           for (int j = 0; j < numVertices; j++) {
               matrix[i][j] = 0;
           }
       }
   }
   
   // Function to add an edge to the graph
   void addEdge(int matrix[MAX_VERTICES][MAX_VERTICES], int start, int end) {
       if (start >= MAX_VERTICES || end >= MAX_VERTICES || start < 0 || end < 0) {
           printf("Invalid edge!\n");
       } else {
           matrix[start][end] = 1;
           matrix[end][start] = 1; // For an undirected graph
       }
   }
   
   // Function to print the adjacency matrix
   void printMatrix(int matrix[MAX_VERTICES][MAX_VERTICES], int numVertices) {
       for (int i = 0; i < numVertices; i++) {
           for (int j = 0; j < numVertices; j++) {
               printf("%d ", matrix[i][j]);
           }
           printf("\n");
       }
   }
   
   int main() {
       int numVertices = 5; 
       int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES];
   
       initializeMatrix(adjacencyMatrix, numVertices);
   
       addEdge(adjacencyMatrix, 0, 1);
       addEdge(adjacencyMatrix, 0, 4);
       addEdge(adjacencyMatrix, 1, 2);
       addEdge(adjacencyMatrix, 1, 3);
       addEdge(adjacencyMatrix, 1, 4);
       addEdge(adjacencyMatrix, 2, 3);
       addEdge(adjacencyMatrix, 3, 4);
   
       printf("Adjacency Matrix:\n");
       printMatrix(adjacencyMatrix, numVertices);
   
       return 0;
   }
   

   Try it Yourself >>

   The above program demonstrates the creation of a graph using an adjacency matrix. First of all, we initialize a matrix of size 10. Then we define a function to add an edge to the graph. At last, we print the adjacency matrix.

   Output

   Adjacency Matrix:
   0 1 0 0 1 
   1 0 1 1 1 
   0 1 0 1 0 
   0 1 1 0 1 
   1 1 0 1 0
   

2. Adjacency List: It represents a graph as an array of linked lists. The index of the array represents a vertex and each element in its linked list represents the other vertices that form an edge with the vertex.

   Example of Adjacency List Representation of Graph in C

   
   #include <stdio.h>
   #include <stdlib.h>
   
   struct AdjListNode {
       int dest;
       struct AdjListNode* next;
   };
   
   struct AdjList {
       struct AdjListNode* head;
   };
   
   struct Graph {
       int V;
       struct AdjList* array;
   };
   
   struct AdjListNode* createAdjListNode(int dest) {
       struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
       newNode->dest = dest;
       newNode->next = NULL;
       return newNode;
   }
   
   struct Graph* createGraph(int V) {
       struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
       graph->V = V;
   
       graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));
   
       for (int i = 0; i < V; ++i) {
           graph->array[i].head = NULL;
       }
       return graph;
   }
   
   void addEdge(struct Graph* graph, int src, int dest) {
       // Add an edge from src to dest. A new node is added to the adjacency list of src.
       struct AdjListNode* newNode = createAdjListNode(dest);
       newNode->next = graph->array[src].head;
       graph->array[src].head = newNode;
   
       newNode = createAdjListNode(src);
       newNode->next = graph->array[dest].head;
       graph->array[dest].head = newNode;
   }
   
   // Function to print the adjacency list representation of graph
   void printGraph(struct Graph* graph) {
       for (int v = 0; v < graph->V; ++v) {
           struct AdjListNode* pCrawl = graph->array[v].head;
           printf("\n Adjacency list of vertex %d\n head ", v);
           while (pCrawl) {
               printf("-> %d", pCrawl->dest);
               pCrawl = pCrawl->next;
           }
           printf("\n");
       }
   }
   
   int main() {
       int V = 5;
       struct Graph* graph = createGraph(V);
       addEdge(graph, 0, 1);
       addEdge(graph, 0, 4);
       addEdge(graph, 1, 2);
       addEdge(graph, 1, 3);
       addEdge(graph, 1, 4);
       addEdge(graph, 2, 3);
       addEdge(graph, 3, 4);
   
       printGraph(graph);
   
       return 0;
   }
   

   Try it Yourself >>

   The above code defines structures for nodes and lists. The createGraph() function initializes the graph, addEdge() adds edges between vertices and printGraph() displays the adjacency list of each vertex.

   Output

    Adjacency list of vertex 0
    head -> 4-> 1
   
    Adjacency list of vertex 1
    head -> 4-> 3-> 2-> 0
   
    Adjacency list of vertex 2
    head -> 3-> 1
   
    Adjacency list of vertex 3
    head -> 4-> 2-> 1
   
    Adjacency list of vertex 4
    head -> 3-> 1-> 0
   

2. Trees

Tree data structure forms a hierarchy containing a collection of nodes such that each node of the tree stores a value and a list of references to other nodes (the "children"). The topmost node of the tree is called the root node from which the tree originates, and the nodes below it are called the child nodes.

Syntax to Declare a Tree in C

struct node {
    int data;
    struct node* left;
    struct node* right;
}

There are some popular types of trees in data structures. Let's look at some of them

1. Binary Tree: In this according to the name, binary, each parent node can have at most two nodes or two children i.e. left and right child.

   

   Read More: Binary Trees in Data Structures - Types, Implementation, Applications

2. Binary Search Tree: They are special kinds of Binary Trees having some special characteristics. It is called a binary tree because each tree node has up to two children. It is called a search tree because it can search a number in O(log(n)) time. The only difference between Binary Search and Binary Search Tree is that BST uses Binary Trees to represent the data set instead of an array.

   

   Read More: Binary Search Tree in Data Structures

Choosing the Right Data Structure in C

• Understand Requirements: Start by thoroughly understanding the requirements of your application like the type of data to be stored, the frequency and nature of data operations, memory constraints, and expected performance metrics.
• Analyze Operations: Take a proper analysis of the operations that need to be performed on the data, including searching, sorting, updating, and traversing.
• Consider Time and Space Complexity: Evaluate the time and space complexity of the type of operations for various data structures.
• Size of Data Set: Different data structures and algorithms have different performance characteristics when operating on different size data sets.

Summary

Hence, in the above article, we saw all the prominent data structures in C with examples. We saw the two broad classifications of data structures as primitive and non-primitive. We got into the depth of linear and non-linear non-primitive data structures. Enroll in our C Programming Course to learn C programming in complete detail.