Every algorithm which solves useful problem has data structure. Data structures are mechanism to keep data (primitive data type) arranged inside computer’s memory in some structure. They help algorithm to meet efficiency which otherwise not possible. It is not unusual to map computational problem into data structure at very first stage of problem solving. They are building blocks of modern computer programming model.
Let’s consider we want to arrange the name of students in alphabetical order using 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 sorting algorithm. We can see array and other important data structures are so indispensable and often used, they offered as core features of programming language.
Data Structure in real life
In dictionary, words are sorted in alphabetical order and it enables to search word quickly. If words (data) are not structured in sorted order than it’s impossible to search any word. Dictionary is an example of data structure we use in real life. There are many other examples of real life data structure use, in fact they are inspiration to computational data structure for long time.
Abstract Data Types
Abstract data type (ADT) are blueprint for data structure implementation. They specify operations to carry out as well as computational complexity for those operations. Data structures are concrete implementation of Abstract Data Types. Abstract Data Type is a mathematical model which define the operation, values and behaviours of the data type in 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
Container is a collection of other objects.
Three important characteristics:
- Access – How 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 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 Container have various types of implementation.
List has values and we can count the number of values. Same value may seem multiple times. List is a basic example of container.
Set has distinct values not in a particular order.
Map built of collection of pairs (Key, Value). Key appear only once in the collection. It is also known as associative array, symbol table, or dictionary.
Graph abstract data types made up of Nodes (also called vertices or points) and Edges (also called arcs or lines). Few operations are like adjacent of a node, neighbours of a node, adding node (vertex), removing node (vertex) or others.
Stack abstract data type is collection of elements with two important operations:
- Push – Adding element in collection.
- Pop – Removing element from collection. Elements removed from collection in Last In First Out (LIFO) order.
Queue abstract data type a collection of elements where element added in rear side (called Enqueue) and removed from front side (called Dequeue). It is also known as First In First Out (FIFIO) data structure.
This is a brief introduction of Data Structure to get started our journey to understand it in deep. Please see the reference section to go through more details about terminologies used in this article.
- Data structure wikipedia article. Ref
- Abstract Data Type wikipedia article. Ref
- A very good introduction to data structure. Youtube Video Ref