Software Development Life Cycle?

Software development Life Cycle (SDLC) is a methodology for a software product. It is improving the quality of
software and the overall development process.
Software development Life Cycle (SDLC) refers to all the phases of a software product throughout its
planning, development, and use, all the way through to its eventual obsolescence or retirement. This process
has many variable parts, but it can often be segmented into several main pieces. This helps developers and
others to understand how a product is created, implemented and used.

Several of the most common parts of a software life cycle are planning phases. Typically referred to as
requirements gathering or analysis, where an undeveloped product is defined through gathered criteria.
Subsequent phases involve the analysis and design of the product, followed by development. The last parts
of the life cycle involve a product that has been released to a customer or other end user, at which time the
product maker often continues to be involved through maintenance, problem solving, upgrading and other
processes.

A typical Software Development Life Cycle consists of the following stages −

Stage 1: Planning and Requirement Analysis

Requirement analysis is the most important and fundamental stage in SDLC.
It is performed by the senior members of the team with inputs from the customer, the sales department,
market surveys and domain experts in the industry. This information is then used to plan the basic project
approach and to conduct product feasibility study in the economical, operational and technical areas.
Planning for the quality assurance requirements and identification of the risks associated with the project is
also done in the planning stage. The outcome of the technical feasibility study is to define the various technical
approaches that can be followed to implement the project successfully with minimum risks.

Business analyst and Project organizer set up a meeting with the client to gather all the data like what the
customer wants to build, who will be the end user, what is the objective of the product. Before creating a
product, a core understanding or knowledge of the product is very necessary.

For Example, A client wants to have an application which concerns money transactions. In this method, the
requirement has to be precise like what kind of operations will be done, how it will be done, in which currency
it will be done, etc.

Once the required function is done, an analysis is complete with auditing the feasibility of the growth of a
product. In case of any ambiguity, a signal is set up for further discussion.

Once the requirement is understood, the SRS (Software Requirement Specification) document is created. The
developers should thoroughly follow this document and also should be reviewed by the customer for future
reference.

Stage 2: Defining Requirements

Once the requirement analysis is done the next step is to clearly define and document the product
requirements and get them approved from the customer or the market analysts.
This is done through an SRS (Software Requirement Specification) document which consists of all the product
requirements to be designed and developed during the project life cycle.
Stage 3: Designing the Product Architecture
SRS is the reference for product architects to come out with the best architecture for the product to be
developed. Based on the requirements specified in SRS, usually more than one design approach for the
product architecture is proposed and documented in a DDS - Design Document Specification.
This DDS is reviewed by all the important stakeholders and based on various parameters as risk assessment,
product robustness, design modularity, budget and time constraints, the best design approach is selected for
the product.
A design approach clearly defines all the architectural modules of the product along with its communication
and data flow representation with the external and third party modules (if any). The internal design of all the
modules of the proposed architecture should be clearly defined with the minutest of the details in DDS.
Stage 4: Building or Developing the Product
In this stage of SDLC the actual development starts and the product (programming) is built. The programming
code is generated as per DDS during this stage. If the design is performed in a detailed and organized manner,
code generation can be accomplished without much hassle.
Developers must follow the coding guidelines defined by their organization and programming tools like
compilers, interpreters, debuggers, etc. are used to generate the code. Different high level programming
languages such as Python C, C++, Pascal, Java and PHP are used for coding. The programming language is
chosen with respect to the type of software being developed.
Stage 5: Testing the Product
This stage is usually a subset of all the stages as in the modern SDLC models, the testing activities are mostly
involved in all the stages of SDLC. However, this stage refers to the testing only stage of the product where
product defects are reported, tracked, fixed and retested, until the product reaches the quality standards
defined in the SRS.
Stage 6: Deployment in the Market and Maintenance
Once the product is tested and ready to be deployed it is released formally in the appropriate market.
Sometimes product deployment happens in stages as per the business strategy of that organization. The
product may first be released in a limited segment and tested in the real business environment (UAT- User
acceptance testing).
Then based on the feedback, the product may be released as it is or with suggested enhancements in the
targeting market segment. After the product is released in the market, its maintenance is done for the existing
customer base.

NEED OF SOFTWARE DEVELOPMENT LIFE CYCLE

The development team must determine a suitable life cycle model for a particular plan and then observe to it.

Without using an exact life cycle model, the development of a software product would not be in a systematic
and disciplined manner. When a team is developing a software product, there must be a clear understanding
among team representative about when and what to do. Otherwise, it would point to chaos and project
failure. This problem can be defined by using an example. Suppose a software development issue is divided
into various parts and the parts are assigned to the team members. From then on, suppose the team
representative is allowed the freedom to develop the roles assigned to them in whatever way they like. It is
possible that one representative might start writing the code for his part, another might choose to prepare
the test documents first, and some other engineer might begin with the design phase of the roles assigned to
him. This would be one of the perfect methods for project failure.

A software life cycle model describes entry and exit criteria for each phase. A phase can begin only if its stage-
entry criteria have been fulfilled. So without a software life cycle model, the entry and exit criteria for a stage
cannot be recognized. Without software life cycle models, it becomes tough for software project managers to
monitor the progress of the project.
What are SDLC models?

A software development lifecycle (SDLC) model conceptually presents SDLC in an organized fashion to help
organizations implement it. Different models arrange the SDLC phases in varying chronological order to
optimize the development cycle. We look at some popular SDLC models below.

Waterfall

The waterfall model arranges all the phases sequentially so that each new phase depends on the outcome of
the previous phase. Conceptually, the design flows from one phase down to the next, like that of a waterfall.

Pros and cons

The waterfall model provides discipline to project management and gives a tangible output at the end of
each phase. However, there is little room for change once a phase is considered complete, as changes can
affect the software's delivery time, cost, and quality. Therefore, the model is most suitable for small
software development projects, where tasks are easy to arrange and manage and requirements can be pre-
defined accurately.

Iterative

The iterative process suggests that teams begin software development with a small subset of requirements.
Then, they iteratively enhance versions over time until the complete software is ready for production. The
team produces a new software version at the end of each iteration.

Pros and cons

It’s easy to identify and manage risks, as requirements can change between iterations. However, repeated
cycles could lead to scope change and underestimation of resources.

Spiral

The spiral model combines the iterative model's small repeated cycles with the waterfall model's linear
sequential flow to prioritize risk analysis. You can use the spiral model to ensure software's gradual release
and improvement by building prototypes at each phase.

Pros and cons

The spiral model is suitable for large and complex projects that require frequent changes. However, it can be
expensive for smaller projects with a limited scope.

Agile

The agile model arranges the SDLC phases into several development cycles. The team iterates through the
phases rapidly, delivering only small, incremental software changes in each cycle. They continuously
evaluate requirements, plans, and results so that they can respond quickly to change. The agile model is
both iterative and incremental, making it more efficient than other process models.

Pros and cons

