Data Structures in C Programs

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.

What are 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

#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;
}

You can also try this code with Online C Compiler

Run Code

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.

Linked Lists

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

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

// A structure to represent a node
struct Node {
    int data;
    struct Node* next;
};

// Function to add a new node at the beginning
void 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 list
void 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;
}

You can also try this code with Online C Compiler

Run Code

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

#include <stdio.h>
#define MAX 5  // Defining maximum size of the stack

int stack[MAX];
int top = -1;

// Function to add an element to the stack
void 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 stack
int 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 operations
int main() {
    push(10);
    push(20);
    push(30);
    printf("%d popped from stack\n", pop());
    return 0;
}

You can also try this code with Online C Compiler

Run Code

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

#include <stdio.h>
#define MAX 5  // Defining maximum size of the queue

int queue[MAX];
int front = 0, rear = -1;

// Function to add an element to the queue
void 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 queue
int 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 operations
int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    printf("%d dequeued from queue\n", dequeue());
    return 0;
}

You can also try this code with Online C Compiler

Run Code

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.

Dynamic Size (Linked Lists)

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.

Extra Memory Overhead (Linked Lists)

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.

Non-sequential Access (Linked Lists)

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.

Cache Performance (Linked 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.

What are 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

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

// A structure to represent a node of the tree
struct Node {
    int data;
    struct Node *left, *right;
};

// Function to create a new node
struct 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 fashion
void 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;
}

You can also try this code with Online C Compiler

Run Code

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

#include <stdio.h>
#define V 5

// Function to print the adjacency matrix
void 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;
}

You can also try this code with Online C Compiler

Run Code

Output

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.

Memory Overhead

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

Aspect	Linear Data Structures	Non-Linear Data Structures
Basic Concept	Data elements are arranged in a sequential order, one after another.	Data elements are arranged in a hierarchical order, allowing for a more complex relationship between elements.
Structure	Linear data structures can be traversed in a single run due to their sequential nature.	Non-linear data structures require multiple runs for traversal due to their hierarchical nature.
Examples	Arrays, Linked Lists, Stacks, Queues	Trees (Binary Trees, AVL Trees, etc.), Graphs (Directed, Undirected)
Memory Allocation	Elements are stored in contiguous (arrays) or non-contiguous (linked lists, stacks, queues) memory locations.	Elements are stored in a hierarchical manner, often requiring pointers to connect child elements to parent elements.
Access Methods	Elements can be accessed sequentially. Direct access is possible in arrays.	Direct access to any element is not possible; elements are accessed based on their relationship.
Traversal	Linear traversal is used, i.e., one element after another.	Traversal methods are more complex and varied (e.g., Pre-order, In-order, Post-order for trees; DFS, BFS for graphs).
Application	Suitable for simple data storage and operations where data relationship is linear or flat.	Ideal for representing hierarchical or complex network structures like family trees, network protocols, etc.
Insertion/Deletion	Insertion and deletion can be simple (linked lists, stacks, queues) or require shifting elements (arrays).	Insertion and deletion may require reorganization of the entire structure (especially in balanced trees).
Efficiency	Operations like search, insert, and delete have linear time complexity in worst-case scenarios.	Can have more efficient search, insert, and delete operations due to inherent structure (e.g., logarithmic in balanced trees).

Frequently Asked Questions

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 Code360. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.