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.

What is C Programming Language

C is a procedural programming language which was developed in 1972 by Dennis Ritchie. It is among the most popularly used programming languages today and is an excellent choice for building data-centric applications. C provides low-level access to memory, making it well-suited for applications that require precise control over how data is manipulated and stored in memory.

One of the major advantages of using C is its support for data structures. Data structures are collections of related information that can be accessed and modified quickly and easily. C supports several types of data structures, including arrays, structs, linked lists, trees, stacks, queues and graphs. Struct in C programming is particularly useful when it comes to assembling large amounts of data into meaningful chunks.

Check out our free courses to get an edge over the competition 

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.

Benefits of Data Structures in C:

Data structures in C provide multiple benefits and are essential to developing efficient, robust programs. Some of the main advantages include:

• Improved Efficiency 

Data structures in C such as linked lists and hash tables can significantly improve data processing speed by reducing search time complexity and allowing more direct access to information. This is especially important for large datasets that may take considerable time to process without these optimized data structures.

• Easier Debugging 

Structured data helps developers spot errors quickly, eliminating long debugging sessions. It even makes it easier to identify and address problems before they become major issues that require in-depth code reworking. 

• Reusability 

Data Structures using C enable developers to create reusable code that can be applied and adapted to different situations. This eliminates the need to rewrite code for each new project, saving time and resources.

• Greater Flexibility 

With structured data, developers can quickly adjust programs as needs change and create new solutions based on existing data structures. This is an incredible way to extend the functionality of an application without creating more overhead in terms of complexity or development time.

Using C for programming offers powerful tools that make use of these data structures and can provide significant performance improvements compared to other languages. Understanding how they work and the associated benefits and potential pitfalls is essential for developing efficient applications that can meet modern software development’s rigours. Moreover data structures using C can help developers create more robust code that is easier to debug, reuse, and modify.

Check out upGrad’s Java Bootcamp 

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.

Check out upGrad’s Full Stack Development Bootcamp (JS/MERN) 

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. 

upGrad’s Exclusive Software Development Webinar for you –

SAAS Business – What is So Different?

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’.

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

Learn Software Courses online from the World’s top Universities. Earn Executive PG Programs, Advanced Certificate Programs, or Masters Programs to fast-track your career.

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 Executive PG Program 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.