Rapid development cycles help teams identify and address issues in complex projects early on and before
they become significant problems. They can also engage customers and stakeholders to obtain feedback
throughout the project lifecycle. However, overreliance on customer feedback could lead to excessive scope
changes or end the project midway.
SDLC - WATERFALL MODEL
The Waterfall Model was the first Process Model to be introduced. It is also referred to as a linear-sequential
life cycle model. It is very simple to understand and use. In a waterfall model, each phase must be completed
before the next phase can begin and there is no overlapping in the phases.
The Waterfall model is the earliest SDLC approach that was used for software development.
The waterfall Model illustrates the software development process in a linear sequential flow. This means that
any phase in the development process begins only if the previous phase is complete. In this waterfall model,
the phases do not overlap.
Waterfall Model - Design
Waterfall approach was first SDLC Model to be used widely in Software Engineering to ensure success of the
project. In "The Waterfall" approach, the whole process of software development is divided into separate
phases. In this Waterfall model, typically, the outcome of one phase acts as the input for the next phase
sequentially.

The following illustration is a representation of the different phases of the Waterfall Model.

The sequential phases in Waterfall model are −

 Requirement Gathering and analysis − All possible requirements of the system to be developed are
captured in this phase and documented in a requirement specification document.
 System Design − The requirement specifications from first phase are studied in this phase and the
system design is prepared. This system design helps in specifying hardware and system requirements
and helps in defining the overall system architecture.
 Implementation − With inputs from the system design, the system is first developed in small programs
called units, which are integrated in the next phase. Each unit is developed and tested for its
functionality, which is referred to as Unit Testing.
 Integration and Testing − All the units developed in the implementation phase are integrated into a
system after testing of each unit. Post integration the entire system is tested for any faults and failures.
 Deployment of system − Once the functional and non-functional testing is done; the product is
deployed in the customer environment or released into the market.
 Maintenance − There are some issues which come up in the client environment. To fix those issues,
patches are released. Also to enhance the product some better versions are released. Maintenance is
done to deliver these changes in the customer environment.
All these phases are cascaded to each other in which progress is seen as flowing steadily downwards (like a
waterfall) through the phases. The next phase is started only after the defined set of goals are achieved for
previous phase and it is signed off, so the name "Waterfall Model". In this model, phases do not overlap.
Waterfall Model - Application
Every software developed is different and requires a suitable SDLC approach to be followed based on the
internal and external factors. Some situations where the use of Waterfall model is most appropriate are −
 Requirements are very well documented, clear and fixed.
 Product definition is stable.
 Technology is understood and is not dynamic.
 There are no ambiguous requirements.
 Ample resources with required expertise are available to support the product.
 The project is short.

Waterfall Model - Advantages
The advantages of waterfall development are that it allows for departmentalization and control. A schedule
can be set with deadlines for each stage of development and a product can proceed through the development
process model phases one by one.
Development moves from concept, through design, implementation, testing, installation, troubleshooting,
and ends up at operation and maintenance. Each phase of development proceeds in strict order.
Some of the major advantages of the Waterfall Model are as follows −
 Simple and easy to understand and use
 Easy to manage due to the rigidity of the model. Each phase has specific deliverables and a review
process.
 Phases are processed and completed one at a time.
 Works well for smaller projects where requirements are very well understood.
 Clearly defined stages.
 Well understood milestones.
 Easy to arrange tasks.
 Process and results are well documented.

Waterfall Model - Disadvantages

The disadvantage of waterfall development is that it does not allow much reflection or revision. Once an
application is in the testing stage, it is very difficult to go back and change something that was not well-
documented or thought upon in the concept stage.
The major disadvantages of the Waterfall Model are as follows −
 No working software is produced until late during the life cycle.
 High amounts of risk and uncertainty.
 Not a good model for complex and object-oriented projects.
 Poor model for long and ongoing projects.
 Not suitable for the projects where requirements are at a moderate to high risk of changing. So, risk
and uncertainty is high with this process model.
 It is difficult to measure progress within stages.
 Cannot accommodate changing requirements.
 Adjusting scope during the life cycle can end a project.
 Integration is done as a "big-bang” at the very end, which doesn't allow identifying any technological
or business bottleneck or challenges early.
SDLC - ITERATIVE MODEL
In the Iterative model, iterative process starts with a simple implementation of a small set of the software
requirements and iteratively enhances the evolving versions until the complete system is implemented and
ready to be deployed.
An iterative life cycle model does not attempt to start with a full specification of requirements. Instead,
development begins by specifying and implementing just part of the software, which is then reviewed to
identify further requirements. This process is then repeated, producing a new version of the software at the
end of each iteration of the model.
Iterative Model - Design
Iterative process starts with a simple implementation of a subset of the software requirements and iteratively
enhances the evolving versions until the full system is implemented. At each iteration, design modifications
are made and new functional capabilities are added. The basic idea behind this method is to develop a system
through repeated cycles (iterative) and in smaller portions at a time (incremental).
The following illustration is a representation of the Iterative and Incremental model –

Iterative and Incremental development is a combination of both iterative design or iterative method and
incremental build model for development. "During software development, more than one iteration of the
software development cycle may be in progress at the same time." This process may be described as an
"evolutionary acquisition" or "incremental build" approach."
In this incremental model, the whole requirement is divided into various builds. During each iteration, the
development module goes through the requirements, design, implementation and testing phases. Each
subsequent release of the module adds function to the previous release. The process continues till the
complete system is ready as per the requirement.
The key to a successful use of an iterative software development lifecycle is rigorous validation of
requirements, and verification & testing of each version of the software against those requirements within
each cycle of the model. As the software evolves through successive cycles, tests must be repeated and
extended to verify each version of the software.
Iterative Model - Application
Like other SDLC models, Iterative and incremental development has some specific applications in the software
industry. This model is most often used in the following scenarios −
 Requirements of the complete system are clearly defined and understood.
 Major requirements must be defined; however, some functionalities or requested enhancements may
evolve with time.
 There is a time to the market constraint.
  A new technology is being used and is being learnt by the development team while working on the
project.
 Resources with needed skill sets are not available and are planned to be used on contract basis for
specific iterations.
 There are some high-risk features and goals which may change in the future.

Iterative Model - Pros and Cons

The advantage of this model is that there is a working model of the system at a very early stage of
development, which makes it easier to find functional or design flaws. Finding issues at an early stage of
development enables to take corrective measures in a limited budget.
The disadvantage with this SDLC model is that it is applicable only to large and bulky software development
projects. This is because it is hard to break a small software system into further small serviceable
increments/modules.
The advantages of the Iterative and Incremental SDLC Model are as follows −
 Some working functionality can be developed quickly and early in the life cycle.
 Results are obtained early and periodically.
 Parallel development can be planned.
 Progress can be measured.
 Less costly to change the scope/requirements.
 Testing and debugging during smaller iteration is easy.
 Risks are identified and resolved during iteration; and each iteration is an easily managed milestone.
 Easier to manage risk - High risk part is done first.
 With every increment, operational product is delivered.
 Issues, challenges and risks identified from each increment can be utilized/applied to the next
