Data structure and algorithms using C, C++, Java, JavaScript

Algorithms

In the last video, we came across the applications of data structures and in this video, we will discuss algorithms.

Algorithms are step-by-step procedures or sets of rules designed to perform specific tasks or solve particular problems. They provide a systematic way to carry out a computational process, guiding the execution of operations to achieve desired outcomes. Algorithms are fundamental to computer science and play a central role in various applications, from sorting and searching data to complex tasks in artificial intelligence and machine learning.

Characteristic of algorithms

• Well-defined: Algorithms must have precisely defined and unambiguous instructions. Each step in the algorithm should be clearly and accurately specified.
  

• Input: An algorithm takes input from a specified set, which is processed to produce the desired output. The input can vary, and the algorithm should be designed to handle different inputs.
  

• Output: Algorithms produce an output that is related to the input by a clear set of rules. The output should represent a solution to the problem or the result of the algorithmic process.
  

• Finiteness: An algorithm must be composed of a finite number of steps. It should eventually terminate after executing a finite sequence of operations.
  

• Effectiveness: Every step of the algorithm must be effective, meaning it can be executed precisely and in a reasonable amount of time. The operations involved should be feasible with the available resources.
  

• Unambiguous: Each step of the algorithm must be free from ambiguity or multiple interpretations. The instructions should be straightforward and leave no room for confusion.
  

• Generality: An algorithm should be designed to handle a broad range of input cases, not just specific instances. It should be applicable to a general class of problems.
  

• Independence: The steps of an algorithm should be independent, meaning the execution of one step does not depend on the outcome of another. This allows for parallelisation and optimisation.
  

• Deterministic: An algorithm should be deterministic, meaning that given the same input, it will produce the same output every time it is executed. Randomness in algorithms is introduced through specific mechanisms.
  

• Correctness: An algorithm should produce the correct output for all valid inputs. It should solve the intended problem and adhere to the specifications.
  

• Resource Efficiency: While solving a problem, an algorithm should use resources (such as time and memory) judiciously. Efficiency is often a critical factor in evaluating the quality of an algorithm.
  

• Scalability: A good algorithm should be scalable, meaning it can handle larger inputs or datasets without a disproportionate increase in resources or time.
  

Understanding and applying these characteristics are essential when designing algorithms to ensure their reliability, efficiency, and effectiveness in solving computational problems.

Data flow of the algorithm

The term "data flow of an algorithm" typically refers to how data is processed and transferred within the steps of the algorithm. Here's a general overview of the data flow in an algorithm:

• Input:

  • The algorithm begins by taking input data, which could be values, variables, or information needed for the algorithm to perform its task.

• Processing Steps:

  • The algorithm consists of a sequence of steps, each specifying operations to be performed on the input data. These steps manipulate and transform the data according to the logic of the algorithm.

• Intermediate Data:

  • As the algorithm progresses through its steps, intermediate data is generated. This data represents the evolving state of the computation and is often used in subsequent steps.

• Control Structures:

  • The algorithm may include control structures such as loops and conditionals that determine the flow of execution based on certain conditions. These structures influence how data is processed and may lead to repeated or conditional execution of certain steps.

• Output Data:

  • Ultimately, the algorithm produces output data as a result of the processing steps. This output is the desired outcome or solution to the problem the algorithm is designed to address.

• Data Transfer:

  • Data is transferred between steps of the algorithm. For example, the output of one step might become the input for the next step. This transfer of data ensures that the algorithm can carry out a coherent and logical sequence of operations.

• Memory or Storage:

  • In some cases, algorithms may involve the use of memory or storage to temporarily hold and retrieve data. This could be in the form of variables, arrays, or other data structures.

• Recursion (if applicable):

  • In recursive algorithms, a function or procedure may call itself, leading to a nested series of calls. Each recursive call operates on a subset of the data, contributing to the overall data flow.

Understanding the data flow of an algorithm is crucial for analysing its efficiency, identifying potential bottlenecks, and ensuring that the algorithm produces the correct output. This perspective helps programmers and analysts optimise algorithms and troubleshoot issues related to data processing within the computational steps.

Why do we need algorithms?

Algorithms are essential in computer science and various aspects of problem-solving for several reasons:

• Problem Solving: Algorithms provide systematic and structured approaches to problem-solving. They offer step-by-step procedures for tackling complex issues and achieving desired outcomes.
  

• Efficiency: Algorithms contribute to the development of efficient solutions. They help optimize processes, reduce resource usage, and enhance the overall performance of computational tasks.
  

• Reproducibility: Algorithms ensure that a specific set of instructions can be consistently followed to achieve the same result. This reproducibility is crucial for reliability in various applications.
  

• Automation: Algorithms enable automation by defining a set of instructions that can be executed by a computer without constant human intervention. This is fundamental for streamlining repetitive tasks.
  

• Scalability: Well-designed algorithms can handle larger datasets or increasingly complex problems without a disproportionate increase in resources, making them scalable for various applications.
  

• Consistency: Algorithms provide a consistent and logical framework for solving problems. This consistency is crucial in producing reliable results across different scenarios.
  

• Precision: Algorithms can be designed to execute tasks with precision, ensuring accuracy and reducing the likelihood of errors in calculations or decision-making processes.
  

• Optimization: Algorithms help optimize processes by finding the most efficient way to accomplish a task. This is particularly important in resource-constrained environments.
  

• Decision-Making: Algorithms are used in decision-making processes, ranging from business strategies to artificial intelligence applications. They assist in analyzing data and deriving insights to support informed decisions.
  

• Standardization: Algorithms offer standardized approaches to problem-solving. This standardization allows for the development of consistent methodologies across different applications and industries.
  

• Adaptability: Algorithms can be adapted to different contexts and applications, making them versatile tools for solving a wide range of problems.
  

• Technological Advancement: Algorithms drive innovation and technological advancement. They are foundational to the development of software, artificial intelligence, machine learning, and various computational technologies.
  

• Scientific Research: Algorithms play a crucial role in scientific research, assisting researchers in analyzing data, modelling phenomena, and simulating complex systems.
  

In summary, algorithms are indispensable in the field of computer science and problem-solving. They provide structured, efficient, and scalable solutions to a myriad of challenges, contributing to the advancement of technology, automation, and our ability to solve complex problems.

Example

Let's consider a real-world example to understand algorithms:

Task: Prepare a refreshing glass of lemonade.

Algorithm: Step-by-Step Instructions

Step - 1

• Gather Ingredients:

  • Collect the necessary ingredients: lemons, sugar, water, and ice.

Step - 2

• Wash and Cut Lemons:

  • Wash the lemons thoroughly.

  • Cut the lemons in half.

Step - 3

• Extract Lemon Juice:

  • Squeeze the lemon halves to extract the juice.

  • Use a strainer to separate seeds and pulp from the juice.

Step - 4

• Prepare Simple Syrup (Optional):

  • In a separate container, dissolve sugar in warm water to make a simple syrup. Adjust sweetness according to preference.

Step - 5

• Mix Lemon Juice and Simple Syrup:

  • Combine the freshly squeezed lemon juice with the prepared simple syrup. Adjust the ratio to achieve the desired sweetness.

Step - 6

• Add Water:

  • Dilute the lemon-sugar mixture with cold water. Adjust the water quantity based on taste preferences.

Step 7

• Stir Well:

  • Mix the ingredients thoroughly to ensure an even distribution of flavors.

Step - 8

• Taste and Adjust:

  • Taste the lemonade and adjust the sweetness or tartness by adding more sugar, water, or lemon juice as needed.

Step - 9

• Serve:

  • Pour the prepared lemonade into glasses over ice.

Real-world analogy:

Imagine you're following a recipe to make lemonade, carefully measuring and mixing each ingredient to create a delicious and refreshing beverage.

Algorithm Analysis:

• Input: Lemons, sugar, water, and ice.

• Processing: The sequence of steps involving squeezing, mixing, and adjusting ingredients.

• Output: A glass of freshly prepared lemonade.

Factors of algorithms

The design and evaluation of algorithms involve considering various factors to ensure their effectiveness and efficiency. Here are key factors to consider when working with algorithms:

• Time Complexity:

  • Definition: The measure of the amount of time an algorithm takes to complete as a function of the input size.

  • Importance: A crucial factor in determining the efficiency of an algorithm. Algorithms with lower time complexity are generally preferred.

• Space Complexity:

  • Definition: The measure of the amount of memory or storage space an algorithm requires as a function of the input size.

  • Importance: Efficient use of memory is essential for optimal algorithm performance. Lower space complexity is generally desirable.

• Correctness:

  • Definition: The algorithm should produce the correct output for all valid inputs.

  • Importance: The fundamental requirement of any algorithm. Incorrect algorithms can lead to flawed results and unreliable computations.

• Simplicity and Clarity:

  • Definition: The algorithm should be straightforward, easy to understand, and not overly complex.

  • Importance: Simple and clear algorithms are easier to maintain, debug, and modify. They enhance collaboration among developers.

• Robustness:

  • Definition: The ability of an algorithm to handle unexpected inputs or situations without crashing or producing incorrect results.

  • Importance: Robust algorithms are more reliable in real-world scenarios where inputs may deviate from the expected.

• Scalability:

  • Definition: The ability of an algorithm to handle larger inputs or increasing workloads without a significant increase in resources or time.

  • Importance: Scalable algorithms are crucial for applications dealing with growing datasets or expanding user bases.

• Adaptability:

  • Definition: The ability of an algorithm to adapt to different scenarios or requirements.

  • Importance: Algorithms that can be easily adapted are more versatile and can be reused in various contexts.

• Optimality:

  • Definition: An algorithm is considered optimal if it produces the best possible result within certain constraints.

  • Importance: In situations where resources are limited, finding optimal solutions is crucial.

• Parallelism:

  • Definition: The extent to which an algorithm can be parallelized, allowing multiple computations to occur simultaneously.

  • Importance: In modern computing environments, parallel algorithms can take advantage of multi-core processors for improved performance.

• Quantifiability:

  • Definition: The ability to measure and analyze the performance of an algorithm using quantitative metrics.

  • Importance: Quantifiable factors, such as time and space complexity, provide a basis for comparing and evaluating different algorithms.

• Versatility:

  • Definition: The ability of an algorithm to be applied in various contexts and solve a range of related problems.

  • Importance: Versatile algorithms can be reused in different applications, promoting code efficiency and maintainability.

Understanding and balancing these factors is crucial for developing algorithms that meet the specific requirements and constraints of different computational tasks.

Importance of Algorithms:

• Problem Solving:

  • Significance: Algorithms provide systematic and structured approaches to problem-solving, allowing for efficient and effective solutions.

• Efficiency:

  • Significance: Well-designed algorithms optimize resource usage, leading to faster execution times, reduced energy consumption, and improved overall system performance.

• Reproducibility:

  • Significance: Algorithms enable the replication of solutions across different platforms and programming languages, fostering collaboration and standardization.

• Automation:

  • Significance: Algorithms automate processes, enabling systems to perform tasks, analyze data, and make decisions without continuous human intervention.

• Data Processing:

  • Significance: Algorithms are fundamental for data processing, including sorting, searching, filtering, and transforming data, facilitating meaningful insights from large datasets.

• Computational Complexity:

  • Significance: Understanding computational complexity helps in selecting appropriate algorithms, balancing time and space efficiency for different problem scenarios.

• Scientific Advancements:

  • Significance: Algorithms are vital for scientific research, aiding in solving complex equations, simulating physical processes, and conducting experiments in silico.

• Artificial Intelligence and Machine Learning:

  • Significance: Algorithms form the backbone of AI and ML, powering tasks like pattern recognition, classification, regression, and optimization for data-driven decision-making.

• Communication and Networking:

  • Significance: Algorithms are crucial in designing efficient communication protocols and network routing strategies, ensuring reliable data transfer between devices.

• Cryptography and Security:

  • Significance: Algorithms underpin secure communication through encryption and hashing, safeguarding data confidentiality and integrity.

• Optimization Problems:

  • Significance: Algorithms are employed to find optimal solutions in various domains, such as resource allocation, scheduling, and logistics, improving decision-making processes.

• Innovation and Technology Advancements:

  • Significance: The development of new algorithms often leads to technological breakthroughs, driving progress in fields from computer graphics to computational biology.

Issues with Algorithms:

• Algorithmic Bias and Fairness:

  • Challenge: Algorithms can perpetuate biases present in training data, leading to discriminatory outcomes, especially in machine learning applications.

• Transparency and Explainability:

  • Challenge: Some complex algorithms lack transparency, making it challenging to understand and explain their decisions, raising concerns about accountability and trust.

• Data Quality and Integrity:

  • Challenge: Algorithms heavily depend on the quality and integrity of data; inaccurate or biased data can lead to flawed outcomes.

• Overfitting and Generalization:

  • Challenge: Overfitting occurs when algorithms are too closely tailored to training data, negatively impacting performance on new, unseen data.

• Computational Complexity:

  • Challenge: High computational complexity in some algorithms can make them resource-intensive and impractical for certain applications.

• Security Concerns:

  • Challenge: Algorithms may be vulnerable to attacks, such as adversarial attacks in machine learning or vulnerabilities in cryptographic algorithms.

• Ethical Considerations:

  • Challenge: Ethical issues may arise when algorithms are used in decision-making processes, leading to concerns about privacy, consent, and fairness.

• User Acceptance and Bias Amplification:

  • Challenge: Algorithms may not always align with human values, leading to resistance and lack of acceptance. Biases in training data can be amplified, reinforcing stereotypes.

• Environmental Impact:

  • Challenge: Resource-intensive algorithms, particularly in deep learning, can contribute to significant energy consumption, raising environmental concerns.

• Regulatory and Legal Challenges:

  • Challenge: The rapid advancement of technology has outpaced the development of regulatory frameworks, leading to uncertainties in legal and ethical considerations.

Addressing these issues requires interdisciplinary collaboration, ethical considerations, and ongoing efforts to ensure that algorithms are designed and deployed responsibly and with societal well-being in mind.

ARRAY

An array is a data structure that stores a collection of elements, where each element can be accessed using an index or a key. Arrays are used to organize and store data systematically, making it easy to perform various operations on the elements. Here are some key properties and characteristics of arrays:

• Homogeneous Elements:

  • Arrays typically store elements of the same data type. For example, an array of integers will only contain integer values, and an array of strings will only contain string values.

• Fixed Size:

  • In most programming languages, arrays have a fixed size, meaning that once the array is created, its size cannot be changed. If you need a dynamic size, other data structures like lists or dynamic arrays may be more suitable.

• Contiguous Memory Allocation:

  • Array elements are stored in contiguous memory locations. This means that the memory addresses of consecutive elements in the array are adjacent.

• Zero-based Indexing:

  • In many programming languages, array indices start from 0. This means that the first element in the array is accessed using the index 0, the second element with index 1, and so on.

• Random Access:

  • Arrays support random access, meaning that you can directly access any element in the array using its index. This allows for efficient and constant-time access to individual elements.

• Ordered Elements:

  • The order of elements in an array is determined by their indices. This order is maintained throughout the lifetime of the array unless explicitly modified.

• Efficient for Iteration:

  • Iterating over the elements of an array is usually more efficient than other data structures, as the elements are stored in contiguous memory locations.

• Common Operations:

  • Arrays support common operations such as inserting, updating, and deleting elements. However, some of these operations may be less efficient than in other data structures, especially if the array needs to be resized.

Representation of Array

The representation of an array depends on the programming language. However, I'll provide a general explanation of how arrays are represented in memory, using a one-dimensional array as an example.

In memory, an array is a contiguous block of memory locations, and each element of the array is stored at a specific memory address. The memory addresses for the elements are determined based on the data type and the size of each element.

Let's consider an example of an array of integers in C:

c

int myArray[5] = {1, 2, 3, 4, 5};

Here,

int is a type.

myArray is an array of 5 integers,

5 is the size of the array

and these integers are elements of the array.

In memory, it might be represented like this:

| Element 0 | Element 1 | Element 2 | Element 3 | Element 4 | --

