Data Structure In C

• ✅ Linear Data Structures
• ✅ Non- Linear Data Structures

Linear Data Structures

A linear arrangement in C programming refers to a scenario where data elements are organized sequentially or in a linear fashion. Examples of linear data structures commonly employed in C include arrays, linked lists, stacks, and queues.

1. Arrays:

In the C programming language, arrays are employed to hold a fixed quantity of elements that are of the same data type.

Characteristics:

• ✅ Stores a fixed number of elements of the same data type
• ✅ Allows random access to elements using index
• ✅ Can be used to represent matrices and other mathematical structures

Advantages:

• ✅ Simple and easy to use
• ✅ Provides fast access to elements using index
• ✅ Can be used to implement various algorithms, including sorting and searching algorithms

Disadvantages:

• ✅ Having a predetermined size can lead to inefficiency when dealing with data sets of unknown or changing sizes.
• ✅ The cost of adding or removing elements can be high when working with sizable arrays.

Here is a sample array that holds 5 integer values:

C Program:

#include <stdio.h>
#define SIZE 5
 
int main() {
  int arr[SIZE] = {2, 4, 6, 8, 10};
  int i;
 
  for (i = 0; i < SIZE; i++) {
    printf("%d ", arr[i]);
  }
 
  return 0;
}

Output:

2 4 6 8 10

2. Linked Lists:

Linked lists in C are employed to hold a group of elements in a flexible manner. These lists are valuable for creating dynamic data structures that allow for convenient alterations.

Characteristics:

• ✅ Dynamic data structure that can grow or shrink as needed
• ✅ Provides fast insertion and deletion of elements
• ✅ Can be easily traversed using pointers

Advantages:

• ✅ Provides efficient memory management
• ✅ Allows you to create dynamic data structures that can be easily modified
• ✅ Provides fast insertion and deletion of elements

Disadvantages:

• ✅ Efficiency decreases when accessing elements randomly
• ✅ Memory usage can increase significantly when handling extensive datasets

Here is an illustration of a linked list that holds integer values.

C Program:

#include <stdio.h>
#include <stdlib.h>
 
struct Node {
  int data;
  struct Node *next;
};
 
void printList(struct Node *node) {
  while (node != NULL) {
    printf("%d ", node->data);
    node = node->next;
  }
}
 
int main() {
  struct Node* head = NULL;
  struct Node* second = NULL;
  struct Node* third = NULL;
 
  head = (struct Node*)malloc(sizeof(struct Node)); 
  second = (struct Node*)malloc(sizeof(struct Node));
  third = (struct Node*)malloc(sizeof(struct Node));
 
  head->data = 1; 
  head->next = second; 
 
  second->data = 2; 
  second->next = third; 
 
  third->data = 3; 
  third->next = NULL;
 
  printList(head);
 
  return 0;
}

Output:

3. Queues:

Queues in C are employed to hold a group of elements in a first-in, first-out (FIFO) sequence. Queues prove beneficial for executing algorithms that require a specific order of processing.

Characteristics:

• ✅ Stores a collection of elements in a first-in, first-out (FIFO) order
• ✅ Can be used to implement a wide range of algorithms and data structures
• ✅ Provides efficient memory management

Advantages:

• ✅ Provides a simple and efficient way to implement algorithms that require a FIFO order
• ✅ Can be easily implemented using an array or a linked list
• ✅ Provides fast access to the first element in the queue

Disadvantages:

• ✅ Efficiency is compromised when trying to access elements randomly.
• ✅ Inefficiencies may arise when utilizing it for algorithms needing random element access.

Here is a demonstration of a queue that holds integer values:

C Program:

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

#define MAX_SIZE 100

// define the structure for the queue
struct queue {
    int items[MAX_SIZE];
    int front;
    int rear;
};

// function to create an empty queue
struct queue* createQueue() {
    struct queue* q = malloc(sizeof(struct queue));
    q->front = -1;
    q->rear = -1;
    return q;
}

// function to check if the queue is empty
int isEmpty(struct queue* q) {
    if (q->rear == -1)
        return 1;
    else
        return 0;
}

// function to add an element to the queue
void enqueue(struct queue* q, int value) {
    if (q->rear == MAX_SIZE - 1)
        printf("Queue is full!");
    else {
        if (q->front == -1)
            q->front = 0;
        q->rear++;
        q->items[q->rear] = value;
    }
}