increment.
 Risk analysis is better.
 It supports changing requirements.
 Initial Operating time is less.
 Better suited for large and mission-critical projects.
 During the life cycle, software is produced early which facilitates customer evaluation and feedback.
The disadvantages of the Iterative and Incremental SDLC Model are as follows −
 More resources may be required.
 Although cost of change is lesser, but it is not very suitable for changing requirements.
 More management attention is required.
 System architecture or design issues may arise because not all requirements are gathered in the
beginning of the entire life cycle.
 Defining increments may require definition of the complete system.
 Not suitable for smaller projects.
 Management complexity is more.
 End of project may not be known which is a risk.
 Highly skilled resources are required for risk analysis.
 Projects progress is highly dependent upon the risk analysis phase.
SDLC - SPIRAL MODEL
The spiral model combines the idea of iterative development with the systematic, controlled aspects of the
waterfall model. This Spiral model is a combination of iterative development process model and sequential
linear development model i.e. the waterfall model with a very high emphasis on risk analysis. It allows
incremental releases of the product or incremental refinement through each iteration around the spiral.
Spiral Model - Design
The spiral model has four phases. A software project repeatedly passes through these phases in iterations
called Spirals.
Identification
This phase starts with gathering the business requirements in the baseline spiral. In the subsequent spirals as
the product matures, identification of system requirements, subsystem requirements and unit requirements
are all done in this phase.
This phase also includes understanding the system requirements by continuous communication between the
customer and the system analyst. At the end of the spiral, the product is deployed in the identified market.
Design
The Design phase starts with the conceptual design in the baseline spiral and involves architectural design,
logical design of modules, physical product design and the final design in the subsequent spirals.
Construct or Build
The Construct phase refers to production of the actual software product at every spiral. In the baseline spiral,
when the product is just thought of and the design is being developed a POC (Proof of Concept) is developed
in this phase to get customer feedback.
Then in the subsequent spirals with higher clarity on requirements and design details a working model of the
software called build is produced with a version number. These builds are sent to the customer for feedback.
Evaluation and Risk Analysis
Risk Analysis includes identifying, estimating and monitoring the technical feasibility and management risks,
such as schedule slippage and cost overrun. After testing the build, at the end of first iteration, the customer
evaluates the software and provides feedback.
The following illustration is a representation of the Spiral Model, listing the activities in each phase.
Based on the customer evaluation, the software development process enters the next iteration and
subsequently follows the linear approach to implement the feedback suggested by the customer. The process
of iterations along the spiral continues throughout the life of the software.
Spiral Model Application
The Spiral Model is widely used in the software industry as it is in sync with the natural development process
of any product, i.e. learning with maturity which involves minimum risk for the customer as well as the
development firms.
The following pointers explain the typical uses of a Spiral Model −
 When there is a budget constraint and risk evaluation is important.
 For medium to high-risk projects.
 Long-term project commitment because of potential changes to economic priorities as the
requirements change with time.
 Customer is not sure of their requirements which is usually the case.
 Requirements are complex and need evaluation to get clarity.
 New product line which should be released in phases to get enough customer feedback.
 Significant changes are expected in the product during the development cycle.

Spiral Model - Pros and Cons

The advantage of spiral lifecycle model is that it allows elements of the product to be added in, when they
become available or known. This assures that there is no conflict with previous requirements and design.
This method is consistent with approaches that have multiple software builds and releases which allows
making an orderly transition to a maintenance activity. Another positive aspect of this method is that the spiral
model forces an early user involvement in the system development effort.
On the other side, it takes a very strict management to complete such products and there is a risk of running
the spiral in an indefinite loop. So, the discipline of change and the extent of taking change requests is very
important to develop and deploy the product successfully.
The advantages of the Spiral SDLC Model are as follows −
 Changing requirements can be accommodated.
 Allows extensive use of prototypes.
 Requirements can be captured more accurately.
 Users see the system early.
 Development can be divided into smaller parts and the risky parts can be developed earlier which helps
in better risk management.
The disadvantages of the Spiral SDLC Model are as follows −
 Management is more complex.
 End of the project may not be known early.
 Not suitable for small or low risk projects and could be expensive for small projects.
 Process is complex
 Spiral may go on indefinitely.
 Large number of intermediate stages requires excessive documentation
SDLC - V-MODEL
The V-model is an SDLC model where execution of processes happens in a sequential manner in a V-shape. It
is also known as Verification and Validation model.
The V-Model is an extension of the waterfall model and is based on the association of a testing phase for each
corresponding development stage. This means that for every single phase in the development cycle, there is
a directly associated testing phase. This is a highly-disciplined model and the next phase starts only after
completion of the previous phase.
V-Model - Design
Under the V-Model, the corresponding testing phase of the development phase is planned in parallel. So, there
are Verification phases on one side of the ‘V’ and Validation phases on the other side. The Coding Phase joins
the two sides of the V-Model.
The following illustration depicts the different phases in a V-Model of the SDLC.

V-Model - Verification Phases

There are several Verification phases in the V-Model, each of these are explained in detail below.
Business Requirement Analysis
This is the first phase in the development cycle where the product requirements are understood from the
customer’s perspective. This phase involves detailed communication with the customer to understand his
expectations and exact requirement. This is a very important activity and needs to be managed well, as most
of the customers are not sure about what exactly they need. The acceptance test design planning is done at
this stage as business requirements can be used as an input for acceptance testing.
System Design
Once you have the clear and detailed product requirements, it is time to design the complete system. The
system design will have the understanding and detailing the complete hardware and communication setup for
the product under development. The system test plan is developed based on the system design. Doing this at
an earlier stage leaves more time for the actual test execution later.
Architectural Design
Architectural specifications are understood and designed in this phase. Usually more than one technical
approach is proposed and based on the technical and financial feasibility the final decision is taken. The system
design is broken down further into modules taking up different functionality. This is also referred to as High
Level Design (HLD).
The data transfer and communication between the internal modules and with the outside world (other
systems) is clearly understood and defined in this stage. With this information, integration tests can be
designed and documented during this stage.
Module Design
In this phase, the detailed internal design for all the system modules is specified, referred to as Low Level
Design (LLD). It is important that the design is compatible with the other modules in the system architecture
and the other external systems. The unit tests are an essential part of any development process and helps
eliminate the maximum faults and errors at a very early stage. These unit tests can be designed at this stage
based on the internal module designs.
Coding Phase
The actual coding of the system modules designed in the design phase is taken up in the Coding phase. The
best suitable programming language is decided based on the system and architectural requirements.
The coding is performed based on the coding guidelines and standards. The code goes through numerous code
reviews and is optimized for best performance before the final build is checked into the repository.
Validation Phases
The different Validation Phases in a V-Model are explained in detail below.
Unit Testing
Unit tests designed in the module design phase are executed on the code during this validation phase. Unit
testing is the testing at code level and helps eliminate bugs at an early stage, though all defects cannot be
uncovered by unit testing.
Integration Testing
Integration testing is associated with the architectural design phase. Integration tests are performed to test
the coexistence and communication of the internal modules within the system.
System Testing
System testing is directly associated with the system design phase. System tests check the entire system
functionality and the communication of the system under development with external systems. Most of the
software and hardware compatibility issues can be uncovered during this system test execution.
Acceptance Testing
Acceptance testing is associated with the business requirement analysis phase and involves testing the
product in user environment. Acceptance tests uncover the compatibility issues with the other systems
available in the user environment. It also discovers the non-functional issues such as load and performance
defects in the actual user environment.
V- Model ─ Application
V- Model application is almost the same as the waterfall model, as both the models are of sequential type.
Requirements have to be very clear before the project starts, because it is usually expensive to go back and
make changes. This model is used in the medical development field, as it is strictly a disciplined domain.
The following pointers are some of the most suitable scenarios to use the V-Model application.
 Requirements are well defined, clearly documented and fixed.
 Product definition is stable.
 Technology is not dynamic and is well understood by the project team.
 There are no ambiguous or undefined requirements.
 The project is short.
