1.
Introduction
2.
Linear Data Structures
3.
Arrays
3.1.
C
4.
4.1.
C
5.
Stack
5.1.
C
6.
Queue
6.1.
C
7.
7.1.
Efficient Memory Usage (Arrays)
7.2.
7.3.
7.4.
Sequential Access
8.
8.1.
Fixed Size (Arrays)
8.2.
Costly Operations (Arrays)
8.3.
8.4.
8.5.
9.
Non-Linear Data Structures
10.
Trees
10.1.
C
11.
Graphs
11.1.
C
12.
12.1.
Efficient Data Organization (Trees)
12.2.
Flexibility (Graphs)
12.3.
Efficient Relationship Representation
12.4.
Scalability
13.
13.1.
13.2.
Complexity in Traversal
13.3.
Balancing Issues (Trees)
13.4.
Difficulty in Modification
14.
Difference of Linear and Non-Linear Data Structure
15.
15.1.
What makes a data structure "linear"?
15.2.
Can you convert a linear data structure to a non-linear one?
15.3.
Why would you choose a non-linear data structure over a linear one?
16.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Data Structures in C Programs

Rahul Singh
0 upvote

## Introduction

Data structures are fundamental to programming, allowing us to organize & store data efficiently in our computer programs. Whether it's managing a list of student names or processing complex mathematical operations, data structures come into play, making our code cleaner, faster, & more scalable.

In this article, we'll look into the essential types of data structures in C programming, focusing on linear & non-linear structures. You'll learn how these structures work, when to use them, & see practical examples to apply in your own projects.

## Linear Data Structures

Linear data structures are like a line of people waiting for their turn at the counter. Each person stands behind another, forming a straight line. In computer science, linear data structures organize data in a sequence, one after another, making it easy to add, remove, and access elements in order.

## Arrays

An array is a collection of items stored at contiguous memory locations. Think of it as a row of lockers, each with a unique number. You can store and retrieve items from these lockers using their numbers.

Here's a simple example in C:

• C

### C

``#include <stdio.h>int main() {    int numbers[5] = {1, 2, 3, 4, 5};  // An array of 5 integers    printf("Third element: %d\n", numbers[2]);  // Accessing the third element    numbers[2] = 10;  // Changing the value of the third element    printf("Updated third element: %d\n", numbers[2]);    return 0;}``

Output

``````Third element: 3
Updated third element: 10``````

This example demonstrates a graph with 5 vertices, using a 2D array (graph[V][V]) to represent connections between them. A 1 at graph[i][j] indicates a connection between vertex i and j, while a 0 signifies no connection.

A linked list is a series of connected "nodes". Each node contains data and a reference (or link) to the next node in the sequence. Unlike an array, elements are not stored in contiguous memory locations.

Here's how you can define a simple linked list node in C:

• C

### C

``#include <stdio.h>#include <stdlib.h>// A structure to represent a nodestruct Node {    int data;    struct Node* next;};// Function to add a new node at the beginningvoid push(struct Node** head_ref, int new_data) {    // Allocate node    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));    // Put in the data    new_node->data  = new_data;    // Link the old list off the new node    new_node->next = (*head_ref);    // Move the head to point to the new node    (*head_ref)    = new_node;}// Function to print nodes in a given linked listvoid printList(struct Node *node) {    while (node != NULL) {        printf(" %d ", node->data);        node = node->next;    }}int main() {    // Start with the empty list    struct Node* head = NULL;    // Add elements in linked list    push(&head, 5);    push(&head, 4);    push(&head, 3);    push(&head, 2);    push(&head, 1);    puts("Created Linked List: ");    printList(head);    return 0;}``

Output

``````Created Linked List:
1  2  3  4  5 ``````

In this example, we define a Node structure with two members: data and next. We then create a simple function, push, to add new nodes at the beginning of the list, & printList to display the list. This demonstrates how linked lists allow for flexible data management, where you can easily insert and remove elements without reallocating the entire structure.

## Stack

A stack operates on the principle of Last In, First Out (LIFO), where the last element added to the stack is the first one to be removed. Common operations include push (to add an element to the top of the stack) and pop (to remove the top element from the stack).

Here's a simple implementation of a stack using an array in C:

• C

### C