-----| 1 |                   |2 |               |3 |                |4 |                 |5 | ---

In this representation:

• Each element of the array is stored in a contiguous block of memory.

• The size of each element is determined by its data type (e.g., int in this case).

• The elements are accessed using indices (0 to 4 in this case) as the array index starts from zero

• The memory addresses of consecutive elements are sequential.

In languages like C or C++, you can use pointer arithmetic to navigate through the array elements based on memory addresses.

In languages like Python, arrays are implemented as lists, and the representation might be more abstract. Python lists are dynamic arrays, and their elements can be of different data types. The internal details of the implementation may vary based on the Python interpreter.

Understanding the memory representation of arrays is essential for optimizing algorithms and data access

Accessing elements from an array in different programming languages like C, C++, Java, Python, JavaScript and Ruby

To access an element from an array, we use the index

corresponding to the position of the element in the array.

The index is typically an integer value that starts at 0 for the first element

and increments by 1 for each subsequent element.

Here's how you can access elements from an array in different programming languages:

Let's go through accessing elements from an array in different programming languages with code snippets and breakdowns:

1. C:

In the language C

int myArray[5] = {1, 2, 3, 4, 5}; int element = myArray[2]; // Accessing the third element (index 2)

• Breakdown:

  • int myArray[5]: Declares an array named myArray that can hold integers.

  • {1, 2, 3, 4, 5}: Initializes the array with values 1, 2, 3, 4, and 5.

  • myArray[2]: Accesses the third element of the array (index 2).

2. C++:

int myArray[5] = {1, 2, 3, 4, 5}; int element = myArray[2]; // Accessing the third element (index 2)

• Breakdown:

  • Similar to C, C++ supports the same array syntax.

3. Java:

int[] myArray = {1, 2, 3, 4, 5}; int element = myArray[2]; // Accessing the third element (index 2)

• Breakdown:

  • int[] myArray: Declares an array named myArray that can hold integers.

  • {1, 2, 3, 4, 5}: Initializes the array with values 1, 2, 3, 4, and 5.

  • myArray[2]: Accesses the third element of the array (index 2).

4. Python:

my_array = [1, 2, 3, 4, 5] element = my_array[2] # Accessing the third element (index 2)

• Breakdown:

  • my_array: Declares a list named my_array with values 1, 2, 3, 4, and 5.

  • my_array[2]: Accesses the third element of the list (index 2).

5. JavaScript:

var myArray = [1, 2, 3, 4, 5]; var element = myArray[2]; // Accessing the third element (index 2)

• Breakdown:

  • var myArray: Declares an array named myArray with values 1, 2, 3, 4, and 5.

  • myArray[2]: Accesses the third element of the array (index 2).

6. Ruby:

my_array = [1, 2, 3, 4, 5] element = my_array[2] # Accessing the third element (index 2)

• Breakdown:

  • my_array: Declares an array named my_array with values 1, 2, 3, 4, and 5.

  • my_array[2]: Accesses the third element of the array (index 2).

In each case, the breakdown explains the declaration, initialisation, and access of elements in the respective programming language.

The specific syntax might vary, but the basic concept of array access remains consistent.

Operations of Array

Arrays support various operations for manipulating and accessing their elements.

Here are some common operations performed on arrays:

I am going to explain the operations in the programming language C.

You can download the PDF file for other programming language explanations.

So let’s begin.

C language supports various operations that allow you to organize and manipulate data efficiently.

1. Declaration and Initialization:

we will Declare an array and initialize it with values.

first we will do

Array Declaration:

int myArray[5]: Declares an array named myArray capable of holding integers, and its size is specified as 5.

Initialization:

{1, 2, 3, 4, 5}: Initializes the array with the values 1, 2, 3, 4, and 5. The values are assigned to the elements of the array in order.

So, after this line of code, the array myArray is created and

contains the values:

myArray[0] = 1

myArray[1] = 2

myArray[2] = 3

myArray[3] = 4

myArray[4] = 5

In C, array indices start from 0,

so myArray[0] represents the first element,

myArray[1] the second element,

and so on.

The array is of size 5, and indices range from 0 to 4.

2. Accessing Elements:

we have already discussed the accessing elements from an array in our previous video, now let us have a quick look at it.

so let us Retrieve the value of an element at a specific index.

Accessing Element:

myArray[2]: Accesses the third element of the array myArray. In C, array indices start from 0, so myArray[2] refers to the third element (index 2).

Assignment to Variable:

int element = myArray[2];: Assigns the value of the third element to the variable element. After this line, the variable element contains the value of myArray[2].

So, if we consider the array myArray from the previous example:

myArray[0] = 1

myArray[1] = 2

myArray[2] = 3 // This is the accessed element

myArray[3] = 4

myArray[4] = 5

• After this line of code, the variable element will have the value 3.
  

In summary, this line of code retrieves the value of the third element in the array myArray (at index 2) and assigns it to the variable element.

3. Updating Elements:

Modify the value of an element at a specific index.

myArray[2] = 10; // Updating the third element (index 2)

• Updating Element:

  • myArray[2]: Refers to the third element of the array myArray. In C, array indices start from 0, so myArray[2] represents the third element at index 2.

• Assignment:

  • myArray[2] = 10;: Assigns the value 10 to the third element of the array myArray.

• If we consider the array myArray:
  

myArray[0] = 1

myArray[1] = 2

myArray[2] = 10 // This is the updated element

myArray[3] = 4

myArray[4] = 5

• After this line of code, the value of the third element in the array has been updated to 10.
  

In summary, this line of code modifies the value of the third element in the array myArray (at index 2) and sets it to 10.

4. Insertion:

Add a new element to the array.

This may involve shifting existing elements to accommodate the new ones.

// Inserting a new element at the third position (index 2) for (int i = 4; i > 2; i--) { myArray[i] = myArray[i - 1]; } myArray[2] = 6;