V-Model - Pros and Cons
The advantage of the V-Model method is that it is very easy to understand and apply. The simplicity of this
model also makes it easier to manage. The disadvantage is that the model is not flexible to changes and just
in case there is a requirement change, which is very common in today’s dynamic world, it becomes very
expensive to make the change.
The advantages of the V-Model method are as follows −
 This is a highly-disciplined model and Phases are completed one at a time.
 Works well for smaller projects where requirements are very well understood.
 Simple and easy to understand and use.
 Easy to manage due to the rigidity of the model. Each phase has specific deliverables and a review
process.
The disadvantages of the V-Model method are as follows −
 High risk and uncertainty.
 Not a good model for complex and object-oriented projects.
 Poor model for long and ongoing projects.
 Not suitable for the projects where requirements are at a moderate to high risk of changing.
 Once an application is in the testing stage, it is difficult to go back and change a functionality.
 No working software is produced until late during the life cycle.

SDLC - BIG BANG MODEL

The Big Bang model is an SDLC model where we do not follow any specific process. The development just
starts with the required money and efforts as the input, and the output is the software developed which may
or may not be as per customer requirement. This Big Bang Model does not follow a process/procedure and
there is a very little planning required. Even the customer is not sure about what exactly he wants and the
requirements are implemented on the fly without much analysis.
Usually this model is followed for small projects where the development teams are very small.
Big Bang Model ─ Design and Application
The Big Bang Model comprises of focusing all the possible resources in the software development and coding,
with very little or no planning. The requirements are understood and implemented as they come. Any changes
required may or may not need to revamp the complete software.
This model is ideal for small projects with one or two developers working together and is also useful for
academic or practice projects. It is an ideal model for the product where requirements are not well understood
and the final release date is not given.
Big Bang Model - Pros and Cons
The advantage of this Big Bang Model is that it is very simple and requires very little or no planning. Easy to
manage and no formal procedure are required.
However, the Big Bang Model is a very high risk model and changes in the requirements or misunderstood
requirements may even lead to complete reversal or scraping of the project. It is ideal for repetitive or small
projects with minimum risks.
The advantages of the Big Bang Model are as follows −
 This is a very simple model
 Little or no planning required
 Easy to manage
 Very few resources required
 Gives flexibility to developers
 It is a good learning aid for new comers or students.
The disadvantages of the Big Bang Model are as follows −
 Very High risk and uncertainty.
 Not a good model for complex and object-oriented projects.
 Poor model for long and ongoing projects.
 Can turn out to be very expensive if requirements are misunderstood.
 SOFTWARE DESIGN

Software design is a process to transform user requirements into some suitable form, which helps the
programmer in software coding and implementation.
For assessing user requirements, an SRS (Software Requirement Specification) document is created whereas
for coding and implementation, there is a need of more specific and detailed requirements in software terms.
The output of this process can directly be used into implementation in programming languages.
Software design is the first step in SDLC (Software Design Life Cycle), which moves the concentration from
problem domain to solution domain. It tries to specify how to fulfill the requirements mentioned in SRS.

Objectives of Software Design

Following are the purposes of Software design:

1. Correctness: Software design should be correct as per requirement.

2. Completeness: The design should have all components like data structures, modules, and external
interfaces, etc.
3. Efficiency: Resources should be used efficiently by the program.
4. Flexibility: Able to modify on changing needs.
5. Consistency: There should not be any inconsistency in the design.
6. Maintainability: The design should be so simple so that it can be easily maintainable by other
designers.

Principles of Software Design

Software design principles are concerned with providing means to handle the complexity of the design process
effectively. Effectively managing the complexity will not only reduce the effort needed for design but can also
reduce the scope of introducing errors during design.

Following are the principles of Software Design

1. Problem Partitioning
For small problem, we can handle the entire problem at once but for the significant problem, divide the
problems and conquer the problem it means to divide the problem into smaller pieces so that each piece can
be captured separately.

For software design, the goal is to divide the problem into manageable pieces.

Benefits of Problem Partitioning

1. Software is easy to understand
2. Software becomes simple
3. Software is easy to test
4. Software is easy to modify
5. Software is easy to maintain
6. Software is easy to expand

These pieces cannot be entirely independent of each other as they together form the system. They have to
cooperate and communicate to solve the problem. This communication adds complexity.
Data packaging and implementation, including issues of scope and

2. Abstraction

An abstraction is a tool that enables a designer to consider a component at an abstract level without bothering
about the internal details of the implementation. Abstraction can be used for existing element as well as the
component being designed.

Here, there are two common abstraction mechanisms

1. Functional Abstraction
2. Data Abstraction

Functional Abstraction
i. A module is specified by the method it performs.
ii. The details of the algorithm to accomplish the functions are not visible to the user of the function.

Functional abstraction forms the basis for Function oriented design approaches.

Data Abstraction

Details of the data elements are not visible to the users of data. Data Abstraction forms the basis for Object
Oriented design approaches.

3. Modularity

Modularity specifies the division of software into separate modules which are differently named and
addressed and are integrated later on to obtain the completely functional software. It is the only property that
allows a program to be intellectually manageable. Single large programs are difficult to understand and read
due to a large number of reference variables, control paths, global variables, etc.
The desirable properties of a modular system are:

1. Each module is a well-defined system that can be used with other applications.
2. Each module has single specified objectives.
3. Modules can be separately compiled and saved in the library.
4. Modules should be easier to use than to build.
5. Modules are simpler from outside than inside.

Advantages of Modularity

There are several advantages of Modularity

1. It allows large programs to be written by several or different people

2. It encourages the creation of commonly used routines to be placed in the library and used by other
programs.
3. It simplifies the overlay procedure of loading a large program into main storage.
4. It provides more checkpoints to measure progress.
5. It provides a framework for complete testing, more accessible to test
6. It produced the well designed and more readable program.

Disadvantages of Modularity

There are several disadvantages of Modularity

1. Execution time maybe, but not certainly, longer

2. Storage size perhaps, but is not certainly, increased
3. Compilation and loading time may be longer
4. Inter-module communication problems may be increased
5. More linkage required, run-time may be longer, more source lines must be written, and more
documentation has to be done

