Data Structures and Algorithms - Explained with Examples

Data structures and algorithms(DSA) are the foundational stones and pillars of Computer Sciences. They are the building blocks in all disciplines of software development. 

The efficiency of a software application depends on what data structures and algorithms have been used to create it and thus they’re as integral as the programming language itself. 

Needless to say, every Computer Science student must learn DSA to be a successful software developer in their career.

As important as they are, most of the students in India, however, either skip learning DSA or aren’t able to understand the subject. We understand that learning data structures and algorithms is not as easy a process as learning a programming language. 

Table of contents:

What are arrays?

What are stacks?

Algorithms explained

How does Recursion work?

Searching and Sorting algorithms

Students face different types of challenges like:

1. They follow lots of mismatched content on the internet which confuses them,
2. They adopt the wrong strategies.

When we talk about strategies, there are mostly two ways to go about it. 

• Volume
• Components and techniques

Now, if a student picks the first strategy of ‘volume’, and let’s say, they follow a 300 question guide;

Will they be able to solve different data structures? 

Can they decide which data structure and algorithm suits best for the application?

Generally, the answer is no. Students lose track with this strategy of solving a planned number of questions per day. In some situations, one would get stuck with problems for days and finally tap out.

To learn Programming, one must have a quality understanding of the fundamentals of the programming language, data structure, and algorithms. 

How do all of these work together to produce the desired result? 

See, it’s not about memorizing the terms and formulas. One should be able to create a mind-map of the process that goes into developing a web/software. 

And that’s why we have created this roadmap, not to puzzle you with complex terms and long definitions, but to simplify all of them in layman’s terms using relevant examples that would make you learn everything from scratch.

Before getting into DSA, let’s first understand programming language and its different aspects. 

Programming Language

To follow the instructions, the computer has to understand the language of your command. That’s the function of a programming language.

“In some ways, programming is like painting. You start with a blank canvas and certain basic raw materials. You use a combination of science, art, and craft to determine what to do with them.”

Andrew Hunt

Programming language is the paintbrush in this scenario. It enables us to translate the binary digits (0s and 1s) into something understandable by us humans so that we can read and write the programs. Programming languages are responsible for almost everything we see today in the digital world.

They consist of a series of symbols that act as a bridge between human thought and the command received by the computer.

Now, there are multiple languages that humans use to communicate, and similarly, the computer can also understand multiple programming languages. 

“Which language should I learn?”. This is a frequently asked question by many aspiring developers.

Honestly, there’s no definitive answer to this. One can start with any language, the main focus should be on thoroughly understanding that particular language before moving forward as the fundamentals are similar for each language out there.

And the first step in learning any programming language is to get fully acquainted with the syntax of the language. 

What is Syntax in Programming Language?

Syntax refers to the rules and structure that make up a language. It controls the structure of the symbols, punctuation, and words in a programming language.

How one needs to study grammar to speak correctly, syntax plays the same role in programming. While speaking, you can get away with a few grammatical errors here and there, but if you apply the wrong syntax to a program, it won’t be understood by the compiler or the interpreter resulting in a program failure. 

Just like the languages we speak, every programming language has its own set of rules that governs the composition. of a command. However, these are minute changes and once you have a good understanding of one language, you can use that framework in learning other languages. 

For example, 

• Some languages like Java, C++, and Python are case-sensitive. This means inputs such as notebook and Notebook would carry different meanings in those languages. Whereas, both of them would interpret the same meaning in certain case-insensitive languages such as Basic and SQL. 

• There are different ways of writing “Class names’ ‘ too in different languages. Where Java needs an uppercase first letter for each word in class names (example- class NokiaLatestPhones), languages such as C and C++ need underscores to separate the words. (example- class nokia_latest_phones)

Apart from Syntax i.e. the form/structure of the code, there’s another significant factor in a programming language- Semantics.  

Semantics refers to the meaning of the instruction that you give to the computer. It answers the question – is the statement/program even valid? 

For example: “Rivers fly high” is a grammatically correct sentence but does it even make any sense? 

In programming, semantics answers if the syntactically valid programs have a correct meaning and what action they perform. 

To get hold of any programming language, there are 6 main components you should focus on: 

