Apply DSA Classes
+91 8088975867 Talk To Our Tech Team Any query related to live classes

Advanced
Data Structures Algorithms & System Design(HLD+LLD)
by Logicmojo

Cracking FAANG companies interviews with a few months of preparation

Learn Advanced Data Structures, Algorithms & System Design

Online live classes from 4 to 7 months programs

Get job assistance after course completion

Download Course Brochure

Become an Expert with
Logicmojo DSA Course


Learn DSA & System Design from Industry experts in
Logicmojo DSA Course. This course covers end-to-end
all topics of Data Structures and Algorithms from very basic to
complete advanced. All lectures cover complete code explanations.

Crack Tech Interviews at MAANG and Top Product based companies

  • Learn Data Structures , Algorithms & Problems Solving techniques
  • Coding & System Design Interview Interview Preparation
  • System Design Preparation (HLD + LLD)
Apply For DSA Classes
Watch
120% average Hike

In Job switch

18 LPA average CTC

(Product Based Companies)

1.3 Cr Highest CTC

(In Microsoft, India)

EMI 3,200/month

Easy No cost EMIs

Our students have gotten job offers from :

DSA Course Features

Live Interactive Sessions

Get Trained by MAANG Industry Experts Live classes

Practical experience through Projects

Practical experience through real-time projects

1:1 doubt clearing sessions

Personalized programs with Live classes and 1:1 doubt clearing sessions/mentorship sessions.

Job Assistance Program

Job Referrals in Product Companies, Resume Preparation Session and Mock interviews

Missed Classes ?

Attend multiple batches with multiple trainers if you miss any sessions or Topic for 1 Year subscription.

Life Time Access

Missed Classes, get lifetime access recorded lectures of all classes

peer to Peer Learning?

Slack group for peer-to-peer learning & discussion with batchmates. Hackerrank for 1:1 tests & GitHub for Code review.

Flexible Pay

Flexible EMI options on Credit cards and loan options on debit cards.

Assignments for Practise After Class

Practise question is key to crack interviews. Instructor provides assignments for all the topics covered in the class.

Competitive Coding Tests

Evaluate yourself in competitive coding tests with your batchmates.

Get Assured Interview Call from Top Recruiters

Over 200+ Hiring Partners



Course Reviews

  • 4.9

  • 4.8

  • 4.7

  • 4.7

  • 5

DSA Courses

• For Working Professionals LIVE Classes

Advanced Course of Data Structures, Algorithms & System Design(HLD + LLD)

Learn From Basic to Advanced DSA, Problem Solving, Scalable System Design (HLD + LLD),Design Patten etc

  • Curriculum

    1:1 Mentorship

  • Duration

    7 Months Classes
    Life Time Access

  • Mode

    LIVE Classes Weekend

  • ADDITIONAL CURRICULUM

    Projects included

• For Freshers Candidates LIVE Classes

Advanced Course of Data Structures, Algorithms & Problem Solving

Learn From Basic to Advanced Data Structures, Algorithms & Problem-Solving techniques

  • Curriculum

    1:1 Mentorship

  • Duration

    4 Months Classes
    Life Time Access

  • Mode

    LIVE Classes Weekend

  • ADDITIONAL CURRICULUM

    Projects included



Syllabus - DSA Course

Syllabus for the DSA Course in Logicmojo is comprehensive and structured to cater to a wide range of learners. It encompasses fundamental concepts, advanced DSA and analysis, and practical problem-solving techniques. The course is designed to provide a deep understanding of both theoretical and applied aspects of data structures and algorithms, ensuring a solid foundation for aspiring professionals. Additionally, it includes hands-on projects and real-world applications to reinforce learning and skill application.

Detail Syllabus - Live Classes

Scalable System Design with HLD + LLD

(Duration - Next 3 months)

This course is curated by leading faculties and industry leaders to provide practical learning experience with live interactive classes and projects.

  • • Techniques to start discussing the problem statement scope
  • • Define all design constraints in the system
  • • Finalizing the scalability, the system will support

  • • System capacity/size estimation with number of users access it
  • • Finalizing the target environment (Tools, library or open sources)
  • • Concise the problem, support the scalability

  • • Identify system level REST API to access the recourses.
  • • Define parameters, return types JSON
  • • Finalize read/write/delete/paste API possible in the system

  • Identify all the data models & business logic involved in backend
  • Identify all functional/Non-functional components involved
  • Finalize state machine, service layer & interfaces

  • Check reliability and redundancy
  • Components required to make low latency system
  • Database finalization, Metadata Sharding etc.

  • Distributed Hash Table, LRU, In-memory Data Lookup
  • Memcache, Read-Through, Write-Through Cache

  • http/https, DOS, web server, abstraction layer
  • Scheduling algo, Round robin, FCFS
  • One to Many, Many to One Communication

  • Vertical scaling, Horizontal scaling, which is better
  • Minimize Latency & Increase Throughput Of System
  • Factors Need to be considered for Scalable System Design

  • High Availability Clustering
  • Desinging & Configuring Distributed Cache
  • Abstraction & Consistency Model

  • Introduction & Configuration of Pub-Sub Model
  • Real-Time Streaming, Active MQ,Message Broker
  • Configuration Load Balancer, Set up CDN

  • Basic Architecture of Kubernetes
  • Kubectl Describe, Configuration of Zookeeper
  • Root Nameserver, Authoritative nameserver, DNS Resolver

  • Client Side vs Server Side Rendering
  • Adding,deleting and Finding Specific Nodes

  • REST API - CORS and Enabling CORS
  • REST-PUT,DELETE,GET,POST Configuration
  • Serialization vs De-Serialization,Working with JSON
  • POSTMAN,Swagger Configuration
  • Restful Web Services Implementation

  • Key Data Store
  • Pull and Push Models Implementations
  • HTTP keep-alive vs long polling

Program Highlights

  • 85+ Hours Live sessions
  • 1:1 Doubt Session
  • 3+ Design Projects
  • Multiple Batches Options
  • Life time accessibility
  • Job Referrals Program
  • Peer to peer Learning
  • Mock Interviews
  • Resume Preparation
  • Weekly Assignments
  • Regular Progress Tests
  • Code Explanation

Detail Syllabus - Live Classes

Advanced DSA & Problem Solving course

(Duration - First 4 months)

This course is curated by leading faculties and industry leaders to provide practical learning experience with live interactive classes and projects.

Program Highlights

  • 110+ Hours Live sessions
  • 1:1 Doubt Session
  • 4+ Projects
  • Multiple Batches Options
  • Life time accessibility
  • Job Referrals Program
  • Peer to peer Learning
  • Mock Interviews
  • Resume Preparation
  • Weekly Assignments
  • Regular Progress Tests
  • Code Explanation

Eligibility For Logicmojo DSA Course

Eligibility criteria must be met for candidates to qualify for the DSA Course. A mentor will call every candidate before enrollment in the course

Eligibility for DSA Course

DSA & System Design Course

For Working Professionals

This course is primarly designed for working professionals. Talk to our experts for profile review before joining

For Freshers

Fresh graduates or undergraduates from a CS/IT background are eligible for this course.

Improve DSA Skills

Candidates who want to improve their problem-solving skills and knowledge of DSA can join this course.

Placement assistance

All candidates who qualify for this course are eligible to receive job assistance in top product companies.

Land in your dream job with real work experience

Live Demo Session For Upcoming Batch - 30th March

DSA, Problem Solving & System Design
7 months Course

Live Classes Will Start From 30th March.This is a Live Demo Session For Upcoming Batch. Initial 4 months We Focus on Data Structures, Algorithms & Problems Solving Part Where We Prepare Candidates For MAANG Companies Coding Interviews Rounds

After Completion of the 4 Months Coding Part then Next 3 Months. We Focus on Scalable System Design Part, Archirectures & Internal Design of Many Scalable System Model with HLD + LLD. We prepare Candidates for System Design Rounds.

Mentor - Aman (DSA)


Aman stands out as the finest instructor at Logicmojo. Aman is currently working in R & D Division at Top Tech organization WalmartLabs as a Senior Developer, He also has relevant teaching experience. He focus more on techniques of solving problems and tricks to solve any coding problems. Aman will be tutoring the candidates for the upcoming batch starting the 24th of Feb/24. You can find his Live Demo Class Recording.

Mentor - Ranjan Kumar (System Design)


Ranjan is working at Amazon in the US (Seattle). He previously worked with Microsoft for several years. He has experience in design and architecture, focusing on scalable system design. He has prepared several candidates for top tech companies.

Enhanced your salary 8X just by learning from DSA & System Design Course

High demand for software developer profile across all product companies in the world

Just Few Months Of Preparation in Live Classes and Crack Coding & System Design Rounds in Top Product Based Companies

25,12,290

Average Annual
Base Salary (2024)

85%

Average Salary Growth Annual
(Service Companies --> Top Product Companies)

161%

Software Developer
Job Listings Growth,
Annual (2019-2024)

Career Impact

Software Development Engineer(SDE) Roles have Average package of 25+ Lakh in Top Product Based Companies.

Learn from MAANG companies
Experts & Transform your Career

Apply For Live Classes

What you’ll learn in first 4 months in Live Course

1
Time Complexity

Learn fundamentals of programming and understand time complexity.

3
Array, String and Linked List

Master array, string and linked list and implement real time project on Git and GitHub.

5
Stack and Queue

Learn fundamentals of programming of stack and queue and its useage.

7
Hashing & Heap Sort

Learn fundamentals of programming the hashing/heap sort in very simpler way.

9
OOPS Concepts & Design

Learn fundamentals concepts of OOPs and use it real projects.

11
Competitive Programming

String based and mathematical competitive programming practise,Hackerank, Hackerearch Practise in Live classes

2
Binary Tree, N-ary Tree, Segment Tree etc

Learn fundamentals of binary tree and N-ary tree and use it project/assignements.

4
Greedy Algorithm

Learn all about building responsive websites using HTML5 and CSS3; discuss key HTML5 APIs and their use cases.

6
Backtracking & Recursion

Learn fundamentals of programming the world-wide web and its key stakeholders.

8
Graph Theory

Learn fundamentals of programming the world-wide web and its key stakeholders.

10
Dynamic Programming

Learn fundamentals of programming the world-wide web and its key stakeholders.

12
Advanced Data Structures

Complete Advanced data structures like Trie, Suffix Tree, Suffix Tree, ternary search trees etc

DSA + System Design Course Fee

Total Fee

₹ 45,000

No Cost EMI

As low as ₹ 3,750/month

Apply now

We have partnered with the following financing companies to provide competitive finance options at 0% interest rate with no hidden costs.

DSA + System Design Course Duration

  • Duration: 7 months Live Weekend Classes
  • Prerequisite : Basic understanding of programming required
  • Complete Interview Preparation Course

Who can apply for the DSA + System Design Classes?

  • Software engineers
  • IT Professionals
  • Managers
  • Architect
  • Senior Developers

What People Say - DSA Course Review

How it has helped them accelerate their careers to the next level.

140%

Siddharth Pande

Full Stack Developer
One of the Best Resources for Learning DSA & Design. Logicmojo Course Helped me Multiple Times During Interview Preparation For Companies like Walmart, Oracle, and Microsoft. No Need of Any Other Online Materials.
Oracle
295%

Anjani Kumar

Software Development Engineer - 1
Very Well-arranged Course and its Amazing Lecture Delivery by Trainers. Expert Team is always Available to solve Any Technical Queries. Logicmojo Live Preparation Training Helps me to Crack Zynga and Now Amazon Interview.
Zynga
190%

Afnaan Rafique

Software Engineer 2
I have a very great experience with Logicmojo. Learning by doing is a great way to learn something which Logicmojo team encouraged me to do so. The course has a big contribution to my success.
GlobalLogic
270%

Piyush Mittal

Senior Developer
The Course Curriculum is of the Best Quality Along with the Best Learning Experience from my Tutor. Best Course to Prepare For MAANG Companies Interview. I Cracked Paytm, Adobe, Intuit, and Microsoft. Finally joined Microsoft at 1.3 Cr LPA Hyderabad MS IDC
Paytm
170%

Diwakar Choudhary