``#include <stdio.h>#define MAX 5  // Defining maximum size of the stackint stack[MAX];int top = -1;// Function to add an element to the stackvoid push(int data) {    if (top >= MAX - 1) {        printf("Stack Overflow\n");    } else {        stack[++top] = data;  // Increment top and add data        printf("%d pushed to stack\n", data);    }}// Function to remove an element from the stackint pop() {    if (top < 0) {        printf("Stack Underflow\n");        return 0;    } else {        int data = stack[top--];  // Remove data and decrement top        return data;    }}// Driver code to test the stack operationsint main() {    push(10);    push(20);    push(30);    printf("%d popped from stack\n", pop());    return 0;}``

Output

``````10 pushed to stack
20 pushed to stack
30 pushed to stack
30 popped from stack``````

In this example, push adds an element to the stack unless it's full, indicated by a "Stack Overflow" message. The pop function removes and returns the top element, or signals "Stack Underflow" if the stack is empty.

## Queue

A queue operates on the principle of First In, First Out (FIFO), where the first element added to the queue is the first one to be removed. Key operations include enqueue (to add an element to the rear of the queue) and dequeue (to remove an element from the front of the queue).

Here's a simple implementation of a queue using an array in C:

• C

### C

``#include <stdio.h>#define MAX 5  // Defining maximum size of the queueint queue[MAX];int front = 0, rear = -1;// Function to add an element to the queuevoid enqueue(int data) {    if (rear >= MAX - 1) {        printf("Queue Overflow\n");    } else {        queue[++rear] = data;  // Increment rear and add data        printf("%d enqueued to queue\n", data);    }}// Function to remove an element from the queueint dequeue() {    if (front > rear) {        printf("Queue Underflow\n");        return 0;    } else {        int data = queue[front++];  // Remove data and increment front        return data;    }}// Driver code to test the queue operationsint main() {    enqueue(10);    enqueue(20);    enqueue(30);    printf("%d dequeued from queue\n", dequeue());    return 0;}``

Output

``````10 enqueued to queue
20 enqueued to queue
30 enqueued to queue
10 dequeued from queue``````

In this queue implementation, enqueue adds an element to the rear of the queue unless it's full, indicated by a "Queue Overflow" message. The dequeue function removes and returns the front element, or signals "Queue Underflow" if the queue is empty, determined by the front being greater than the rear.

## Advantages of Linear Data Structures

Simplicity in Implementation: Linear data structures like arrays and linked lists are straightforward to implement. Their simple memory organization allows for easy data access and manipulation, making them ideal for beginners to understand and use in programming.

### Efficient Memory Usage (Arrays)

Arrays have a compact memory layout, which can lead to efficient use of memory. Since elements are stored in contiguous memory locations, accessing elements in an array is fast due to locality of reference, which enhances cache performance.

Unlike arrays, linked lists are dynamic in size. This means they can grow or shrink at runtime, allowing for efficient memory utilization based on the program's needs without wasting resources.

### Ease of Insertion/Deletion (Linked Lists)

Linked lists enable easy insertion and deletion of elements without the need to shift elements, as would be necessary in an array. This makes linked lists particularly useful for applications where frequent addition and removal of data are required.

### Sequential Access

Linear data structures are designed for efficient sequential access to elements. This makes them suitable for applications where data needs to be processed in order, such as in file IO operations or handling streams of data.

## Disadvantages of Linear Data Structures

### Fixed Size (Arrays)

Once an array is declared, its size is fixed and cannot be altered at runtime, leading to either wasted space if the array is too large or insufficient space if the array is too small.

### Costly Operations (Arrays)

Operations like insertion and deletion in arrays can be costly, especially for large datasets, as they require shifting elements to maintain the array's contiguous nature.

Each element in a linked list requires additional memory for storing the pointer to the next (and possibly previous) element, leading to increased memory usage compared to arrays.

Linked lists do not allow direct access to their elements. To access an element, you must traverse the list from the beginning, which can be inefficient for large lists.

The non-contiguous storage of linked list elements can lead to poor cache performance, as adjacent elements in the list may not be located close to each other in memory.

## Non-Linear Data Structures

Non-linear data structures don't line up their elements in a single sequence. Instead, they branch out in different directions, creating a more complex network of connections. This structure allows for more flexible and efficient ways to organize and access data, particularly when dealing with hierarchical or multi-dimensional data sets.

## Trees

A tree is a collection of nodes where one node is marked as the root, and all the other nodes are connected by edges, forming a parent-child relationship. The best example of a tree in real life is, well, a tree! There's a root, a trunk, branches, and then leaves, all connected in a hierarchical structure.

Here's a simple example of a binary tree in C, where each node has at most two children:

• C

### C