Modular Design

Modular design reduces the design complexity and results in easier and faster implementation by allowing
parallel development of various parts of a system. We discuss a different section of modular design in detail
in this section:

1. Functional Independence: Functional independence is achieved by developing functions that perform only
one kind of task and do not excessively interact with other modules. Independence is important because it
makes implementation more accessible and faster. The independent modules are easier to maintain, test, and
reduce error propagation and can be reused in other programs as well. Thus, functional independence is a
good design feature which ensures software quality.
It is measured using two criteria:
 Cohesion: It measures the relative function strength of a module.
 Coupling: It measures the relative interdependence among modules.

2. Information hiding: The fundamental of Information hiding suggests that modules can be characterized by
the design decisions that protect from the others, i.e., In other words, modules should be specified that data
include within a module is inaccessible to other modules that do not need for such information.

The use of information hiding as design criteria for modular system provides the most significant benefits
when modifications are required during testing's and later during software maintenance. This is because as
most data and procedures are hidden from other parts of the software, inadvertent errors introduced during
modifications are less likely to propagate to different locations within the software.

Strategy of Design

A good system design strategy is to organize the program modules in such a method that are easy to develop
and latter too, change. Structured design methods help developers to deal with the size and complexity of
programs. Analysts generate instructions for the developers about how code should be composed and how
pieces of code should fit together to form a program.

To design a system, there are two possible approaches:

1. Top-down Approach
2. Bottom-up Approach

1. Top-down Approach: This approach starts with the identification of the main components and then
decomposing them into their more detailed sub-components.

2. Bottom-up Approach: A bottom-up approach begins with the lower details and moves towards up the
hierarchy, as shown in fig. This approach is suitable in case of an existing system.
DATA STRUCTURES TUTORIAL
Data Structure is a way to store and organize data so that it can be used efficiently.

The data structure as the name indicates is organizing the data in memory. There are many ways of
organizing the data in the memory as we have already seen one of the data structures, i.e., array in
C language. Array is a collection of memory elements in which data is stored sequentially, i.e., one
after another. In other words, we can say that array stores the elements in a continuous manner.
This organization of data is done with the help of an array of data structures. There are also other
ways to organize the data in memory. Let's see the different types of data structures.

The data structure is not any programming language like C, C++, java, etc. It is a set of algorithms that
we can use in any programming language to structure the data in the memory.

To structure the data in memory, 'n' number of algorithms were proposed, and all these algorithms
are known as Abstract data types. These abstract data types are the set of rules.

Types of Data Structures

There are two types of data structures:

o Primitive data structure

o Non-primitive data structure

Primitive Data structure

The primitive data structures are primitive data types. The int, char, float, double, and pointer are
the primitive data structures that can hold a single value.

Non-Primitive Data structure

The non-primitive data structure is divided into two types:

o Linear data structure

o Non-linear data structure
 Linear data structure: Data structure in which data elements are arranged sequentially or
linearly, where each element is attached to its previous and next adjacent elements, is called a
linear data structure.
Examples of linear data structures are array, stack, queue, linked list, etc.
 Static data structure: Static data structure has a fixed memory size. It is easier to
access the elements in a static data structure.
An example of this data structure is an array.
 Dynamic data structure: In the dynamic data structure, the size is not fixed. It can be
randomly updated during the runtime which may be considered efficient concerning
the memory (space) complexity of the code.
Examples of this data structure are queue, stack, etc.
 Non-linear data structure: Data structures where data elements are not placed sequentially or
linearly are called non-linear data structures. In a non-linear data structure, we can’t traverse all
the elements in a single run only.
Examples of non-linear data structures are trees and graphs.

Major Operations

The major or the common operations that can be performed on the data structures are:

o Searching: We can search for any element in a data structure.

o Sorting: We can sort the elements of a data structure either in an ascending or descending
order.
o Insertion: We can also insert the new element in a data structure.
o Updation: We can also update the element, i.e., we can replace the element with another
element.
o Deletion: We can also perform the delete operation to remove the element from the data
structure.

A data structure is a way of organizing the data so that it can be used efficiently. Here, we have used
the word efficiently, which in terms of both the space and time. For example, a stack is an ADT
(Abstract data type) which uses either arrays or linked list data structure for the implementation.
Therefore, we conclude that we require some data structure to implement a particular ADT.

An ADT tells what is to be done and data structure tells how it is to be done. In other words, we can
say that ADT gives us the blueprint while data structure provides the implementation part. Now the
question arises: how can one get to know which data structure to be used for a particular ADT?.

As the different data structures can be implemented in a particular ADT, but the different
implementations are compared for time and space. For example, the Stack ADT can be implemented
by both Arrays and linked list. Suppose the array is providing time efficiency while the linked list is
providing space efficiency, so the one which is the best suited for the current user's requirements
will be selected.
Advantages of Data structures

The following are the advantages of a data structure:

o Efficiency: If the choice of a data structure for implementing a particular ADT is proper, it
makes the program very efficient in terms of time and space.
o Reusability: The data structure provides reusability means that multiple client programs can
use the data structure.
o Abstraction: The data structure specified by an ADT also provides the level of abstraction. The
client cannot see the internal working of the data structure, so it does not have to worry about
the implementation part. The client can only see the interface.

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. For example, we have some data
which has, player's name "Virat" and age 26. Here "Virat" is of String data type and 26 is
of integer data type.

We can organize this data as a record like Player record, which will have both player's name and
age in it. Now we can collect and store player's records in a file or database as a data structure. For
example: "Dhoni" 30, "Gambhir" 31, "Sehwag" 33

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

The data structures can also be classified on the basis of the following characteristics:

Characteristic Description

In Linear data structures, the data items are arranged in a linear sequence.
Linear
Example: Array

In Non-Linear data structures, the data items are not in sequence.

Non-Linear
Example: Tree, Graph

In homogeneous data structures, all the elements are of same type.

Homogeneous
Example: Array

Non- In Non-Homogeneous data structure, the elements may or may not be of the same
Homogeneous type. Example: Structures

Static data structures are those whose sizes and structures associated memory
Static
locations are fixed, at compile time. Example: Array

Dynamic structures are those which expands or shrinks depending upon the
Dynamic program need and its execution. Also, their associated memory locations changes.
Example: Linked List created using pointers

Data Type Data Structure

The data type is the form of a variable to

Data structure is a collection of different kinds of
which a value can be assigned. It defines
data. That entire data can be represented using an
that the particular variable will assign the
object and can be used throughout the program.
values of the given data type only.

It can hold value but not data. Therefore, it It can hold multiple types of data within a single
is dataless. object.

The implementation of a data type is Data structure implementation is known as

known as abstract implementation. concrete implementation.

There is no time complexity in the case of In data structure objects, time complexity plays an
data types. important role.
 Data Type Data Structure

While in the case of data structures, the data and

In the case of data types, the value of data
its value acquire the space in the computer’s main
is not stored because it only represents
memory. Also, a data structure can hold different
the type of data that can be stored.
kinds and types of data within one single object.