1. Understanding Variables
2. Understanding IF/Else
3. Understand Loops

• For Loop 
• While Loop

4. Functions
5. Understanding Strings
6. Concept of Array

(Know everything about programming language)

Data Structures

A data structure can be defined as a specialized format that is used to store, organize and process data so that it could be used efficiently. 

You must have seen how a bank’s cashier puts cash in different sections of the drawer. They do that so their transactions would be effortless and secure. 

Similarly, it becomes easier to perform operations on the data if you store it in a structured way. 

5 Common Data Structures

1. Arrays
2. Stack
3. Queues
4. Linked list
5. Graph (optional)

And we’ll understand all of them one by one-

What is Array in Data Structures?

An array is a data structure used to store the elements of the same data type such as integers or strings. Arrays store multiple data elements of the same type in adjacent memory locations.

In simple words, arrays are rectangular arrangements of objects in rows and columns.

Egg cartons would be a real-life example of arrays.

Why do we use Array?

Think of the seating arrangement in a movie theatre. There are hundreds of seats and if each one of these seats was to be declared/addressed individually, there will be time and memory problems. To avoid this, seats are arranged in the form of rows and columns and each seat is marked by a combination of row number and column number (like 7C, G9). This structure remains fixed for all the shows so they don’t have to change the address every time.

Similarly, accessing an element at runtime becomes a lot easier in arrays by using the index numbers.

Note: Indexing in an array starts from 0, the first array element is indexed with 0.

What are the types of Arrays?

There are majorly 3 types of arrays:

1. One-dimensional array 

A 1D array is simply a list of related elements and each element can be identified by a single index value. It is like a row of students standing in the assembly.

2. Two-dimensional array (2D array)

You can think of it as a table containing multiple elements in rows and columns. The seating arrangement example that we discussed earlier is an example of a 2D array.

3. Three-dimensional array (3D array)

A 3D array is nothing but a collection of two-dimensional arrays in which an element is identified using three subscripts- block size, row number, and column number. You can think of it as a cuboid made up of smaller cuboids. 

Choosing the type of array depends upon one’s requirement and what kind of storage structure a particular group of data needs.

Implementation of Arrays

To get well-acquainted with the concept of arrays, you need to perform the following operations:

• Inserting the number in the middle, front and last.
• Deleting the number from the middle, front and last.
• Search a number in an array.

Stacks in Data Structure

Stack is a linear sequence of elements that follows a particular order. In stacks, the addition of elements and the removal of elements both happen at the same end.

Consider a pile of books that have been kept over each other(in the stack from), now if you have to add a book, you’d add it at the top of the stack. Even if you have to remove a certain book in the middle, you’d start with removing the first book. In any case, operations start at the top end of the stack. 

This principle is called ‘last in first out’ (LIFO) order as the book at the top is the first one to be removed and the bottommost book would be in the stack for the longest time period.

‘Push’ in this case, is the process of inserting or adding an element and ‘Pop’ means removing an element. 

Here, you can clearly see that you can’t pop 1 without first popping 3 and 2 respectively. 

We can implement a stack using arrays, structure, and linked lists and stacks can be either of a fixed size or dynamic size.

Application of Stack

Suppose, you open a page in your browser (say- amazon.com), you click on a product that brings you to another page and then you decide to buy that product and so you reach the ‘add to cart’  page. 

You have visited 3 pages and the browser has kept these pages in the form of a stack which features the latest page at the top. Now, if you hit the ‘back/return’ button, you’ll be taken to a page right below in the stack (product page), and the same process will follow until you reach the page at the bottom.

Notice that you can’t reach directly from Page3 to Page1 without going through Page2. (First in, last out FILO).

This is an appropriate case for the application of stack as a data structure for different programs.

Advantages of Stack

• Helps in storing data in a LIFO/FILO order which isn’t possible with arrays and linked lists.
• Compilers can automatically allocate and deallocate memory in Stack.
• Stacks are not easily corrupted.

Queues in Data Structure

A queue is majorly similar to stacks in the sense that it’s an abstract data structure (ADS), the only difference being- Queues are open at both ends. 

We use one end of the queue to insert data (Enqueuing) and the other end to remove data (Dequeuing), unlike stacks where both processes take place at the same end. 

A real-life example would be a queue of people in front of the ATM. The first person in the row collects his cash and separates himself from the line at the front end, while a new person joins the line at the back end. 

This is a First-In-First-Out methodology i.e. the data stored first would be accessed first.

Apart from Enqueuing and Dequeuing, these are a few functions required for the efficient functioning of Queues:

1. peek() – This function brings the selected element at the front of the queue without removing it. 
2. isfull() – It checks if the queue is full. It returns false otherwise.
3. isempty() – It’s the opposite of IsFull and returns true if the queue is empty.

Note: These functions work with Stack too as they’re both abstract data types (ADS).

What are Linked Lists?

A linked list is also a linear data structure (just like arrays), but it’s different in the way that the elements aren’t stored in contiguous locations. Instead, they’re connected through links. Each node contains its data and a link to the next node.

For instance, you must have seen/played those treasure hunt games where a person has to solve some puzzle and then they get the clue to the next step and this follows until they find the treasure. 

Last link returns as null marking the end of the list. 

Advantages of Linked List

• There’s no need for memory in advance as the size of the linked list can increase or decrease at run-time.
• Insertion and Deletion processes are easy in a linked list as all elements don’t need to be shifted, one simply has to update the link in the pointer.
• You can also implement other data structures such as Stack, Queues using linked lists.

Other than Insertion and Deletion, a linked list supports basic functions such as Display, Search, and Delete.

Graphs Data Structure

Graphs are a non-linear data structure that represents the relationship between elements. Each graph consists of nodes (elements) and edges (links between elements). 

Take the example of a social media network, where each individual is a node and they’re interconnected with networks/lines that are called edges.

 Real-world applications of Graphs:

• Social networks
• Product recommendation graphs (e.g. E-commerce)
• Path optimization algorithm
• Mapping
• Neural networks (yes, our brain has graphs too)

Now that we have learned about different structures that store the inputs, let’s understand how a task is executed upon these inputs to get the desired results.

Algorithms Explained

Algorithms are a set of rules/instructions that guides the program to solve problems or complete certain tasks. 

In general, algorithms are all around us. We know them as ‘process’. For example, if you’re making tea, you’d follow the process including boiling milk, adding tea leaves and sugar, and then only you can enjoy the first sip. 

Similarly, a computer would perform a job only if we feed the correct algorithm to it. Many a time, we hear things like; Instagram or Twitter has changed their algorithm. It simply means they change the functionality of certain programs which in turn changes the parameters for post reach, post engagement, etc.

To understand algorithms in programming, we need to focus on the following components:

1. Time Complexity and Space complexity
2. Array | Stack | Queues
3. String
4. Recursion
5. Sorting Algorithm
6. Binary Search
7. Linked List

Time Complexity and Space Complexity

All of us want quick and efficient results no matter what actions we’re performing. We innovate, improvise and try to come up with the best possible solutions.

Writing algorithms is no different. We tend to write algorithms that are simple, sophisticated and take less time to run.

Time Complexity is the time taken by the algorithm to run as a function of the length of the input. 

Space Complexity tells the amount of space used by the algorithm to execute the instructions.

There could be algorithms to solve a problem or complete a task in Computer Science but we prioritize the ones that take less time and use less space/memory for optimal functioning of the program.

Let’s say, we ask you to sort a given set of numbers named K= {8, 32, 16, 1, 2},

Now, you can come up with different thought-process and find different connections between the numbers and write algorithms accordingly, but not all algorithms are going to be correct. That’s why we run a computational analysis to check which of the algorithms is the most efficient one.

String in Programming

The string is a data type (just like integers) that represents characters rather than just numbers. Programming languages use data types to sort different kinds of data in a program. 

String defines data values that are made up of an ordered sequence of characters such as “I had a pizza”. The length of a string is simply the number of characters in that string. 

“I had a pizza”  has 13 characters in total, including the spaces. So, 13 will be the length of the string. 

String-matching algorithms look for places where one or several strings are found within a larger string. Search engines use it to sort and categorize data properly so that they can display the most relevant results when a user searches for something. 

Real-world application of a string-matching algorithm