``#include <stdio.h>#include <stdlib.h>// A structure to represent a node of the treestruct Node {    int data;    struct Node *left, *right;};// Function to create a new nodestruct Node* newNode(int data) {    struct Node* node = (struct Node*)malloc(sizeof(struct Node));    node->data = data;    node->left = node->right = NULL;    return node;}// Function to print the nodes of the tree in in-order fashionvoid printInOrder(struct Node* node) {    if (node == NULL) return;    // first recur on left child    printInOrder(node->left);    // then print the data of node    printf("%d ", node->data);    // now recur on right child    printInOrder(node->right);}int main() {    struct Node *root = newNode(1);    root->left             = newNode(2);    root->right           = newNode(3);    root->left->left     = newNode(4);    root->left->right   = newNode(5);     printf("In-order traversal of the binary tree is \n");    printInOrder(root);    return 0;}``

Output

``````In-order traversal of the binary tree is
4 2 5 1 3 ``````

In this code, we define a Node structure representing each tree node, which has data and pointers to the left and right child nodes. We use newNode to create a node and printInOrder to traverse the tree in in-order fashion (left, root, right), which prints the nodes in ascending order for a binary search tree.

## Graphs

Graphs are a set of connected nodes (or vertices) where the connections (or edges) between them can represent relationships or distances. Unlike trees, graphs can have cycles, meaning you might return to the same node without retracing your steps.

A simple graph representation in C using an adjacency matrix:

• C

### C

``#include <stdio.h>#define V 5// Function to print the adjacency matrixvoid printGraph(int graph[][V]) {    for (int i = 0; i < V; i++) {        for (int j = 0; j < V; j++)            printf("%d ", graph[i][j]);        printf("\n");    }}int main() {    int graph[V][V] = {        {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}    };    printGraph(graph);    return 0;}``

Output

``````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 ``````

## Advantages of Non-Linear Data Structures

Hierarchy Representation: Non-linear data structures like trees provide a natural representation of hierarchical relationships, making them ideal for applications like file systems, organizational structures, and category classifications.

### Efficient Data Organization (Trees)

Trees, especially binary search trees, allow for efficient organization and retrieval of data. Operations like search, insert, and delete can be performed quickly if the tree is balanced.

### Flexibility (Graphs)

Graphs provide a flexible structure to represent various real-world problems, from networks and social media connections to maps and routing algorithms.

### Efficient Relationship Representation

Non-linear data structures can efficiently represent complex relationships and connections between data elements, which is essential for algorithms like those used in networking and database management.

### Scalability

Non-linear data structures can handle large, complex datasets more effectively than linear structures, as they can organize data in a multi-dimensional manner, reducing the time complexity for many operations.

## Disadvantages of Non-Linear Data Structures

Complexity in Implementation: Non-linear data structures are more complex to implement and understand than linear structures. This complexity can lead to increased development time and a higher risk of errors.

Non-linear structures like trees and graphs often require additional memory for storing pointers or edges, leading to higher memory consumption.

### Complexity in Traversal

Traversing non-linear data structures can be complex and requires recursive algorithms, which can be difficult to implement and understand, especially for those new to programming.

### Balancing Issues (Trees)

Certain types of trees, such as binary search trees, can become unbalanced with uneven data, leading to degraded performance in operations like search, insert, and delete.

### Difficulty in Modification

Modifying non-linear data structures, especially graphs, can be complex and time-consuming, as changes might affect multiple connections or relationships, requiring careful consideration to maintain integrity.

## Difference of Linear and Non-Linear Data Structure

### What makes a data structure "linear"?

In linear data structures, elements are stored in a sequential order, meaning each element is connected to its previous and next element in a single level. Examples include arrays, linked lists, stacks, and queues.

### Can you convert a linear data structure to a non-linear one?

While you can't directly "convert" a linear structure into a non-linear one, you can organize data stored in a linear structure (like an array) into a non-linear format (like a tree or graph) based on certain rules or algorithms.

### Why would you choose a non-linear data structure over a linear one?

Non-linear data structures are chosen for complex data relationships and hierarchical data organization, where operations like search, insert, and delete can be more efficient due to the structure's properties, such as in trees and graphs.

## Conclusion

In this article, we looked into the essential aspects of linear and non-linear data structures in C programming, understanding their characteristics, advantages, and disadvantages. Through practical examples, we looked into arrays, linked lists, stacks, and queues for linear structures, and trees and graphs for non-linear structures. We highlighted their applications also, which helped us to understand which data structure can be used at different places.

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMSSystem Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.