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

Comments

Popular posts from this blog

Working with request header in Jersey (JAX-RS) guide

In the  previous post , we talked about, how to get parameters and their values from the request query string. In this guide learn how to get request header values in Jersey (JAX-RS) based application. We had tested or used the following tools and technologies in this project: Jersey (v 2.21) Gradle Build System (v 2.9) Spring Boot (v 1.3) Java (v 1.8) Eclipse IDE This is a part of  Jersey (JAX-RS) Restful Web Services Development Guides series. Please read Jersey + Spring Boot getting started guide . Gradle Build File We are using Gradle for our build and dependency management (Using Maven rather than Gradle is a very trivial task). File: build.gradle buildscript { ext { springBootVersion = '1.3.0.RELEASE' } repositories { mavenCentral() } dependencies { classpath("org.springframework.boot:spring-boot-gradle-plugin:${springBootVersion}") } } apply plugin: 'java' apply plugin: 'eclipse' a

Ajax Cross Domain Resource Access Using jQuery

Some time back in our project we faced a problem while making an Ajax call using jQuery. Chrome Browser console had given some weird error message like below when we try to access one of our web pages: When we try to access the same web page in the Firefox browser, it doesn't give any error in the console but some parsing error occurred. In our case, we were accessing XML as an Ajax request resource. I was curious to check if the non-XML cross-domain resource was successfully loading or not. But finally, I realized that it is not going through. jersey-spring-boot-quick-starter-guide In our Ajax call, requesting domain was not the same as the requested URL domain. $.ajax({ url: "https://10.11.2.171:81/xxxxxx/xxxxxxx.xml" , type : "get" , success: function (response) { alert( "Load was performed." ); }, error : function (xhr, status) {

FastAPI first shot

Setup on my Mac (Macbook Pro 15 inch Retina, Mid 2014) Prerequisite Python 3.6+ (I used 3.7.x. I recently reinstalled OS after cleaning up disk, where stock Python 2.7 was available. I installed Pyenv and then used it to install 3.7.x). I already had a git repo initialized at Github for this project. I checked that out. I use this approach to keep all the source code safe or at a specific place 😀. I set the Python version in .python-version file. I also initialize the virtual environment using pyenv in venv folder. I started the virtual environment. FastAPI specific dependencies setup Now I started with basic pip commands to install dependency for the project. I saved dependencies in requirements.txt  the file. Minimal viable code to spin an API Server FastAPI is as cool as NodeJS or Go Lang (?) to demonstrate the ability to spin an API endpoint up and running in no time. I had the same feeling for the Flask too, which was also super cool. app/main.py: from typing i