Data type examples are int, float, double, Data structure examples are stack, queue, tree,
etc. etc.

Need Of Data Structure:

The structure of the data and the synthesis of the algorithm are relative to each other. Data
presentation must be easy to understand so the developer, as well as the user, can make an
efficient implementation of the operation.
Data structures provide an easy way of organizing, retrieving, managing, and storing data.
Here is a list of the needs for data.
1. Data structure modification is easy.
2. It requires less time.
3. Save storage memory space.
4. Data representation is easy.
Easy access to the large database.

ARRAYS:
An array is a linear data structure and it is a collection of items stored at contiguous memory
locations. The idea is to store multiple items of the same type together in one place. It allows the
processing of a large amount of data in a relatively short period. The first element of the array is
indexed by a subscript of 0. There are different operations possible in an array, like Searching,
Sorting, Inserting, Traversing, Reversing, and Deleting.

Array

Characteristics of an Array:
An array has various characteristics which are as follows:
 Arrays use an index-based data structure which helps to identify each of the elements in an
array easily using the index.
 If a user wants to store multiple values of the same data type, then the array can be utilized
efficiently.
 An array can also handle complex data structures by storing data in a two-dimensional array.
 An array is also used to implement other data structures like Stacks, Queues, Heaps, Hash
tables, etc.
 The search process in an array can be done very easily.

Operations performed on array:

 Initialization: An array can be initialized with values at the time of declaration or later using an
assignment statement.
 Accessing elements: Elements in an array can be accessed by their index, which starts from 0
and goes up to the size of the array minus one.
 Searching for elements: Arrays can be searched for a specific element using linear search or
binary search algorithms.
 Sorting elements: Elements in an array can be sorted in ascending or descending order using
algorithms like bubble sort, insertion sort, or quick sort.
 Inserting elements: Elements can be inserted into an array at a specific location, but this
operation can be time-consuming because it requires shifting existing elements in the array.
 Deleting elements: Elements can be deleted from an array by shifting the elements that come
after it to fill the gap.
 Updating elements: Elements in an array can be updated or modified by assigning a new value
to a specific index.
 Traversing elements: The elements in an array can be traversed in order, visiting each element
once.
These are some of the most common operations performed on arrays. The specific operations and
algorithms used may vary based on the requirements of the problem and the programming
language used.
Applications of Array:
Different applications of an array are as follows:
 An array is used in solving matrix problems.
 Database records are also implemented by an array.
 It helps in implementing a sorting algorithm.
 It is also used to implement other data structures like Stacks, Queues, Heaps, Hash tables, etc.
 An array can be used for CPU scheduling.
 Can be applied as a lookup table in computers.
 Arrays can be used in speech processing where every speech signal is an array.
 The screen of the computer is also displayed by an array. Here we use a multidimensional array.
 The array is used in many management systems like a library, students, parliament, etc.
 The array is used in the online ticket booking system. Contacts on a cell phone are displayed by
this array.
 In games like online chess, where the player can store his past moves as well as current moves. It
indicates a hint of position.
 To save images in a specific dimension in the android Like 360*1200

Real-Life Applications of Array:

 An array is frequently used to store data for mathematical computations.
 It is used in image processing.
 It is also used in record management.
 Book pages are also real-life examples of an array.
 It is used in ordering boxes as well.
LINKED LIST:
A linked list is a linear data structure in which elements are not stored at contiguous memory
locations. The elements in a linked list are linked using pointers as shown in the below image:
Types of linked lists:
 Singly-linked list
 Doubly linked list
 Circular linked list
 Doubly circular linked list

Linked List

Characteristics of a Linked list:

A linked list has various characteristics which are as follows:
 A linked list uses extra memory to store links.
 During the initialization of the linked list, there is no need to know the size of the elements.
 Linked lists are used to implement stacks, queues, graphs, etc.
 The first node of the linked list is called the Head.
 The next pointer of the last node always points to NULL.
 In a linked list, insertion and deletion are possible easily.
 Each node of the linked list consists of a pointer/link which is the address of the next node.
 Linked lists can shrink or grow at any point in time easily.

Operations performed on Linked list:

A linked list is a linear data structure where each node contains a value and a reference to the next
node. Here are some common operations performed on linked lists:
 Initialization: A linked list can be initialized by creating a head node with a reference to the first
node. Each subsequent node contains a value and a reference to the next node.
 Inserting elements: Elements can be inserted at the head, tail, or at a specific position in the
linked list.
 Deleting elements: Elements can be deleted from the linked list by updating the reference of
the previous node to point to the next node, effectively removing the current node from the
list.
 Searching for elements: Linked lists can be searched for a specific element by starting from the
head node and following the references to the next nodes until the desired element is found.
 Updating elements: Elements in a linked list can be updated by modifying the value of a specific
node.
 Traversing elements: The elements in a linked list can be traversed by starting from the head
node and following the references to the next nodes until the end of the list is reached.
 Reversing a linked list: The linked list can be reversed by updating the references of each node
so that they point to the previous node instead of the next node.
These are some of the most common operations performed on linked lists. The specific operations
and algorithms used may vary based on the requirements of the problem and the programming
language used.
Applications of the Linked list:
Different applications of linked lists are as follows:
 Linked lists are used to implement stacks, queues, graphs, etc.
 Linked lists are used to perform arithmetic operations on long integers.
 It is used for the representation of sparse matrices.
 It is used in the linked allocation of files.
 It helps in memory management.
 It is used in the representation of Polynomial Manipulation where each polynomial term
represents a node in the linked list.
 Linked lists are used to display image containers. Users can visit past, current, and next images.
 They are used to store the history of the visited page.
 They are used to perform undo operations.
 Linked are used in software development where they indicate the correct syntax of a tag.
 Linked lists are used to display social media feeds.

Real-Life Applications of a Linked list:

 A linked list is used in Round-Robin scheduling to keep track of the turn in multiplayer games.
 It is used in image viewer. The previous and next images are linked, and hence can be accessed
by the previous and next buttons.
 In a music playlist, songs are linked to the previous and next songs.

STACK:
Stack is a linear data structure that follows a particular order in which the operations are
performed. The order is LIFO(Last in first out). Entering and retrieving data is possible from only one
end. The entering and retrieving of data is also called push and pop operation in a stack. There are
different operations possible in a stack like reversing a stack using recursion, Sorting, Deleting the
middle element of a stack, etc.
Characteristics of a Stack:
Stack has various different characteristics which are as follows:
 Stack is used in many different algorithms like Tower of Hanoi, tree traversal, recursion, etc.
 Stack is implemented through an array or linked list.
 It follows the Last In First Out operation i.e., an element that is inserted first will pop in last and
vice versa.
 The insertion and deletion are performed at one end i.e. from the top of the stack.
 In stack, if the allocated space for the stack is full, and still anyone attempts to add more
elements, it will lead to stack overflow.