Staff Engineer/Manager
Excellent Course for Interview Preparation, Very Straight to the Point ,In-Depth Coverage of Every Point in Live Classes. Speecially Focus on Practical Implementation of Every Coding & Architectiral Problems.
Cirtix
160%

Priya Singh

Senior Software Engineer
The Course Curriculum is of Best Quality Along with Good Coding Problems that Discussed in the Class. Materials are Helpful even After Completion of the Course.
MindTree
210%

Mohammed Shirhaan

Lead Engineer
For Learning and Growing in your Tech Carrier, I Would Highly Recommend to Attend the 7 Months Program, it Help you in Very Way to Achieve your Dreams. Very Structured Course, Covering Almost all Techniques and Concepts of Solving Advanced Coding & Design Problems.
Informatica
210%

Arpit Singh

Senior Software Engineer - 1
Thank you, Logicmojo Team. Your classes are amazing. All topics are covered sequentially, and the techniques and patterns of problem-solving are the best parts of the course.
B.Tech
130%

Rajnish Kumar

Staff Engineer
Great course! Definitely helped me open some new doors in understanding how algorithms work and implementing solutions for the different exercises. Live Courses are recommended for Working Professionals.
Cred
220%

Aravindo Swain

Software Engineer - II
I Would say the Best Part is the Explanation by the Trainer, Concise and Clear. Great Quality of Online Materials and Classes, It Covers all Algorithms and System Design Problems asked During Interviews
Oracle
View more reviews

Few Reviews From Subscribers

Over Chat, Email, And Linkedin

Our subscribers create milestones by cracking top tech companies' interviews & grab more than 80+ LPA(Lakh Per Annum) package in India . Logicmojo course provides them the guidance, direction, concepts & well-structured content to help them during their preparation.

These are a few of the reviews of our subscribers.

Logicmojo in
the News
Logicmojo Awards
& Affiliation

What Are Data Structures and Algorithms?

Data structures refer to the way data is organized in a virtual system, such as a sequence of numbers or a table of data. Meanwhile, an algorithm is a set of instructions performed by a computer to transform input into output.

How Do Data Structures and Algorithms Work Together?

1. There are numerous algorithms designed for specific tasks that operate on different data structures with the same level of computational complexity. Algorithms can be thought of as dynamic elements that interact with static data structures.

2. The expression of data in code is adaptable. Once you comprehend the construction of algorithms, you can apply this knowledge across various programming languages. In essence, it's similar to understanding the syntax of a family of related languages. Understanding the foundational principles of programming languages and their organizing principles can facilitate faster learning and easier transitioning between different languages.

How to learn DSA Steps by Steps ?

DSA courses are crucial for learning complete Data Structures and Algorithms. In the video below, we explain how you can learn DSA step by step. Understanding DSA concepts step by step, with regular practice of the problems, is essential. The video explains how we can solve problems in every topic of DSA and how much time should be spent on each topic.



Why Learn Data Structures and Algorithms ?

1. To write code that is both efficient and can handle large amounts of data, it's important to understand various data structures and algorithms. With this knowledge, you can decide which data structure and algorithm to use in different situations to create optimized and scalable code.

2. Knowing about data structures and algorithms can assist you in utilizing time and memory more effectively by enabling you to write code that runs faster and uses less storage.

3. Having knowledge of data structures and algorithms can increase your chances of finding employment opportunities, as these concepts are commonly tested in job interviews across a range of organizations, such as Google, Facebook, and others.

How you can learn data structure and Algorithms ?

1. Learn DSA from Logicmojo

Logicmojo provides a comprehensive set of tutorials on data structures and algorithms, complete with relevant examples that are easy to understand. These tutorials are designed specifically for individuals with no prior experience in computer programming who wish to explore this field.

2. Get familiar with computational complexity

Big O notation is crucial for understanding the time and space complexity of algorithms, particularly in worst-case scenarios where the input size is at its maximum. Time scales range from linear to polynomial, exponential, and logarithmic, and each represents a different level of performance and expected computation time.

The performance of algorithms can vary drastically depending on the scale. For instance, a logarithmic scale may perform well with larger data sets and inputs, while an exponential scale may result in computations that never finish in time.

3. Understand different data structures and algorithm types

Read through basic data structure and algorithm types to get a better feel for the subject.

4. Get on-the-job training

Get a job in software engineering or a role where data structures and algorithms are implemented in order to best exercise your new knowledge.

Learn DSA From Logicmojo Course

For learning DSA, you can refer multiple courses for DSA. These DSA courses will help to you understand the concepts and complete your preparation for Data Structures and Algorithms in few months.

Below we have mentioned two DSA courses to prepare for Interviews.

1. Advanced Course of Data Structures, Algorithms(DSA) & System Design: This Course is for working professionals who wants to prepare DSA to switch there profile from service to top product companies.

2. Advanced Course of Data Structures, Algorithms(DSA) & Problem Solving: This Course is for Freshers candidates who wants to prepare DSA to start there Tech carrier in top product companies.

Features of Logicmojo DSA Course

Logicmojo DSA Course is designed for both working professionals and fresher candidates to prepare for DSA & System Design interviews. Along with live classes, the DSA course is equipped with many other features, as stated below.

1.Live Interactive Classes: Weekend Live classesfrom Experts of MAANG Companies.

2. Practical Experience through Projects: All Topics in DSA & System Design teaches with practical industry based projects.

3. Live Doubt Session: Assignments & Doubts will answered in seperate weekdays Live Doubt Session By Trainer.

4. Job Assistance: : All Candidadates in DSA Course will provided with Job Assistance in Top Product based Companies.

5. Incase Missed Classes: : Attend multiple batches with multiple trainers if you miss any sessions or Topic for 1 Year subscription.

6. LifeTime Access of Content: : Access all recording in the DSA Classes for Life time.

Below image explains all features in an elaborate way.

Need of Data Structures and Algorithms.

  1. Data structures and algorithms are important for solving real-world problems, such as efficiently searching for books in a library.
  2. Knowledge of DSA can help optimize and scale code by selecting the appropriate data structure and algorithm for the specific use case.
  3. DSA skills improve problem-solving abilities and are valuable in the tech industry. Most applications, such as WhatsApp and LinkedIn, use DSA in some way.
  4. Whether working on personal projects, participating in coding contests, or being a software developer, understanding DSA is always beneficial.
  5. Many product-based companies now include DSA and algorithm questions in their interviews to assess problem-solving abilities. Learning DSA can increase the chances of landing a dream job.

Common Data Structures and Algorithms.

  1. Linked lists
  2. Stacks
  3. Queues
  4. Sets
  5. Hash tables
  6. Search trees

Each of these data structures has its own level of computational complexity when performing tasks like adding items or calculating aggregate measures, such as the mean, based on the data stored within them.
Some common categories of algorithms are:

  1. Search
  2. Sorting
  3. Graph/tree traversing
  4. Dynamic programming
  5. Hashing and regex (string pattern matching)

Importance of Data Structures and Algorithms :

Dsa optimize code with complexity : DSA plays a crucial role in reducing time complexity in code. Although a problem can be approached in various ways, selecting the most optimized approach can increase productivity and solve the problem in a shorter time frame. Learning data structures and algorithms can help achieve this optimization.

DSA improves CS Fundamenetal : Data structures and algorithms are regarded as the fundamental pillars of computer science. As technology evolves, the amount of data being stored also increases. However, large volumes of data can adversely affect the processing speed of computer systems. In such scenarios, data structures can be useful as they optimize the storage and utilization of data, leading to improved processing power of the computer.

Applications of Data Structures and Algorithms

In this link we explain in detail about Application of Data Structures & Algorithms

What are Algorithms?

Algorithms are the logical procedures used to manipulate data structures in order to solve problems. There are many different types of algorithms, each with its own unique set of advantages and disadvantages. Here are some of the most common types of algorithms:

Searching Algorithms

A searching algorithm is used to find a specific element in a data structure. There are many different searching algorithms, each with its own trade-offs in terms of efficiency and simplicity.

Sorting Algorithms

A sorting algorithm is used to rearrange the elements of a data structure in a specific order, such as alphabetical or numerical..

Logicmojo offering best online data structures and algorithms course for preparing coding interviews in 2024. All tech giant companies in 2024 focus on problem-solving during interviews irrespective of the domain you are working for or you’re a fresher. Learn data structure and algorithm for experts and finish your preparation in 2-3 months. We teach data structures and algorithms in Java, Python and C++ languages with complete code explanation.

Books For Data Structures and Algorithms

A superlative, contemporary, and user-friendly treatise on data structures and algorithms, this compendium has been meticulously crafted for undergraduate scholars in computer science and information science domains. Comprising thirteen chapters, the content is the brainchild of a global consortium of accomplished pedagogues, delving into the quintessential notions of algorithms, a plethora of pivotal data structures, and the art of interface design. The tome is replete with illustrative examples and schematics, judiciously interspersed with program codes to augment the learning experience..

Data Structures and Algorithms Course for Freshers Candidate

The best way to learn data structure and algorithm courses is to practice every problem by yourself. Practice is only key to cracking top tech company's interviews. Experienced candidates must prepare for System Design problems also. Learn System Design, Distributed System as well as oops design from experts Instructor with 12+ experience in FAANG companies.

This book receives backing from a worldwide team of writers skilled in data structures and algorithms. Through its website at http://www.cs.pitt.edu/~jung/GrowingBook/, it offers valuable insights for both educators and learners to make the most of the authors' knowledge.

Contents of the Book:

course features

logicmojo provides 60+ HOURS LECTURES in data structures and algorithms course
60+
HOURS LECTURES
logicmojo provides ASSIGNMENTS & ASSIGNMENTS DISCUSSION in data structures and algorithms course
ASSIGNMENTS &
ASSIGNMENTS DISCUSSION
logicmojo provides WEEKLY CODING TEST in data structures and algorithms course
WEEKLY CODING
TEST
logicmojo provides JOB ASSISTANCE in data structures and algorithms course
JOB ASSISTANCE
logicmojo provides LIFE TIME COURSE ACCESS in data structures and algorithms course
LIFE TIME COURSE
ACCESS
logicmojo provides DOUBT CLEARING SESSION in data structures and algorithms course
DOUBT CLEARING
SESSION
logicmojo provides COMPLETE CODE EXPLANATION in data structures and algorithms course
COMPLETE CODE
EXPLANATION
logicmojo provides REGULAR UPDATES in data structures and algorithms course
REGULAR UPDATES

Data Structures & Algorithms

Classification of Data Structure

This article contains a detailed view of all common data structures and algorithms we use in our daily life programming to allow readers to become well equipped.

Listed below are the topics discussed in this article:

Introduction to Data Structures And Algorithms
- Linear Data Structures
- Hierarchical Data Structures
Algorithms
- Sorting Algorithms
- Searching Algorithms

Introduction

Data Structure is a way of collecting and organising data in such a way that we can perform operations on these data in an effective way. Data Structures is about rendering data elements in terms of some relationship, for better organization and storage. Let’s say We have some data which has, student’s name “Shivam” and his age 13. Here Shivam is of String data type and 13 is of integer data type.

In simple language, Data Structures are structures programmed to store ordered data, so that various operations can be performed on it easily. It represents the knowledge of data to be organized in memory. It should be designed and implemented in such a way that it reduces the complexity and increases the efficiency.

Basic types of Data Structures

Basic Types Of Data Structures

As we have discussed above, anything that can store data can be called as a data structure, hence Integer, Float, Boolean, Char etc, all are data structures. They are known as Primitive Data Structures. Then we also have some complex Data Structures, which are used to store large and connected data. Some examples of Abstract Data Structure are Linked List, Stack, Queue, Tree, Graph etc.

All these data structures allow us to perform different operations on data. We select these based on our requirements.

Let’s Check out each of them in detail.

Linear Data Structures And Algorithms

Linear data structures are those whose elements are in sequential and in ordered way. For example: Array, Linked list

Arrays

An array is a linear data structure representing a group of similar elements, accessed by index. Some Properties of Array Data Structures:

Basic Types Of Data Structures