• Plagiarism Detection
• Digital Forensics
• Spam Filters
• Content Search

Recursion and Recursive Algorithms

Recursion refers to a programming method in which a function calls itself as a subset, thus allowing itself to be repeated several times in order to reach the specified condition. 

Okay? Had problems absorbing that? Let’s make it simpler for you.

Recursion is used to break the complex problems into smaller blocks and repeat the same procedure over them again and again to get the desired solution. 

It’s a really effective algorithm as it requires the least amount of code to meet the necessary tasks/functions. 

Think about it: You write the code once and it keeps repeating itself.

Recursion can be explained better through factorial function.

Let’s say we have to solve factorial (4).  (Given: 0! = 1)

4! = 4*3*2*1, which can also be written as: 4! = 4*3! Where 3! Becomes a subset of the problem. 

Similarly, to solve factorial (3), we need to solve the subset of factorial (2),

The case follows as:

factorial(n) = n*factorial(n-1)

till we reach factorial (0) which we have defined as 1. This is the base case in recursion where we start the recursive function. 

And then we run the algorithm on all the sub-problems repeatedly to solve the main problem. 

Recursive algorithms have three main parts:

1. Base Case – It is the simplest case/block we can think of while solving a problem.

2. Work towards Base Case – It is the process of simplifying the problem into smaller parts (each smaller than the original). 

3. Recursive Call – When we use the same algorithm to solve smaller versions of the problem, it is a recursive call.

Sorting Algorithm

A sorting algorithm is the set of instructions we write to arrange data in a specified order.  We can use numerical and alphabetical orders to sort data. 

Sorting helps in the optimization for data-searching and also makes it easily readable. 

A few real-life scenarios of sorting include a dictionary or an attendance register at schools where they sort the words and names using an alphabetical algorithm. 

Based on their function, sorting algorithms can be either adaptive or non-adaptive.

An adaptive algorithm takes into account the elements in a list that are already sorted and doesn’t attempt to re-order them. 

The non-adaptive Algorithm re-orders every single element from scratch and doesn’t consider the already sorted elements. 

Searching Algorithm

Searching algorithms locate specific elements among a collection of data from the data structure. Hundreds of software applications and search engines like Google and Amazon use searching algorithms to find and retrieve a specific item. 

Let’s look at the two most popular types of searching algorithms:

1. Linear Search 

In linear search, every item is checked one by one in a sequenced way. If we find the match, that specific item is returned, or else the search continues till the end of the structure. Linear search works best while finding an element in an unsorted data collection.

2. Binary Search

This algorithm searches for an item by dividing the list in half again and again until we narrow down the possible locations to just one. 

Remember how we select multiple clothes at first, and then we keep eliminating the less-liked ones until we have the final design remaining? 

Binary Search works somewhat similar to that. However, it works only when we’ve already sorted the data.

Linked Lists 

Linked list, as we have discussed in Data structure, starts with a link element called ‘first’. Each element or node has two fields – data field(s) and a link field called next which points to the next element. 

Types of Linked List

1. Single linked list – Only forward navigation is possible.
2. Doubly linked list – Both forward and backward navigation is possible.
3. Circular linked list – Last element points to the first element as ‘next’ and the first element contains a link to the last element as ‘previous’ resulting in a circular setup.

So, these were the main components in Data Structures and Algorithms. We believe that we’ve been able to describe them in the simplest of ways and you understand things with more clarity. 

Watch this video if you want a proper guide/strategy to mastering DSA.

Now, try answering these questions to yourself:

1. Should I learn Programming?
2. Do I want a long-term successful career in Software Engineering?

If your answer to both the questions is a- Yes, and you’re determined to make it big as a Software Engineer, you must check out this Full Stack Web Development course at Masai School. 

We prepare students coming from different backgrounds for jobs in the software industry at zero initial payment. Reputed companies hire students from Masai School as engineers and developers. 

You can be in that place too, all you’ve got to do is to apply for admission and choose your desired course. We don’t ask for any initial payment in any form whatsoever. 

You need to pay back a small percentage of your salary only after you get a job worth 5 LPA or more. (Income Share Agreement)

You’re learning Programming and we’re building programmers. We’re a good match, don’t you think? 

Cheers and Happy Coding.