// function to remove an element from the queue
int dequeue(struct queue* q) {
    int item;
    if (isEmpty(q)) {
        printf("Queue is empty");
        item = -1;
    } else {
        item = q->items[q->front];
        q->front++;
        if (q->front > q->rear) {
            q->front = q->rear = -1;
        }
    }
    return item;
}

int main() {
    struct queue* q = createQueue();

    enqueue(q, 1);
    enqueue(q, 2);
    enqueue(q, 3);

    printf("Dequeued item: %d\n", dequeue(q));
    printf("Dequeued item: %d\n", dequeue(q));
    printf("Dequeued item: %d\n", dequeue(q));

    return 0;
}

Output:

Dequeued item: 1
Dequeued item: 2
Dequeued item: 3

4. Stacks:

Storing a collection of elements in stacks in the C programming language follows the last-in, first-out (LIFO) principle. Stacks prove valuable for executing algorithms requiring a hierarchical sequence.

Characteristics:

• ✅ Stores a collection of elements in a last-in, first-out (LIFO) order
• ✅ Can be used to implement a wide range of algorithms and data structures
• ✅ Provides efficient memory management

Advantages:

• ✅ Provides a simple and efficient way to implement algorithms that require a LIFO order
• ✅ Can be easily implemented using an array or a linked list
• ✅ Provides fast access to the top element in the stack

Disadvantages:

• ✅ Efficiency is compromised when accessing elements randomly.
• ✅ Inefficiency may arise when utilizing it for algorithms needing random element access.

Here is a demonstration of a stack that holds whole numbers:

C Program:

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

#define MAX_SIZE 100

// define the structure for the stack
struct stack {
    int items[MAX_SIZE];
    int top;
};

// function to create an empty stack
struct stack* createStack() {
    struct stack* s = malloc(sizeof(struct stack));
    s->top = -1;
    return s;
}

// function to check if the stack is empty
int isEmpty(struct stack* s) {
    if (s->top == -1)
        return 1;
    else
        return 0;
}

// function to check if the stack is full
int isFull(struct stack* s) {
    if (s->top == MAX_SIZE - 1)
        return 1;
    else
        return 0;
}

// function to add an element to the stack
void push(struct stack* s, int value) {
    if (isFull(s))
        printf("Stack is full!");
    else {
        s->top++;
        s->items[s->top] = value;
    }
}

// function to remove an element from the stack
int pop(struct stack* s) {
    int item;
    if (isEmpty(s)) {
        printf("Stack is empty");
        item = -1;
    } else {
        item = s->items[s->top];
        s->top--;
    }
    return item;
}

int main() {
    struct stack* s = createStack();

    push(s, 1);
    push(s, 2);
    push(s, 3);

    printf("Popped item: %d\n", pop(s));
    printf("Popped item: %d\n", pop(s));
    printf("Popped item: %d\n", pop(s));

    return 0;
}

Output:

Popped item: 3
Popped item: 2
Popped item: 1

Non- Linear Data Structures

Non-sequential data structures are characterized by elements that are not arranged in a linear or sequential order, distinguishing them from arrays and linked lists. Rather, these elements can be structured hierarchically, in a tree-like format, or in a graph-like arrangement.

Non-linear data structures include, for instance:

1. Trees:

A tree is a hierarchical data structure in which every node has at least one child and at least one parent. The bottom nodes are referred to as leaves, and the uppermost node is known as the root. Uncommon tree data structures include binary trees.

• ✅ Characteristics: Trees are hierarchical data structures made up of nodes, each of which has a parent and zero to many offspring. In trees, leaf nodes and roots both lack parents and have no offspring. Binary trees (each node has a maximum of two children) and n-ary trees (each node has a maximum of n children) are two types of trees that can be categorised based on the maximum number of children that each node can have.
• ✅ Advantages: Trees are useful for representing hierarchical relationships between data, such as file systems, organization charts, and family trees. Additionally, they are employed in search algorithms with logarithmic time complexity for searching, introducing, and removing elements, like binary search trees.
• ✅ Disadvantages: Trees can have poor worst-case performance if they become unbalanced, meaning that one branch of the tree is much longer than the others. This can result in linear time complexity for search, insertion, and deletion operations.

Here is an example of tree:

C Program:

// Tree traversal in C

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

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

// Inorder traversal
void inorderTraversal(struct node* root) {
  if (root == NULL) return;
  inorderTraversal(root->left);
  printf("%d ->", root->item);
  inorderTraversal(root->right);
}

// Preorder traversal
void preorderTraversal(struct node* root) {
  if (root == NULL) return;
  printf("%d ->", root->item);
  preorderTraversal(root->left);
  preorderTraversal(root->right);
}

// Postorder traversal
void postorderTraversal(struct node* root) {
  if (root == NULL) return;
  postorderTraversal(root->left);
  postorderTraversal(root->right);
  printf("%d ->", root->item);
}

// Create a new Node
struct node* createNode(value) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->item = value;
  newNode->left = NULL;
  newNode->right = NULL;

  return newNode;
}

// Insert on the left of the node
struct node* insertLeft(struct node* root, int value) {
  root->left = createNode(value);
  return root->left;
}

// Insert on the right of the node
struct node* insertRight(struct node* root, int value) {
  root->right = createNode(value);
  return root->right;
}

int main() {
  struct node* root = createNode(1);
  insertLeft(root, 2);
  insertRight(root, 3);
  insertLeft(root->left, 4);

  printf("Inorder traversal \n");
  inorderTraversal(root);

  printf("\nPreorder traversal \n");
  preorderTraversal(root);

  printf("\nPostorder traversal \n");
  postorderTraversal(root);
}

Output:

Inorder traversal 
4 ->2 ->1 ->3 ->
Preorder traversal 
1 ->2 ->4 ->3 ->
Postorder traversal 
4 ->2 ->3 ->1 ->

2. Graphs:

A graph is made up of nodes, or vertices, and the connecting edges. We know that graphs can be cyclic or acyclic, directed or undirected and also weighted or unweighted.

• ✅ Characteristics: Graphs are nothing but the collections of the nodes (also known as the vertices) connected by the edges. Edges can include weights to represent the cost or distance between vertices and can be either directed or undirected. Graphs can be classified based on the presence of cycles, such as acyclic graphs (no cycles) and cyclic graphs (one or more cycles).
• ✅ Advantages: Graphs are useful for representing complex relationships between data, such as social networks, transportation networks, and computer networks. They are also used in algorithms for shortest path, minimum spanning tree, and network flow problems.
• ✅ Disadvantages: Graphs can be difficult to manipulate and analyse because of their complexity. Algorithms for graph problems can have high time and space complexity, especially for large graphs.

Here is an example of a graph:

C Program:

#include <stdio.h>
#include <stdlib.h>
 
// We are defining the maximum number of vertices in the graph
#define N 6
 
// It is a data structure to store a graph object
struct Graph
{
    // An adjacency list can be represented by an array of pointers to Nodes
    struct Node* head[N];
};
 
// An adjacency list for the graph's nodes is kept in a data structure.
struct Node
{
    int dest;
    struct Node* next;
};
 
// An edge-storing data structure for graphs
struct Edge {
    int src, dest;
};
 
// Function to create an adjacency list from specified edges
struct Graph* createGraph(struct Edge edges[], int n)
{
    // allocate storage for the graph data structure
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
 
    // initialize head pointer for all vertices
    for (int i = 0; i < N; i++) {
        graph->head[i] = NULL;
    }
 
    // add edges to the directed graph one by one
    for (int i = 0; i < n; i++)
    {
        // get the source and destination vertex
        int src = edges[i].src;
        int dest = edges[i].dest;
 
        // allocate a new node of adjacency list from src to dest
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->dest = dest;
 
        // point new node to the current head
        newNode->next = graph->head[src];
 
        // point head pointer to the new node
        graph->head[src] = newNode;
    }
 
    return graph;
}
 
// Function to print adjacency list representation of a graph
void printGraph(struct Graph* graph)
{
    for (int i = 0; i < N; i++)
    {
        // print current vertex and all its neighbors
        struct Node* ptr = graph->head[i];
        while (ptr != NULL)
        {
            printf("(%d ?> %d)\t", i, ptr->dest);
            ptr = ptr->next;
        }
 
        printf("\n");
    }
}
 
// Directed graph implementation in C
int main(void)
{
    // input array containing edges of the graph (as per the above diagram)
    // (x, y) pair in the array represents an edge from x to y
    struct Edge edges[] =
    {
        {0, 1}, {1, 2}, {2, 0}, {2, 1}, {3, 2}, {4, 5}, {5, 4}
    };
 
    // calculate the total number of edges
    int n = sizeof(edges)/sizeof(edges[0]);
 
    // construct a graph from the given edges
    struct Graph *graph = createGraph(edges, n);
 
    // Function to print adjacency list representation of a graph
    printGraph(graph);
 
    return 0;
}

Output:

(0 ?> 1)	
(1 ?> 2)	
(2 ?> 1)	(2 ?> 0)	
(3 ?> 2)	
(4 ?> 5)	
(5 ?> 4)

3. Heaps:

A heap is a specialized tree-based data structure that satisfies the heap property. In a min-heap, the parent node is always smaller than its children, and in a max-heap, the parent node is always larger than its children.

• ✅ Characteristics: Heaps are tree-based data structures that satisfy the heap property, which is that the value of each parent node is greater than or equal to the value of its children (for a max heap) or less than or equal to the value of its children (for a min heap). Heaps are often implemented as binary trees, with each node representing an element of the heap.
• ✅ Advantages: Heaps are useful for implementing priority queues, where elements are removed from the queue in order of priority (i.e., the highest or lowest value). They are also used in sorting algorithms, such as heapsort, which has a time complexity of O(n log n).
• ✅ Disadvantages: Heaps can have poor worst-case performance for inserting elements, especially if the heap becomes unbalanced. Also, because heaps are typically implemented as binary trees, they can have wasted space if the number of elements in the heap is not a power of two.

Here is an example of heap:

C Program:

// Max-Heap data structure in C

#include <stdio.h>
int size = 0;
void swap(int *a, int *b)
{
  int temp = *b;
  *b = *a;
  *a = temp;
}
void heapify(int array[], int size, int i)
{
  if (size == 1)
  {
    printf("Single element in the heap");
  }
  else
  {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    if (l < size && array[l] > array[largest])
      largest = l;
    if (r < size && array[r] > array[largest])
      largest = r;
    if (largest != i)
    {
      swap(&array[i], &array[largest]);
      heapify(array, size, largest);
    }
  }
}
void insert(int array[], int newNum)
{
  if (size == 0)
  {
    array[0] = newNum;
    size += 1;
  }
  else
  {
    array[size] = newNum;
    size += 1;
    for (int i = size / 2 - 1; i >= 0; i--)
    {
      heapify(array, size, i);
    }
  }
}
void deleteRoot(int array[], int num)
{
  int i;
  for (i = 0; i < size; i++)
  {
    if (num == array[i])
      break;
  }

  swap(&array[i], &array[size - 1]);
  size -= 1;
  for (int i = size / 2 - 1; i >= 0; i--)
  {
    heapify(array, size, i);
  }
}
void printArray(int array[], int size)
{
  for (int i = 0; i < size; ++i)
    printf("%d ", array[i]);
  printf("\n");
}
int main()
{
  int array[10];

  insert(array, 3);
  insert(array, 4);
  insert(array, 9);
  insert(array, 5);
  insert(array, 2);

  printf("Max-Heap array: ");
  printArray(array, size);

  deleteRoot(array, 4);

  printf("After deleting an element: ");

  printArray(array, size);
}

Output:

Max-Heap array: 9 5 4 3 2 
After deleting an element: 9 5 2 3

Here are a limited number of illustrations of non-linear data arrangements, with a multitude of others employed across different applications.

Conclusion:

In summary, linear and non-linear data structures hold significance in the field of computer science and can be executed through the C programming language.

Linear data structures, like arrays, linked lists, and stacks, exhibit a straightforward linear arrangement and are beneficial for orderly data storage. They offer the benefit of quick access to elements positioned within the structure, although they may experience reduced efficiency when inserting or removing elements from the middle of the structure.

Non-sequential data arrangements like trees, graphs, and heaps exhibit intricate structures and are beneficial for housing data with hierarchical or interconnected connections. They offer efficient searching, insertion, and deletion functionalities; however, they may demonstrate poorer performance when accessing elements within the structure's middle.

The selection of a data structure is determined by the particular needs of the given problem. Sequential data structures are preferable for scenarios where data access follows a specific order or when the data size is predetermined. On the other hand, hierarchical data structures are better suited for situations involving intricate data connections or when there is a need for effective search, insertion, and deletion functionalities.

In C programming, arrays, pointers, and structures are utilized to implement both sequential and hierarchical data structures. Various libraries and frameworks, like the Standard Template Library (STL) in C++, offer pre-built data structure solutions. Proficiency in assessing the features, benefits, and drawbacks of diverse data structures is a vital proficiency for individuals in the realms of computer science and software development.