Each element in an array is of the same data type and has the same size
Elements of the array are stored at contiguous memory locations with the first element is starting at the smallest memory location
Elements of the array can be randomly accessed like arr[0] for 1st element, arr[3] for 3rd element
Array data structures is not completely dynamic meaning memory allocated as soon as array is declared but we can create dynamic array by using different libraries in many modern programming languages.

Linked List

Linked List in Data Structures And Algorithms In Java

A linked list is a linear data structure with the collection of multiple nodes, where each element stores its own data and a pointer to the location of the next element. The last link of linked List points to null.

An element in Linked List is called node. The first node is called head. The last node is called tail.

Difference Between Array & Linked List in Data Structures And Algorithms In Java

Types of Linked List

Singly Linked List (Uni-directional)

The singly linked list is a linear data structure in which each element of the list contains a pointer which points to the next element in the list. Each node has two components: data and a pointer next which point to the next node in the list.

Below the Single LinkedList Creation Animation


Linked List in Data Structures And Algorithms In Java

    
    class LinkedList {
        Node head; // head of the list
        /* Linked list Node*/
        class Node {
            int data;
            Node next;
            // Constructor to create a new node
            // Next is by default initialized
            // as null
            Node(int d) { data = d; }
        }
    }
    

Doubly Linked List (Bi-Directional)

Doubly Linked List is just same as singly Linked List except it contains an extra pointer, typically called previous pointer, together with next pointer and data.



// Class for Doubly Linked List
public class DLL {
    Node head; // head of list
 
    /* Doubly Linked list Node*/
    class Node {
        int data;
        Node prev;
        Node next;
 
        // Constructor to create a new node
        // next and prev is by default initialized as null
        Node(int d) { data = d; }
    }
}

Advantages over singly linked list

A DLL can be traversed in both forward and backward direction.
The delete operation in DLL is more efficient if pointer to the node to be deleted is given.

Circular Linked List

A circular linked list is a variation of a linked list in which the last node points to the first node, completing a full circle of nodes. You can say it doesn’t have null element at the end.


Circular LinkedList

Application of Circular Linked List

The real life application where the circular linked list is used is our Personal Computers, where multiple applications are running. All the running applications are kept in a circular linked list and the OS gives a fixed time slot to all for running. The Operating System keeps on iterating over the linked list until all the applications are completed.
Another example can be Multiplayer games. All the Players are kept in a Circular Linked List and the pointer keeps on moving forward as a player's chance ends.
Circular Linked List can also be used to create Circular Queue. In a Queue we have to keep two pointers, FRONT and REAR in memory all the time, where as in Circular Linked List, only one pointer is required.

Stacks

What is Stack?

Stack, an abstract data structure, is a collection of objects that are inserted and removed according to the last-in-first-out (LIFO) principle. Objects can be inserted into a stack at any point of time, but only the most recently inserted (that is, “last”) object can be removed at any time.

Listed below are properties of a stack:

It is an orderd list in which insertion and deletion can be performed only at one end that is called the top.
Recursive data structure with a pointer to its top element.
Follows the last-in-first-out (LIFO) principle
Stack Concepts

Stack Concepts in Data Structures And Algorithms In Java

When an element is inserted in a stack, the concept is called a push.
When an element is removed from the stack, the concept is called pop.
Trying to pop out an empty stack is called underflow (treat as Exception).
Trying to push an element in a full stack is called overflow (treat as Exception).
Applications of Stack

Applications Of Stack in Data Structures And Algorithms In Java

Following are some of the applications in which stacks play an important role.

Balancing of symbols
Page-visited history in a Web browser [Back Buttons]
Undo sequence in a text editor
Finding of spans (finding spans in stock markets)
Stack Implementation using Array
Push Operation
In a push operation, we add an element into the top of the stack.
Increment the variable Top so that it can now refer to the next memory location.
Add an element at the position of the incremented top.
This is referred to as adding a new element at the top of the stack.
Throw an exception if Stack is full.
public void push(int data) throws Exception {
    if (size() == capacity)
        throw new Exception("Stack is full.");
        stackArray[++top] = data;
}

Pop Operation
Remove the top element from the stack and decrease the size of a top by 1.
Throw an exception if Stack is empty.
public int pop() throws Exception {
    int data;
    if (isEmpty())
        throw new Exception("Stack is empty.");
    data = stackArray[top];
    stackArray[top--] = Integer.MIN_VALUE;
    return data;
}

Complexity Analysis

Let n be the number of elements in the stack. The complexities of stack operations with this representation can be given as:

Time Complexity of push() O(1)
Time Complexity of pop() O(1)
Space Complexity O(n)

Queues

Queues

Queues are also another type of abstract data structure. Unlike a stack, the queue is a collection of objects that are inserted and removed according to the first-in-first-out (FIFO) principle.

Listed below are properties of a queue:

Often referred to as the first-in-first-out list
Supports two most fundamental methods enqueue(e): Insert element e, at the rear of the queue dequeue(): Remove and return the element from the front of the queue
Queue Concepts

Queue Concepts in Data Structures And Algorithms In Java

When an element is inserted in a queue, the concept is called EnQueue.
When an element is removed from the queue, the concept is called DeQueue.
DeQueueing an empty queue is called underflow (treat as Exception)
EnQueuing an element in a full queue is called overflow (treat as Exception).
Applications of Queue
Operating systems schedule jobs (with equal priority) in the order of arrival (e.g., a print queue).
Simulation of real-world queues such as lines at a ticket counter, or any other first come the first-served scenario requires a queue.
Multiprogramming. Asynchronous data transfer (file IO, pipes, sockets).
Implementation of Circular Queue using Linked List

Circular Queue Concept in Data Structures And Algorithms In Java

Operations on Circular Queue:

For enQueue

Create a new node dynamically and insert value into it
Check if front==NULL, if it is true then front = rear = (newly created node)
If it is false then rear=(newly created node) and rear node always contains the address of the front node.

For Dequeue

Check whether queue is empty or not means front == NULL.
If it is empty then display Queue is empty. If queue is not empty then step 3
Check if (front==rear) if it is true then set front = rear = NULL else move the front forward in queue, update address of front in rear node and return the element.

Circular Queue Concept in Data Structures And Algorithms In Java

Below is the code implementation in Java

// Java program for insertion and
// deletion in Circular Queue Using Linked List
import java.util.*;

class Solution {

  // Structure of a Node
  static class Node {
    int data;
    Node link;
  }

  static class Queue {
    Node front, rear;
  }

  // Function to create Circular queue
  static void enQueue(Queue q, int value)
  {
    Node temp = new Node();
    temp.data = value;
    if (q.front == null)
      q.front = temp;
    else
      q.rear.link = temp;

    q.rear = temp;
    q.rear.link = q.front;
  }

  // Function to delete element from Circular Queue
  static int deQueue(Queue q)
  {
    if (q.front == null) {
      System.out.printf("Queue is empty");
      return Integer.MIN_VALUE;
    }

    // If this is the last node to be deleted
    int value; // Value to be dequeued
    if (q.front == q.rear) {
      value = q.front.data;
      q.front = null;
      q.rear = null;
    }
    else // There are more than one nodes
    {
      Node temp = q.front;
      value = temp.data;
      q.front = q.front.link;
      q.rear.link = q.front;
    }

    return value;
  }

  // Function displaying the elements of Circular Queue
  static void displayQueue(Queue q)
  {
    Node temp = q.front;
    System.out.printf("\nElements in Circular Queue are: ");
    while (temp.link != q.front) {
      System.out.printf("%d ", temp.data);
      temp = temp.link;
    }
    System.out.printf("%d", temp.data);
  }

  /* Driver of the program */
  public static void main(String args[])
  {
    // Create a queue and initialize front and rear
    Queue q = new Queue();
    q.front = q.rear = null;

    // Inserting elements in Circular Queue
    enQueue(q, 14);
    enQueue(q, 22);
    enQueue(q, 6);

    // Display elements present in Circular Queue
    displayQueue(q);

    // Deleting elements from Circular Queue
    System.out.printf("\nDeleted value = %d", deQueue(q));
    System.out.printf("\nDeleted value = %d", deQueue(q));

    // Remaining elements in Circular Queue
    displayQueue(q);

    enQueue(q, 9);
    enQueue(q, 20);
    displayQueue(q);
  }
}

Implementation Of Circular Queue Using Linked List in Data Structures And Algorithms In Java

Hierarchical Data Structures And Algorithms in Java

Binary Tree

Tree Data Structure in Data Structures And Algorithms In Java

Binary Tree is a hierarchical tree data structures in which each node has at most two children, which are referred to as the left child and the right child. Each binary tree has the following groups of nodes:

Root Node: It is the topmost node and often referred to as the main node because all other nodes can be reached from the root

Left Sub-Tree, which is also a binary tree

Right Sub-Tree, which is also a binary tree

Binary Tree: Common Terminologies

Root:Topmost node in a tree.

Parent:Every node (excluding a root) in a tree is connected by a directed edge from exactly one other node. This node is called a parent.

Child:A node directly connected to another node when moving away from the root

Leaf/External node:Node with no children.

Internal node:Node with atleast one children.

Depth of a node:Number of edges from root to the node.

Height of a node:Number of edges from the node to the deepest leaf. Height of the tree is the height of the root

Listed below are the properties of a binary tree:

A binary tree can be traversed in two ways:

Depth First Traversal: In-order (Left-Root-Right), Preorder (Root-Left-Right) and Postorder (Left-Right-Root)

Breadth First Traversal: Level Order Traversal

Time Complexity of Tree Traversal: O(n)

The maximum number of nodes at level "n" = 2(n-1).

The maximum number of nodes of Binary Tree of height "h" = 2(h).

Below is the image which gives better visualization that how maximum number of nodes of Binary tree is 2(h)

how maximum number of nodes of Binary tree in Data Structures And Algorithms In Java

Applications of binary trees include:
Used in many search applications where data is constantly entering/leaving
Used in almost every high-bandwidth router for storing router-tables
Used in compression algorithms and many more

Graph

What is graph (data structure)?

A graph is a common data structure that consists of a finite set of nodes (or vertices) and a set of edges connecting them.

A pair (x,y) is referred to as an edge, which communicates that the x vertex connects to the y vertex.

Graphs are used to solve real-life problems that involve representation of the problem space as a network. Examples of networks include telephone networks, circuit networks, social networks (like LinkedIn, Facebook etc.).

Types of graphs:

Undirected Graph:

In an undirected graph, nodes are connected by edges that are all bidirectional. For example if an edge connects node 1 and 2, we can traverse from node 1 to node 2, and from node 2 to 1.

Directed Graph:

In a directed graph, nodes are connected by directed edges – they only go in one direction. For example, if an edge connects node 1 and 2, but the arrow head points towards 2, we can only traverse from node 1 to node 2 – not in the opposite direction.

Types of Graph Representations:

Adjacency List

To create an Adjacency list, an array of lists is used. The size of the array is equal to the number of nodes. A single index, array[i] represents the list of nodes adjacent to the ith node.

For example, we have given below.

Adjacency List Representations in Data Structures And Algorithms In Java

We use Java Collections to store the Array of Linked Lists.

class Graph{
    private int numVertices;
    private LinkedList<integer> adjLists[];
}

Adjacency Matrix

An Adjacency Matrix is a 2D array of size V x V where V is the number of nodes in a graph. A slot matrix[i][j] = 1 indicates that there is an edge from node i to node j.

For example, we have given below.

Adjacency Matrix Representations

Here is the implementation part in Java.

public AdjacencyMatrix(int vertex){
        this.vertex = vertex;
        matrix = new int[vertex][vertex];
}

Algorithms in Java

Algorithms are deeply connected with computer science, and with data structures in particular. An algorithm is a sequence of instructions that describes a way of solving a specific problem in a finite period of time. They are represented in two ways:

Flowcharts- It is a visual representation of an algorithm’s control flow

Pseudocode– It is a textual representation of an algorithm that approximates the final source code

Note: The performance of the algorithm is measured based on time complexity and space complexity. Mostly, the complexity of any algorithm is dependent on the problem and on the algorithm itself.

Let’s explore the two major categories of algorithms in Java, which are:

Sorting Algorithms in Java

Sorting algorithms are algorithms that put elements of a list in a certain order. The most commonly used orders are numerical order and lexicographical order.

Let's dive into some famous sorting algorithms.

Bubble Sort in Java

Bubble Sort is a simple algorithm which is used to sort a given set of n elements provided in form of an array with n number of elements. Bubble Sort compares all the element one by one and sort them based on their values.

It is known as bubble sort, because with every complete iteration the largest element in the given array, bubbles up towards the last place or the highest index, just like a water bubble rises up to the water surface.

Here’s pseudocode representing Bubble Sort Algorithm (ascending sort context).

a[] is an array of size N
begin BubbleSort(a[])
 
declare integer i, j
for i = 0 to N - 1
   for j = 0 to N - i - 1
      if a[j] > a[j+1] then 
         swap a[j], a[j+1]
      end if
   end for
  return a
   
end BubbleSort

Worst and Average Case Time Complexity: O(n*n) (The worst-case occurs when an array is reverse sorted).

Best Case Time Complexity:O(n) (Best case occurs when an array is already sorted).

Selection Sort in Java

Selection sorting is a combination of both searching and sorting. The algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from the unsorted part and putting it at a proper position in the array.

Here’s pseudocode representing Selection Sort Algorithm (ascending sort context).

a[] is an array of size N
begin SelectionSort(a[])
 
 for i = 0 to n - 1
   /* set current element as minimum*/
      min = i    
      /* find the minimum element */
       for j = i+1 to n 
         if list[j] < list[min] then
            min = j;
         end if
      end for
  /* swap the minimum element with the current element*/
      if min != i  then
         swap list[min], list[i]
      end if
   end for
     
end SelectionSort

Time Complexity: O(n2) as there are two nested loops.

Auxiliary Space: O(1).

Insertion Sort in Java

Insertion Sort is a simple sorting algorithm which iterates through the list by consuming one input element at a time and builds the final sorted array. It is very simple and more effective on smaller data sets. It is stable and in-place sorting technique.

Here’s pseudocode representing Insertion Sort Algorithm (ascending sort context).

a[] is an array of size N
begin InsertionSort(a[])
 
for i = 1 to N
   key = a[ i ]
   j = i - 1
   while ( j >= 0 and a[ j ] > key0
      a[ j+1 ] = x[ j ]
      j = j - 1
   end while
   a[ j+1 ] = key
end for
 
end InsertionSort

Best Case: The best case is when input is an array that is already sorted. In this case insertion sort has a linear running time (i.e., Θ(n)).

Worst Case: The simplest worst case input is an array sorted in reverse order

QuickSort in Java

Quicksort algorithm is a fast, recursive, non-stable sort algorithm which works by the divide and conquer principle. It picks an element as pivot and partitions the given array around that picked pivot.

Steps to implement Quick sort
Pick a suitable “pivot point”.
Divide the lists into two lists based on this pivot element. Every element which is smaller than the pivot element is placed in the left list and every element which is larger is placed in the right list. If an element is equal to the pivot element then it can go in any list. This is called the partition operation.
Recursively sort each of the smaller lists.

Here’s pseudocode representing Quicksort Algorithm.

QuickSort(A as array, low as int, high as int){
    if (low < high){
        pivot_location = Partition(A,low,high)
        Quicksort(A,low, pivot_location)
        Quicksort(A, pivot_location + 1, high)
    }
}
Partition(A as array, low as int, high as int){
     pivot = A[low]
     left = low
 
     for i = low + 1 to high{
         if (A[i] < pivot) then{
             swap(A[i], A[left + 1])
             left = left + 1
         }
     }
     swap(pivot,A[left])
 
    return (left)}

The complexity of quicksort in the average case is Θ(n log(n)) and in the worst case is Θ(n2).

Merge Sort in Java

Mergesort is a fast, recursive, stable sort algorithm which also works by the divide and conquer principle. Similar to quicksort, merge sort divides the list of elements into two lists. These lists are sorted independently and then combined. During the combination of the lists, the elements are inserted (or merged) at the right place in the list

Here’s pseudocode representing Merge Sort Algorithm

procedure MergeSort( a as array )
   if ( n == 1 ) return a
 
   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]
 
   l1 = mergesort( l1 )
   l2 = mergesort( l2 )
 
   return merge( l1, l2 )
end procedure
 
procedure merge( a as array, b as array )
 
   var c as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while
    
   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while
    
   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while
    
   return c
     
end procedure

Searching Algorithms in Java

Searching is one of the most common and frequently performed actions in regular business applications. Search algorithms are algorithms for finding an item with specified properties among a collection of items. Let’s explore two of the most commonly used searching algorithms.

Linear Search Algorithm in Java

Linear search or sequential search is the simplest search algorithm. It involves sequential searching for an element in the given data structure until either the element is found or the end of the structure is reached. If the element is found, then the location of the item is returned otherwise the algorithm returns NULL.

Here’s pseudocode representing Linear Search in Java:

procedure linear_search (a[] , value)
for i = 0 to n-1
   if a[i] = value then
      print "Found "
      return i
   end if
print "Not found"
end for
 
end linear_search

It is a brute-force algorithm. While it certainly is the simplest, it’s most definitely is not the most common, due to its inefficiency. Time Complexity of Linear search is O(N).

Binary Search Algorithm in Java

Binary search, also known as logarithmic search, is a search algorithm that finds the position of a target value within an already sorted array. It divides the input collection into equal halves and the item is compared with the middle element of the list. If the element is found, the search ends there. Else, we continue looking for the element by dividing and selecting the appropriate partition of the array, based on if the target element is smaller or bigger than the middle element.

Here’s pseudocode representing Binary Search in Java:

Procedure binary_search
   a; sorted array
   n; size of array
   x; value to be searched
 
    lowerBound = 1
    upperBound = n 
 
   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.
    
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
       
      if A[midPoint] < x set lowerBound = midPoint + 1 if A[midPoint] > x
         set upperBound = midPoint - 1
 
      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
    
end procedure

Binary Search Time Complexity

In each iteration, the search space is getting divided by 2. That means that in the current iteration you have to deal with half of the previous iteration array.

Best case could be the case where the first mid-value get matched to the element to be searched

Best Time Complexity: O(1)

Average Time Complexity: O(logn)

Worst Time Complexity: O(logn)

Since we are not using any space so space complexity will be O(1)

This brings us to the end of this ‘Data Structures and Algorithms in Java’ article. We have covered one of the most fundamental and important topics of Java. Hope you are clear with all that has been shared with you in this article.

Make sure you practice as much as possible.


Data Structures And Algorithms in Python

The knowledge of Data Structures and Algorithms forms the basis for identifying programmers, giving yet another reason for tech enthusiasts to get upscaled. While data structures help in the organization of data, algorithms help find solutions to the unending data analysis problems.

So, if you are still unaware of Data Structures and Algorithms in Python, here is a detailed article that will help you understand and implement them.

Before moving on, take a look at all the topics discussed in over here:

Introduction to Data Structures And Algorithms in Python
- Built in Data Structures
- User defined Data Structures
Algorithms in Python
- What are Algorithms?
- Elements of a Good Algorithms
- Sorting Algorithms
- Searching Algorithms

Introduction to Data Structures And Algorithms in Python

In-built Data Structures:

Introduction To Data Structures And Algorithms In Python

Lists: This is the most versatile data structure in Python and is written as a list of comma-separated elements enclosed within square brackets. A List can consist of both heterogeneous and homogeneous elements. Some of the methods applicable on a List are index(), append(), extend(), insert(), remove(), pop(), etc. Lists are mutable; that is, their content can be changed, keeping the identity intact.

Tuples: Tuples are similar to Lists but are immutable. Also, unlike Lists, Tuples are declared within parentheses instead of square brackets. The feature of immutability denotes that once an element has been defined in a Tuple, it cannot be deleted, reassigned or edited. It ensures that the declared values of the data structure are not manipulated or overridden.

Dictionaries: Dictionaries consist of key-value pairs. The ‘key’ identifies an item, and the ‘value’ stores the value of the item. A colon separates the key from its value. The items are separated by commas, with the entire thing enclosed within curly brackets. While keys are immutable (numbers, Strings or Tuples), the values can be of any type.

Sets: Sets are an unordered collection of unique elements. Like Lists, Sets are mutable and written within square brackets, but no two values can be the same. Some Set methods include count(), index(), any(), all(), etc.

User-defined Data-structures And Algorithms in Python:

Linear Data Structures

Linear data structures in python are those whose elements are in sequential and in ordered way. For example: Linked list, Stack, Queue

Linked List

What is Linked list in Data Structures And Algorithms in Python

A linked list is a linear data structure with the collection of multiple nodes, where each element stores its own data and a pointer to the location of the next element. The last link of linked List points to null.

An element in Linked List is called node. The first node is called head. The last node is called tail.

Difference between array and linked list in Data Structures And Algorithms in Python

Types of Linked List

Singly Linked List (Uni-directional)

The singly linked list is a linear data structure in which each element of the list contains a pointer which points to the next element in the list. Each node has two components: data and a pointer next which point to the next node in the list.

# Node class
class Node:

  # Function to initialize the node object
  def __init__(self, data):
    self.data = data # Assign data
    self.next = None # Initialize
            # next as null

# Linked List class
class LinkedList:
  
  # Function to initialize the Linked
  # List object
  def __init__(self):
    self.head = None

Doubly Linked List (Bi-Directional)

Doubly Linked List is just same as singly Linked List except it contains an extra pointer, typically called previous pointer, together with next pointer and data.

# Node of a doubly linked list
class Node:
  def __init__(self, next=None, prev=None, data=None):
    self.next = next # reference to next node in DLL
    self.prev = prev # reference to previous node in DLL
    self.data = data

Advantages over singly linked list

A DLL can be traversed in both forward and backward direction.
The delete operation in DLL is more efficient if pointer to the node to be deleted is given.

Circular Linked List

A circular linked list is a variation of a linked list in which the last node points to the first node, completing a full circle of nodes. You can say it doesn’t have null element at the end.

Application of Circular Linked List

The real life application where the circular linked list is used is our Personal Computers, where multiple applications are running. All the running applications are kept in a circular linked list and the OS gives a fixed time slot to all for running. The Operating System keeps on iterating over the linked list until all the applications are completed.
Another example can be Multiplayer games. All the Players are kept in a Circular Linked List and the pointer keeps on moving forward as a player's chance ends.
Circular Linked List can also be used to create Circular Queue. In a Queue we have to keep two pointers, FRONT and REAR in memory all the time, where as in Circular Linked List, only one pointer is required.

Stacks

What is Stack?

Stack, an abstract data structure, is a collection of objects that are inserted and removed according to the last-in-first-out (LIFO) principle. Objects can be inserted into a stack at any point of time, but only the most recently inserted (that is, “last”) object can be removed at any time.

Listed below are properties of a stack:

It is an orderd list in which insertion and deletion can be performed only at one end that is called the top.
Recursive data structure with a pointer to its top element.
Follows the last-in-first-out (LIFO) principle
Stack Concepts

Stack Concepts in Data Structures And Algorithms In Python

When an element is inserted in a stack, the concept is called a push.
When an element is removed from the stack, the concept is called pop.
Trying to pop out an empty stack is called underflow (treat as Exception).
Trying to push an element in a full stack is called overflow (treat as Exception).
Applications of Stack

Applications of Stack in Data Structures And Algorithms In Python

Following are some of the applications in which stacks play an important role.

Balancing of symbols
Page-visited history in a Web browser [Back Buttons]
Undo sequence in a text editor
Finding of spans (finding spans in stock markets)
Stack Implementation using List
Push Operation
Write a class called Stack.
We have to maintain the data in a list. Let’s add an empty list in the Stack class with name elements.
To push the elements into the stack, we need a method. Let’s write a push method that takes data as an argument and append it to the elements list.
class Stack:
  def __init__(self):
    self.elements = []

  def push(self, data):
    self.elements.append(data)
    return data

Pop Operation
Similarly, let’s write the pop method that pops out the topmost element from the stack. We can use the pop method of the list data type.
class Stack:
  ## ...
  def pop(self):
    return self.elements.pop()

Complexity Analysis

Let n be the number of elements in the stack. The complexities of stack operations with this representation can be given as:

Time Complexity of push() O(1)
Time Complexity of pop() O(1)
Space Complexity O(n)

Queues

Queue in Data Structures And Algorithms In Python

Queues are also another type of abstract data structure. Unlike a stack, the queue is a collection of objects that are inserted and removed according to the first-in-first-out (FIFO) principle.

Listed below are properties of a queue:

Often referred to as the first-in-first-out list
Supports two most fundamental methods enqueue(e): Insert element e, at the rear of the queue dequeue(): Remove and return the element from the front of the queue
Queue Concepts

Queue Concepts in Data Structures And Algorithms In Python

When an element is inserted in a queue, the concept is called EnQueue.
When an element is removed from the queue, the concept is called DeQueue.
DeQueueing an empty queue is called underflow (treat as Exception)
EnQueuing an element in a full queue is called overflow (treat as Exception).
Applications of Queue
Operating systems schedule jobs (with equal priority) in the order of arrival (e.g., a print queue).
Simulation of real-world queues such as lines at a ticket counter, or any other first come the first-served scenario requires a queue.
Multiprogramming. Asynchronous data transfer (file IO, pipes, sockets).
Implementation of Circular Queue using Linked List

Circular Queue Concepts in Data Structures And Algorithms In Python

Operations on Circular Queue:

For enQueue

Create a new node dynamically and insert value into it
Check if front==NULL, if it is true then front = rear = (newly created node)
If it is false then rear=(newly created node) and rear node always contains the address of the front node.

For Dequeue

Check whether queue is empty or not means front == NULL.
If it is empty then display Queue is empty. If queue is not empty then step 3
Check if (front==rear) if it is true then set front = rear = NULL else move the front forward in queue, update address of front in rear node and return the element.

Below is the code implementation in Python

# Python3 program for insertion and
# deletion in Circular Queue

# Structure of a Node
class Node:
  def __init__(self):
    self.data = None
    self.link = None

class Queue:
  def __init__(self):
    front = None
    rear = None

# Function to create Circular queue
def enQueue(q, value):
  temp = Node()
  temp.data = value
  if (q.front == None):
    q.front = temp
  else:
    q.rear.link = temp

  q.rear = temp
  q.rear.link = q.front

# Function to delete element from
# Circular Queue
def deQueue(q):
  if (q.front == None):
    print("Queue is empty")
    return -999999999999

  # If this is the last node to be deleted
  value = None # Value to be dequeued
  if (q.front == q.rear):
    value = q.front.data
    q.front = None
    q.rear = None
  else: # There are more than one nodes
    temp = q.front
    value = temp.data
    q.front = q.front.link
    q.rear.link = q.front

  return value

# Function displaying the elements
# of Circular Queue
def displayQueue(q):
  temp = q.front
        print("Elements in Queue are:end="")
            
  while (temp.link != q.front):
    print(temp.data,end = " ")
    temp = temp.link
  print(temp.data)

# Driver Code
if __name__ == '__main__':

  # Create a queue and initialize
  # front and rear
  q = Queue()
  q.front = q.rear = None

  # Inserting elements in Circular Queue
  enQueue(q, 14)
  enQueue(q, 22)
  enQueue(q, 6)

  # Display elements present in
  # Circular Queue
  displayQueue(q)

  # Deleting elements from Circular Queue
  print("Deleted value = ", deQueue(q))
  print("Deleted value = ", deQueue(q))

  # Remaining elements in Circular Queue
  displayQueue(q)

  enQueue(q, 9)
  enQueue(q, 20)
  displayQueue(q)

Implementation of Circular Queue using Linked List in Data Structures And Algorithms In Python

Hierarchical Data Structures And Algorithms in Python

Binary Tree

Hierarchical Data Structures And Algorithms In Python

Binary Tree is a hierarchical tree data structures in which each node has at most two children, which are referred to as the left child and the right child. Each binary tree has the following groups of nodes:

Root Node: It is the topmost node and often referred to as the main node because all other nodes can be reached from the root

Left Sub-Tree, which is also a binary tree

Right Sub-Tree, which is also a binary tree

Binary Tree: Common Terminologies

Root:Topmost node in a tree.

Parent:Every node (excluding a root) in a tree is connected by a directed edge from exactly one other node. This node is called a parent.

Child:A node directly connected to another node when moving away from the root

Leaf/External node:Node with no children.

Internal node:Node with atleast one children.

Depth of a node:Number of edges from root to the node.

Height of a node:Number of edges from the node to the deepest leaf. Height of the tree is the height of the root

Listed below are the properties of a binary tree:

A binary tree can be traversed in two ways:

Depth First Traversal: In-order (Left-Root-Right), Preorder (Root-Left-Right) and Postorder (Left-Right-Root)

Breadth First Traversal: Level Order Traversal

Time Complexity of Tree Traversal: O(n)

The maximum number of nodes at level "n" = 2(n-1).

The maximum number of nodes of Binary Tree of height "h" = 2(h).

Below is the image which gives better visualization that how maximum number of nodes of Binary tree is 2(h)

how maximum number of nodes of Binary tree in Data Structures And Algorithms In Python

Applications of binary trees include:
Used in many search applications where data is constantly entering/leaving
Used in almost every high-bandwidth router for storing router-tables
Used in compression algorithms and many more

Graph

What is graph (data structure)?

A graph is a common data structure that consists of a finite set of nodes (or vertices) and a set of edges connecting them.

A pair (x,y) is referred to as an edge, which communicates that the x vertex connects to the y vertex.

Graphs are used to solve real-life problems that involve representation of the problem space as a network. Examples of networks include telephone networks, circuit networks, social networks (like LinkedIn, Facebook etc.).

Types of graphs:

Undirected Graph:

In an undirected graph, nodes are connected by edges that are all bidirectional. For example if an edge connects node 1 and 2, we can traverse from node 1 to node 2, and from node 2 to 1.

Directed Graph:

In a directed graph, nodes are connected by directed edges – they only go in one direction. For example, if an edge connects node 1 and 2, but the arrow head points towards 2, we can only traverse from node 1 to node 2 – not in the opposite direction.

Types of Graph Representations:

Adjacency List

To create an Adjacency list, an array of lists is used. The size of the array is equal to the number of nodes. A single index, array[i] represents the list of nodes adjacent to the ith node.

For example, we have given below.

Adjacency List in Data Structures And Algorithms In Python

There is a reason Python gets so much love. A simple dictionary of vertices and its edges is a sufficient representation of a graph. You can make the vertex itself as complex as you want.

graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

Adjacency Matrix

An Adjacency Matrix is a 2D array of size V x V where V is the number of nodes in a graph. A slot matrix[i][j] = 1 indicates that there is an edge from node i to node j.

For example, we have given below.

Adjacency Matrix representation in Data Structures And Algorithms In Python

Here is the implementation part in Python.

# Adjacency Matrix representation in Python


class Graph(object):

    # Initialize the matrix
    def __init__(self, size):
        self.adjMatrix = []
        for i in range(size):
            self.adjMatrix.append([0 for i in range(size)])
        self.size = size

    # Add edges
    def add_edge(self, v1, v2):
        if v1 == v2:
            print("Same vertex %d and %d" % (v1, v2))
        self.adjMatrix[v1][v2] = 1
        self.adjMatrix[v2][v1] = 1
def main():
    g = Graph(5)
    g.add_edge(0, 1)
    g.add_edge(0, 2)
    g.add_edge(1, 2)
    g.add_edge(2, 0)
    g.add_edge(2, 3)

    g.print_matrix()


if __name__ == '__main__':
    main()

Algorithms:

Python algorithms are a set of instructions that are executed to get the solution to a given problem. Since algorithms are not language-specific, they can be implemented in several programming languages. No standard rules guide the writing of algorithms.

Elements of a Good Algorithm:

The steps need to be finite, clear and understandable
There should be a clear and precise description of inputs and outputs
Each step need to have a defined output that depends only on inputs in that step or the preceding steps
The algorithm should be flexible enough to mold it in order to allow a number of solutions
The steps should make use of general programming fundamentals and should not be language-specific

Let’s explore the two major categories of algorithms in Python, which are:

Sorting Algorithms in Python

Sorting algorithms are algorithms that put elements of a list in a certain order. The most commonly used orders are numerical order and lexicographical order.

Let's dive into some famous sorting algorithms.

Bubble Sort

Bubble Sort is a simple algorithm which is used to sort a given set of n elements provided in form of an array with n number of elements. Bubble Sort compares all the element one by one and sort them based on their values.

It is known as bubble sort, because with every complete iteration the largest element in the given array, bubbles up towards the last place or the highest index, just like a water bubble rises up to the water surface.

Bubble Sort in Data Structures And Algorithms In Python

Here’s pseudocode representing Bubble Sort Algorithm (ascending sort context).

a[] is an array of size N
begin BubbleSort(a[])
 
declare integer i, j
for i = 0 to N - 1
   for j = 0 to N - i - 1
      if a[j] > a[j+1] then 
         swap a[j], a[j+1]
      end if
   end for
  return a
   
end BubbleSort

Worst and Average Case Time Complexity: O(n*n) (The worst-case occurs when an array is reverse sorted).

Best Case Time Complexity:O(n) (Best case occurs when an array is already sorted).

Selection Sort

Selection sorting is a combination of both searching and sorting. The algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from the unsorted part and putting it at a proper position in the array.

Selection Sort in Data Structures And Algorithms In Python

Here’s pseudocode representing Selection Sort Algorithm (ascending sort context).

a[] is an array of size N
begin SelectionSort(a[])
 
 for i = 0 to n - 1
   /* set current element as minimum*/
      min = i    
      /* find the minimum element */
       for j = i+1 to n 
         if list[j] < list[min] then
            min = j;
         end if
      end for
  /* swap the minimum element with the current element*/
      if min != i  then
         swap list[min], list[i]
      end if
   end for
     
end SelectionSort

Time Complexity: O(n2) as there are two nested loops.

Auxiliary Space: O(1).

Insertion Sort

Insertion Sort is a simple sorting algorithm which iterates through the list by consuming one input element at a time and builds the final sorted array. It is very simple and more effective on smaller data sets. It is stable and in-place sorting technique.

Insertion Sort in Data Structures And Algorithms In Python

Here’s pseudocode representing Insertion Sort Algorithm (ascending sort context).

a[] is an array of size N
begin InsertionSort(a[])
 
for i = 1 to N
   key = a[ i ]
   j = i - 1
   while ( j >= 0 and a[ j ] > key0
      a[ j+1 ] = x[ j ]
      j = j - 1
   end while
   a[ j+1 ] = key
end for
 
end InsertionSort

Best Case: The best case is when input is an array that is already sorted. In this case insertion sort has a linear running time (i.e., Θ(n)).

Worst Case: The simplest worst case input is an array sorted in reverse order

QuickSort

Quicksort algorithm is a fast, recursive, non-stable sort algorithm which works by the divide and conquer principle. It picks an element as pivot and partitions the given array around that picked pivot.

QuickSort in Data Structures And Algorithms In Python Steps to implement Quick sort

Pick a suitable “pivot point”.
Divide the lists into two lists based on this pivot element. Every element which is smaller than the pivot element is placed in the left list and every element which is larger is placed in the right list. If an element is equal to the pivot element then it can go in any list. This is called the partition operation.
Recursively sort each of the smaller lists.

Here’s pseudocode representing Quicksort Algorithm.

QuickSort(A as array, low as int, high as int){
    if (low < high){
        pivot_location = Partition(A,low,high)
        Quicksort(A,low, pivot_location)
        Quicksort(A, pivot_location + 1, high)
    }
}
Partition(A as array, low as int, high as int){
     pivot = A[low]
     left = low
 
     for i = low + 1 to high{
         if (A[i] < pivot) then{
             swap(A[i], A[left + 1])
             left = left + 1
         }
     }
     swap(pivot,A[left])
 
    return (left)}

The complexity of quicksort in the average case is Θ(n log(n)) and in the worst case is Θ(n2).

Merge Sort

Mergesort is a fast, recursive, stable sort algorithm which also works by the divide and conquer principle. Similar to quicksort, merge sort divides the list of elements into two lists. These lists are sorted independently and then combined. During the combination of the lists, the elements are inserted (or merged) at the right place in the list

Here’s pseudocode representing Merge Sort Algorithm

procedure MergeSort( a as array )
   if ( n == 1 ) return a
 
   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]
 
   l1 = mergesort( l1 )
   l2 = mergesort( l2 )
 
   return merge( l1, l2 )
end procedure
 
procedure merge( a as array, b as array )
 
   var c as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while
    
   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while
    
   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while
    
   return c
     
end procedure

Searching Algorithms in Python

Searching is one of the most common and frequently performed actions in regular business applications. Search algorithms are algorithms for finding an item with specified properties among a collection of items. Let’s explore two of the most commonly used searching algorithms.

Linear Search Algorithm

Linear search or sequential search is the simplest search algorithm. It involves sequential searching for an element in the given data structure until either the element is found or the end of the structure is reached. If the element is found, then the location of the item is returned otherwise the algorithm returns NULL.

Here’s pseudocode representing Linear Search in Python:

procedure linear_search (a[] , value)
for i = 0 to n-1
   if a[i] = value then
      print "Found "
      return i
   end if
print "Not found"
end for
 
end linear_search

It is a brute-force algorithm. While it certainly is the simplest, it’s most definitely is not the most common, due to its inefficiency. Time Complexity of Linear search is O(N).

Binary Search Algorithm

Binary search, also known as logarithmic search, is a search algorithm that finds the position of a target value within an already sorted array. It divides the input collection into equal halves and the item is compared with the middle element of the list. If the element is found, the search ends there. Else, we continue looking for the element by dividing and selecting the appropriate partition of the array, based on if the target element is smaller or bigger than the middle element.

Here’s pseudocode representing Binary Search in Python:

Procedure binary_search
   a; sorted array
   n; size of array
   x; value to be searched
 
    lowerBound = 1
    upperBound = n 
 
   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.
    
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
       
      if A[midPoint] < x set lowerBound = midPoint + 1 if A[midPoint] > x
         set upperBound = midPoint - 1
 
      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
    
end procedure

Binary Search Time Complexity

In each iteration, the search space is getting divided by 2. That means that in the current iteration you have to deal with half of the previous iteration array.

Best case could be the case where the first mid-value get matched to the element to be searched

Best Time Complexity: O(1)

Average Time Complexity: O(logn)

Worst Time Complexity: O(logn)

Since we are not using any space so space complexity will be O(1)

This brings us to the end of this ‘Data Structures and Algorithms in Python’ article. We have covered one of the most fundamental and important topics of Python. Hope you are clear with all that has been shared with you in this article.

Make sure you practice as much as possible.


Data Structures and Algorithms in C++

Knowing some fundamental data structures and algorithms both in theory and from a practical implementation perspective helps you in being a better C++ programmer, gives you a good foundation to understand standard library’s containers and algorithms inner “under the hood” mechanics, and serves as a kind of knowledge that is required in several coding interviews, as well.

In this article, Data Structures and Algorithms in C++, you’ll learn how to implement some fundamental data structures and algorithms in C++ from scratch, with a combination of theoretical introduction using animation, and practical C++ implementation code as well.

Before moving on, take a look at all the topics discussed in over here:

Introduction to Data Structures in C++
- Linear Data Structures
- Hierarchical Data Structures
- Algorithms in C++
- What are Algorithms?
- Elements of a Good Algorithms
- Sorting Algorithms
- Searching Algorithms

Introduction to Data Structures in C++

Data Structure is a way of collecting and organising data in such a way that we can perform operations on these data in an effective way. Data Structures is about rendering data elements in terms of some relationship, for better organization and storage. Let’s say We have some data which has, student’s name “Shivam” and his age 13. Here Shivam is of String data type and 13 is of integer data type.

In simple language, Data Structures are structures programmed to store ordered data, so that various operations can be performed on it easily. It represents the knowledge of data to be organized in memory. It should be designed and implemented in such a way that it reduces the complexity and increases the efficiency.

Linear Data Structures In C++

Linear data structures in C++ are those whose elements are in sequential and in ordered way. For example: Array, Linked list, etc

Arrays

An array is a linear data structure representing a group of similar elements, accessed by index. However, one shall not confuse array with the list like data structures in languages like python. Let us see arrays are presented in C++;

// simple declaration
int array[] = {1, 2, 3, 4, 5 };
// in pointer form (refers to an object stored in heap)
int * array = new int[5]; 

Note: However, we are accustomed to the more friendly vector data structure to which we can push without worrying about the size(i.e Dynamic Array).

Linked List

What is linked list in Data Structures And Algorithms In C++

A linked list is a linear data structure with the collection of multiple nodes, where each element stores its own data and a pointer to the location of the next element. The last link of linked List points to null.

An element in Linked List is called node. The first node is called head. The last node is called tail.

Difference between array and linked list in Data Structures And Algorithms In C++

Types of Linked List

Singly Linked List (Uni-directional)

The singly linked list is a linear data structure in which each element of the list contains a pointer which points to the next element in the list. Each node has two components: data and a pointer next which point to the next node in the list.

Singly Linked List in Data Structures And Algorithms In C++

class Node {
public:
  int data;
  Node* next;
};

Doubly Linked List (Bi-Directional)

Doubly Linked List is just same as singly Linked List except it contains an extra pointer, typically called previous pointer, together with next pointer and data.

Doubly Linked List in Data Structures And Algorithms In C++

/* Node of a doubly linked list */
class Node
{
  public:
  int data;
  Node* next; // Pointer to next node in DLL
  Node* prev; // Pointer to previous node in DLL
};

Advantages over singly linked list

A DLL can be traversed in both forward and backward direction.
The delete operation in DLL is more efficient if pointer to the node to be deleted is given.

Circular Linked List

A circular linked list is a variation of a linked list in which the last node points to the first node, completing a full circle of nodes. You can say it doesn’t have null element at the end.

Application of Circular Linked List

The real life application where the circular linked list is used is our Personal Computers, where multiple applications are running. All the running applications are kept in a circular linked list and the OS gives a fixed time slot to all for running. The Operating System keeps on iterating over the linked list until all the applications are completed.
Another example can be Multiplayer games. All the Players are kept in a Circular Linked List and the pointer keeps on moving forward as a player's chance ends.
Circular Linked List can also be used to create Circular Queue. In a Queue we have to keep two pointers, FRONT and REAR in memory all the time, where as in Circular Linked List, only one pointer is required.

Stacks

What is Stack?

Stack, an abstract data structure, is a collection of objects that are inserted and removed according to the last-in-first-out (LIFO) principle. Objects can be inserted into a stack at any point of time, but only the most recently inserted (that is, “last”) object can be removed at any time.

Listed below are properties of a stack:

It is an orderd list in which insertion and deletion can be performed only at one end that is called the top.
Recursive data structure with a pointer to its top element.
Follows the last-in-first-out (LIFO) principle
Stack Concepts

Stack Concepts in Data Structures And Algorithms In C++

When an element is inserted in a stack, the concept is called a push.
When an element is removed from the stack, the concept is called pop.
Trying to pop out an empty stack is called underflow (treat as Exception).
Trying to push an element in a full stack is called overflow (treat as Exception).
Applications of Stack

Applications of Stack in Data Structures And Algorithms In C++

Following are some of the applications in which stacks play an important role.

Balancing of symbols
Page-visited history in a Web browser [Back Buttons]
Undo sequence in a text editor
Finding of spans (finding spans in stock markets)
Stack Implementation using Array
Push Operation
In a push operation, we add an element into the top of the stack.
Increment the variable Top so that it can now refer to the next memory location.
Add an element at the position of the incremented top.
This is referred to as adding a new element at the top of the stack.
Throw an exception if Stack is full.
void push(int val) {
   if(top>=n-1)
   cout<<"Stack Overflow"<<endl;
   else {
      top++;
      stack[top]=val;
   }
}

Pop Operation
Remove the top element from the stack and decrease the size of a top by 1.
Throw an exception if Stack is empty.
void pop() {
   if(top<=-1)
   cout<<"Stack Underflow"<<endl;
   else {
      cout<<"The popped element is "<< stack[top] <<endl;
      top--;
   }
}

Complexity Analysis

Let n be the number of elements in the stack. The complexities of stack operations with this representation can be given as:

Time Complexity of push() O(1)
Time Complexity of pop() O(1)
Space Complexity O(n)

Queues

Queues in Data Structures And Algorithms In C++

Queues are also another type of abstract data structure. Unlike a stack, the queue is a collection of objects that are inserted and removed according to the first-in-first-out (FIFO) principle.

Listed below are properties of a queue:

Often referred to as the first-in-first-out list
Supports two most fundamental methods enqueue(e): Insert element e, at the rear of the queue dequeue(): Remove and return the element from the front of the queue
Queue Concepts

Queue Concepts in Data Structures And Algorithms In C++

When an element is inserted in a queue, the concept is called EnQueue.
When an element is removed from the queue, the concept is called DeQueue.
DeQueueing an empty queue is called underflow (treat as Exception)
EnQueuing an element in a full queue is called overflow (treat as Exception).
Applications of Queue
Operating systems schedule jobs (with equal priority) in the order of arrival (e.g., a print queue).
Simulation of real-world queues such as lines at a ticket counter, or any other first come the first-served scenario requires a queue.
Multiprogramming. Asynchronous data transfer (file IO, pipes, sockets).
Implementation of Circular Queue using Linked List

Circular Queue Concepts in Data Structures And Algorithms In C++

Operations on Circular Queue:

For enQueue

Create a new node dynamically and insert value into it
Check if front==NULL, if it is true then front = rear = (newly created node)
If it is false then rear=(newly created node) and rear node always contains the address of the front node.

For Dequeue

Check whether queue is empty or not means front == NULL.
If it is empty then display Queue is empty. If queue is not empty then step 3
Check if (front==rear) if it is true then set front = rear = NULL else move the front forward in queue, update address of front in rear node and return the element.

Below is the code implementation in C++

// C++ program for insertion and
// deletion in Circular Queue
#include <bits/stdc++.h>
using namespace std;

// Structure of a Node
struct Node {
  int data;
  struct Node* link;
};

struct Queue {
  struct Node *front, *rear;
};

// Function to create Circular queue
void enQueue(Queue* q, int value)
{
  struct Node* temp = new Node;
  temp->data = value;
  if (q->front == NULL)
    q->front = temp;
  else
    q->rear->link = temp;

  q->rear = temp;
  q->rear->link = q->front;
}

// Function to delete element from Circular Queue
int deQueue(Queue* q)
{
  if (q->front == NULL) {
    printf("Queue is empty");
    return INT_MIN;
  }

  // If this is the last node to be deleted
  int value; // Value to be dequeued
  if (q->front == q->rear) {
    value = q->front->data;
    free(q->front);
    q->front = NULL;
    q->rear = NULL;
  }
  else // There are more than one nodes
  {
    struct Node* temp = q->front;
    value = temp->data;
    q->front = q->front->link;
    q->rear->link = q->front;
    free(temp);
  }

  return value;
}

// Function displaying the elements of Circular Queue
void displayQueue(struct Queue* q)
{
  struct Node* temp = q->front;
  printf("\nElements in Circular Queue are: ");
  while (temp->link != q->front) {
    printf("%d ", temp->data);
    temp = temp->link;
  }
  printf("%d", temp->data);
}

/* Driver of the program */
int main()
{
  // Create a queue and initialize front and rear
  Queue* q = new Queue;
  q->front = q->rear = NULL;

  // Inserting elements in Circular Queue
  enQueue(q, 14);
  enQueue(q, 22);
  enQueue(q, 6);

  // Display elements present in Circular Queue
  displayQueue(q);

  // Deleting elements from Circular Queue
  printf("\nDeleted value = %d", deQueue(q));
  printf("\nDeleted value = %d", deQueue(q));

  // Remaining elements in Circular Queue
  displayQueue(q);

  enQueue(q, 9);
  enQueue(q, 20);
  displayQueue(q);

  return 0;
}

Implementation of Circular Queue using Linked List in Data Structures And Algorithms In C++

Hierarchical Data Structures in C++

Binary Tree

Binary Tree in Data Structures And Algorithms In C++

Binary Tree is a hierarchical tree data structures in which each node has at most two children, which are referred to as the left child and the right child. Each binary tree has the following groups of nodes:

Root Node: It is the topmost node and often referred to as the main node because all other nodes can be reached from the root

Left Sub-Tree, which is also a binary tree

Right Sub-Tree, which is also a binary tree

Binary Tree: Common Terminologies

Root:Topmost node in a tree.

Parent:Every node (excluding a root) in a tree is connected by a directed edge from exactly one other node. This node is called a parent.

Child:A node directly connected to another node when moving away from the root

Leaf/External node:Node with no children.

Internal node:Node with atleast one children.

Depth of a node:Number of edges from root to the node.

Height of a node:Number of edges from the node to the deepest leaf. Height of the tree is the height of the root

Listed below are the properties of a binary tree:

A binary tree can be traversed in two ways:

Depth First Traversal: In-order (Left-Root-Right), Preorder (Root-Left-Right) and Postorder (Left-Right-Root)

Breadth First Traversal: Level Order Traversal

Time Complexity of Tree Traversal: O(n)

The maximum number of nodes at level "n" = 2(n-1).

The maximum number of nodes of Binary Tree of height "h" = 2(h).

Below is the image which gives better visualization that how maximum number of nodes of Binary tree is 2(h)

how maximum number of nodes of Binary tree in Data Structures And Algorithms In C++

Applications of binary trees include:
Used in many search applications where data is constantly entering/leaving
Used in almost every high-bandwidth router for storing router-tables
Used in compression algorithms and many more

Graph

What is graph (data structure)?

A graph is a common data structure that consists of a finite set of nodes (or vertices) and a set of edges connecting them.

A pair (x,y) is referred to as an edge, which communicates that the x vertex connects to the y vertex.

Graphs are used to solve real-life problems that involve representation of the problem space as a network. Examples of networks include telephone networks, circuit networks, social networks (like LinkedIn, Facebook etc.).

Types of graphs:

Undirected Graph:

Undirected Graph in Data Structures And Algorithms In C++

In an undirected graph, nodes are connected by edges that are all bidirectional. For example if an edge connects node 1 and 2, we can traverse from node 1 to node 2, and from node 2 to 1.

Directed Graph:

Directed Graph in Data Structures And Algorithms In C++

In a directed graph, nodes are connected by directed edges – they only go in one direction. For example, if an edge connects node 1 and 2, but the arrow head points towards 2, we can only traverse from node 1 to node 2 – not in the opposite direction.

Types of Graph Representations:

Adjacency List

To create an Adjacency list, an array of lists is used. The size of the array is equal to the number of nodes. A single index, array[i] represents the list of nodes adjacent to the ith node.

For example, we have given below.

Adjacency List in Data Structures And Algorithms In C++

class Graph{
    int numVertices;
    list<int> *adjLists;
    
  public:
    Graph(int V);
    void addEdge(int src, int dest);
};

Adjacency Matrix

An Adjacency Matrix is a 2D array of size V x V where V is the number of nodes in a graph. A slot matrix[i][j] = 1 indicates that there is an edge from node i to node j.

For example, we have given below.

Adjacency Matrix in Data Structures And Algorithms In C++

Here is the implementation part in C++.

#include<iostream>
using namespace std;
int vertArr[20][20]; //the adjacency matrix initially 0
int count = 0;
void displayMatrix(int v) {
   int i, j;
   for(i = 0; i < v; i++) {
      for(j = 0; j < v; j++) {
         cout << vertArr[i][j] << " ";
      }
      cout << endl;
   }
}
void add_edge(int u, int v) {       //function to add edge into the matrix
   vertArr[u][v] = 1;
   vertArr[v][u] = 1;
}
main(int argc, char* argv[]) {
   int v = 6;    //there are 6 vertices in the graph
   add_edge(0, 4);
   add_edge(0, 3);
   add_edge(1, 2);
   add_edge(1, 4);
   displayMatrix(v);
}

Algorithms:

Algorithms are a set of instructions that are executed to get the solution to a given problem. Since algorithms are not language-specific, they can be implemented in several programming languages. No standard rules guide the writing of algorithms.

Elements of a Good Algorithm:

The steps need to be finite, clear and understandable
There should be a clear and precise description of inputs and outputs
Each step need to have a defined output that depends only on inputs in that step or the preceding steps
The algorithm should be flexible enough to mold it in order to allow a number of solutions
The steps should make use of general programming fundamentals and should not be language-specific

Let’s explore the two major categories of algorithms in C++, which are:

Sorting Algorithms in C++

Sorting algorithms are algorithms that put elements of a list in a certain order. The most commonly used orders are numerical order and lexicographical order.

Let's dive into some famous sorting algorithms.

Bubble Sort

Bubble Sort is a simple algorithm which is used to sort a given set of n elements provided in form of an array with n number of elements. Bubble Sort compares all the element one by one and sort them based on their values.

It is known as bubble sort, because with every complete iteration the largest element in the given array, bubbles up towards the last place or the highest index, just like a water bubble rises up to the water surface.

Bubble Sort in Data Structures And Algorithms In C++

Here’s pseudocode representing Bubble Sort Algorithm (ascending sort context).

a[] is an array of size N
begin BubbleSort(a[])
 
declare integer i, j
for i = 0 to N - 1
   for j = 0 to N - i - 1
      if a[j] > a[j+1] then 
         swap a[j], a[j+1]
      end if
   end for
  return a
   
end BubbleSort

Worst and Average Case Time Complexity: O(n*n) (The worst-case occurs when an array is reverse sorted).

Best Case Time Complexity:O(n) (Best case occurs when an array is already sorted).

Selection Sort

Selection sorting is a combination of both searching and sorting. The algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from the unsorted part and putting it at a proper position in the array.

Selection Sort in Data Structures And Algorithms In C++

Here’s pseudocode representing Selection Sort Algorithm (ascending sort context).

a[] is an array of size N
begin SelectionSort(a[])
 
 for i = 0 to n - 1
   /* set current element as minimum*/
      min = i    
      /* find the minimum element */
       for j = i+1 to n 
         if list[j] < list[min] then
            min = j;
         end if
      end for
  /* swap the minimum element with the current element*/
      if min != i  then
         swap list[min], list[i]
      end if
   end for
     
end SelectionSort

Time Complexity: O(n2) as there are two nested loops.

Auxiliary Space: O(1).

Insertion Sort

Insertion Sort is a simple sorting algorithm which iterates through the list by consuming one input element at a time and builds the final sorted array. It is very simple and more effective on smaller data sets. It is stable and in-place sorting technique.

Insertion Sort in Data Structures And Algorithms In C++

Here’s pseudocode representing Insertion Sort Algorithm (ascending sort context).

a[] is an array of size N
begin InsertionSort(a[])
 
for i = 1 to N
   key = a[ i ]
   j = i - 1
   while ( j >= 0 and a[ j ] > key0
      a[ j+1 ] = x[ j ]
      j = j - 1
   end while
   a[ j+1 ] = key
end for
 
end InsertionSort

Best Case: The best case is when input is an array that is already sorted. In this case insertion sort has a linear running time (i.e., Θ(n)).

Worst Case: The simplest worst case input is an array sorted in reverse order

QuickSort

Quicksort algorithm is a fast, recursive, non-stable sort algorithm which works by the divide and conquer principle. It picks an element as pivot and partitions the given array around that picked pivot.

QuickSort in Data Structures And Algorithms In C++ Steps to implement Quick sort

Pick a suitable “pivot point”.
Divide the lists into two lists based on this pivot element. Every element which is smaller than the pivot element is placed in the left list and every element which is larger is placed in the right list. If an element is equal to the pivot element then it can go in any list. This is called the partition operation.
Recursively sort each of the smaller lists.

Here’s pseudocode representing Quicksort Algorithm.

QuickSort(A as array, low as int, high as int){
    if (low < high){
        pivot_location = Partition(A,low,high)
        Quicksort(A,low, pivot_location)
        Quicksort(A, pivot_location + 1, high)
    }
}
Partition(A as array, low as int, high as int){
     pivot = A[low]
     left = low
 
     for i = low + 1 to high{
         if (A[i] < pivot) then{
             swap(A[i], A[left + 1])
             left = left + 1
         }
     }
     swap(pivot,A[left])
 
    return (left)}

The complexity of quicksort in the average case is Θ(n log(n)) and in the worst case is Θ(n2).

Merge Sort

Mergesort is a fast, recursive, stable sort algorithm which also works by the divide and conquer principle. Similar to quicksort, merge sort divides the list of elements into two lists. These lists are sorted independently and then combined. During the combination of the lists, the elements are inserted (or merged) at the right place in the list

Here’s pseudocode representing Merge Sort Algorithm

procedure MergeSort( a as array )
   if ( n == 1 ) return a
 
   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]
 
   l1 = mergesort( l1 )
   l2 = mergesort( l2 )
 
   return merge( l1, l2 )
end procedure
 
procedure merge( a as array, b as array )
 
   var c as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while
    
   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while
    
   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while
    
   return c
     
end procedure

Searching Algorithms in C++

Searching is one of the most common and frequently performed actions in regular business applications. Search algorithms are algorithms for finding an item with specified properties among a collection of items. Let’s explore two of the most commonly used searching algorithms.

Linear Search Algorithm

Linear search or sequential search is the simplest search algorithm. It involves sequential searching for an element in the given data structure until either the element is found or the end of the structure is reached. If the element is found, then the location of the item is returned otherwise the algorithm returns NULL.

Here’s pseudocode representing Linear Search in C++:

procedure linear_search (a[] , value)
for i = 0 to n-1
   if a[i] = value then
      print "Found "
      return i
   end if
print "Not found"
end for
 
end linear_search

It is a brute-force algorithm. While it certainly is the simplest, it’s most definitely is not the most common, due to its inefficiency. Time Complexity of Linear search is O(N).

Binary Search Algorithm

Binary search, also known as logarithmic search, is a search algorithm that finds the position of a target value within an already sorted array. It divides the input collection into equal halves and the item is compared with the middle element of the list. If the element is found, the search ends there. Else, we continue looking for the element by dividing and selecting the appropriate partition of the array, based on if the target element is smaller or bigger than the middle element.

Here’s pseudocode representing Binary Search in C++:

Procedure binary_search
   a; sorted array
   n; size of array
   x; value to be searched
 
    lowerBound = 1
    upperBound = n 
 
   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.
    
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
       
      if A[midPoint] < x set lowerBound = midPoint + 1 if A[midPoint] > x
         set upperBound = midPoint - 1
 
      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
    
end procedure

Binary Search Time Complexity

In each iteration, the search space is getting divided by 2. That means that in the current iteration you have to deal with half of the previous iteration array.

Best case could be the case where the first mid-value get matched to the element to be searched

Best Time Complexity: O(1)

Average Time Complexity: O(logn)

Worst Time Complexity: O(logn)

Since we are not using any space so space complexity will be O(1)

This brings us to the end of this ‘Data Structures and Algorithms in C++’ article. We have covered one of the most fundamental and important topics of C++. Hope you are clear with all that has been shared with you in this article.


🚀Conclusion

We have now reached the end of this page. With the knowledge from this page, you should be able to answers your interview question confidently.

TEST YOUR KNOWLEDGE!


1. For a binary search algorithm to work, it is necessary that the array (list) must be




2. Stack is used for?




3. What data structure is used for breadth first traversal of a graph?




4. Which of the following is example of in-place algorithm?




5. A Binary Tree can have




6. What is the time complexity to count the number of elements in the linked list?








Data Structures and Algorithms (DSA) Course Frequently Asked Questions

Currently, All the product companies in the world ask data structures and algorithms based problems for testing the candidates' programming skills. Data structures and Algorithms is the most important subject of computer science, in fact, this is the only subject of computer science that is widely used across all industry whether it’s an e-commerce company/ retail/ health sector/ banking sector/ telecom/ networking or any technology organizations. Learning Data Structures and Algorithms require fine grip in concepts and hands-on practice in problem-solving.
Logicmojo Data structures and Algorithms Course(DSA Course) covers every topic in the form of lectures and assignments. Lectures for understanding problem-solving techniques and assignments for practicing those techniques.


Space & Time Complexity Before starting to learn Data Structures and Algorithms, it is also very important to understand how to measure the time and space complexity of a program. Based on these complexities we optimized our solutions during interviews.


In this Data Structures and Algorithms Course (DSA Course), our main focus is to teach the candidates how to visualize recursion. Start from array till Graph, Every topic is implemented mostly in recursion. So after space and Time complexity, our main aim is to make candidates well aware of recursions with multiple examples.


Learning Data Structures and Algorithms start with Array problems. Most candidates think array problems are easy and they skip it. But initial rounds of all product companies start with arrays problems. Data Structures and Algorithms course(DSA Course) also starts with a huge list of arrays problems to cover every aspect of it.


Unquestionably, no single "optimal" programming dialect exists for mastering Data Structures and Algorithms, as these tenets transcend language boundaries. Nonetheless, certain vernaculars garner favor in academia or facilitate novices' comprehension. Here are several esteemed alternatives:


    1. Python: Frequently extolled for neophytes, Python boasts straightforward syntax and legibility. This adaptable language, replete with extensive library provisions, simplifies Data Structures and Algorithm implementation. A plethora of digital materials and pedagogical guides elucidate Python and DSA principles.


    2. C++: A stalwart in competitive coding and technical interviews, C++ touts formidable object-oriented programming support and furnishes granular control over memory manipulation—a crucial component when devising intricate data structures. C++ presents a more precipitous learning trajectory compared to Python, yet it yields superior performance and a profound grasp of computer memory.


    3. Java: Another sought-after contender for DSA mastery, Java features a potent object-oriented programming paradigm, innate data structure endorsement via the Java Collections Framework, and automatic memory management. While Java's syntax is more prolix than Python's, it strikes an agreeable equilibrium between user-friendliness and performance.


    4. JavaScript: For those entrenched in web development or prioritizing client-side programming, JavaScript emerges as an apt selection. Though not as prevalent for DSA as previously discussed languages, JavaScript's versatility and burgeoning ecosystem render it a fitting choice for acquiring data structure and algorithm knowledge.

Ultimately, the prime language for Data Structures and Algorithms hinges on individual predilections, antecedent coding familiarity, and aspirations. Python offers an excellent springboard for programming novices. Conversely, those with programming background desiring to delve into memory management and performance may find solace in C++ or Java. Irrespective of the chosen language, concentrate on assimilating the fundamental concepts and axioms, as these transcend programming language barriers.



It's the same principles we learn while solving physics, Maths problems during school days. Try to identify the techniques while solving problems and use the same techniques problems for practice. So we won't forget. In Logicmojo Data Structures and Algorithms Course, we explain techniques of solving problems, and then we have assignments attach with the lecture based on the same techniques. So you have a good hands-on with all the concepts.


Learning Data Structures and algorithms in 2024 is a step-by-step process. It's not about writing any brute force, it's about solving problems by using some algorithms in an optimized manner. Logicmojo Data Structures and Algorithms course(DSA Course) covers all in-depth concepts with full code explanations.



A DSA course, or Data Structures and Algorithms course, is an educational program that teaches students the fundamentals of data structures and algorithms. Data structures are ways of organizing and storing data, while algorithms are sets of instructions or procedures for solving problems or performing tasks in computer programming. This course is typically designed for computer science and software engineering students or professionals who want to enhance their programming skills and understanding of computational problem-solving.

A DSA course usually covers topics such as

    1. Basic data structures: Arrays, linked lists, stacks, queues, and hash tables.

    2. Advanced data structures: Trees, graphs, heaps, and tries.

    3. Sorting algorithms: Bubble sort, selection sort, insertion sort, merge sort, and quick sort.

    4. Searching algorithms: Linear search, binary search, and depth-first and breadth-first graph traversal.

    5. Algorithm design techniques: Divide and conquer, dynamic programming, greedy algorithms, and backtracking.

    6. Algorithm analysis: Time complexity, space complexity, and Big O notation.

Completing a DSA course can help students develop strong problem-solving skills, improve their coding efficiency, and prepare them for technical interviews or advanced courses in computer science.



A Data Structures and Algorithms (DSA) course can be beneficial for a variety of individuals. Here are some groups of people who should consider taking a DSA course:

    1. Computer Science students: Students pursuing a degree in computer science or a related field should learn about data structures and algorithms as they form the foundation of computer programming and problem-solving skills.

    2. Aspiring software developers/engineers: If you plan to work in software development, a strong understanding of data structures and algorithms is essential. This knowledge helps in optimizing code, improving performance, and solving complex problems efficiently.

    3. Professionals looking to upskill: Current software developers or IT professionals who want to improve their skills and stay competitive in the industry should consider taking a DSA course. This can help them tackle more challenging tasks and advance their careers.

    4. Competitive programming enthusiasts: Participants in competitive programming contests, such as ACM ICPC, Google Code Jam, or LeetCode, can benefit from a DSA course. Mastery of data structures and algorithms is critical for success in these competitions.

    5. Job seekers in the tech industry: Many tech companies, including top firms like Google, Amazon, and Facebook, test candidates' knowledge of data structures and algorithms during the interview process. Taking a DSA course can help prepare you for these interviews and increase your chances of securing a job.

    6. Educators and mentors: Computer science educators and mentors who teach programming concepts to others can benefit from a DSA course to strengthen their own understanding and effectively convey these concepts to their students.

In summary, anyone interested in computer programming, problem-solving, or a career in the technology sector can benefit from taking a Data Structures and Algorithms course. It can help build a solid foundation for further learning and career growth.



A Data Structures and Algorithms (DSA) course, at its core, delves into the fundamental principles, architectural design, execution, and dissection of an array of data structures and algorithms. While prerequisites for a DSA course may fluctuate across institutions or specific offerings, the following generally remain constant:

    1. Elementary coding acumen: Acquaintance with at least one programming language (e.g., C, C++, Java, Python, or JavaScript) is crucial, as well as comprehension of programming notions such as variables, iterations, conditionals, and functions.

    2. Mathematical underpinnings: Grasping the rudiments of discrete mathematics, comprising concepts like sets, relations, functions, and graphs, is paramount for decoding the theoretical facets of data structures and algorithms.

    3. Analytical prowess: DSA courses mandate robust analytical and critical cogitation abilities to concoct and scrutinize a variety of algorithms and data structures.

    4. Foundational computer systems knowledge: Comprehending computer architecture, memory strata, and program execution processes is advantageous for discerning the efficacy of algorithms and data structures.

    5. Data structures familiarity: Although the course elucidates data structures, possessing a rudimentary comprehension of prevalent data structures such as arrays, linked lists, stacks, and queues can facilitate a swifter mastery of the concepts.

    6. Antecedent coursework (if applicable): Certain institutions may necessitate the completion of particular prerequisite courses prior to DSA course enrollment. These might encompass introductory programming, discrete mathematics, or computer systems courses.

For programming novices, contemplate enrolling in an elementary programming course or exploring tutorials and practice quandaries online before diving into a DSA course. This approach ensures a robust foundation in programming and problem-solving aptitudes, indispensable for flourishing in the realm of DSA.



A Data Structures and Algorithms (DSA) course typically covers a variety of topics that are fundamental to computer science and programming. Some of the key topics covered in a DSA course include:

    1. Introduction to Data Structures and Algorithms: Basic concepts, algorithm analysis, time and space complexity, Big O notation.

    2. Arrays: Static and dynamic arrays, multi-dimensional arrays, operations, and applications.

    3. Linked Lists: Singly linked lists, doubly linked lists, circular linked lists, operations, and applications.

    4. Stacks: Implementation, operations (push, pop, peek), and applications.

    5. Queues: Implementation, operations (enqueue, dequeue, front, rear), priority queues, circular queues, and applications.

    6. Trees: Binary trees, binary search trees, balanced trees (AVL, Red-Black), tree traversal techniques (in-order, pre-order, post-order), and applications.

    7. Graphs: Representation (adjacency matrix, adjacency list), graph traversal algorithms (BFS, DFS), shortest path algorithms (Dijkstra, Bellman-Ford), minimum spanning tree algorithms (Prim, Kruskal), and applications.

    8. Hashing: Hash functions, hash tables, collision resolution techniques (chaining, open addressing), and applications.

    9. Sorting Algorithms: Bubble sort, selection sort, insertion sort, merge sort, quick sort, heap sort, counting sort, radix sort, and their time complexities.

    10. Searching Algorithms: Linear search, binary search, interpolation search, and their time complexities.

    11. Recursion: Basics of recursion, recursive algorithms, and examples (factorial, Fibonacci series, Tower of Hanoi).

    12. Dynamic Programming: Introduction to dynamic programming, memoization, top-down and bottom-up approaches, examples (Fibonacci series, longest common subsequence, 0/1 knapsack problem).

    13. Greedy Algorithms: Introduction to greedy algorithms, examples (fractional knapsack problem, minimum spanning tree, Huffman coding).

    14. Backtracking: Introduction to backtracking, examples (N-Queens problem, graph coloring problem, Hamiltonian cycle).

    15. Divide and Conquer: Introduction to divide and conquer, examples (merge sort, quick sort, Strassen's matrix multiplication).

These topics provide a solid foundation for understanding the principles and techniques used in designing and analyzing efficient algorithms and data structures, which are essential for solving complex problems in computer science and programming.


Imbibing the erudition of Data Structures and Algorithms (DSA) can yield multifarious boons, especially for those captivated by computer science, software engineering, or affiliated domains. Here are some pivotal merits to consider:

    1. Improved problem-solving skills : DSA courses teach you how to analyze and solve complex problems methodically, making you a more effective problem solver in various domains.

    2. Strong foundation in computer science: Understanding data structures and algorithms is fundamental to computer science. A DSA course lays the groundwork for more advanced topics and helps you develop a solid understanding of key principles.

    3. Enhanced programming skills: DSA courses typically involve hands-on coding exercises, which help you become more proficient in your chosen programming language and enable you to write more efficient, maintainable code.

    4. Better performance in technical interviews: Many tech companies assess candidates' knowledge of data structures and algorithms during interviews. A strong grasp of DSA concepts can give you an edge in the competitive job market.

    5. Increased career opportunities: A thorough understanding of DSA concepts can open doors to various roles in software development, data science, and other technology fields.

    6. Improved software performance: Learning how to choose the right data structure or algorithm for a particular task can lead to significant performance improvements in software applications.

    7: Scalability and optimization: DSA courses help you understand how to build scalable systems and optimize resource usage, which is essential for handling large datasets or high-traffic applications.

    8. Interdisciplinary applications: DSA concepts are applicable across various disciplines, including artificial intelligence, machine learning, and bioinformatics, making this knowledge valuable in diverse fields.

    9. Lifelong learning : A DSA course lays the foundation for continuous learning in computer science and serves as a stepping stone to explore more advanced topics in the future.

    10. Community and networking: By taking a DSA course, you can connect with like-minded individuals, share ideas, and build a professional network that can benefit your career in the long run



A Data Structures and Algorithms (DSA) course, at its core, delves into the fundamental principles, architectural design, execution, and dissection of an array of data structures and algorithms. While prerequisites for a DSA course may fluctuate across institutions or specific offerings, the following generally remain constant:

The duration of a Data Structures and Algorithms (DSA) course can vary greatly depending on the institution, course format, and the student's prior knowledge and dedication. A typical DSA course in a university or college setting may last for one semester, which is about 12 to 16 weeks. However, online courses and boot camps can have different timeframes, ranging from a few weeks to several months.

If you are self-studying, the time it takes to complete a DSA course can depend on your own pace and the amount of time you dedicate to learning. It's important to consider that mastering data structures and algorithms requires practice and hands-on experience, so allocating time for exercises and projects is crucial. In general, self-paced DSA learning can take anywhere from a few weeks to several months, depending on your commitment and available time.


Logicmojo Learning Library