Skip to main content

What is Data Structure?

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

Dictionary

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

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

The container is a collection of other objects.

Container Abstract Data Type

Three important characteristics:

  1. 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.
  2. Storage - How we are storing the object in the container?
  3. Traversal - How we are traversing the objects of the container?

Following operations on the Container Class desired:

  1. Create
  2. Insert
  3. Delete
  4. Delete all
  5. Access the object
  6. 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.

List

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

Set has distinct values not in a particular order.

Set Abstract Data Type 

Map

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

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

Stack abstract data type is a collection of elements with two important operations:

  1. Push - Adding elements to the collection.
  2. 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

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.

Reference

  1. Data structure Wikipedia article. Ref
  2. Abstract Data Type Wikipedia article. Ref
  3. A very good introduction to the data structure. Youtube Video Ref
Labels:

Comments

Post a Comment

Popular posts from this blog

Extend and reuse an existing AirByte destination connector

AirByte is an open-source ELT (Extract, Load, and Transformation) application. It heavily uses containerization for the deployment of its various components. On the local machine, we need docker to run it. AirByte has an impressive list of source and destination connectors available. One of my use case data destinations is the  ClickHouse data warehouse and its destination connector is not yet (2021-12-08) available. As per the documentation, It seems that creating a destination connector is a non-trivial job. It's a great idea to build an open-source ClickHouse destination connector. However, I tried avoiding the temptation to create one because of the required effort. AirByte has a  MySql destination connector available. ClickHouse provides a MySQL connector for access from any MySQL client. We need to configure Clickhouse to give support for the MySQL connector. Accessing ClickHouse from AirByte using its MySQL destination connector looks promising. However, when ...
Post a Comment
Read more

Understanding Type Checking

A few examples of types in the context of programming language can be integer, float, character, string, array, etc.  When a program executes then data flow between instructions and values of specific types are assigned to a variable after some operation. It's important for the system to verify if the correct types are used as operands in operations. For e.g. In a sum operation, the expectation for operands to be of numeric type. The program's execution should fail in the case there is inconsistency. We can classify programming languages into two categories based as per their ability to cater to type safety: Dynamically Typed Language Statically Typed Language
Post a Comment
Read more

Setting Clickhouse column data warehouse at Google Cloud Compute Engine VM

I didn't have a Google Cloud account associated with my email, so I signed up for one. It needs a valid Credit Card and mobile number to check if you are human. On successful sign up I get 300$ to spend within 3 months. Creating a free forever Google Cloud Compute Engine VM As per Google Cloud documentation you can have 1 non-preemptible e2-micro VM instance (1GB 2vCPU, 30GB Disk, etc.) per month free forever in some regions with some restrictions. I wanted the following stuff in my VM before I can install Clickhouse on to that: Ubuntu 20.x LTS SSH access from my machine Enabling SSH-based access to Google Compute Engine VM Step 1 Created an ssh private and public key on my mac using the following command ssh-keygen -t rsa -f ~/.ssh/gcloud-ssh-key -C mrityunjay -b 2048 Step 2 Copied the public key from the console using the following command: cat ~/.ssh/gcloud-ssh-key.pub output ssh-rsa <Gibrish :)> mrityunjay Step 3 I went to Google Cloud Console > Co...
Post a Comment
Read more