Data Structure is a systematic way to organize the data to use it efficiently. In fact, It is a foundation for writing efficient algorithms. The goal of this blog is to provide an introduction to the data structure, its types, and applications.
1. Why is Data Structure useful?
The data structure is useful for computer programs to store and retrieve data effectively. Some of the key advantages are as follows.
- Faster search: Provides the way for efficient data search and manipulation with a large amount of data.
- Better processor utilization: Helps reduce processor and memory utilization with billions of records.
- Handle multiple requests: Ability to serve multiple user requests at the same time.
So, the data structures are useful to implement efficient programs. That is to say, the programs work faster by utilizing minimal CPU and memory.
2. Types of Data Structure
The below diagram illustrates the different types of Data structures.
2.1. Data Types vs Data Structures
Data type indicates the type of data such as int, float, chart, and bool. For example, the type int can represent an integral number. So, it is only the type and not a variable to store the data. In addition, it is a building block to data structures.
A data structure is a collection of data. This can be constructed from various data types. For example, an array of type int can store a set of numbers. But, the array is not limited to storing only numbers. They can also be defined to store other types of data. Linked List on the other side can be defined to store data of multiple types.
3. Primitive Data Types
Primitive data types are the basic data types that represent any one particular type. It is also the building block to construct the data structures such as Stack, and Queue.
| Primitive Type | Description |
| int | Represents integral numbers both positive and negative. For example, 10, and -40. |
| float | Floating point numbers. For example, 3.14, and -5.43. |
| char | Represents a single character. This can be a digit, alphabet, or symbol. For example, 'C', '4', and '#'. |
| bool | Represents the boolean value. For example, true, and false. |
4. Linear Data Structure
Linear data structure stores the data in sequential order. For example, Array, Linked List, Stack, Queue, and Hash Table.
4.1. Array
An array is a collection of linear items of the same type. It stores the elements in contiguous memory locations thus resulting in better performance.
- Almost all the programs use the Array in some places. For instance, storing sequential data such as a list of customer identities or names. The array is best used for storing a fixed amount of data that require frequent access.
- Supported operations are Insertion, Deletion, Search, and Access by index.
- Learn about Array
4.2. Linked List
A linked list is a collection of linear items. In contrast to the array, a linked list stores the elements in non-contiguous memory locations. So, the insertion and deletion operations work faster by simply interchanging the links.
- Linked List is best used for storing dynamic data that requires frequent insertion and deletion operations.
- Supported operations are Insertion, Deletion, and Search.
- Learn about Linked List and its Types
4.3. Stack
A stack is a linear data structure that mimics real-life stacks such as a stack of physical disks. Push and pop operations are performed on the top of the stack. So, it always follows the Last In First Out (LIFO) order.
- Stack is best used for applications that process the data in Last In First Out (LIFO) order such as reversing things.
- Supported operations are Push, Pop, and Top (also called Peek).
- Learn about Stack
- Implement Stack using Array
- Implement Stack using Linked List
4.4. Queue
A queue is a linear data structure that mimics a real-life queue. New elements are inserted into the rear side while the old elements are removed from the front.
- The queue is best used for applications that process the data in First In First Out (FIFO) order. For example, CPU scheduling and disk scheduling.
- Supported operations are Enqueue, Dequeue, and Peek.
- Learn about the Queue and its types.
4.5. Hash Table
Hash Table stores the data as key-value pairs in an Array. Basically, it uses a hash function to determine the array index for every key. An efficient hash function equally distributes the keys across the array. Hash tables are generally linear. But they can also be implemented as non-linear to support dynamic data. See Separate chaining implementation for instance.
- Hash table is best used for applications that require indexing. For instance, a cache application can use the Hash Table to quickly store and retrieve the data.
- Supported operations are Access, Search, Insertion, Deletion, and Rehashing.
- Learn about Hash Table
- Implement a Hash Table using the Linear Probing method
- Implement a non-linear Hash Table using the Separate Chaining method
5. Non-Linear Data Structure
Non-linear data structure store the data in non-sequential order. For example, Trees and Graphs
5.1. Tree
A tree is a non-linear data structure that stores data in a hierarchical form. The data is represented as nodes that are linked in hierarchical order.
- The tree is best used for hierarchical data to perform operations faster than linear data structures.
- Supported operations are Insertion, Deletion, Search, and Traversal.
- Learn about Tree and their Types
5.2. Graph
A graph is a non-linear data structure that stores the data in nodes called vertices. The nodes are connected arbitrarily using edges.
- The graph data structure is best used for data that requires arbitrary relationships. For example, a graph that represents the computer networks connected arbitrarily.
- Supported operations are Add Vertex, Delete Vertex, Add Edge, Remove Edge, Search Vertex, and Find the path.
6. Classifications of Data Structure
Data structures involve multiple classifications based on different aspects.
| Classification | Aspect |
| Primitive and Non-Primitive | Basic types vs derived types |
| Linear and Non-Linear | Sequential arrangement vs non-sequential |
| Static and Dynamic | Fixed-size vs variable size |
| Homogeneous and Heterogeneous | Single type vs multiple types |
6.1. Primitive vs Non-Primitive
Primitive data types are the basic types that can represent any one type. Types such as Integer, Float, Char, and Boolean are the primitives. In fact, they are the building blocks to construct the Non-Primitive data structures.
Non-Primitive data structures can store multiple values of different types. Basically, they are constructed from Primitive data types. For example, Array, Linked List, Stack, and Queue. An array can hold multiple values of the same type. A Linked List also has multiple values. In addition, it can store data of different types.
6.2. Linear vs Non-Linear
Linear data structures store the data in sequential order. For example, Array, Linked List, Stack, and Queue.
In contrast, Non-linear data structures store the data in non-sequential order. For example, Trees and Graphs. Trees have the data in a hierarchical form whereas Graphs have the data arbitrarily. Hence, they are categorized as non-linear data structures.
6.3. Static vs Dynamic
A static data structure is fixed in size and can not grow beyond the original allocation. For example, a static Array of size 10 can hold only 10 values and can not accommodate the 11th value.
Dynamic data structures are variable in size and they can grow or shrink based on the data requirement. For example, a Linked List grows and shrinks at runtime based on insertions and deletions.
6.4. Homogeneous vs Heterogeneous
Homogeneous data structures can store data of any one type. For example, an Array of integers can store only the integer types. In addition, any data structure that is implemented using Array is Homogeneous. For instance, a Stack, Queue, or Heap implemented using the Array is homogenous.
Heterogeneous data structures can store data of multiple types. For instance, a Linked list that generally involves a structure and holding multiple types of data. In addition, a Stack, Queue, or Tree that is implemented using the Linked List is heterogeneous.
7. Real-time Applications of Data Structure
Almost all the programs require Data structures. Some of the key areas are as follows.
- Relational databases commonly use Tree data structure for quick data retrieval.
- Compiler implementations use Hash Tables to look up program identifiers.
- Search engines use different data structures to manage a large number of internet indexes.
- Graphical user interfaces often use the Stack to support undo/redo operations.
- Linux kernel uses the Queue for CPU scheduling.