• For Loop:

  • for (int i = 4; i > 2; i--) {: Initiates a loop starting from index 4 and moving towards index 2, iterating over elements that need to be shifted.

• Shifting Elements to Make Space:

  • myArray[i] = myArray[i - 1];: Shifts each element to the right by one position, starting from the last element and moving towards the third position. This loop effectively makes space for the new element.

• After the loop, the array may look like this:
  

myArray[0] = 1

myArray[1] = 2

myArray[2] = 2 // Original value at index 1 is now at index 2

myArray[3] = 3 // Original value at index 2 is now at index 3

myArray[4] = 4 // Original value at index 3 is now at index 4

Inserting the New Element:

• myArray[2] = 6;: Inserts the new element (6) at the third position (index 2), effectively completing the insertion.

After this line of code, the array will look like this:

myArray[0] = 1

myArray[1] = 2

myArray[2] = 6 // New element

myArray[3] = 3

myArray[4] = 4

In summary, the provided code inserts a new element (6) at the third position (index 2) of the array myArray by shifting existing elements to make space.

5. Deletion:

Remove an element from the array. This may involve shifting elements to close the gap.

// Deleting the third element (index 2) by shifting elements for (int i = 2; i < 4; i++) { myArray[i] = myArray[i + 1]; }

• For Loop:

  • for (int i = 2; i < 4; i++) {: Initiates a loop starting from index 2 and ending at index 3, iterating over elements that need to be shifted.

• Shifting Elements to Close the Gap:

  • myArray[i] = myArray[i + 1];: Shifts each element to the left by one position, starting from the third element (index 2) and moving towards the fourth position. This loop effectively removes the third element by overwriting it with the value of the next element.

• After the loop, the array may look like this:
  

myArray[0] = 1

myArray[1] = 2

myArray[2] = 4 // Original value at index 3 is now at index 2

myArray[3] = 4 // Original value at index 4 is now at index 3

myArray[4] = 5 // The value at the last index remains unchanged

This code effectively removes the third element at index 2 by shifting the subsequent elements to fill the gap. Keep in mind that the last element in the array may remain unchanged after this operation.

6. Finding Length/Size:

Determine the number of elements in the array.

int length = sizeof(myArray) / sizeof(myArray[0]);

• Size of the Whole Array:

  • sizeof(myArray): Returns the total size (in bytes) occupied by the entire array. This includes all elements and any potential padding added by the compiler.

• Size of a Single Element:

  • sizeof(myArray[0]): Returns the size (in bytes) of a single element in the array. Since arrays in C are homogeneous, the size of one element is the same for all elements in the array.

• Division and Assignment:

  • sizeof(myArray) / sizeof(myArray[0]): Divides the total size of the array by the size of a single element. This gives the number of elements in the array.

• Assignment to Variable:

  • int length = ...: Assigns the result of the division to the variable length. This variable now represents the number of elements in the array.

• If myArray is an array of integers, and let's say sizeof(int) is 4 (assuming a 32-bit system):
  

sizeof(myArray) = 5 * 4 = 20 bytes

sizeof(myArray[0]) = 4 bytes

length = 20 / 4 = 5

Therefore, after this line of code, the variable length will have the value 5, indicating the number of elements in the array myArray.

7. Iteration:

Iterate through all elements of the array.

for (int i = 0; i < 5; i++) { printf("%d ", myArray[i]); }

• For Loop Initialization:

  • for (int i = 0; i < 5; i++) {: Initializes a for loop that starts with i set to 0 and iterates while i is less than 5. After each iteration, i is incremented by 1.

• Loop Body:

  • printf("%d ", myArray[i]);: Within the loop, this statement prints the value of the current element at index i in the array myArray. The %d is a format specifier for printing integers.

• Inside the loop, the code performs the following iterations:

Iteration 1 (i = 0): Prints myArray[0], which is the first element.

Iteration 2 (i = 1): Prints myArray[1], the second element.

Iteration 3 (i = 2): Prints myArray[2], the third element.

Iteration 4 (i = 3): Prints myArray[3], the fourth element.

Iteration 5 (i = 4): Prints myArray[4], the fifth element.

• Loop Termination:

  • The loop continues as long as i is less than 5, and after the fifth iteration, the loop terminates.

The output of this loop would be the values of the elements in the array myArray printed with spaces between them. If myArray is {1, 2, 3, 4, 5}, the output would be:

1 2 3 4 5

Each element is printed with a space after it.

8. Searching:

Find the index of a specific value in the array.

int searchValue = 3; int index = -1; for (int i = 0; i < 5; i++) { if (myArray[i] == searchValue) { index = i; break; } }

• Initialization:

  • int searchValue = 3;: Specifies the value to be searched for in the array.

  • int index = -1;: Initializes the variable index to -1, indicating that the search value has not been found initially.

• For Loop Initialization:

  • for (int i = 0; i < 5; i++) {: Initializes a for loop that iterates through the elements of the array from index 0 to 4.

• Conditional Check:

  • if (myArray[i] == searchValue) {: Checks if the current element at index i is equal to the search value (3 in this case).

• Update Index and Break:

  • index = i;: If the search value is found, updates the index variable with the current index i.

  • break;: Exits the loop as soon as the search value is found. Since we are looking for the first occurrence, there's no need to continue searching.

After this loop, the variable index will contain the index of the first occurrence of the search value in the array, or it will remain -1 if the value is not found.

If myArray is {1, 2, 3, 4, 5}, and searchValue is 3, the loop will find the value at index 2, and index will be updated to 2. If searchValue were, for example, 6, index would remain -1, indicating that the value was not found in the array.

9. Sorting:

Arrange the elements of the array in a specific order. Common sorting algorithms include bubble sort, selection sort, and insertion sort.

// Implement a sorting algorithm (e.g., bubble sort)

We will see the sorting operation in detail in upcoming chapters.

These operations are crucial for working with arrays in the context of data structures in C,

and they form the basis for various algorithms and data manipulation tasks.

For other language reference please download the document provided in the course material.

Advantages of arrays

Arrays offer several advantages in programming due to their simplicity and efficiency in certain scenarios. Here are some key advantages of using arrays:

• Random Access:

  • Elements in an array can be accessed directly using their index. This allows for constant-time complexity for read and write operations, making access to elements efficient (O(1)).

• Sequential Storage:

  • Arrays store elements in contiguous memory locations. This sequential storage ensures better cache locality, potentially improving access times and system performance.

• Simplicity and Ease of Use:

  • Arrays are simple and intuitive data structures. They provide a straightforward way to organize and access a collection of elements of the same data type.

• Fixed Size:

  • The fixed size of arrays can be an advantage when the number of elements is known in advance. It allows for efficient memory allocation and can eliminate the need for dynamic memory management.

• Memory Efficiency:

  • Arrays are memory-efficient, as they do not incur the overhead associated with more complex data structures. Each element in an array occupies a fixed amount of memory.

• Performance in Mathematical Operations:

  • Arrays are well-suited for mathematical operations on large datasets. Many mathematical and scientific computations can be optimized using arrays and vectorized operations.

• Compatibility with Low-Level Operations:

  • Arrays are compatible with low-level memory operations and are often used in systems programming and embedded systems where direct memory manipulation is important.

• Efficient Traversal:

  • Traversing an array is a simple and efficient operation. Looping through elements using a for loop is a common and effective pattern.

• Efficient for Known Data Size:

  • When the number of elements is known and does not change frequently, arrays provide a concise and efficient way to store and retrieve data.

• Ease of Implementation:

  • Arrays are supported by virtually all programming languages and are usually among the first data structures introduced in programming courses. They are easy to declare, initialize, and use.

While arrays have these advantages, it's important to note that they may not be the best choice for all scenarios, particularly when dynamic resizing, insertion, or deletion of elements are frequent requirements. In such cases, other data structures like linked lists or dynamic arrays may be more suitable.

Disadvantages of Arrays

While arrays have several advantages, they also come with certain disadvantages that make them less suitable for certain scenarios. Here are some of the main disadvantages of using arrays:

• Fixed Size:

  • One of the significant drawbacks of arrays is their fixed size. The size of an array must be specified at the time of declaration, and it cannot be easily changed during runtime. This limitation can lead to either wasted memory or insufficient space for data.

• Memory Wastage:

  • If an array is declared with a size larger than the actual number of elements it needs to store, memory may be wasted. This is particularly true in situations where the array needs to accommodate the worst-case scenario.

• Inefficient Insertion and Deletion:

  • Inserting or deleting elements in the middle or at the beginning of an array requires shifting all subsequent elements, resulting in a time complexity of O(n). This can be inefficient for large arrays or frequent modification operations.

• Contiguous Memory Requirement:

  • Arrays require contiguous memory locations to store elements. In situations where contiguous memory is not available, it may limit the size of arrays or result in memory fragmentation.

• Homogeneous Data Type:

  • Arrays typically store elements of the same data type. If you need to store elements of different data types, an array may not be the most flexible data structure. In such cases, a collection or structure may be more appropriate.

• Static Structure:

  • The static nature of arrays makes them less suitable for scenarios where the size of the data is dynamic and unknown at compile time. Dynamic data structures like linked lists or dynamic arrays may be more appropriate.

• Lack of Built-in Methods:

  • Arrays in many low-level languages lack built-in methods for common operations such as sorting or searching. While higher-level languages may provide such functions, developers in lower-level languages may need to implement these operations manually.

• Poor Performance in Dynamic Sizing:

  • If dynamic resizing is required, such as when the number of elements is not known in advance, arrays may not be the most efficient data structure. Dynamic arrays or linked lists offer more flexibility in this regard.

• Not Well-Suited for Sparse Data:

  • For datasets with many empty or null values, arrays can be inefficient in terms of memory usage. Sparse data may be better represented using data structures designed for such scenarios, like sparse matrices.

In summary, while arrays are simple and efficient for certain use cases, their fixed size and limitations in terms of dynamic resizing and efficient insertion/deletion make them less suitable for certain applications. Developers often choose alternative data structures based on the specific requirements of their programs.

2D array

A 2D array, or a two-dimensional array, is an array of arrays.

It can be thought of as a table or a matrix with rows and columns.

In C, a 2D array is declared as follows:

// Syntax for declaration:

data_type array_name[row_size][column_size];

breakdown of each part of the syntax:

• • data_type: This is the type of data that the array will hold.

• In the example provided, the data type is int, meaning that the array will store integers.
  

• array_name: This is the name given to the array. In the example, it's called a matrix.
  

• row_size: This specifies the number of rows in the 2D array. In the example, 3 indicates that the array has 3 rows.
  

• column_size: This specifies the number of columns in the 2D array. In the example, 4 indicates that the array has 4 columns.
  

So, in the provided example:

// Example:

int matrix[3][4]; // Declaration of a 2D array with 3 rows and 4 columns

• The array is named a matrix.

• It is of type int.

• It has 3 rows.

• It has 4 columns.

This creates a 2D array with 3 rows and 4 columns, and you can access individual elements using indices like matrix[i][j], where i is the row index and j is the column index.

Here are some key points and operations related to 2D arrays in C:

Initialization:

int matrix[3][4] = {

{1, 2, 3, 4},

{5, 6, 7, 8},

{9, 10, 11, 12}

};

• int matrix[3][4]:

  • int: The data type of the array. In this case, it's an array of integers.

  • matrix: The name of the array.

  • [3]: Indicates that the array has 3 rows.

  • [4]: Indicates that each row has 4 columns.

• =:

  • The equal sign is used for initialization.

• Array Initialization:

  • The outermost curly braces {} indicate the initialization of the 2D array.

  • Each inner set of curly braces represents a row of the array.

  • The comma-separated values inside each inner set of braces represent the elements of that row.

So, the provided example initializes a 3x4 matrix as follows:

• Row 1: {1, 2, 3, 4}

• Row 2: {5, 6, 7, 8}

• Row 3: {9, 10, 11, 12}

This results in a 2D array named matrix with the following values:

1 2 3 4

5 6 7 8

9 10 11 12

You can access individual elements using indices like matrix[i][j], where i is the row index and j is the column index. For example, matrix[1][2] would give you the value 7.

Accessing Elements:

int value = matrix[1][2];

• matrix:

  • This is the name of the 2D array declared earlier.

• [1]:

  • This is the index to access the second row of the matrix. Remember, array indices in C/C++ are zero-based, so [1] corresponds to the second row.

• [2]:

  • This is the index to access the third column of the second row. Again, indices are zero-based, so [2] corresponds to the third column.

• int value =:

  • This declares a variable named value of type int to store the value obtained from the array.

Putting it all together, the line of code is accessing the element in the second row and third column of the matrix array and assigning it to the variable value. In the example matrix:

1 2 3 4

5 6 7 8

9 10 11 12

The value at the second row (index 1) and third column (index 2) is 7. Therefore, after this line of code executes, the variable value will be assigned the value 7.

Traversal:

for (int i = 0; i < 3; i++) {

for (int j = 0; j < 4; j++) {

printf("%d ", matrix[i][j]);

}

printf("\n");

}

• Outer Loop (for (int i = 0; i < 3; i++)):

  • This loop is responsible for iterating over the rows of the matrix.

  • int i = 0: Initializes the loop variable i to 0.

  • i < 3: The loop will continue as long as i is less than 3.

  • i++: Increments i after each iteration.

• Inner Loop (for (int j = 0; j < 4; j++)):

  • This loop is nested inside the outer loop and is responsible for iterating over the columns of each row.

  • int j = 0: Initializes the loop variable j to 0.

  • j < 4: The loop will continue as long as j is less than 4.

  • j++: Increments j after each iteration.

• printf("%d ", matrix[i][j]);:

  • Inside the inner loop, this statement prints the value of the current element at the position (i, j) in the matrix.

  • %d is the format specifier for an integer.

  • matrix[i][j] is the value at the current position in the matrix.

• printf("\n");:

  • After the inner loop completes for a particular row, this statement prints a newline character (\n), moving the cursor to the next line.

So, the combined effect of the nested loops is to iterate over each element of the 3x4 matrix and print it, row by row, with each row on a new line. This results in output similar to the original matrix:

1 2 3 4

5 6 7 8

9 10 11 12

It's a common pattern for iterating over elements in a 2D array.

Updating Elements:

matrix[1][2] = 20; // Updating the element in the second row and third column to 20

• matrix:

  • This is the name of the 2D array declared earlier.

• [1]:

  • This is the index to access the second row of the matrix. Remember, array indices in C/C++ are zero-based, so [1] corresponds to the second row.

• [2]:

  • This is the index to access the third column of the second row. Again, indices are zero-based, so [2] corresponds to the third column.

• =:

  • The equal sign is used for assignment.

• 20:

  • This is the value that is assigned to the element at the specified position in the matrix.

Putting it all together, the line of code is updating the element in the second row and third column of the matrix array with the value 20. In the example matrix:

1 2 3 4

5 6 7 8

9 10 11 12

After this line of code executes, the matrix becomes:

1 2 3 4

5 6 20 8

9 10 11 12

So, the element at the position (1, 2) (second row, third column) is now 20.

Passing 2D Arrays to Functions:

When passing a 2D array to a function, you need to specify the number of columns (or the size of the inner array) in the function parameter list. For example:

void printMatrix(int rows, int cols, int arr[rows][cols]) {

for (int i = 0; i < rows; i++) {

for (int j = 0; j < cols; j++) {

printf("%d ", arr[i][j]);

}

printf("\n");

}

}

// Calling the function

printMatrix(3, 4, matrix);

Function Definition:

void printMatrix(int rows, int cols, int arr[rows][cols]) {

• • This defines a function named printMatrix that takes three parameters:

    • rows: The number of rows in the matrix.

    • cols: The number of columns in the matrix.

    • arr: A 2D array (matrix) with dimensions determined by rows and cols.

  • The function is declared to return void, meaning it doesn't return any value.

Nested For Loop Inside the Function:

for (int i = 0; i < rows; i++) {

for (int j = 0; j < cols; j++) {

printf("%d ", arr[i][j]);

}

printf("\n");

}

• • This is a nested for loop that iterates over each element of the 2D array (arr).

  • The outer loop (for (int i = 0; i < rows; i++)) iterates over the rows.

  • The inner loop (for (int j = 0; j < cols; j++)) iterates over the columns.

  • printf("%d ", arr[i][j]); prints the value of each element in the matrix.

  • After printing each row, printf("\n"); is used to move to the next line.

• Calling the Function:
  

// Calling the function

printMatrix(3, 4, matrix);

• • This line calls the printMatrix function with the arguments 3, 4, and matrix.

  • In this case, the matrix is assumed to be a 3x4 array of integers, and the function will print its elements using the logic defined inside the function.

Overall, the printMatrix function is designed to print the elements of a 2D array (matrix) in a row-by-row format. In the provided example, it's called with a 3x4 matrix named matrix.

Dynamic Allocation of 2D Arrays:

If the size of the array is not known at compile time, you can dynamically allocate memory for a 2D array using pointers:

int **dynamicMatrix;

int rows = 3;

int cols = 4;

dynamicMatrix = (int **)malloc(rows * sizeof(int *));

for (int i = 0; i < rows; i++) {

dynamicMatrix[i] = (int *)malloc(cols * sizeof(int));

}

// Accessing and using dynamicMatrix similar to a regular 2D array

Declaration of the Pointer to 2D Array:

int **dynamicMatrix;

• • dynamicMatrix is a pointer to a pointer, which will be used to point to the dynamically allocated 2D array.

Initialization of Rows and Columns:
int rows = 3;

int cols = 4;

• • rows and cols store the dimensions of the 2D array.

• 
  

Dynamic Memory Allocation:

dynamicMatrix = (int **)malloc(rows * sizeof(int *));

• • Allocates memory for an array of int* pointers (rows) using malloc.

  • rows * sizeof(int *) is the size in bytes needed to store the array of pointers.

Allocation for Each Row:

for (int i = 0; i < rows; i++) {

dynamicMatrix[i] = (int *)malloc(cols * sizeof(int));

}

• • Inside a loop, memory is allocated for each row of the 2D array.

  • dynamicMatrix[i] is assigned the address of the memory block allocated for each row.

  • cols * sizeof(int) is the size in bytes needed to store the elements in each row.

Now, you have a dynamically allocated 2D array stored in dynamicMatrix. You can access and use it similarly to a regular 2D array:

// Accessing and using dynamicMatrix similar to a regular 2D array

dynamicMatrix[1][2] = 42; // Assigning a value to the element in the second row and third column

int value = dynamicMatrix[1][2]; // Accessing the element in the second row and third column

Remember to free the allocated memory when you're done using it:

for (int i = 0; i < rows; i++) {

free(dynamicMatrix[i]);

}

free(dynamicMatrix);

LINKED LISTS

A linked list is a data structure used in computer science to organize and store data.

It consists of a sequence of elements, each of which contains a reference (or link) to the next element in the sequence.

The last element typically has a reference to null, indicating the end of the list.

Representation of linked list

Each node has two components:

• Data: The actual data stored in the node.

• Next: A reference (pointer or link) to the next node in the sequence. The last node's "Next" points to null.

The linked list is then formed by connecting these nodes.

• Head: Points to the first node in the list.

• Data: Represents the actual information stored in each node.

• Next: Represents the reference to the next node.

Let's consider a simple example where the linked list contains the elements 1, 2, and 3.

In this example:

• The first node contains the data "1" and points to the next node with the data "2."

• The second node contains the data "2" and points to the next node with the data "3."

• The third node contains the data "3" and points to null, indicating the end of the list.

Traversal through the linked list involves starting from the head and following the "Next" pointers until reaching the end (null). Each arrow represents the link from one node to the next.

Why use linked lists over arrays

The choice between linked lists and arrays depends on the specific requirements and characteristics of the task at hand. Each data structure has its own advantages and disadvantages. Here are some reasons why you might choose linked lists over arrays:

• Dynamic Size:

  • Linked lists allow for dynamic sizing. They can easily grow or shrink during runtime by allocating or deallocating memory for nodes. In contrast, arrays in many programming languages have a fixed size, and resizing them can be inefficient.

• Efficient Insertions and Deletions:

  • Insertions and deletions can be more efficient in linked lists, especially when dealing with elements in the middle of the list. In arrays, inserting or removing an element may require shifting all subsequent elements.

• No Pre-allocation of Memory:

  • Linked lists don't require pre-allocation of a contiguous block of memory. Each node in a linked list can be allocated independently, which can be beneficial in scenarios where memory is fragmented or when the size of the data structure is unpredictable.

• Constant-time Insertions/Deletions at Head:

  • Adding or removing elements at the beginning of a linked list is a constant-time operation, as it only involves updating the head pointer and the next reference of the new first node. In arrays, this operation is typically more expensive as it requires shifting all elements.

• Ease of Implementation:

  • Linked lists can be easier to implement in certain cases, especially when dealing with dynamic data structures. There's no need to worry about resizing, and inserting or deleting nodes can be done without

  • 
    

  • the need for complex memory management.

However, it's essential to note that linked lists also have their own disadvantages compared to arrays:

• Random Access:

  • Random access to elements (accessing elements by index) is inefficient in linked lists. In arrays, direct access is achieved in constant time, but in linked lists, you need to traverse the list from the head to the desired position.

• Memory Overhead:

  • Each node in a linked list requires additional memory for the next pointer, leading to a higher memory overhead compared to arrays.

• Cache Performance:

  • Arrays have better cache performance due to their contiguous memory allocation, resulting in faster access times. Linked lists may cause cache misses more frequently, leading to slower access times.

The choice between linked lists and arrays depends on the specific requirements of the application. For scenarios where dynamic sizing and efficient insertions/deletions are crucial, linked lists might be a better choice. In cases where random access and memory efficiency are more critical, arrays may be more suitable.

Types of Linked Lists

let’s have a look at the overview of types of linked lists.

There are several types of linked lists, each with its own variations and use cases. The two primary types are singly linked lists and doubly linked lists. Here's an overview of these types:

• Singly Linked List:

  • In a singly linked list, each node contains data and a reference to the next node in the sequence.

  • The last node typically points to null, indicating the end of the list.

  • Traversal is only forward.

  • Simple and memory-efficient.
    

• Doubly Linked List:

  • In a doubly linked list, each node contains data and references to both the next and the previous nodes in the sequence.

  • Allows for traversal in both forward and backward directions.

  • More memory overhead due to the additional "prev" pointers.

  • Easier implementation of certain operations, such as deletion of a node given a reference to that node.
    

• Circular Linked List:

  • In a circular linked list, the last node points back to the first node, forming a circle.

  • Useful for applications where it's convenient to start again at the beginning after reaching the end.

  • The traversal continues indefinitely until a specific condition is met.
    

• Circular singly linked list -A circular singly linked list is characterized by the last node in the list having a pointer that references the first node. Both circular singly linked lists and circular doubly linked lists can be implemented.

• Circular doubly linked list -A circular doubly linked list is a sophisticated data structure where each node includes pointers to both its preceding and succeeding nodes. Unlike regular doubly linked lists, a circular doubly linked list doesn't have any NULL references within its nodes. Instead, the last node in the list holds the address of the first node, creating a circular structure. Additionally, the first node includes the address of the last node in its previous pointer.
  

These are some of the common types of linked lists. Depending on specific requirements and constraints, one type of linked list may be more suitable than another for a given application or problem.

Advantages of Linked lists

Linked lists offer several advantages that make them suitable for certain applications. Here are some key advantages of linked lists:

• Dynamic Size:

  • Linked lists can easily grow or shrink in size during runtime. This dynamic sizing makes them flexible in handling data structures where the size is not known in advance.

• Efficient Insertions and Deletions:

  • Adding or removing elements in a linked list, especially in the middle, is more efficient compared to arrays. It involves updating pointers, and there is no need to shift elements as in arrays.

• No Pre-allocation of Memory:

  • Linked lists do not require pre-allocation of a fixed-size block of memory. Nodes can be allocated independently, and new nodes can be added as needed.

• Constant-time Insertions/Deletions at Head:

  • Adding or removing elements at the beginning of a linked list is a constant-time operation. It only involves updating the head pointer and the next reference of the new first node.

• Ease of Implementation:

  • Implementing linked lists can be simpler in certain cases, especially when dealing with dynamic data structures. There is no need to worry about resizing, and inserting or deleting nodes can be done without complex memory management.

• No Wasted Memory:

  • Linked lists do not suffer from wasted memory due to pre-allocation of a fixed-size block. Memory is used more efficiently, as each node only requires space for data and references.

• No Overhead for Resizing:

  • Linked lists do not incur the overhead associated with resizing, which can be a concern with dynamically resizing arrays.

• Constant-time Concatenation:

  • Concatenating two linked lists can be done in constant time by adjusting pointers, unlike arrays where concatenation involves copying elements from one array to another.

• Support for Various Types:

  • Linked lists can be easily adapted to support different types of nodes, such as singly linked lists, doubly linked lists, or circular linked lists, based on specific requirements.

• Ease of Building Other Data Structures:

  • Linked lists provide the foundation for building other data structures, such as stacks, queues, and symbolic expressions in languages.

Linked lists are particularly advantageous when there is a need for dynamic sizing, efficient insertions and deletions, and flexibility in managing memory. However, the choice between linked lists and other data structures depends on the specific requirements of the application.

Disadvantages of Linked lists

While linked lists offer several advantages, they also come with certain disadvantages that should be considered depending on the specific requirements of an application. Here are some disadvantages of linked lists:

• No Random Access:

  • Accessing elements by index is inefficient in linked lists. To reach a specific element, you need to traverse the list from the beginning, which takes linear time. This contrasts with arrays, where random access is constant time.

• Memory Overhead:

  • Each node in a linked list requires additional memory for the next (and possibly previous in the case of doubly linked lists) pointers. This can result in higher memory overhead compared to arrays, where only the data needs to be stored.

• Cache Performance:

  • Linked lists may exhibit poorer cache performance compared to arrays. This is because elements in arrays are stored in contiguous memory locations, which can lead to better cache utilization and faster access times.

• Sequential Access:

  • While forward traversal is efficient, backward traversal (in the case of singly linked lists) or bidirectional traversal (in the case of doubly linked lists) may be less efficient than sequential access in arrays.

• Lack of Contiguity:

  • The non-contiguous nature of linked lists can result in poor cache utilization and may lead to increased memory paging in some scenarios. This can impact performance in certain applications.

• More Complex Implementation:

  • Implementing linked lists can be more complex than arrays, especially when dealing with pointers and dynamic memory allocation. This complexity may lead to increased chances of errors in the code.

• Extra Time and Space for Pointer References:

  • The need for storing references (pointers) in each node consumes extra memory, and dereferencing these pointers adds some overhead in terms of execution time.

• Not Suitable for Small Data Sets:

  • For small data sets or situations where random access is crucial, the overhead of linked lists may outweigh their benefits. Arrays might be more suitable in such cases.

• Potential for Memory Leaks:

  • If not managed properly, linked lists can lead to memory leaks. Failing to deallocate memory properly when nodes are removed can result in unreleased memory.

• Complexity in Reverse Traversal:

  • In singly linked lists, traversing the list in reverse requires maintaining additional information (such as a stack) or changing the structure of the list.

In summary, linked lists have their disadvantages, and the choice between linked lists and other data structures depends on the specific needs of the application. While linked lists are powerful in certain scenarios, they may not be the best choice for every situation.

Applications of linked lists

Linked lists find application in various scenarios due to their dynamic nature and efficient insertions and deletions. Some common applications include:

• Dynamic Memory Allocation:

  • Linked lists are often used for dynamic memory allocation, where the size of the data structure is not known in advance, and memory needs to be allocated or deallocated during runtime.

• Implementation of Data Structures:

  • Linked lists serve as the foundation for implementing other data structures such as stacks, queues, deques, and symbolic expressions in languages like Lisp.

• Undo Mechanisms:

  • In applications that require an "undo" mechanism, linked lists can be used to keep track of the state changes. Each node represents a state, and traversing backwards allows undoing operations.

• File Systems:

  • In file systems, linked lists are employed to maintain the directory structure. Each node represents a file or directory, and the links connect the hierarchical structure.

• Task Scheduling:

  • Operating systems often use linked lists to manage processes in a queue, where each node represents a process and the links determine the order of execution.

• Music Playlists:

  • Linked lists can be used to implement playlists in music applications. Each node represents a song, and the links determine the order of playback.

• Graphs:

  • Linked lists are used in the adjacency list representation of graphs. Each node represents a vertex, and the links connect vertices that share an edge.

• Hash Tables:

  • Separate chaining in hash tables often involves using linked lists to handle collisions. Each bucket in the hash table can be a linked list of elements that hash to the same index.

• Simulation of Real-World Objects:

  • Linked lists can be used to simulate real-world objects and their relationships. For example, modeling a train with each car represented by a node, linked together in sequence.

• Polynomial Representation:

  • Linked lists are used to represent polynomials, where each node contains a term of the polynomial, and links connect the terms in the proper order.

• Symbol Table in Compilers:

  • Compilers use linked lists to implement symbol tables. Each node represents a symbol, and the links connect symbols based on their scope and references.

• Network Routing Algorithms:

  • In networking, linked lists can be used to represent routes. Each node represents a router, and the links represent the connections between routers.

These are just a few examples, and the versatility of linked lists makes them suitable for a wide range of applications where dynamic data structures and efficient insertions/deletions are essential.

Operations performed on linked lists

Here are some common operations performed on linked lists:

• Insertion at the Beginning (Push):

  • Add a new node at the beginning of the linked list by updating the head pointer to point to the new node, and the new node's next pointer to the previous head.

• Insertion at the End (Append):

  • Add a new node at the end of the linked list by traversing to the last node and updating its next pointer to point to the new node.

• Insertion at a Specific Position:

  • Insert a new node at a specified position by updating the next pointers of the preceding and succeeding nodes accordingly.

• Deletion at the Beginning (Pop):

  • Remove the first node by updating the head pointer to point to the second node and freeing the memory of the removed node.

• Deletion at the End:

  • Remove the last node by traversing to the second-to-last node and updating its next pointer to null, then freeing the memory of the removed node.

• Deletion at a Specific Position:

  • Delete a node at a specified position by updating the next pointers of the preceding and succeeding nodes accordingly and freeing the memory of the removed node.

• Traversal (Print/Display):

  • Traverse the linked list from the head to the last node, printing or displaying the data of each node.

• Search:

  • Search for a specific element in the linked list by traversing the list and comparing the data of each node.

• Length (Size) Calculation:

  • Calculate the number of nodes in the linked list by traversing the list and counting the nodes.

• Reverse:

  • Reverse the order of nodes in the linked list by adjusting the next pointers of each node to point to the previous node.

• Concatenation:

  • Concatenate two linked lists by updating the next pointer of the last node in the first list to point to the head of the second list.

• Splitting:

  • Split a linked list into two by updating the next pointer of the last node in the first list to null.

• Detecting a Cycle:

  • Check if a linked list has a cycle (loop) by using Floyd's cycle-finding algorithm or similar techniques.

• Finding the Middle Node:

  • Determine the middle node of a linked list, often used in various algorithms.

These operations provide the basic functionalities needed to manipulate and manage data in a linked list. The choice of operation depends on the specific requirements of the application.

Please download the file for reference of the program in other programming languages.

Circular doubly linked list

A circular doubly linked list is a variation of the traditional doubly linked list data structure where the last node's next pointer points back to the first node, creating a circular structure. Similarly, the first node's previous pointer points to the last node, completing the circular linkage.

Because a circular doubly linked list incorporates three components in its structure, it requires greater memory per node and entails more costly fundamental operations. Nevertheless, this type of linked list facilitates straightforward manipulation of pointers and enhances search efficiency twofold.

Here's a brief overview of how a circular doubly linked list is structured:

• Node Structure: node in the circular doubly linked list contains two pointers - one pointing to the next node and the other pointing to the previous node. Additionally, it holds some data.
  

• Circularity: The last node's next pointer points to the first node, and the first node's previous pointer points to the last node, forming a circular structure. This ensures that the traversal of the list can be continuous without reaching a null pointer.
  

• Operations: Operations such as insertion, deletion, and traversal are similar to those in a traditional doubly linked list. However, care must be taken to handle the circular nature of the list properly, especially during insertion and deletion operations.
  

• Traversal: Traversal of a circular doubly linked list can start from any node and can proceed either forward (using next pointers) or backward (using previous pointers) until the starting node is reached again.
  

Here's a basic implementation of a circular doubly linked list in C:

#include <stdio.h>

#include <stdlib.h>

// Define a node structure for the circular doubly linked list

struct Node {

int data;

struct Node* next;

struct Node* prev;

};

// Function to create a new node

struct Node* createNode(int data) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

if (newNode == NULL) {

printf("Memory allocation failed!\n");

exit(1);

}

newNode->data = data;

newNode->next = NULL;

newNode->prev = NULL;

return newNode;

}

// Function to insert a new node at the beginning of the list

void insertAtBeginning(struct Node** head, int data) {

struct Node* newNode = createNode(data);

if (*head == NULL) {

*head = newNode;

(*head)->next = *head;

(*head)->prev = *head;

} else {

newNode->next = *head;

newNode->prev = (*head)->prev;

(*head)->prev->next = newNode;

(*head)->prev = newNode;

*head = newNode;

}

}

// Function to display the circular doubly linked list

void display(struct Node* head) {

if (head == NULL) {

printf("List is empty!\n");

return;

}

struct Node* temp = head;

do {

printf("%d ", temp->data);

temp = temp->next;

} while (temp != head);

printf("\n");

}

int main() {

struct Node* head = NULL;

// Insert some elements into the circular doubly linked list

insertAtBeginning(&head, 1);

insertAtBeginning(&head, 2);

insertAtBeginning(&head, 3);

insertAtBeginning(&head, 4);

// Display the circular doubly linked list

printf("Circular Doubly Linked List: ");

display(head);

return 0;

}

BREAK DOWN

#include <stdio.h>

#include <stdlib.h>

These are standard C header files. <stdio.h> is included for input and output operations like printf, and <stdlib.h> is included for dynamic memory allocation functions like malloc and exit.

Node Structure:

struct Node {

int data;

struct Node* next;

struct Node* prev;

};

• struct Node: This line declares a structure named Node. Structures in C are user-defined data types that allow you to group multiple variables of different types under a single name.
  

• int data: This line declares a member variable data of type int within the structure. This member variable is used to store the actual data associated with a node in the linked list.
  

• struct Node next*: This line declares a pointer variable next of type struct Node*. This pointer is used to point to the next node in the linked list. Since it's a pointer to the same type struct Node, it facilitates the creation of linked lists where each node points to the next node.
  

• struct Node prev*: This line declares another pointer variable prev of type struct Node*. This pointer is used to point to the previous node in a doubly linked list. A doubly linked list is a type of linked list where each node contains a pointer to the previous node as well as the next node. This allows traversal of the list in both forward and backward directions.
  

So, overall, this struct declaration is defining a node structure for a doubly linked list, where each node contains an integer data value (data), a pointer to the next node (next), and a pointer to the previous node (prev).

Next we will see the Function to Create a New Node:

struct Node* createNode(int data) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

if (newNode == NULL) {

printf("Memory allocation failed!\n");

exit(1);

}

newNode->data = data;

newNode->next = NULL;

newNode->prev = NULL;

return newNode;

}

struct Node* createNode(int data)

• • This function takes an integer data as a parameter and returns a pointer to a struct Node.

• 
  

• struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

• This line allocates memory dynamically using the malloc() function to create a new node.

• sizeof(struct Node) calculates the size required to store a struct Node.

• malloc() returns a pointer to the allocated memory block.

• The pointer is cast to (struct Node*) to ensure compatibility with the pointer type.

if (newNode == NULL) {

printf("Memory allocation failed!\n");

exit(1);

}

• This block checks if memory allocation was successful.

• If malloc() returns NULL, it indicates that memory allocation failed.

• In such a case, an error message is printed, and the program exits with an error code (exit(1)).

newNode->data = data;

newNode->next = NULL;

newNode->prev = NULL;

• This part initializes the members of the newly created node.

• newNode->data assigns the data parameter to the data member of the node.

• newNode->next and newNode->prev set the next and prev pointers of the node to NULL, indicating that this node is currently not linked to any other nodes.

return newNode;

• • Finally, the function returns a pointer to the newly created node.

Overall, this function dynamically allocates memory for a new node, initializes its data and pointers, and returns a pointer to the created node. It's a common function used when working with linked list implementations in C.

Now we will write the Function to Insert a Node at the Beginning:

void insertAtBeginning(struct Node** head, int data) {

struct Node* newNode = createNode(data);

if (*head == NULL) {

*head = newNode;

(*head)->next = *head;

(*head)->prev = *head;

} else {

newNode->next = *head;

newNode->prev = (*head)->prev;

(*head)->prev->next = newNode;

(*head)->prev = newNode;

*head = newNode;

}

}

• struct Node* newNode = createNode(data);: This line creates a new node with the given data using the createNode function. This function dynamically allocates memory for a new node, initializes its fields with the given data, and returns a pointer to the newly created node.
  

• if (*head == NULL) {: This conditional statement checks if the pointer to the head of the list (*head) is NULL, which means the list is currently empty.
  

• *head = newNode;: If the list is empty, this line sets the pointer to the head of the list (*head) to point to the newly created node (newNode). Since this is the only node in the list, both its next and prev pointers are set to point back to itself, making it circular.
  

• (*head)->next = *head;: This line sets the next pointer of the newly created node (which is now the head of the list) to point to itself, establishing the circular link.
  

• (*head)->prev = *head;: This line sets the prev pointer of the newly created node (which is now the head of the list) to point to itself, establishing the circular link.
  

• else {: If the list is not empty, execution continues from here.
  

• newNode->next = *head;: This line sets the next pointer of the newly created node (newNode) to point to the current head of the list (*head), effectively inserting the new node at the beginning.
  

• newNode->prev = (*head)->prev;: This line sets the prev pointer of the newly created node (newNode) to point to the node that was previously the last node in the list (which is (*head)->prev).
  

• (*head)->prev->next = newNode;: This line updates the next pointer of the node that was previously the last node in the list (which is (*head)->prev) to point to the newly created node (newNode), effectively linking it to the new node.
  

• (*head)->prev = newNode;: This line updates the prev pointer of the current head of the list (*head) to point to the newly created node (newNode), effectively completing the circular link.
  

• *head = newNode;: Finally, this line updates the pointer to the head of the list (*head) to point to the newly created node (newNode), making it the new head of the list.
  

In summary, the insertAtBeginning function inserts a new node with the given data at the beginning of the circular doubly linked list. If the list is empty, it creates a new node and makes it the head of the list, establishing circular links. If the list is not empty, it inserts the new node at the beginning and updates the necessary pointers to maintain the circular doubly linked list structure.

Function to Display the List:

void display(struct Node* head) {

if (head == NULL) {

printf("List is empty!\n");

return;

}

struct Node* temp = head;

do {

printf("%d ", temp->data);

temp = temp->next;

} while (temp != head);

printf("\n");

}

• if (head == NULL) {: This conditional statement checks if the pointer to the head of the list (head) is NULL, which means the list is empty.
  

• printf("List is empty!\n");: If the list is empty, this line prints a message indicating that the list is empty.
  

• return;: After printing the message, the function returns, terminating further execution of the function.
  

• struct Node* temp = head;: If the list is not empty, this line declares a temporary pointer temp and initializes it with the pointer to the head of the list (head). This pointer will be used to traverse the list.
  

• do {: This initiates a do-while loop that will iterate at least once and continue until temp reaches the head of the list again, forming a circular loop.
  

• printf("%d ", temp->data);: Inside the loop, this line prints the data of the current node (temp->data), which is the data stored in the node pointed to by temp.
  

• temp = temp->next;: This line updates the temp pointer to point to the next node in the list, moving it forward in the list.
  

• } while (temp != head);: This loop continues until the temp pointer reaches the head of the list again, completing one full traversal of the circular list.
  

• printf("\n");: After the loop terminates, this line prints a newline character to move to the next line in the output.
  

In summary, the display function prints the data stored in each node of the circular doubly linked list. If the list is empty, it prints a message indicating that the list is empty. If the list is not empty, it traverses the list starting from the head node and prints the data of each node until it reaches the head node again, completing one full traversal of the circular list.

Main Function:

int main() {

struct Node* head = NULL;

// Insert some elements into the circular doubly linked list

insertAtBeginning(&head, 1);

insertAtBeginning(&head, 2);

insertAtBeginning(&head, 3);

insertAtBeginning(&head, 4);

// Display the circular doubly linked list

printf("Circular Doubly Linked List: ");

display(head);

return 0;

}

• struct Node* head = NULL;: This line declares a pointer head to the head of the circular doubly linked list and initializes it to NULL, indicating that the list is initially empty.
  

• insertAtBeginning(&head, 1);: This line inserts a new node with data 1 at the beginning of the circular doubly linked list pointed to by head. Since the list is initially empty, this node becomes the head of the list.
  

• insertAtBeginning(&head, 2);: This line inserts a new node with data 2 at the beginning of the list. This node becomes the new head of the list, and the previous head becomes the next node in the list.
  

• insertAtBeginning(&head, 3);: This line inserts a new node with data 3 at the beginning of the list. Similar to the previous step, this node becomes the new head of the list, and the previous head becomes the next node in the list.
  

• insertAtBeginning(&head, 4);: This line inserts a new node with data 4 at the beginning of the list. Again, this node becomes the new head of the list, and the previous head becomes the next node in the list.
  

• printf("Circular Doubly Linked List: ");: This line prints a message indicating that the following output represents a circular doubly linked list.
  

• display(head);: This line calls the display function to print the elements of the circular doubly linked list starting from the head node.
  

• return 0;: This line indicates that the main function has executed successfully, and the program should exit with a return code of 0, indicating success.
  

In summary, the main function creates a circular doubly linked list with elements 1, 2, 3, and 4, inserts them at the beginning of the list, and then displays the contents of the list.

STACK

A stack is a fundamental data structure that follows the Last In, First Out (LIFO) principle. It is named "stack" because it resembles a stack of items, like a stack of plates or books. In a stack, the last element added is the first one to be removed.

The standard stack operations are

The standard operations that can be performed on a stack data structure are as follows:

• Push: This operation adds an element to the top of the stack.

• Pop: This operation removes the top element from the stack.

• Peek or Top: This operation allows you to view the top element of the stack without removing it.

• isEmpty: This operation checks whether the stack is empty or not.

• Size: This operation returns the number of elements currently present in the stack.

Working of stack

Let us understand the Working of the stack

First, we will see push operations

The steps involved in push operation are

Before adding an element to a stack, it is verified whether the stack is empty.

• If we try to insert the element in a stack, and the stack is full, then the overflow condition occurs.

• When we initialize a stack, we set the value of top as -1 to check that the stack is empty.

• When the new element is pushed in a stack, first, the value of the top gets incremented, i.e., top=top+1, so the top = -1 becomes top = 0 and the element will be placed at the new position of the top.

First, we will add element 10 to the stack and the top will be incremented from - 1 to 0

• The elements will be inserted until we reach the maximum size of the stack.

Next, we will Insert 20 and the top becomes 1

push the element 30 the top is now 2

push the element 40 the top is 3

and push the element 50 top is 4 and the stack is full.

we cannot not push the elements further in this stack. if we do so the overflow condition occurs.

now let us see the next operation that is pop.

deleting the elements from the stack is called a pop operation.

• Before deleting the element from the stack, we check whether the stack is empty.

• If we try to delete the element from the empty stack, then the underflow condition occurs.

• If the stack is not empty, we first access the element which is pointed by the top

• Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.

Here we have a stack that is not empty

so first we will remove element 50

next, we will remove element 40

now remove element 30

remove the element 20

and remove 10

now the stack is empty

Next we will discuss the applications of stacks

Stacks have numerous applications across various domains in computer science and beyond. Here are some common applications of stacks:

• Function Call Stack: In programming languages like C/C++, Java, and Python, a stack is used to manage function calls. When a function is called, its parameters and local variables are pushed onto the stack. When the function returns, these values are popped off the stack.
  

• Expression Evaluation: Stacks are used to evaluate arithmetic expressions, such as infix, postfix, and prefix expressions. Infix expressions can be converted to postfix or prefix notation using stacks for easier evaluation.
  

• Backtracking Algorithms: Stacks are often used in backtracking algorithms such as Depth-First Search (DFS). During the search process, the states and choices are pushed onto the stack, and when a dead end is reached, the algorithm backtracks by popping from the stack.
  

• Undo Mechanisms: Stacks can be used to implement undo mechanisms in text editors and other software applications. Each action performed by the user is pushed onto the stack, allowing for easy reversal of actions by popping from the stack.
  

• Browser History: Web browsers use stacks to implement the back and forward navigation buttons. Each visited page is pushed onto the stack, allowing users to navigate backward and forward through their browsing history.
  

• Parenthesis Matching: Stacks are used to validate the correctness of expressions containing parentheses, braces, and brackets. By pushing opening symbols onto the stack and popping them when closing symbols are encountered, the balance of the symbols can be checked.
  

• Compiler and Interpreter Implementations: Stacks play a crucial role in the implementation of compilers and interpreters for programming languages. They are used for parsing, code generation, and managing the execution environment.
  

• Memory Management: Stacks are used in memory management systems to allocate and deallocate memory for function calls and local variables. The stack memory is automatically managed by the system, making it efficient for managing memory in a structured manner.
  

These are just a few examples of the many applications of stacks in computer science and software development. Stacks provide a simple and efficient way to manage data and perform various operations in a wide range of applications.

A queue is a fundamental data structure in computer science that follows the First-In-First-Out (FIFO) principle.

In a queue, elements are added at one end called the "rear" or "tail" and removed from the other end called the "front" or "head".

A real-world example of a queue is a line at a supermarket checkout. When customers arrive at the checkout, they join the queue, and the cashier serves them one by one in the order they joined the line. This follows the First-In-First-Out (FIFO) principle of a queue data structure.

Here's how the analogy maps to the queue operations:

1. Enqueue: When a new customer arrives at the checkout, they join the back of the queue.

2. Dequeue: The cashier serves the customer at the front of the queue, removing them from the line.

3. Peek: The cashier can see who is at the front of the queue without serving them yet, perhaps to prepare for the next customer.

4. IsEmpty: If there are no customers in the queue, it is empty.

5. IsFull: In a real-world scenario like a supermarket, the queue is often not limited by a fixed size, but in a theoretical queue implementation with a fixed-size array, the queue could be considered full when it reaches its maximum capacity.

Other real-world examples of queues include:

• Waiting in line at a ticket counter, bank, or amusement park.

• Processing print jobs in a printer queue.

• Handling requests in a web server's request queue.

• Processing tasks in a CPU scheduling algorithm.

Application of queues

1. Queues are commonly employed as waitlists for a singular shared resource, such as a printer, disk drive, or CPU.

2. In scenarios involving asynchronous data transfer, where data exchange rates between two processes are not synchronized, queues play a pivotal role. This includes processes like handling pipes, file input/output operations, and sockets.

3. In numerous applications, queues serve as buffers to manage data flow. This includes media players like MP3 players and CD players, among others.

4. Media players utilize queues to manage playlists, enabling the addition and removal of songs in a sequential manner.

5. Within operating systems, queues are utilized to manage interrupts effectively, ensuring timely handling of various system events.

Types of queues

Four different types of queues are

• Simple Queue or Linear Queue

• Circular Queue

• Priority Queue

• Double Ended Queue (or Deque)

Let's discuss each of the types of queues.

Simple Queue or Linear Queue

In a Linear Queue, insertion occurs at one end, while deletion occurs at the other end. The end where insertion takes place is called the rear end, and the end where deletion takes place is called the front end. Linear Queue strictly adheres to the FIFO (First In, First Out) rule.

Diagram

The primary limitation of using a linear queue is that insertion is only possible from the rear end. If the first three elements are deleted from the queue, even though space is available, we cannot insert more elements. In this scenario, the linear queue indicates an overflow condition because the rear is pointing to the last element of the queue.

Next we will see circular queue

Circular Queue

In a Circular Queue, all the nodes are arranged in a circular manner. It resembles a linear queue, but the last element of the queue is connected to the first element, creating a circular structure. Circular Queue is also known as a Ring Buffer because all ends are connected to one another.

Diagram

The drawback of a linear queue is overcome by using a circular queue. In a circular queue, if there is empty space available, a new element can be added to that space by simply incrementing the value of the rear pointer. The primary advantage of using a circular queue is improved memory utilization.

Now let see the priority queue

Priority queue

A priority queue is a special type of queue where elements are arranged based on their priority. In this queue data structure, each element is associated with a priority. If multiple elements have the same priority, they are arranged according to the FIFO (First In, First Out) principle. The representation of a priority queue is shown in the image below:

In a priority queue, insertion is based on arrival time, while deletion is based on priority. Priority queues are primarily used to implement CPU scheduling algorithms.

There are two types of priority queues

1. Ascending priority queue - In an ascending priority queue, elements can be inserted in arbitrary order, but only the smallest element can be deleted first. For example, if an array has elements 7, 5, and 3 in the same order, insertion can be done in the same sequence, but the order of deleting the elements is 3, 5, 7.

2. Descending priority queue - In a descending priority queue, elements can be inserted in arbitrary order, but only the largest element can be deleted first. For example, if an array has elements 7, 3, and 5 in the same order, insertion can be done in the same sequence, but the order of deleting the elements is 7, 5, 3.

Deque (or, Double Ended Queue)

In a Deque or Double Ended Queue, insertion and deletion can be performed from both ends of the queue, either from the front or the rear. This means that elements can be inserted and deleted from both the front and rear ends of the queue. A Deque can be used as a palindrome checker, as reading the string from both ends would result in the same string.

A Deque can be used both as a stack and a queue because it allows insertion and deletion operations at both ends. It can be considered as a stack because a stack follows the LIFO (Last In, First Out) principle, where insertion and deletion can only be performed from one end. In a deque, it is possible to perform both insertion and deletion from one end, and it does not strictly follow the FIFO principle.

Array representation of Queue

We can represent a queue using linear arrays.

Each queue has two variables, front and rear, which indicate the positions for insertions and deletions.

Initially, both front and rear are set to -1, indicating an empty queue.

The array representation of a queue containing 5 elements, along with the corresponding values of front and rear, is illustrated here.

The figure displays a queue of characters forming the English word “SMILE”. Since no deletion has occurred in the queue yet, the value of the front remains -1. However, the value of the rear increases by one each time an insertion is performed in the queue. After inserting an element into the queue shown in the above figure, the queue will appear as follows. The value of the rear will become 5, while the value of the front remains the same.

After deleting an element, the value of 'front' will increase from -1 to 0. However, the queue will appear like this

Algorithm to insert any element in a queue

1. Check if the queue is full.

2. If the queue is full, return an overflow error.

3. If the queue is not full, increment the rear pointer.

4. Insert the new element at the rear position.

enqueue(queue, element):

if isFull(queue): # Check if the queue is full

return "Queue is full" # If the queue is full, return an overflow error

else if isEmpty(queue): # Check if the queue is empty

front = rear = 0 # If the queue is empty, set both front and rear to 0

else:

rear = rear + 1 # Increment the rear pointer

queue[rear] = element # Insert the new element at the rear position

Let’s see a C function to insert an element in the queue

void insert(int queue[], int max, int front, int rear, int item)

{

if (rear + 1 == max) // Check if the queue is full

{

printf("overflow"); // If the queue is full, print "overflow"

}

else

{

if(front == -1 && rear == -1) // Check if the queue is empty

{

front = 0; // If the queue is empty, set both front and rear to 0

rear = 0;

}

else

{

rear = rear + 1; // If the queue is neither full nor empty, increment the rear pointer

}

queue[rear] = item; // Insert the new element at the position pointed to by rear

}

}

Algorithm to delete an element from the queue

1. Check if the queue is empty.

2. If the queue is empty, return an underflow error.

3. Retrieve the element at the front of the queue.

4. Increment the front pointer.

5. If the front becomes equal to the rear, set both front and rear to -1 to indicate an empty queue.

dequeue(queue):

if isEmpty(queue):

return "Queue is empty"

else:

element = queue[front]

front = front + 1

if front > rear:

front = rear = -1

return element

C function to delete an element from the queue

int delete(int queue[], int max, int front, int rear)

{

int y; // Variable to store the deleted element

if (front == -1 || front > rear) // Check if the queue is empty

{

printf("underflow"); // If the queue is empty, print "underflow"

}

else

{

y = queue[front]; // Store the element to be deleted

if (front == rear) // If there is only one element in the queue

{

front = rear = -1; // Set both front and rear to -1 to indicate an empty queue

}

else

{

front = front + 1; // Increment front to point to the next element

}

return y; // Return the deleted element

}

}

Now let us write a C Program to implement a queue using array

#include <stdio.h>

#include <stdlib.h>

#define MAX_SIZE 100

// Structure to represent a queue

struct Queue {

int items[MAX_SIZE];

int front;

int rear;

};

// Function to create a new queue

struct Queue* createQueue() {

struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));

queue->front = -1;

queue->rear = -1;

return queue;

}

// Function to check if the queue is empty

int isEmpty(struct Queue* queue) {

if (queue->rear == -1)

return 1;

else

return 0;

}

// Function to check if the queue is full

int isFull(struct Queue* queue) {

if (queue->rear == MAX_SIZE - 1)

return 1;

else

return 0;

}

// Function to add an element to the queue

void enqueue(struct Queue* queue, int value) {

if (isFull(queue))

printf("Queue is full\n");

else {

if (queue->front == -1)

queue->front = 0;

queue->rear++;

queue->items[queue->rear] = value;

printf("%d enqueued to queue\n", value);

}

}

// Function to remove an element from the queue

int dequeue(struct Queue* queue) {

int item;

if (isEmpty(queue)) {

printf("Queue is empty\n");

return -1;

} else {

item = queue->items[queue->front];

queue->front++;

if (queue->front > queue->rear) {

queue->front = queue->rear = -1;

}

return item;

}

}

// Function to display the queue

void display(struct Queue* queue) {

int i;

if (isEmpty(queue))

printf("Queue is empty\n");

else {

printf("Queue elements are:\n");

for (i = queue->front; i <= queue->rear; i++)

printf("%d\n", queue->items[i]);

}

}

int main() {

struct Queue* queue = createQueue();

enqueue(queue, 10);

enqueue(queue, 20);

enqueue(queue, 30);

enqueue(queue, 40);

display(queue);

printf("%d dequeued from queue\n", dequeue(queue));

printf("%d dequeued from queue\n", dequeue(queue));

display(queue);

return 0;

}

1. #include <stdio.h>: This line includes the standard input-output header file (stdio.h). It provides functions like printf() and scanf() for input and output operations.

2. #include <stdlib.h>: This line includes the standard library header file (stdlib.h). It provides functions like malloc(), free(), and exit().

3. #define MAX_SIZE 100: This line defines a macro MAX_SIZE with the value 100. Macros are replaced by their values during the pre-processing stage of compilation. So, whenever the compiler sees MAX_SIZE, it will replace it with 100.

// Structure to represent a queue

struct Queue {

int items[MAX_SIZE];

int front;

int rear;

};

• items[MAX_SIZE]: This is an array of integers used to store the elements of the queue. MAX_SIZE is a macro defined earlier, and it determines the maximum capacity of the queue.

• front: This is an integer variable that holds the index of the front element in the queue.

• rear: This is an integer variable that holds the index of the rear element in the queue.

// Function to create a new queue

struct Queue* createQueue() {

struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));

queue->front = -1;

queue->rear = -1;

return queue;

}

• malloc(sizeof(struct Queue)): This line allocates memory dynamically for a new queue structure using malloc(). The sizeof(struct Queue) ensures enough memory is allocated for a Queue structure.

• queue->front = -1; and queue->rear = -1;: These lines initialize the front and rear indices of the queue to -1, indicating that the queue is empty.

• Finally, the function returns a pointer to the newly created queue.

// Function to check if the queue is empty

int isEmpty(struct Queue* queue) {

if (queue->rear == -1)

return 1;

else

return 0;

}

• queue->rear == -1: This condition checks if the rear index of the queue is -1, which indicates that the queue is empty.

• If the queue is empty, the function returns 1, indicating true (or yes, the queue is empty).

• If the queue is not empty, the function returns 0, indicating false (or no, the queue is not empty).

// Function to check if the queue is full

int isFull(struct Queue* queue) {

if (queue->rear == MAX_SIZE - 1)

return 1;

else

return 0;

}

• queue->rear == MAX_SIZE - 1: This condition checks if the rear index of the queue is equal to MAX_SIZE - 1, which indicates that the queue is full.

• If the queue is full, the function returns 1, indicating true (or yes, the queue is full).

• If the queue is not full, the function returns 0, indicating false (or no, the queue is not full).

// Function to add an element to the queue

void enqueue(struct Queue* queue, int value) {

if (isFull(queue))

printf("Queue is full\n");

else {

if (queue->front == -1)

queue->front = 0;

queue->rear++;

queue->items[queue->rear] = value;

printf("%d enqueued to queue\n", value);

}

}

• isFull(queue): This function checks if the queue is full. If the queue is full, a message is printed, and the function returns without performing any further operations.

• If the queue is not full, the function checks if the queue was empty before adding the new element. If it was, it sets the front index to 0.

• It then increments the rear index to move to the next available position in the queue and adds the new element to that position.

• Finally, it prints a message indicating that the value has been added to the queue.

// Function to remove an element from the queue

int dequeue(struct Queue* queue) {

int item;

if (isEmpty(queue)) {

printf("Queue is empty\n");

return -1;

} else {

item = queue->items[queue->front];

queue->front++;

if (queue->front > queue->rear) {

queue->front = queue->rear = -1;

}

return item;

}

}

• isEmpty(queue): This function checks if the queue is empty. If the queue is empty, a message is printed, and -1 is returned to indicate an empty queue.

• If the queue is not empty, the function dequeues the element at the front of the queue and stores it in the variable item.

• It then increments the front index to remove the element from the queue.

• If after dequeuing, the queue becomes empty, front and rear indices are reset to -1.

• Finally, it returns the dequeued item.

// Function to display the queue

void display(struct Queue* queue) {

int i;

if (isEmpty(queue))

printf("Queue is empty\n");

else {

printf("Queue elements are:\n");

for (i = queue->front; i <= queue->rear; i++)

printf("%d\n", queue->items[i]);

}

}

• isEmpty(queue): This function checks if the queue is empty. If the queue is empty, a message is printed, and the function returns without displaying any elements.

• If the queue is not empty, the function prints a message indicating that the queue elements will be displayed.

• It then iterates through the elements of the queue from front to rear and prints each element.

int main() {

struct Queue* queue = createQueue();

enqueue(queue, 10);

enqueue(queue, 20);

enqueue(queue, 30);

enqueue(queue, 40);

display(queue);

printf("%d dequeued from queue\n", dequeue(queue));

printf("%d dequeued from queue\n", dequeue(queue));

display(queue);

return 0;

}

• createQueue(): Creates a new queue.

• enqueue(queue, 10), enqueue(queue, 20), enqueue(queue, 30), enqueue(queue, 40): Adds elements 10, 20, 30, and 40 to the queue, respectively.

• display(queue): Displays the elements of the queue.

• dequeue(queue), dequeue(queue): Removes and returns the front elements of the queue (10 and 20), respectively.

• display(queue): Displays the elements of the queue after dequeuing.

Out Put

10 enqueued to queue

20 enqueued to queue

30 enqueued to queue

40 enqueued to queue

Queue elements are:

10

20

30

40

10 dequeued from queue

20 dequeued from queue

Queue elements are:

30

40

=== Code Execution Successful =

While implementing a queue using an array is straightforward, but there are some drawbacks to this approach:

1. Fixed Size: In the array representation, the size of the queue is fixed at the time of creation. Once the queue is created with a specific size, it cannot be resized dynamically. If the queue becomes full, it is not possible to add more elements to it.

2. Wastage of Memory: If the size of the array is declared to be very large to accommodate potential maximum elements, but the actual number of elements in the queue is much smaller, it leads to a wastage of memory.

3. Queue Overflow and Underflow: In the array implementation, it's possible to face two types of errors:

   • Queue Overflow: If you try to add an element to a full queue, it leads to a queue overflow.

   • Queue Underflow: If you try to remove an element from an empty queue, it leads to a queue underflow.

4. Continuously Shifting Elements: In a queue, once an element is dequeued, the remaining elements need to be shifted to fill the vacant position. This shifting operation is time-consuming and makes the dequeue operation less efficient.

5. Dynamic Memory Management Overhead: If dynamic memory allocation is used to create an array-based queue, there is overhead associated with memory allocation and deallocation.

6. Not Suitable for Real-time Applications: Array representation of a queue is not suitable for real-time applications where the size of the queue is not known in advance or may vary during program execution.

These drawbacks make the array representation of a queue less efficient for dynamic and large-scale applications. To overcome these drawbacks, linked list representation of a queue can be used, where memory utilization is more efficient and the size of the queue can be dynamic.

Linked list representation of the queue.

Because of the limitations outlined in the previous section, the array implementation cannot be used for large-scale applications where queues are implemented.

One alternative to the array implementation is the linked list implementation of a queue.

The linked representation of a queue with

n elements has a storage requirement of

O(n), while the time requirement for operations is O(1).

In a linked queue, each node consists of two parts: a data part and a link part. Each element of the queue points to its immediate next element in memory.

There are two pointers”the front pointer and the rear pointer” maintained in memory in the linked queue. The address of the queue's first element is contained in the front pointer, while the address of the queue's last element is contained in the rear pointer.

At the front end and back end, respectively, insertions and deletions are made. The queue is empty if both the front and rear are NULL.

Operation on Linked Queue

There are 2 fundamental operations performed on the linked queues, they are insertion and deletion

Insertion operation.

By appending an element to the end of the queue, the insert operation appends the queue. The final element in the queue will be the new one.

we will use the this line to allocate memory for the new node ptr.

Ptr = malloc (sizeof(struct node) * (struct node *);

Inserting this new node PTR into the connected queue can go in one of two ways.

The first case involves adding an element to a queue that is empty. Under these circumstances, front = NULL becomes true.

At this time, the front and rear pointers' next points will both point to NULL, making the new element the only one in the queue.

ptr -> data = item;

if(front == NULL)

{

front = ptr;

rear = ptr;

front -> next = NULL;

rear -> next = NULL;

}

ptr->data = item;

This line assigns the value of item to the data member of the structure that ptr is pointing to.

if(front == NULL)

{

front = ptr;

rear = ptr;

front->next = NULL;

rear->next = NULL;

}

This part of the code is a conditional statement. It checks if the front pointer is NULL. If it is, it means the queue is empty.

• If the queue is empty (front is NULL), front, and rear are assigned to ptr, which is the new node being added to the queue.

• Then, front->next and rear->next are set to NULL, indicating that there is no other element in the queue.

So, in summary, if the queue is empty, ptr becomes the only node in the queue, and both front and rear point to it.

In the second scenario, there are multiple elements in the queue. It becomes false when the condition front = NULL. To make the next pointer of rear point to the new node ptr in this circumstance, we must update the end pointer rear. We also need to set the rear pointer to point to the newly inserted node ptr because this is a linked queue. Additionally, we must set the subsequent rear point pointer to NULL.

rear -> next = ptr;

rear = ptr;

rear->next = NULL;

rear->next = ptr;

This line sets the next pointer of the current rear node to point to the new node ptr that has been added to the queue.

rear = ptr;

This line updates the rear pointer to point to the new node ptr, making ptr the new rear of the queue.

rear->next = NULL;

This line ensures that the next pointer of the new rear node (ptr) is NULL, indicating the end of the queue.

So, in summary:

• rear->next = ptr;: Connects the current rear node to the new node ptr.

• rear = ptr;: Updates rear to point to the new node ptr.

• rear->next = NULL;: Sets the next pointer of the new rear node (ptr) to NULL, indicating the end of the queue.

Algorithm

Allocate the space for the new node PTR

SET PTR -> DATA = VAL

IF FRONT = NULL
SET FRONT = REAR = PTR
SET FRONT -> NEXT = REAR -> NEXT = NULL
ELSE
SET REAR -> NEXT = PTR
SET REAR = PTR
SET REAR -> NEXT = NULL
[END OF IF]

END

1. Allocate the space for the new node PTR: This allocates memory for a new node and assigns it to the pointer PTR.

2. SET PTR -> DATA = VAL: Sets the DATA part of the new node to the value VAL.

3. IF FRONT = NULL: Checks if the list is empty.

   • SET FRONT = REAR = PTR: If the list is empty, FRONT and REAR are set to point to the new node (PTR). This means that FRONT and REAR both point to the first node in the list.

   • SET FRONT -> NEXT = REAR -> NEXT = NULL: Sets the NEXT pointers of both FRONT and REAR to NULL, as there's only one node in the list.

4. ELSE: If the list is not empty,

   • SET REAR -> NEXT = PTR: Sets the NEXT pointer of the current last node (REAR) to point to the new node (PTR), effectively linking the new node to the end of the list.

   • SET REAR = PTR: Moves the REAR pointer to the new last node (PTR).

   • SET REAR -> NEXT = NULL: Sets the NEXT pointer of the new last node (REAR) to NULL, indicating the end of the list.

function to insert an element in linked queue

void insert(struct node *ptr, int item)

{

ptr = (struct node *) malloc (sizeof(struct node));

if(ptr == NULL)

{

printf("\nOVERFLOW\n");

return;

}

else

{

ptr -> data = item;

if(front == NULL)

{

front = ptr;

rear = ptr;

front -> next = NULL;

rear -> next = NULL;

}

else

{

rear -> next = ptr;

rear = ptr;

rear->next = NULL;

}

}

}

ptr = (struct node *) malloc (sizeof(struct node));:

This line allocates memory for a new node and assigns the address of the allocated memory to ptr.

if(ptr == NULL):

This checks if memory allocation was successful. If not, it prints "OVERFLOW" and returns, indicating that the function was unable to insert the new node.

ptr -> data = item;:

Assigns the value of item to the data member of the newly created node.

if(front == NULL): Checks if the list is empty.

a. If the list is empty, front and rear are set to the newly created node ptr. Also, front -> next and rear -> next are set to NULL.

b. If the list is not empty, the new node is added after rear. rear -> next is updated to point to the new node ptr, and rear is updated to point to the new node.

Deletion Operation

The element that is initially placed out of all the queue elements is removed during a deletion operation. First, we must determine whether or not the list is empty. If the list is empty, the condition front == NULL becomes true; in this scenario, we just print underflow to the console and quit.

Else, it will delete the element that is pointed by the pointer front.

For this reason, copy the node pointed by the front pointer into the pointer ptr.

Now, move the front pointer, point to its next node and free the node pointed by the node ptr. This is done by using the following statements.

These statements are utilised to do this.

ptr = front;

front = front -> next;

free(ptr);

ptr = front;

Here, ptr is a pointer that will be used to temporarily store the address of the node that is being removed.

front = front -> next;

This line moves the front pointer to the next node, effectively removing the first node from the linked list.

free(ptr);

Finally, this line deallocates the memory occupied by the node that was removed.

In summary, this code segment removes the first node from the linked list and deallocates the memory occupied by that node.

Algorithm DeleteFromQueue()

if front is NULL

print "Queue is empty"

return

end if

temp = front

front = front -> next

free(temp)

if front is NULL

rear = NULL

end if

End Algorithm

1. Check if the queue is empty:
   We check if the front pointer is NULL. If it is NULL, it means the queue is empty. In this case, we print an error message and exit the function.

2. Create a temporary pointer and point it to the front of the queue:
   We create a temporary pointer temp and set it to point to the same node as front.

3. Move the front pointer to the next node:
   We move the front pointer to the next node in the queue, effectively removing the first node from the queue.

4. Free the memory occupied by the node pointed to by temp:
   We use the free() function to deallocate the memory occupied by the node pointed to by temp, which is the node we are removing from the queue.

5. Check if the queue is now empty:
   After deleting the node, we check if the queue is now empty. If the front pointer is NULL, it means the queue is empty. In this case, we set both the front and rear pointers to NULL.

Algorithm DeleteFromQueue()

if front is NULL

print "Queue is empty"

return

end if

// Create a temporary pointer and point it to the front of the queue

temp = front

// Move the front pointer to the next node

front = front -> next

// Free the memory occupied by the node pointed to by temp

free(temp)

// If the queue is now empty, set both front and rear to NULL

if front is NULL

rear = NULL

end if

End Algorithm

C function to delete an element from linked queue

void delete (struct node *ptr)

{

if(front == NULL)

{

printf("\nUNDERFLOW\n");

return;

}

else

{

ptr = front;

front = front -> next;

free(ptr);

}

}

1. Check if the queue is empty:

   • The function first checks if the queue is empty. This is done by checking if the front pointer is NULL. If it is NULL, it means the queue is empty, and the function prints "UNDERFLOW" and returns.

2. Delete the first node:

   • If the queue is not empty, it proceeds to delete the first node.

   • It assigns the front pointer to the ptr pointer. This step is not necessary because ptr is a local variable and changing it won't affect the caller's front pointer.

3. Move the front pointer to the next node:

   • It moves the front pointer to the next node in the queue, effectively removing the first node from the queue.

4. Free the memory occupied by the node:

   • It deallocates the memory occupied by the node pointed to by ptr using the free() function.

Includes

#include<stdio.h>

#include<stdlib.h>

These are standard C library includes. stdio.h for standard input/output functions like printf() and scanf(), and stdlib.h for malloc() and free().

Define a Structure:

struct node

{

int data;

struct node *next;

};

This defines a structure node which contains an integer data and a pointer to the next node.

Declare Global Pointers for Front and Rear:

struct node *front;

struct node *rear;

front and rear are pointers to the front and rear of the queue respectively.

• front: Points to the first element in the queue.

• rear: Points to the last element in the queue.

Function prototypes:

void insert();

void delete();

void display();

These are function prototypes for functions to insert, delete, and display elements in the queue.

Main function:

void main ()

{

int choice;

while(choice != 4)

{

printf("\n================Main Menu====================\n”);

printf(“\n————————————————————————————————————————————\n”);

printf("\n1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");

printf("\nEnter your choice ?");

scanf("%d",& choice);

switch(choice)

{

case 1:

insert();

break;

case 2:

delete();

break;

case 3:

display();

break;

case 4:

exit(0);

break;

default:

printf("\nEnter valid choice??\n");

}

}

}

This is the main function where the user can choose to insert an element, delete an element, display the queue, or exit the program.

1. void main(): The main() function is the entry point of the program. It returns void, indicating that it does not return any value.

2. int choice;: This variable is used to store the user's choice for the menu.

3. while(choice != 4): This loop continues until the user chooses to exit (i.e., until the user enters 4).

4. The printf() statements display the menu options to the user.

5. scanf("%d", &choice);: This statement reads the user's choice from the standard input (keyboard) and stores it in the choice variable.

6. The switch statement is used to perform different actions based on the user's choice:

   • case 1: If the user chooses 1, the insert() function is called to insert an element into the queue.

   • case 2: If the user chooses 2, the delete() function is called to delete an element from the queue.

   • case 3: If the user chooses 3, the display() function is called to display the elements of the queue.

   • case 4: If the user chooses 4, the exit(0) function is called to exit the program.

   • default: If the user enters a choice other than 1, 2, 3, or 4, an error message is displayed, and the user is prompted to enter a valid choice.

7. After performing the selected operation, the menu is displayed again, and the user is prompted to enter their choice.

8. This process continues until the user chooses to exit the program.

Now we’ll write code for Insert Function:

void insert()

{

struct node *ptr;

int item;

// Allocate memory for the new node

ptr = (struct node *) malloc (sizeof(struct node));

if(ptr == NULL)

{

printf("\nOVERFLOW\n");

return;

}

else

{

printf("\nEnter value?\n");

scanf("%d", &item);

ptr -> data = item;

// If the queue is empty

if(front == NULL)

{

front = ptr;

rear = ptr;

front -> next = NULL;

rear -> next = NULL;

}

else

{

rear -> next = ptr;

rear = ptr;

rear->next = NULL;

}

}

}

1. void insert(): This is the function definition for inserting an element into the queue.

2. struct node *ptr;: Declares a pointer to a structure of type node.

3. int item;: Declares a variable item to hold the value of the new node.

4. ptr = (struct node *) malloc (sizeof(struct node));: Allocates memory for a new node using malloc().

5. if(ptr == NULL) { printf("\nOVERFLOW\n"); return; }: Checks if memory allocation was successful. If ptr is NULL, it means memory allocation failed, and the function displays "OVERFLOW" and returns.

6. printf("\nEnter value?\n"); scanf("%d", &item); ptr -> data = item;: Asks the user for the value of the new node and assigns it to the data field of the new node.

7. if(front == NULL) { ... } else { ... }: Checks if the queue is empty or not.

   • If the queue is empty (front == NULL), the new node becomes the first and last node of the queue.

   • If the queue is not empty, the new node is added after the rear node, and rear is updated to point to the new node.

8. rear->next = NULL;: Ensures that the next pointer of the newly inserted node points to NULL, indicating the end of the queue.

This code assumes that front and rear are global pointers pointing to the front and rear of the queue, respectively, and that struct node is defined somewhere in the code.

Now lets write the delete function

void delete ()

{

struct node *ptr;

if(front == NULL)

{

printf("\nUNDERFLOW\n");

return;

}

else

{

ptr = front;

front = front -> next;

free(ptr);

}

}

1. void delete(): This is the function definition for deleting an element from the queue.

2. struct node *ptr;: Declares a pointer ptr to a structure of type node.

3. if(front == NULL) { printf("\nUNDERFLOW\n"); return; }: Checks if the queue is empty. If front is NULL, it means the queue is empty, and the function displays "UNDERFLOW" and returns.

4. ptr = front;: Assigns the front pointer to ptr.

5. front = front -> next;: Moves front to the next node in the queue, effectively removing the first node.

6. free(ptr);: Frees the memory allocated for the node pointed to by ptr, effectively deleting it.

Now lets write the code for the display function

void display()

{

struct node *ptr;

ptr = front;

if(front == NULL)

{

printf("\nEmpty queue\n");

}

else

{

printf("\nprinting values .....\n");

while(ptr != NULL)

{

printf("\n%d\n", ptr -> data);

ptr = ptr -> next;

}

}

}

1. void display(): This is the function definition for displaying the elements of the queue.

2. struct node *ptr;: Declares a pointer ptr to a structure of type node.

3. ptr = front;: Sets ptr to point to the front of the queue.

4. if(front == NULL) { printf("\nEmpty queue\n"); }: Checks if the queue is empty. If front is NULL, it means the queue is empty, and the function prints "Empty queue".

5. else { printf("\nprinting values .....\n"); ... }: If the queue is not empty, it prints "printing values ....." and then proceeds to print the data of each node in the queue.

6. while(ptr != NULL) { printf("\n%d\n", ptr -> data); ptr = ptr -> next; }: Iterates through the queue using ptr. For each node, it prints the value of data and moves ptr to the next node in the queue.

This program presents a menu-driven approach for inserting elements into, deleting elements from, and displaying elements of a queue.

So after compiling the code, a menu will be displayed.

out of which you have to choose the option

first we will choose option 1 to insert the element

it will ask you to enter the value to insert in the queue

I am going to enter 10

again it will prompt you to enter the choice

i will go once again for option 1 and insert the value 20

and i will repeat this option to insert 30

now I will go with option 2

program will call the delete function and ask you to enter the value

I will delete 20

now i ll choose to display the queue values it will display

10, 30

chose 4 to exit

Circular queue

Before going to learn about the circular queue lets first understand why the circular queue was introduced. The array implementation of Queue has one drawback. There's a chance that some empty spots may remain at the front of the queue that cannot be filled if the back of the queue reaches the end. Thus, the idea of the circular queue was presented in order to get around these restrictions.

The front of the queue is pointing somewhere instead than at position zero, while the back is at the last position. There are just two elements and three empty spaces in the array above. The back is the last point in the queue; if we attempt to insert the element, it will indicate that the queue is empty. One way to prevent this kind of memory waste is to move both components to the left and modify the front and back ends accordingly. It is not a very practical technique because it will take a lot of time to change every piece. Using the circular queue data structure is an effective way to prevent memory waste.

So lets understand about the circular queue.

When it comes to the FIFO (First In First Out) principle, a circular queue and a linear queue are comparable. However, in a circular queue, the positions are connected from the last to the first, forming a circle. An alternative name for it is a Ring Buffer.

Operations on Circular Queue

1. Enqueue (Insertion): Adds an element to the rear of the queue.

2. Dequeue (Deletion): Removes an element from the front of the queue.

3. isFull(): Checks whether the circular queue is full.

4. isEmpty(): Checks whether the circular queue is empty.

5. Display: Displays the elements of the circular queue.

Applications of circular queue

Circular queues are used in various applications where data is transferred in a circular manner. Here are some common applications of circular queues:

1. Operating System Buffers: Circular queues are often used in operating systems for task scheduling, managing interrupts, and in buffering.

2. Resource Allocation: In systems where resources are limited and need to be allocated efficiently, circular queues can be used. For example, printers often use circular queues to manage print jobs.

3. Network Traffic Management: Circular queues are used in network traffic management systems to control the flow of data packets.

4. Simulation Systems: In simulation systems, circular queues can be used to model waiting lines, such as queues in banks, restaurants, or supermarkets.

5. Job Scheduling: Circular queues are used in job scheduling algorithms to manage a queue of tasks or jobs waiting to be processed.

6. Data Buffers: Circular queues are used in data buffering applications where data is produced at one rate and consumed at another.

7. Memory Management: In memory management systems, circular queues can be used to manage memory blocks.

8. Keyboard Input Buffer: Circular queues are used in handling keyboard input in computer systems.

These are just a few examples, but circular queues are a fundamental data structure and find applications in many areas where data needs to be managed in a first-in-first-out (FIFO) manner.

Enqueue operation

Algorithm: Enqueue (Insertion) in Circular Queue

Input: Circular Queue (queue), Element to be inserted (element)

Output: Updated Circular Queue (queue)

1. If (rear + 1) % max_size == front

Display "Queue is full"

Return queue

2. If front == -1

Set front = 0

3. Set rear = (rear + 1) % max_size

4. Set queue[rear] = element

5. Return queue

• Step 1: Check if the circular queue is full. If (rear + 1) % max_size is equal to front, then the queue is full.

• Step 2: If front is -1, it means the queue is empty. Set front to 0.

• Step 3: Increment rear by 1, but since it's a circular queue, use modulo max_size to wrap around.

• Step 4: Insert the element at the position indicated by rear.

• Step 5: Return the updated circular queue.

Dequeue Operation

The steps of the dequeue operation are

• Firstly, check whether the Queue is empty or not. If the queue is empty, we cannot perform the dequeue operation.

• When the element is deleted, the value of front gets decremented by 1.

• If there is only one element left which is to be deleted, then the front and rear are reset to -1.

Algorithm: Dequeue (Deletion) in Circular Queue

Input: Circular Queue (queue), Front index (front), Rear index (rear)

Output: Updated Circular Queue (queue), Front index (front), Rear index (rear), Deleted Element (element)

1. If front == -1

Display "Queue is empty"

Return queue, front, rear, None

2. Set element = queue[front]

3. If front == rear

Set front = rear = -1

Return queue, front, rear, element

4. Set front = (front + 1) % max_size

5. Return queue, front, rear, element

• Step 1: Check if the circular queue is empty. If front is -1, then the queue is empty.

• Step 2: Store the element to be deleted (element).

• Step 3: If front and rear are equal after deletion, it means the queue becomes empty after this deletion. Reset front and rear to -1.

• Step 4: Increment front by 1, but since it's a circular queue, use modulo max_size to wrap around.

• Step 5: Return the updated circular queue along with the deleted element.

Program for implementation of a circular queue using an array in C:

#include <stdio.h>

#include <stdlib.h>

#define MAX_SIZE 5

// Structure to represent a circular queue

struct CircularQueue {

int items[MAX_SIZE];

int front, rear;

};

// Function to create a new circular queue

struct CircularQueue* createQueue() {

struct CircularQueue* queue = (struct CircularQueue*)malloc(sizeof(struct CircularQueue));

queue->front = -1;

queue->rear = -1;

return queue;

}

// Function to check if the queue is full

int isFull(struct CircularQueue* queue) {

if ((queue->front == 0 && queue->rear == MAX_SIZE - 1) || (queue->rear == (queue->front - 1) % (MAX_SIZE - 1))) {

return 1;

}

return 0;

}

// Function to check if the queue is empty

int isEmpty(struct CircularQueue* queue) {

return queue->front == -1;

}

// Function to add an element to the queue

void enqueue(struct CircularQueue* queue, int value) {

if (isFull(queue)) {

printf("Queue is full\n");

return;

}

if (isEmpty(queue)) {

queue->front = queue->rear = 0;

} else {

queue->rear = (queue->rear + 1) % MAX_SIZE;

}

queue->items[queue->rear] = value;

printf("%d enqueued to queue\n", value);

}

// Function to remove an element from the queue

int dequeue(struct CircularQueue* queue) {

int item;

if (isEmpty(queue)) {

printf("Queue is empty\n");

return -1;

}

if (queue->front == queue->rear) {

item = queue->items[queue->front];

queue->front = queue->rear = -1;

} else {

item = queue->items[queue->front];

queue->front = (queue->front + 1) % MAX_SIZE;

}

return item;

}

// Function to display the elements of the queue

void display(struct CircularQueue* queue) {

if (isEmpty(queue)) {

printf("Queue is empty\n");

return;

}

int i;

printf("Queue elements are: ");

if (queue->rear >= queue->front) {

for (i = queue->front; i <= queue->rear; i++)

printf("%d ", queue->items[i]);

} else {

for (i = queue->front; i < MAX_SIZE; i++)

printf("%d ", queue->items[i]);

for (i = 0; i <= queue->rear; i++)

printf("%d ", queue->items[i]);

}

printf("\n");

}

int main() {

struct CircularQueue* queue = createQueue();

enqueue(queue, 1);

enqueue(queue, 2);

enqueue(queue, 3);

enqueue(queue, 4);

enqueue(queue, 5);

enqueue(queue, 6);

display(queue);

printf("Dequeued element: %d\n", dequeue(queue));

printf("Dequeued element: %d\n", dequeue(queue));

display(queue);

enqueue(queue, 7);

enqueue(queue, 8);

display(queue);

return 0;

}

Double ended queue

A double-ended queue, often abbreviated as deque (pronounced "deck"), is a data structure that allows insertion and deletion of elements from both the front and the back. It is similar to a queue, but it allows insertion and deletion at both ends, making it more flexible.

Operations supported by deque are

1. Insertion:

   • Insertion at the front (push_front)

   • Insertion at the back (push_back)

2. Deletion:

   • Deletion from the front (pop_front)

   • Deletion from the back (pop_back)

3. Access:

   • Accessing the front element (front)

   • Accessing the back element (back)

Deques can be implemented using various data structures such as arrays, linked lists, or dynamic arrays.

Types of deque

There are two types of deque

• Input restricted queue

• Output restricted queue

Input restricted Queue

In input restricted queue, insertion operation can be performed at only one end, while deletion can be performed from both ends.

Output restricted Queue

In output restricted queue, deletion operation can be performed at only one end, while insertion can be performed from both ends.

Applications of deque

Deques are very versatile data structures and have numerous applications in computer science and real-world scenarios. Some of the common applications of deques include:

Implementing a Queue or a Stack:

Deques can be used to implement both queues and stacks efficiently. Using a deque, you can implement a queue that supports insertion and deletion from both ends, making it more flexible than a simple queue.

Sliding Window Problems:

Deques are often used to solve sliding window problems efficiently. Sliding window problems involve finding the maximum (or minimum) value of all contiguous subarrays of size k in an array of size n.

Undo Operations in Text Editors:

Deques can be used to implement the undo functionality in text editors efficiently. You can maintain a deque of the previous states of the text document and easily undo/redo operations.

Breadth-First Search (BFS):

Deques can be used to implement the queue data structure required for BFS traversal of graphs. BFS involves visiting all the nodes of a graph level by level.

Task Scheduling:

Deques can be used in task scheduling algorithms where tasks need to be scheduled based on their priority or other criteria.

Memory Management:

Deques are used in memory management algorithms, such as the buddy memory allocation technique, which divides memory into partitions to satisfy allocation requests.

Implementation of deque in C

#include <stdio.h>

#include <stdlib.h>

#define MAX_SIZE 100

typedef struct {

int data[MAX_SIZE];

int front, rear;

} Deque;

// Function to initialize deque

void initDeque(Deque *dq) {

dq->front = -1;

dq->rear = -1;

}

// Function to check if deque is empty

int isEmpty(Deque *dq) {

return (dq->front == -1 && dq->rear == -1);

}

// Function to check if deque is full

int isFull(Deque *dq) {

return ((dq->rear + 1) % MAX_SIZE == dq->front);

}

// Function to add element at front end of deque

void addFront(Deque *dq, int value) {

if (isFull(dq)) {

printf("Deque is full. Cannot add element.\n");

return;

}

if (isEmpty(dq)) {

dq->front = dq->rear = 0;

} else {

dq->front = (dq->front - 1 + MAX_SIZE) % MAX_SIZE;

}

dq->data[dq->front] = value;

}

// Function to add element at rear end of deque

void addRear(Deque *dq, int value) {

if (isFull(dq)) {

printf("Deque is full. Cannot add element.\n");

return;

}

if (isEmpty(dq)) {

dq->front = dq->rear = 0;

} else {

dq->rear = (dq->rear + 1) % MAX_SIZE;

}

dq->data[dq->rear] = value;

}

// Function to delete element from front end of deque

void deleteFront(Deque *dq) {

if (isEmpty(dq)) {

printf("Deque is empty. Cannot delete element.\n");

return;

}

if (dq->front == dq->rear) {

dq->front = dq->rear = -1;

} else {

dq->front = (dq->front + 1) % MAX_SIZE;

}

}

// Function to delete element from rear end of deque

void deleteRear(Deque *dq) {

if (isEmpty(dq)) {

printf("Deque is empty. Cannot delete element.\n");

return;

}

if (dq->front == dq->rear) {

dq->front = dq->rear = -1;

} else {

dq->rear = (dq->rear - 1 + MAX_SIZE) % MAX_SIZE;

}

}

// Function to get the front element of deque

int getFront(Deque *dq) {

if (isEmpty(dq)) {

printf("Deque is empty.\n");

return -1;

}

return dq->data[dq->front];

}

// Function to get the rear element of deque

int getRear(Deque *dq) {

if (isEmpty(dq)) {

printf("Deque is empty.\n");

return -1;

}

return dq->data[dq->rear];

}

// Function to display elements of deque

void display(Deque *dq) {

if (isEmpty(dq)) {

printf("Deque is empty.\n");

return;

}

printf("Deque elements: ");

int i = dq->front;

while (i != dq->rear) {

printf("%d ", dq->data[i]);

i = (i + 1) % MAX_SIZE;

}

printf("%d\n", dq->data[i]);

}

int main() {

Deque dq;

initDeque(&dq);

addFront(&dq, 10);

addRear(&dq, 20);

addFront(&dq, 30);

addRear(&dq, 40);

display(&dq); // Output: Deque elements: 30 10 20 40

deleteFront(&dq);

deleteRear(&dq);

display(&dq); // Output: Deque elements: 10 20

printf("Front element: %d\n", getFront(&dq)); // Output: Front element: 10

printf("Rear element: %d\n", getRear(&dq)); // Output: Rear element: 20

return 0;

}

PRIORITY QUEUE

A priority queue is a data structure that stores elements with associated priorities and allows for efficient retrieval of the element with the highest (or lowest) priority. It's similar to a regular queue, but each element has a priority value, and the element with the highest priority is always at the front of the queue.

Only comparable elements are supported by the priority queue, therefore the elements are either sorted in ascending or descending order.

Assume, for instance, that we have values 1, 3, 4, 8, 14, and 22 added to a priority queue and that the values are arranged from least to greatest. As a result, number 1 would have the highest priority while number 22 would have the lowest.

characteristics of a priority queue:

1. Ordered Elements: Elements in a priority queue are ordered based on their priority. Higher priority elements are dequeued before lower priority elements.
   

2. Support for Arbitrary Types: Priority queues can store elements of any data type, as long as they can be compared.
   

3. Priority-based Retrieval: The element with the highest priority is dequeued first. The priority can be defined based on a predefined order or using a custom comparator function.
   

4. No Order Guarantees: Unlike regular queues, there is no guarantee about the order in which elements are dequeued if they have the same priority.
   

5. Efficient Insertion and Removal: Priority queues are designed to efficiently insert and remove elements while maintaining the order based on priority.
   

Types of Priority Queue

There are two types of priority queue:

Ascending Order Priority Queue: In an ascending order priority queue, elements with lower priority numbers are considered higher priority. For instance, if we have numbers from 1 to 5 arranged in ascending order (1, 2, 3, 4, 5), the smallest number (1) is given the highest priority in the queue.

Descending order priority queue:

In a descending order priority queue, higher priority is assigned to numbers with higher values. For instance, if we consider the numbers 1 through 5 arranged in descending order (5, 4, 3, 2, 1), the highest priority is given to the largest number, which in this case is 5.

Program to Implementation of priority queue

The priority queue can be implemented in four different ways: using arrays, linked lists, the heap data structure, or binary search trees.

Here's a simple implementation of a priority queue in C using an array. This implementation assumes that lower numerical priority values indicate higher priority.

c

#include <stdio.h>

#include <stdlib.h>

#define MAX 100

typedef struct {

int data;

int priority;

} Element;

typedef struct {

Element elements[MAX];

int size;

} PriorityQueue;

void initPriorityQueue(PriorityQueue *pq) {

pq->size = 0;

}

void swap(Element *a, Element *b) {

Element temp = *a;

*a = *b;

*b = temp;

}

void heapifyUp(PriorityQueue *pq, int index) {

if (index && pq->elements[(index - 1) / 2].priority < pq->elements[index].priority) {

swap(&pq->elements[(index - 1) / 2], &pq->elements[index]);

heapifyUp(pq, (index - 1) / 2);

}

}

void heapifyDown(PriorityQueue *pq, int index) {

int left = 2 * index + 1;

int right = 2 * index + 2;

int largest = index;

if (left < pq->size && pq->elements[left].priority > pq->elements[largest].priority) {

largest = left;

}

if (right < pq->size && pq->elements[right].priority > pq->elements[largest].priority) {

largest = right;

}

if (largest != index) {

swap(&pq->elements[index], &pq->elements[largest]);

heapifyDown(pq, largest);

}

}

void enqueue(PriorityQueue *pq, int data, int priority) {

if (pq->size == MAX) {

printf("Priority Queue is full\n");

return;

}

pq->elements[pq->size].data = data;

pq->elements[pq->size].priority = priority;

pq->size++;

heapifyUp(pq, pq->size - 1);

}

int dequeue(PriorityQueue *pq) {

if (pq->size == 0) {

printf("Priority Queue is empty\n");

return -1;

}

int data = pq->elements[0].data;

pq->elements[0] = pq->elements[--pq->size];

heapifyDown(pq, 0);

return data;

}

int peek(PriorityQueue *pq) {

if (pq->size == 0) {

printf("Priority Queue is empty\n");

return -1;

}

return pq->elements[0].data;

}

int isEmpty(PriorityQueue *pq) {

return pq->size == 0;

}

int main() {

PriorityQueue pq;

initPriorityQueue(&pq);

enqueue(&pq, 10, 2);

enqueue(&pq, 30, 3);

enqueue(&pq, 20, 1);

enqueue(&pq, 40, 4);

while (!isEmpty(&pq)) {

printf("Dequeued element: %d\n", dequeue(&pq));

}

return 0;

}

The tree is a data structure representing hierarchical data with connected nodes.

If we want to show an organisation’s employees concerning their designation in a hierarchical form then it can be shown like this.

This is an organisation hierarchy in which the topmost position is of CEO Mr Karan who has 2 direct reports Ankita and Vikas.

Ankita has 3 direct reports Ishita, Rakshita, and Reem on the other side Vikas has 2 reporters Rahul and Sudesh.

Sudesh also has 2 reporters bharti and Krishna

at last, bharti has one reporter that is harsh.

Tree is an efficient way of storing the data in a hierarchical way

A tree data structure can be defined as a collection of entities called nodes, which are interconnected to represent or simulate a hierarchical structure.

A tree data structure is non-linear because its elements are not stored sequentially. Instead, it organizes elements in a hierarchical structure, arranging them across multiple levels.

In a tree data structure, the topmost node is called the root node. Each node holds some data, which can be of any type. In the example above, the nodes contain employee names, so the data type would be a string.

Each node contains data and a link or reference to other nodes, which are called children.

now let us see some of the basic terms used in the tree structure.

As you can see each node in a tree here is labeled with some number. Each arrow depicted in the figure above represents a connection between two nodes.

Root: The root node is the uppermost node in the tree hierarchy, meaning it is the node without a parent. In the structure shown here, the node numbered 1 is the root node of the tree. When a node is directly connected to another node, this forms a parent-child relationship.

Child node: If a node is a descendant of another node, it is referred to as a child node.

Parent: If a node contains any sub-nodes, it is referred to as the parent of those sub-nodes.

Sibling: Nodes that share the same parent are known as siblings.

Leaf Node: A node in a tree that does not have any child nodes is called a leaf node. It is the bottom-most node of the tree. A general tree can have any number of leaf nodes, which are also known as external nodes.

Internal Nodes: A node that has at least one child node is known as an internal node.

Ancestor Node: An ancestor of a node is any predecessor on the path from the root to that node. The root node has no ancestors. In the tree depicted in the image above, nodes 1, 2, and 5 are the ancestors of node 10.

Descendant: The immediate successor of a given node is known as its descendant. In the figure above, node 10 is a descendant of node 5.

Properties of Tree data structure

**Recursive Data Structure**: A tree is often referred to as a recursive data structure because it can be defined recursively. In a tree, the distinguished node is the root node, which contains links to the roots of its subtrees. For example, in the figure below, the left subtree is shown in yellow, and the right subtree is shown in red. The left subtree can be further divided into smaller subtrees, each shown in different colours. Recursion involves breaking down a problem into smaller, self-similar problems, and this recursive property of the tree data structure is utilized in various applications.

**Number of Edges**: In a tree with \( n \) nodes, there are \( n-1 \) edges. Each arrow in the structure represents a link or path. Every node, except the root node, has at least one incoming link called an edge. Each parent-child relationship is represented by one link.

**Depth of Node \( x \)**: The depth of node \( x \) is defined as the length of the path from the root to node \( x \). Each edge in the path contributes one unit to the length. Therefore, the depth of node \( x \) can also be described as the number of edges between the root node and node \( x \). The root node has a depth of 0.

**Height of Node \( x \)**: The height of node \( x \) is defined as the length of the longest path from node \( x \) to a leaf node.

Applications of Tree Data Structure

Hierarchical Data Organization

• File Systems: Trees are used to represent directories and files in a hierarchical structure. Each directory is a node with subdirectories or files as its children.

• XML/HTML Data Parsing: Documents are parsed into trees, where each tag represents a node in the tree, making it easy to traverse and manipulate structured data.

Search Operations

• Binary Search Trees (BST): Used for efficient searching, insertion, and deletion. They keep data sorted, enabling quick access (O(log n) average time complexity).

• Tries: A special tree structure used for fast prefix-based search, commonly seen in autocomplete systems and spell-checkers.

Databases and Indexing

• B-trees/B+ Trees: Commonly used in databases to store and retrieve large datasets efficiently, particularly for indexing operations.

• Database Indexes: Trees help in creating indexes that improve the speed of data retrieval operations.

Compilers and Expression Evaluation

• Abstract Syntax Trees (AST): In compilers, code is converted into an abstract syntax tree for parsing and optimization before generating machine code.

• Expression Trees: Represent mathematical expressions where leaves represent operands and internal nodes represent operators, used for evaluating arithmetic expressions.

Artificial Intelligence and Machine Learning

• Decision Trees: A widely used algorithm in machine learning for classification and regression tasks. They model decisions and their possible consequences.

• Game Trees: Used in AI to simulate potential moves in games like chess or checkers, analyzing different strategies based on possible outcomes.

Network Algorithms

• Spanning Trees: Used in network routing to ensure data is transmitted efficiently without redundancy, forming the basis for protocols like Ethernet and wireless communication.

• Routing Protocols: Many routing algorithms use trees to find the shortest path between nodes in a network.

Compression Algorithms

• Huffman Coding: A tree-based algorithm used in file compression (e.g., ZIP, GZIP) where characters are encoded using variable-length codes based on their frequency.

• File Compression: Trees enable efficient representation of data that helps reduce file sizes without losing information.

Graphics and User Interface Design

• Scene Graphs: In computer graphics, trees represent hierarchical relationships between objects in a scene, helping manage complex rendering tasks.

• DOM Trees: In web development, the Document Object Model (DOM) represents the structure of an HTML or XML document, allowing dynamic interaction with the content.

Peer-to-Peer Networks

• Distributed Hash Tables (DHT): Trees help organize data in decentralized networks, ensuring efficient data distribution and lookup in systems like blockchain and file-sharing platforms.

Biological and Phylogenetic Trees

• Phylogenetic Trees: Used in bioinformatics to model the evolutionary relationships among species, representing how they diverged from common ancestors.

• Genealogical Trees: Trees represent family histories, tracking relationships over generations.

Internet and Web

• Search Engine Algorithms: Many search engines rely on tree-like structures (e.g., tries or suffix trees) to index and quickly retrieve web pages based on search queries.

These examples highlight the broad use of trees across different domains, making them one of the most versatile data structures in computing.

Types of Tree data structures

There are several types of tree data structures, each designed for specific use cases.

we will just list out the types of trees here, and will learn one by one in detail, in upcoming videos.

1. **Binary Tree**

- A tree where each node has at most two children, referred to as the left and right child.

2. **Binary Search Tree (BST)**

- A special type of binary tree where for each node:

- The left child contains values less than the node.

- The right child contains values greater than the node.

3. **AVL Tree**

- A self-balancing binary search tree where the height difference between the left and right subtrees of any node is at most 1.

- It ensures O(log n) time complexity for insertion, deletion, and searching.

4. **Red-Black Tree**

- A balanced binary search tree where each node has an additional color attribute (either red or black) to ensure the tree remains balanced after insertions and deletions.

- The tree ensures O(log n) operations for searching, inserting, and deleting.

5. **B-Tree**

- A self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time.

- Commonly used in databases and file systems.

6. **Heap**

- A complete binary tree that satisfies the heap property:

- **Max-Heap**: Parent nodes are always greater than or equal to their children.

- **Min-Heap**: Parent nodes are always less than or equal to their children.

- Typically used to implement priority queues.

7. **Trie (Prefix Tree)**

- A tree used to store strings where each node represents a character of the string.

- It is widely used for efficient retrieval of keys in dictionaries, such as autocomplete systems.

8. **Segment Tree**

- A tree used for storing intervals or segments.

- It allows answering range queries efficiently (like sum, minimum, maximum) and can also be updated dynamically.

9. **Fenwick Tree (Binary Indexed Tree)**

- A data structure that provides efficient methods for calculating cumulative frequencies or sums and supports updates in logarithmic time.

- Often used in scenarios like frequency analysis and range queries.

10. **Suffix Tree**

- A compressed trie that represents all suffixes of a given string.

- It is mainly used in string processing algorithms for pattern matching and finding the longest common substring.

11. **k-ary Tree**

- A tree where each node can have up to **k** children.

- For example, a **3-ary tree** allows each node to have up to three children.

12. **Spanning Tree**

- A subgraph of a connected graph that includes all vertices with the minimum possible number of edges, forming a tree.

- Commonly used in network routing algorithms.

13. **Binary Heap**

- A binary tree-based data structure where every parent node is either greater than (max-heap) or less than (min-heap) its children.

14. **Ternary Tree**

- A tree data structure where each node has at most three children.

BInary Tree

A binary tree is a data structure in which each node has at most two children, referred to as the left child and the right child. It is a hierarchical structure where each node contains a value and pointers to its children.

Lets understand the binary tree thorugh an example

This is the binary tree because each node contains the utmost two children

This is the logical representation of the tree

In this tree node 1 has two pointers they are left and right pointer pointing to the left and right node respectively.

Node 2 has both nodes therefore it has two pointers

node 3, 5 and 6 are the leaf nodes, so all these nodes contain NULL pointers on both left and right side.

Properties of binary Tree

Each node has at most two children: a left child and a right child.

Leaf Nodes: are Nodes with no children.

Internal Nodes: are Nodes that have at least one child.

Height of a Tree: The length of the longest path from the root node to a leaf node. For a tree with a single node, the height is 0.

Depth of a Node: The length of the path from the root node to the node. The depth of the root node is 0.

Size of a Tree: is The total number of nodes in the tree

Level of a Node: The number of edges from the root node to the node. The root node is at level 0.

Each node in a binary tree can be the root of a subtree. A subtree consists of a node and all its descendants.

• The height of the tree is defined as the longest path from the root node to the leaf node. The tree which is shown above has a height equal to 3. Therefore, the maximum number of nodes at height 3 is equal to (1+2+4+8) = 15. In general, the maximum number of nodes possible at height h is (20 + 21 + 22+….2h) = 2h+1 -1.

• The minimum number of nodes possible at height h is equal to h+1.

• If the number of nodes is minimum, then the height of the tree would be maximum. Conversely, if the number of nodes is maximum, then the height of the tree would be minimum.

If there are 'n' number of nodes in the binary tree.

The minimum height can be computed as:

As we know that,

n = 2h+1 -1

n+1 = 2h+1

Taking log on both the sides,

log2(n+1) = log2(2h+1)

log2(n+1) = h+1

h = log2(n+1) - 1

log2(n+1) = log2(2h+1)

log2(n+1) = h+1

h = log2(n+1) - 1

Types of Binary Tree

There are four types of Binary tree:

• Full/ proper/ strict Binary tree

• Complete Binary tree

• Perfect Binary tree

• Degenerate Binary tree

• Balanced Binary tree

• Full/ proper/ strict Binary tree

FULL BINARY TREE

The terms "full binary tree," "proper binary tree," and "strict binary tree" are often used interchangeably, but they can have slightly different interpretations depending on the context. Here’s a clarification of each:

Definition: A binary tree in which every node has either 0 or 2 children. No node has only one child.

Properties:

• All internal nodes have exactly two children.

• All leaves are at the same level or depth.

Proper Binary Tree

• Definition: This is often used as a synonym for a full binary tree, where every node has either 0 or 2 children. However, in some contexts, "proper" may be used to describe a tree where all non-leaf nodes have exactly two children, and the leaves are at the same level.

• Properties:

  • Every node has 0 or 2 children.

  • Leaves may not necessarily be at the same level (depending on the definition used).

Strict Binary Tree

• Definition: This term is sometimes used interchangeably with "full binary tree" but can also refer to a binary tree where all nodes have either 0 or 2 children, with strict adherence to the binary structure.

• Properties:

  • Every node must have either 0 or exactly 2 children.

  • This structure is the same as that of a full binary tree.

Summary

• Full Binary Tree: All internal nodes have exactly two children; leaves are at the same level.

• Proper Binary Tree: Typically used to describe a binary tree where all nodes have either 0 or 2 children, though definitions may vary.

• Strict Binary Tree: Often used as a synonym for a full binary tree, indicating that every node has either 0 or 2 children.

In most contexts, these terms are used interchangeably, but it’s essential to clarify the definition if you encounter them in different contexts or sources.

Complete Binary Tree

A complete binary tree is a type of binary tree in which all levels are fully filled except possibly for the last level, which is filled from left to right. Here’s a diagram to illustrate a complete binary tree:

1

/ \

2 3

/ \ / \

4 5 6 7

/ \

8 9

Explanation:

1. Level 0: The root node 1 is at level 0.

2. Level 1: Nodes 2 and 3 are at level 1.

3. Level 2: Nodes 4, 5, 6, and 7 are at level 2.

4. Level 3: Nodes 8 and 9 are at level 3.

In a complete binary tree:

• All levels except the last are completely filled.

• In the last level, nodes are filled from left to right.

This tree is complete because:

• Every level above the last is fully populated.

• The last level is filled from the left up to a point, and there are no gaps on the left side.

Perfect binary tree

A perfect binary tree is a type of binary tree in which all internal nodes have exactly two children and all leaf nodes are at the same level. Here’s a diagram to illustrate a perfect binary tree:

1

/ \

2 3

/ \ / \

4 5 6 7

Explanation:

1. Level 0: The root node 1 is at level 0.

2. Level 1: Nodes 2 and 3 are at level 1.

3. Level 2: Nodes 4, 5, 6, and 7 are at level 2.

In a perfect binary tree:

• Every non-leaf node has exactly two children.

• All leaf nodes are at the same depth or level.

• All nodes are fully filled at every level.