Applications of Stack:
Different applications of Stack are as follows:
 The stack data structure is used in the evaluation and conversion of arithmetic expressions.
 Stack is used in Recursion.
 It is used for parenthesis checking.
 While reversing a string, the stack is used as well.
 Stack is used in memory management.
 It is also used for processing function calls.
 The stack is used to convert expressions from infix to postfix.
 The stack is used to perform undo as well as redo operations in word processors.
 The stack is used in virtual machines like JVM.
 The stack is used in the media players. Useful to play the next and previous song.
 The stack is used in recursion operations.

Operation performed on stack:

A stack is a linear data structure that implements the Last-In-First-Out (LIFO) principle. Here are
some common operations performed on stacks:
 Push: Elements can be pushed onto the top of the stack, adding a new element to the top of the
stack.
 Pop: The top element can be removed from the stack by performing a pop operation,
effectively removing the last element that was pushed onto the stack.
 Peek: The top element can be inspected without removing it from the stack using a peek
operation.
 IsEmpty: A check can be made to determine if the stack is empty.
 Size: The number of elements in the stack can be determined using a size operation.
These are some of the most common operations performed on stacks. The specific operations and
algorithms used may vary based on the requirements of the problem and the programming
language used. Stacks are commonly used in applications such as evaluating expressions,
implementing function call stacks in computer programs, and many others.
Real-Life Applications of Stack:
 Real life example of a stack is the layer of eating plates arranged one above the other. When
you remove a plate from the pile, you can take the plate to the top of the pile. But this is exactly
the plate that was added most recently to the pile. If you want the plate at the bottom of the
pile, you must remove all the plates on top of it to reach it.
 Browsers use stack data structures to keep track of previously visited sites.
 Call log in mobile also uses stack data structure.
QUEUE:
Queue is a linear data structure that follows a particular order in which the operations are
performed. The order is First In First Out(FIFO) i.e. the data item stored first will be accessed first. In
this, entering and retrieving data is not done from only one end. An example of a queue is any
queue of consumers for a resource where the consumer that came first is served first. Different
operations are performed on a Queue like Reversing a Queue (with or without using recursion),
Reversing the first K elements of a Queue, etc. A few basic operations performed In Queue are
enqueue, dequeue, front, rear, etc.

Characteristics of a Queue:
The queue has various different characteristics which are as follows:
 The queue is a FIFO (First In First Out) structure.
 To remove the last element of the Queue, all the elements inserted before the new element in
the queue must be removed.
 A queue is an ordered list of elements of similar data types.

Applications of Queue:
Different applications of Queue are as follows:
 Queue is used for handling website traffic.
 It helps to maintain the playlist in media players.
 Queue is used in operating systems for handling interrupts.
 It helps in serving requests on a single shared resource, like a printer, CPU task scheduling, etc.
 It is used in the asynchronous transfer of data e.g. pipes, file IO, and sockets.
 Queues are used for job scheduling in the operating system.
 In social media to upload multiple photos or videos queue is used.
 To send an e-mail queue data structure is used.
 To handle website traffic at a time queues are used.
 In Windows operating system, to switch multiple applications.

Operation performed on queue:

A queue is a linear data structure that implements the First-In-First-Out (FIFO) principle. Here are
some common operations performed on queues:
 Enqueue: Elements can be added to the back of the queue, adding a new element to the end of
the queue.
 Dequeue: The front element can be removed from the queue by performing a dequeue
operation, effectively removing the first element that was added to the queue.
 Peek: The front element can be inspected without removing it from the queue using a peek
operation.
 IsEmpty: A check can be made to determine if the queue is empty.
 Size: The number of elements in the queue can be determined using a size operation.
These are some of the most common operations performed on queues. The specific operations and
algorithms used may vary based on the requirements of the problem and the programming
language used. Queues are commonly used in applications such as scheduling tasks, managing
communication between processes, and many others.
Real-Life Applications of Queue:
 A real-world example of a queue is a single-lane one-way road, where the vehicle that enters
first will exit first.
 A more real-world example can be seen in the queue at the ticket windows.
 A cashier line in a store is also an example of a queue.
 People on an escalator

TREE:
A tree is a non-linear and hierarchal data structure where the elements are arranged in a tree-like
structure. In a tree, the topmost node is called the root node. Each node contains some data, and
data can be of any type. It consists of a central node, structural nodes, and sub-nodes which are
connected via edges. Different tree data structures allow quicker and easier access to the data as it
is a non-linear data structure. A tree has various terminologies like Node, Root, Edge, Height of a
tree, Degree of a tree, etc.
There are different types of Tree-like
 Binary Tree,
 Binary Search Tree,
 AVL Tree,
 B-Tree, etc.

Tree
Characteristics of a Tree:
The tree has various different characteristics which are as follows:
 A tree is also known as a Recursive data structure.
 In a tree, the Height of the root can be defined as the longest path from the root node to the
leaf node.
 In a tree, one can also calculate the depth from the top to any node. The root node has a depth
of 0.
Applications of Tree:
Different applications of Tree are as follows:
 Heap is a tree data structure that is implemented using arrays and used to implement priority
queues.
 B-Tree and B+ Tree are used to implement indexing in databases.
 Syntax Tree helps in scanning, parsing, generation of code, and evaluation of arithmetic
expressions in Compiler design.
 K-D Tree is a space partitioning tree used to organize points in K-dimensional space.
 Spanning trees are used in routers in computer networks.

Operation performed on tree:

A tree is a non-linear data structure that consists of nodes connected by edges. Here are some
common operations performed on trees:
 Insertion: New nodes can be added to the tree to create a new branch or to increase the height
of the tree.
 Deletion: Nodes can be removed from the tree by updating the references of the parent node
to remove the reference to the current node.
 Search: Elements can be searched for in a tree by starting from the root node and traversing the
tree based on the value of the current node until the desired node is found.
 Traversal: The elements in a tree can be traversed in several different ways, including in-order,
pre-order, and post-order traversal.
 Height: The height of the tree can be determined by counting the number of edges from the
root node to the furthest leaf node.
 Depth: The depth of a node can be determined by counting the number of edges from the root
node to the current node.
 Balancing: The tree can be balanced to ensure that the height of the tree is minimized and the
distribution of nodes is as even as possible.
These are some of the most common operations performed on trees. The specific operations and
algorithms used may vary based on the requirements of the problem and the programming
language used. Trees are commonly used in applications such as searching, sorting, and storing
hierarchical data.
Real-Life Applications of Tree:
 In real life, tree data structure helps in Game Development.
 It also helps in indexing in databases.
 A Decision Tree is an efficient machine-learning tool, commonly used in decision analysis. It has
a flowchart-like structure that helps to understand data.
 Domain Name Server also uses a tree data structure.
 The most common use case of a tree is any social networking site.
GRAPH:
A graph is a non-linear data structure that consists of vertices (or nodes) and edges. It consists of a
finite set of vertices and set of edges that connect a pair of nodes. The graph is used to solve the
most challenging and complex programming problems. It has different terminologies which are
Path, Degree, Adjacent vertices, Connected components, etc.

Graph

Characteristics of Graph:
The graph has various different characteristics which are as follows:
 The maximum distance from a vertex to all the other vertices is considered the Eccentricity of
