Every algorithm which solves useful problems has one or many data structures. Data structures are mechanisms to keep data (primitive data type) arranged inside a computer's memory in some structure. They help algorithms to meet efficiency which is otherwise not possible. It is not unusual to map computational problems into data structure at the very first stage of problem-solving. They are building blocks of the modern computer programming models.
|Students in the classroom|
Let's consider we want to arrange the name of students in alphabetical order using the program. When we formulate a solution we need a way to keep the list of students before we apply the sorting algorithm. Obviously, we will use an array (list) where we will keep them and use our algorithm to iterate over it and do a sorting algorithm. We can see array and other important data structures are so indispensable and often used, that they are offered as core features of programming language.
Data Structure in real life
In dictionary, words are sorted in alphabetical order and it enables to a search of words quickly. If words (data) are not structured in sorted order then it's impossible to search any word. Dictionary is an example of a data structure we use in real life. There are many other examples of real-life data structure use, in fact, they are an inspiration to the computational data structure for a long time.
Abstract Data Types
Abstract data type (ADT) is a blueprint for data structure implementation. They specify operations to carry out as well as computational complexity for those operations. Data structures are a concrete implementation of Abstract Data Types. Abstract Data Type is a mathematical model which defines the operation, values, and behaviors of the data type from the user's perspective.
Integers are ADT with
values: .. -2, -1, 0, 1, 2, ..
Operations: addition, subtraction, multiplication, division
as per general mathematics.
However, computers are free to represent Integer as they want to.
Important Abstract Data Types
The container is a collection of other objects.
|Container Abstract Data Type|
Three important characteristics:
- Access - How do we access the objects? It will be using index in case of Array, LIFO (Last in First Out) in case of Stacks, and FIFO (First in First Out) in case of Queue.
- Storage - How we are storing the object in the container?
- Traversal - How we are traversing the objects of the container?
Following operations on the Container Class desired:
- Delete all
- Access the object
- Access the objects count
All operations are self-explanatory. It is to explain the essence of Abstract Data Types. In real life, Containers have various types of implementation.
The list has values and we can count the number of values. The same value may seem multiple times. A list is a basic example of a container.
|List Abstract Data Type|
Set has distinct values not in a particular order.
|Set Abstract Data Type|
Map built of a collection of pairs (Key, Value). Key appears only once in the collection. It is also known as an associative array, symbol table, or dictionary.
|Map Abstract Data Type|
Graph abstract data types are made up of Nodes (also called vertices or points) and Edges (also called arcs or lines). Few operations are like adjacent of a node, neighbors of a node, adding node (vertex), removing a node (vertex), or others.
|Graph Abstract Data Type|
Stack abstract data type is a collection of elements with two important operations:
- Push - Adding elements to the collection.
- Pop - Removing elements from the collection. Elements were removed from the collection in the Last In First Out (LIFO) order.
|Stack abstract data type LIFO|
Queue abstract data type is a collection of elements where elements are added on the rear side (called Enqueue) and removed from the front side (called Dequeue). It is also known as the First In First Out (FIFIO) data structure.
|Queue FIFO abstract data type|
This is a brief introduction to Data Structure to get started on our journey to understand it in deep. Please see the reference section to go through more details about the terminologies used in this article.