This article is a Series on Data Structures and carries the discussion on different types of data structures and their implementation. The aim of this series is to provide easy and practical examples that anyone can understand. In our last article, we discussed Flexible Array Member in C (FAM). In this article, we’re going to take a look at a key topic when it comes to computer science and software development which is Data Structure in C and its types. If you are a developer in any software industry including Embedded Systems, you must know this Data Structure.
You can also read other C programming articles here.
Table of Contents
Data Structure in C Introduction
What is Data Structure?
The data structure is a way of organizing and storing the data in an efficient manner. So that it can be accessed and updated efficiently. Almost every application uses various types of data structures in one or the other way. More precisely, a data structure is a collection of data values, and processing, and retrieving those data.
Why do we need Data Structures?
Nowadays, applications are getting more complex and it has to process a wide number of data. Do you have any idea how much data Netflix has? It is huge and it receives billions of requests per day. How do they manage to serve those requests? They have to search and get the required data from their huge database. If we don’t organize the data, how come they will serve faster? So, we need to arrange and organize the data efficiently. That’s why we need data structures.
Types of Data Structures
There are 2 types of data structures available,
- Primitive Data structure
- Non-Primitive Data structure
Primitive Data Structure
Primitive Data Structures are predefined types of data that are used by programming languages. Integers, floating-point numbers, character constants, string constants, and pointers are examples of Primitive Data structures.
Non-primitive data structure
Non-primitive data structures are not defined by the programming language but are instead created by the programmer. Non-primitive data structures are more complicated data structures and are derived from primitive data structures.
Under the Non-primitive data structure, there are 2 subdivisions,
- Linear Data structure
- Non-Linear Data structure
Linear Data structure
In a linear data structure, data items are ordered sequentially or linearly, with each member attached to its previous and next to neighboring members or elements. Since the data elements are stored in a linear fashion, the structure allows single-level data storage. As a result, traversal of the data is accomplished in a single run. Memory is not efficiently utilized in a linear data structure.
The common examples of the linear data structure are:
Non-Linear Data structure
Unlike Linear data structure, in non-Linear Data Structure, their elements are not connected in a linear fashion (sequence manner), as mentioned by its name itself. The elements might be connected in a hierarchical manner like a tree or graph, or it may be nonhierarchical like in a LinkedList. One element can be connected to more than two adjacent elements. Non-linear data structures have more complex implementation, than linear.
The common examples of the non-linear data structure are:
- Tree
- Graphs
- Hashing
- Trie
Difference between Linear and Non-linear Data Structures
| Linear Data Structure | Non-Linear Data Structure |
|---|---|
| Elements are connected sequentially or in a contiguous manner one after the other.. | Elements are not connected sequentially (hierarchical manner). |
| A user can find all of the data elements at a single layer in a linear data structure. | Elements may be present on different or multiple levels. |
| There is no hierarchy between the elements. | There is usually a hierarchy between elements. |
| It can be traversed on a single run. If we start from the first element, we can traverse all the elements sequentially in a single pass. | It is not easy to traverse the non-linear data structures. The users need multiple runs to traverse them completely. |
| The linear data structures are comparatively easier to implement. | They have a more complex implementation. |
| Memory allocation is sequential. | Memory allocation isn’t sequential. |
| It is not very memory-friendly. It means these linear data structures can’t utilize memory very efficiently. | Different structures utilize memory in different efficient ways depending on the need. |
| The time complexity increases with the data size. | Time complexity remains the same. |
| Linear data structures work well mainly in the development of application software. | Non-linear data structures work mainly well in image processing and Artificial Intelligence. |
| Examples include arrays, hash tables, stacks, queues, etc. | Examples include trees, graphs, etc. |
Common Operations on Data Structure
We can do some operations on the data structure. We have mentioned a few below.
- Insertion: Insert the new element in a data structure anywhere.
- Updation: Update the element, i.e., replace the element with another element.
- Deletion: Remove the element from the data structure.
- Searching: Search for any element in a data structure.
- Sorting: Sort the elements of a data structure either in an ascending or descending order.
Applications of Data Structure
As we have many data structures, each has separate advantages and applications. We will discuss those applications in those articles.
In our next article, we will discuss Stack Data Structure in C programming.
You can also read the below topics.
Embedded Software Developer who is passionate about Embedded Systems.
