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

Java Functional Interface

1. What is Functional Interface An interface with only one abstract method is called Functional Interface. Pre Java 8, there was no concept of Functional Interface. However, interfaces like Comparator and Runnable have only one abstract method. Hence they fell into the Functional Interface category in Java 8 unintentionally. 2. Example 2.1 getSellingPrice method snippet from App.Java package org.geekmj.java8; public class App { public static void main(String[] args) { // } private static float getSellingPrice(float cost, float couponDiscount, DiscounterFunctionalInterface discounter) { return cost - couponDiscount - discounter.discount(cost); } } Here, we have a method getSellingPrice , with three arguments cost , couponDiscount and discounter . discounter is of type DiscounterFunctionalInterface . It calculates the selling price for an item. 2.2 DiscounterFunctionalInterface.java package org.geekmj.java8; @FunctionalInterface public interface DiscounterFunctiona...
Post a Comment
Read more

Useful SFTP terminal commands

First Step - Connect to a remote computer sftp -i ~/.ssh/LightsailDefaultKey-ap-south-1.pem ubuntu@52.66.180.155 Similar to ssh command. Output: Connected to 52.66.180.155. sftp> Remote and Local computer commands When we relay basic terminal commands at sftp> like 'pwd , ls , cd , and it is executed at the remote computer. Basic terminal commands above when prefixed with l like lpwd , lls , lcd and etc. it is executed at a local computer. For e.g. List all files in the present working directory at the remote computer: sftp> ls List all files in the present working directory at the local computer: sftp> lls Sending a local computer file to present the working directory of a remote computer sftp> put /Users/mj/Downloads/test.png Output Uploading /Users/mj/Downloads/test.png to /home/ubuntu/test.png /Users/mj/Downloads/tech-mrit-prod.ovpn 100% 13KB 382.9KB/s 00:00 References How To Use SFTP to Securely Transfer Files with a Re...
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