that vertex.
 The vertex having minimum Eccentricity is considered the central point of the graph.
 The minimum value of Eccentricity from all vertices is considered the radius of a connected
graph.
Applications of Graph:
Different applications of Graphs are as follows:
 The graph is used to represent the flow of computation.
 It is used in modeling graphs.
 The operating system uses Resource Allocation Graph.
 Also used in the World Wide Web where the web pages represent the nodes.

Operation performed on Graph:

A graph is a non-linear data structure consisting of nodes and edges. Here are some common
operations performed on graphs:
 Add Vertex: New vertices can be added to the graph to represent a new node.
 Add Edge: Edges can be added between vertices to represent a relationship between nodes.
 Remove Vertex: Vertices can be removed from the graph by updating the references of
adjacent vertices to remove the reference to the current vertex.
 Remove Edge: Edges can be removed by updating the references of the adjacent vertices to
remove the reference to the current edge.
 Depth-First Search (DFS): A graph can be traversed using a depth-first search by visiting the
vertices in a depth-first manner.
 Breadth-First Search (BFS): A graph can be traversed using a breadth-first search by visiting the
vertices in a breadth-first manner.
 Shortest Path: The shortest path between two vertices can be determined using algorithms
such as Dijkstra’s algorithm or A* algorithm.
 Connected Components: The connected components of a graph can be determined by finding
sets of vertices that are connected to each other but not to any other vertices in the graph.
 Cycle Detection: Cycles in a graph can be detected by checking for back edges during a depth-
first search.
These are some of the most common operations performed on graphs. The specific operations and
algorithms used may vary based on the requirements of the problem and the programming
language used. Graphs are commonly used in applications such as computer networks, social
networks, and routing problems.
Real-Life Applications of Graph:
 One of the most common real-world examples of a graph is Google Maps where cities are
located as vertices and paths connecting those vertices are located as edges of the graph.
 A social network is also one real-world example of a graph where every person on the network
is a node, and all of their friendships on the network are the edges of the graph.
 A graph is also used to study molecules in physics and chemistry.

Advantages of data structure:

1. Improved data organization and storage efficiency.
2. Faster data retrieval and manipulation.
3. Facilitates the design of algorithms for solving complex problems.
4. Eases the task of updating and maintaining the data.
5. Provides a better understanding of the relationships between data elements.

Disadvantage of Data Structure:

1. Increased computational and memory overhead.
2. Difficulty in designing and implementing complex data structures.
3. Limited scalability and flexibility.
4. Complexity in debugging and testing.
5. Difficulty in modifying existing data structures.
BINARY SEARCH TREE (BST)

 The binary search tree is a node – based non linear data structure that analyzes the node,
its left, and right branches, and arranged in a tree structure format.

Binary Search Tree (BST) follows the following two properties,

 The value of the key of the left sub-tree is less than the value of its parent (root) node's key.
 The value of the key of the right sub-tree is greater than or equal to the value of its parent
(root) node's key.

Basic operations performed by BST are search, insert, pre-order, in-order, and post-order traversal.

Features of BST:

 Nodes of the tree are represented in a parent-child relationship

 Each parent node can have zero child nodes or a maximum of two subnodes or subtrees on
the left and right sides.
 Every sub-tree, also known as a binary search tree, has sub-branches on the right and left of
themselves.
 All the nodes are linked with key-value pairs.
 The keys of the nodes present on the left subtree are smaller than the keys of their parent
node
 Similarly, The left subtree nodes’ keys have lesser values than their parent node’s keys.
 The keys of the nodes present on the right subtree are greater than the keys of their parent
node
 Similarly, The right subtree nodes’ keys have greater values than their parent node’s keys.

Binary Search Tree Traversal – Inorder, Preorder, Post Order for BST
 In this tutorial, you will learn what a binary search tree is, what parts make up a tree, and some of
the common terms we use when describing parts of a tree.

We will also see how to traverse a tree using some of the common algorithms – all illustrated with
clear examples.

The root node is the parent node of both subtrees.

The diagram below shows the main parts of a binary tree:

Diagram of a binary search tree

Let's us look at the relationship between the nodes.

 A is the root node.

 The left subtree begins at B while the right subtree begins at C.
 Node A has two child nodes – B and C.
 Node C is the parent node to F and G. F and G are siblings.
 Node F and G are know as leaf nodes because they do not have children.
 Node B is the parent node to D and E.
 Node D is the parent node to H and I.
 D and E are siblings as well as H and I.
 Node E is a leaf node.
So here are some important terms that we just used to describe the tree above:

Root: The topmost node in the tree.

Parent: A node with a child or children.
Child: A node extended from another node (parent node).
Leaf: A node without a child.
 What Is a Binary Search Tree Used For?
Binary search trees help us speed up our binary search as we are able to find items faster.

We can use the binary search tree for the addition and deletion of items in a tree.

We can also represent data in a ranked order using a binary tree. And in some cases, it can be used
as a chart to represent a collection of information.

Next, we'll look at some techniques used in traversing a binary tree.

What is Tree Traversal?

Traversing a tree means visiting and outputting the value of each node in a particular order. In this
tutorial, we will use the Inorder, Preorder, and Post order tree traversal methods.

The major importance of tree traversal is that there are multiple ways of carrying out traversal
operations unlike linear data structures like arrays, bitmaps, matrices where traversal is done in a
linear order.

Each of these methods of traversing a tree have a particular order they follow:

 For Inorder, you traverse from the left subtree to the root then to the right subtree.
 For Preorder, you traverse from the root to the left subtree then to the right subtree.
 For Post order, you traverse from the left subtree to the right subtree then to the root.
Here is another way of representing the information above:

Inorder => Left, Root, Right.

Preorder => Root, Left, Right.

Post order => Left, Right, Root.

How to Traverse a Tree Using Inorder Traversal

We are going to create a tree similar to the one in the last section, but this time the node keys will
be numbers instead of letters.

Remember that the values of the nodes on the left subtree are always smaller than the value of the
root node. Also, the values of the nodes on the right subtree are larger than the value of the root
node.

Here is the diagram we will be working with:

Recall that the order for inorder traversal is Left, Root, Right.

This is the result we get after using inorder traversal:

D, B, E, A, F, C, G
If that seems a bit complex for you to understand, then follow the order of the colors in the picture
below

Inorder traversal
How to Traverse a Tree Using Preorder Traversal
The order here is Root, Left, Right.

Using the same diagram above, we have:

A, B, D, E, C, F, G
Here is the same diagram with different colors used as a guide:
Preorder traversal

How to Traverse a Tree Using Postorder Traversal

The order for post order traversal is Left, Right, Root.

Here is the output:

D, E, B, F, G, C, A
If you can't figure out how we arrived at that result, then use the colors in the picture below as a
guide:

Postorder traversal
Example 1
Binary Search Tree (BST) for the following sequence of numbers-
47, 55, 23, 17, 39, 11, 50,
Always consider the first element as the root node. Consider the given elements and insert them in
the BST one by one.

Answer: