Programs

What are Data Structures in C & How to Use Them?

Introduction

To start with, a data structure is a collection of data items that are kept together under one name or heading and is a specific way of storing and assembling the data so that the data can be used efficiently.

Types

Data Structures are prevalent and used in almost every software system. Some of the most common examples of Data Structures are arrays, queues, stacks, linked lists, and trees.

Applications

In designing compilers, operating systems, making databases, Artificial Intelligence applications, and many more.

Classification

Data Structures are classified into two categories: primitive data structures and non-primitive data structures.

1. Primitive: They are the basic data types that are supported by a programming language. A common example of this classification is integers, characters, and boolean.

2. Non-Primitive: These categories of data structures are created using primitive data structures. Examples include linked stacks, linked lists, graphs, and trees.

Arrays

An array is a simple collection of data elements that have the same data type. That means an array of type integers can only store integer values. An array of data type float can store values that correspond to float data type and nothing else.

Elements stored in an array are linearly accessible and are present in contiguous blocks of memory that can be referred to using an index.

Declaring an Array

In C, an array can be declared as:

data_type name[length];

For example,

int orders[10];

The above line of code creates an array of 10 memory blocks in which an integer value can be stored. In C, the array index value starts from 0. So the index values will range from 0 to 9. If we want to access any particular value in that array, we simply have to type:

printf(order[index_number]);

Another way to declare an array is as follows:

data_type array_name[size]={list of values};

For example,

int marks[5]={9, 8, 7, 9, 8};

The above line of command creates an array having 5 memory blocks with fixed values in each of the blocks. On a 32 bit compiler, the 32-bit memory occupied by int data type is 4 bytes. So, 5 blocks of memory would take up 20 bytes of memory. 

Another legit way of initializing arrays is:

int marks [5] = {9 , 45};

This command will create an array of 5 blocks, with the last 3 blocks having 0 as their value. 

Another legit way is:

int marks [] = {9 , 5, 2, 1, 3,4};

The C compiler understands that only 5 blocks are required to fit these data into an array. It will therefore initialize an array of name marks of size 5. 

Similarly, a 2-D array can be initialized in the following way

int marks[2][3]={{9,7,7},{6, 2, 1}};

The above command will create a 2-D array having 2 rows and 3 columns.

Read: Data Structure Project Ideas & Topics

Operations

There are some operations that can be performed on arrays. For example:

  1. traversing an array
  2.  Inserting an element in the array
  3.  Searching for a particular element in the array
  4. Deleting a particular element from the array
  5. Merging the two arrays and,
  6. Sorting the array — in ascending or descending order.

Disadvantages

Memory allocated to the array is fixed. This actually is a problem. Say, we created an array of size 50 and only accessed 30 blocks of memory. The remaining 20 blocks take up memory without any use. Therefore, to tackle this problem, we have a linked list. 

Linked List

Linked List, very much like arrays stores data serially. The main difference is that it does not store everything all at once. Instead stores the data or makes a memory block available as and when required. In a linked list, the blocks are divided into two parts. The first part contains the actual data.

The second part is a pointer that points to the next block in a linked list. The pointer stores the address of the next block that holds the data. There is one more pointer known as the head pointer. head points to the first block of memory in the linked list. Following is the representation of the linked list. These blocks are also referred to as ‘nodes’.

source

Initializing Linked Lists

To initialize the link list, we create a structure names node. The structure has two things. 1. The data that it holds and 2. The pointer that points to the next node. The data type of pointer will be that of the structure as it is pointing to the structure node.

struct node 

int data;

 struct node *next; 

};

In a linked list, the last node’s pointer will not point to anything, or simply, will point to null. 

Also Read: Graphs in Data Structure

Linked List Traversal

In a linked list, the last node’s pointer will not point to anything, or simply, it will point to null. So to traverse an entire linked list, we create a dummy pointer that initially points to the head. And, for the length of the linked list, the pointer continues to move forward until it points to null or reaches the last node of the linked list.

Adding a Node

The algorithm to add a node before a specific node would be as follows:

  1. set two dummy pointers(ptr and preptr) that point to head initially
  2. move the ptr till ptr.data is equal to the data before we intend to insert the node. preptr will be 1 node behind ptr. 
  3. Create a node 
  4. The node to which the dummy preptr was pointing, that node’s next will point to this new node 
  5. New node’s next will point to the ptr. 

The algorithm for adding a node after a particular data would be done in a similar way. 

Advantages of Linked List 

  1. Dynamic size unlike an array
  2. Performing insertion and deletion are easier in the linked list than in an array. 

Queue 

Queue follows a First In First Out or FIFO type of system. In an array implementation, we will have two pointers to demonstrate the use case of Queue. 

Source

FIFO basically means that the value that enters the stack first, leaves the array first. In the above queue diagram, the pointer front points to the value 7. If we delete the first block (dequeue), the front will now point to the value 2. Similarly, if we enter a number (enqueue), say, 3 in position 5. Then, the rear pointer will point at position 5. 

Overflow and Underflow Conditions

Nevertheless, prior to entering a data value in the queue, we must check for overflow conditions. An overflow will occur when there is an attempt to insert an element into a queue that is already full. A queue will full when rear = max_size–1.

Likewise, before deleting data from the queue, we should check for underflow conditions. An underflow will occur when there is an attempt to delete an element from a queue that is already empty, i.e. if front = null and rear = null, then the queue is empty.

Stack

A stack is a data structure in which we insert and delete elements only at one end, also known as the top of the stack. Stack implementation is therefore referred to as a last-in, first-out (LIFO) implementation. Unlike queue, for the stack, we only require one top pointer.

If we want to enter (push) elements in an array, the top pointer moves up or increments by 1. If we want to delete(pop) an element, the top pointer decrements by 1 or goes down by 1 unit. A stack supports three basic operations: push, pop, and peep. Peep operation is simply displaying the topmost element in the stack. 

Source

Conclusion

In this article, we have talked about 4 types of data structures namely, arrays, linked lists, queues, and stacks. Hope you liked this article and stay tuned for more interesting reads. Until next time.

If you’re interested to learn more about Javascript, full-stack development, check out upGrad & IIIT-B’s PG Diploma in Full-stack Software Development which is designed for working professionals and offers 500+ hours of rigorous training, 9+ projects, and assignments, IIIT-B Alumni status, practical hands-on capstone projects & job assistance with top firms.

Land on Your Dream Job

UPGRAD AND IIIT-BANGALORE'S PG DIPLOMA IN FULL STACK DEVELOPMENT
APPLY NOW

Leave a comment

Your email address will not be published.

Accelerate Your Career with upGrad

Our Popular Software Engineering Courses

×