Data Structure

Module I
1. Introduction of Data Structure:
• Data Structure, Date Structure Operations, abstract Data types (ADT),
Arrays, Structures, Pointers, Dynamic memory Management
• Asymptotic notations – Big-Oh, Theta, Omega, Linked Representation
of stacks, Applications of stacks, Example – infix, postfix and prefix.
2. Queues and Link List:
• Linked Representation of queues, queue as ADT, Circular queues,
priority queues, applications of queues.
• Linked List - Linked List, searching a linked list, insertion, deletion,
header linked list, circularly linked list, doubly linked list, buddy
systems.

Module II
1. Trees
• Binary Trees, representing binary tree in memory, traversing binary
trees, header nodes, threaded binary trees, binary search trees,
searching and inserting in binary search tree, deleting from a binary
search tree, application of trees.
2. Sorting
• Bubble sort, merge sort, quick sort, radix sort, insertion sort, selection
sort, heap sort, Performance analysis and comparison of all sorting
methods.
 Module III
1. Searching and Hashing Algorithms:
• Search algorithms – Sequential Search, Ordered lists, binary search,
Searching Using Hashing, Hash tables, Hash Functions, Some examples
of hash functions, Collision resolution methods, Complexity analysis of
searching methods.
2. Graphs:
• Graph theory terminology, sequential representation of graphs:
Adjacency matrix, path matrix, graph traversal – DFS, BFS,
Warshall’s algorithm.
• Dijkstra’s algorithm:- Shortest path, linked representation of graph,
operations on graph, topological sorting, spanning trees: Prim’s and
Kruskal’s algorithm.
 Introduction of Data Structure:

Data Structure:

Data Structure is the way of storing data in computer's memory so that it can
be used easily and efficiently. There are different data-structures used for the
storage of data. It can also be defined as a mathematical or logical model of
a particular organization of data items. The representation of particular data
structure in the main memory of a computer is called as storage structure.

For Examples: Array, Stack, Queue, Tree, Graph, etc.

Operations on different Data Structure:

There are different types of operations that can be performed for the
manipulation of data in every data structure. Some operations are explained
and illustrated below:

• Traversing: Traversing a Data Structure means to visit the element

stored in it. It visits data in a systematic manner. This can be done with
any type of DS.
Below is the program to illustrate traversal in an array, stack, queue and
LinkedList:

• Searching: Searching means to find a particular element in the given

data-structure. It is considered as successful when the required
element is found. Searching is the operation which we can performed
on data-structures like array, linked-list, tree, graph, etc.
Below is the program to illustrate searching an element in an array,
stack, queue and LinkedList:
• Insertion: It is the operation which we apply on all the data-
structures. Insertion means to add an element in the given data
structure. The operation of insertion is successful when the required
element is added to the required data-structure. It is unsuccessful in
some cases when the size of the data structure is full and when there
is no space in the data-structure to add any additional element. The
 insertion has the same name as an insertion in the data-structure as
an array, linked-list, graph, tree. In stack, this operation is called Push.
In the queue, this operation is called Enqueue.
Below is the program to illustrate insertion in array, stack, queue and
LinkedList :
• Deletion: It is the operation which we apply on all the data-
structures. Deletion means to delete an element in the given data
structure. The operation of deletion is successful when the required
element is deleted from the data structure. The deletion has the same
name as a deletion in the data-structure as an array, linked-list, graph,
tree, etc. In stack, this operation is called Pop. In Queue this operation
is called Dequeue.
Below is the program to illustrate dequeue in Stack, Queue and
LinkedList:

Create: -
It reserves memory for program elements by declaring them. The creation of
data structure Can be done during

1. Compile-time

2. Run-time.

You can use malloc() function.

Selection:-
It selects specific data from present data. You can select any specific data by
giving condition in loop .
Update
It updates the data in the data structure. You can also update any specific
data by giving some condition in loop like select approach.
Sort
Sorting data in a particular order (ascending or descending).
We can take the help of many sorting algorithms to sort data in less time.
Example: bubble sort which takes O(n^2) time to sort data.
There are many algorithms present like merge sort, insertion sort, selection
sort, quick sort, etc.
Merge
Merging data of two different orders in a specific order may ascend or
descend. We use merge sort to merge sort data.

Split Data
Dividing data into different sub-parts to make the process complete in less
time.

Programs:

1. Array Operations

Insertion and Traversal in Array

#include <stdio.h>

int main() {

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

int n = 5; // current size

int pos = 2, value = 99;

// Shift elements to the right

for (int i = n; i > pos; i--) {

arr[i] = arr[i - 1];

arr[pos] = value;

n++;

// Traversal

printf("Array after insertion:\n");

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

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

return 0;

Output:

Array after insertion:

1 2 99 3 4 5

[Link]
89a7ea98aa36

2. Linked List Operations

Insertion at Beginning and Traversal

#include <stdio.h>

#include <stdlib.h>

struct Node {

int data;

struct Node* next;

};

// Insert at beginning

struct Node* insertAtBeginning(struct Node* head, int value)

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

 newNode->data = value;

newNode->next = head;

return newNode;

// Traversal

void printList(struct Node* head) {

struct Node* temp = head;

while (temp != NULL) {

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

temp = temp->next;

printf("NULL\n");

int main() {

struct Node* head = NULL;

head = insertAtBeginning(head, 10);

head = insertAtBeginning(head, 20);

head = insertAtBeginning(head, 30);

printf("Linked List:\n");

printList(head);
 return 0;

Output:

Linked List:

30 -> 20 -> 10 -> NULL

[Link]

3. Stack Operations (Using Array)

Push and Pop

#include <stdio.h>

#define SIZE 5

int stack[SIZE], top = -1;

// Push

void push(int value)

if (top == SIZE - 1)

printf("Stack Overflow\n");

else

stack[++top] = value;

}
// Pop

void pop()

if (top == -1)

printf("Stack Underflow\n");

else

printf("Popped: %d\n", stack[top--]);

// Display

void display() {

printf("Stack: ");

for (int i = top; i >= 0; i--)

printf("%d ", stack[i]);

printf("\n");

int main() {

push(10);

push(20);

push(30);
 display();

pop();

display();

return 0;

Output:

Stack: 30 20 10

Popped: 30

Stack: 20 10

4. Queue Operations (Using Array)

Enqueue and Dequeue

#include <stdio.h>

#define SIZE 5

int queue[SIZE], front = -1, rear = -1;

// Enqueue

void enqueue(int value) {

if (rear == SIZE - 1)

printf("Queue Overflow\n");

else {
 if (front == -1) front = 0;

queue[++rear] = value;

// Dequeue

void dequeue() {

if (front == -1 || front > rear)

printf("Queue Underflow\n");

else

printf("Dequeued: %d\n", queue[front++]);

// Display

void display() {

printf("Queue: ");

for (int i = front; i <= rear; i++)

printf("%d ", queue[i]);

printf("\n");

int main() {
 enqueue(100);

enqueue(200);

enqueue(300);

display();

dequeue();

display();

return 0;

Output:

Queue: 100 200 300

Dequeued: 100

Queue: 200 300

5. Binary Tree Traversal (Inorder)

#include <stdio.h>

#include <stdlib.h>

struct Node {

int data;

struct Node* left;

struct Node* right;

};
// Create new node

struct Node* newNode(int value) {

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

node->data = value;

node->left = node->right = NULL;

return node;

// Inorder traversal

void inorder(struct Node* root) {

if (root != NULL) {

inorder(root->left);

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

inorder(root->right);

int main() {

struct Node* root = newNode(10);

root->left = newNode(20);

root->right = newNode(30);
 root->left->left = newNode(40);

printf("Inorder Traversal:\n");

inorder(root);

return 0;

Output:

Inorder Traversal:

40 20 10 30

Abstract Data Types

An Abstract Data Type (ADT) is a conceptual model that defines a set of
operations and behaviors for a data structure, without specifying how these
operations are implemented or how data is organized in memory. The
definition of ADT only mentions what operations are to be performed but
not how these operations will be implemented. It does not specify how data
will be organized in memory and what algorithms will be used for
implementing the operations. It is called "abstract" because it provides an
implementation-independent view.

The process of providing only the essentials and hiding the details is known
as abstraction.

Features of ADT
Abstract data types (ADTs) are a way of encapsulating data and operations
on that data into a single unit. Some of the key features of ADTs include:

• Abstraction: The user does not need to know the implementation of the
data structure only essentials are provided.

• Better Conceptualization: ADT gives us a better conceptualization of

the real world.

• Robust: The program is robust and has the ability to catch errors.

• Encapsulation: ADTs hide the internal details of the data and provide a
public interface for users to interact with the data. This allows for easier
maintenance and modification of the data structure.

• Data Abstraction: ADTs provide a level of abstraction from the

implementation details of the data. Users only need to know the
operations that can be performed on the data, not how those
operations are implemented.

• Data Structure Independence: ADTs can be implemented using

different data structures, such as arrays or linked lists, without affecting
the functionality of the ADT.

• Information Hiding: ADTs can protect the integrity of the data by

allowing access only to authorized users and operations. This helps
prevent errors and misuse of the data.

• Modularity: ADTs can be combined with other ADTs to form larger, more
complex data structures. This allows for greater flexibility and
modularity in programming.

Overall, ADTs provide a powerful tool for organizing and manipulating data in
a structured and efficient manner.
This image demonstrates how an Abstract Data Type (ADT) hides internal
data structures (like arrays, linked lists) using public and private functions,
exposing only a defined interface to the application program.

Why Use ADTs?

The key reasons to use ADTs in Java are listed below:

• Encapsulation: Hides complex implementation details behind a clean

interface.

• Reusability: Allows different internal implementations (e.g., array or

linked list) without changing external usage.

• Modularity: Simplifies maintenance and updates by separating logic.

• Security: Protects data by preventing direct access, minimizing bugs

and unintended changes.

Example of Abstraction

For example, we use primitive values like int, float, and char with the
understanding that these data types can operate and be performed on
without any knowledge of their implementation details. ADTs operate similarly
by defining what operations are possible without detailing their
implementation.

Examples of ADTs

Now, let's understand three common ADT's: List ADT, Stack ADT, and Queue
ADT.

1. List ADT

The List ADT (Abstract Data Type) is a sequential collection of elements that
supports a set of operations without specifying the internal implementation.
It provides an ordered way to store, access, and modify data.

Vies of list

Operations:

The List ADT need to store the required data in the sequence and should have
the following operations:

• get(): Return an element from the list at any given position.

• insert(): Insert an element at any position in the list.

• remove(): Remove the first occurrence of any element from a non-

empty list.

• removeAt(): Remove the element at a specified location from a non-

empty list.
 • replace(): Replace an element at any position with another element.

• size(): Return the number of elements in the list.

• isEmpty(): Return true if the list is empty; otherwise, return false.

• isFull(): Return true if the list is full, otherwise, return false. Only
applicable in fixed-size implementations (e.g., array-based lists).

2. Stack ADT

The Stack ADT is a linear data structure that follows the LIFO (Last In, First Out)
principle. It allows elements to be added and removed only from one end,
called the top of the stack.

View of stack

Operations:

In Stack ADT, the order of insertion and deletion should be according to the
FILO or LIFO Principle. Elements are inserted and removed from the same end,
called the top of the stack. It should also support the following operations:
 • push(): Insert an element at one end of the stack called the top.

• pop(): Remove and return the element at the top of the stack, if it is not
empty.

• peek(): Return the element at the top of the stack without removing it, if
the stack is not empty.

• size(): Return the number of elements in the stack.

• isEmpty(): Return true if the stack is empty; otherwise, return false.

• isFull(): Return true if the stack is full; otherwise, return false. Only
relevant for fixed-capacity stacks (e.g., array-based).

3. Queue ADT

The Queue ADT is a linear data structure that follows the FIFO (First In, First
Out) principle. It allows elements to be inserted at one end (rear) and
removed from the other end (front).

View of Queue

Operations:

The Queue ADT follows a design similar to the Stack ADT, but the order of
insertion and deletion changes to FIFO. Elements are inserted at one end
(called the rear) and removed from the other end (called the front). It should
support the following operations:
 • enqueue(): Insert an element at the end of the queue.

• dequeue(): Remove and return the first element of the queue, if the
queue is not empty.

• peek(): Return the element of the queue without removing it, if the
queue is not empty.

• size(): Return the number of elements in the queue.

• isEmpty(): Return true if the queue is empty; otherwise, return false.

Advantages and Disadvantages of ADT

Abstract data types (ADTs) have several advantages and disadvantages that
should be considered when deciding to use them in software development.
Here are some of the main advantages and disadvantages of using ADTs:

Advantage:

The advantages are listed below:

• Encapsulation: ADTs provide a way to encapsulate data and

operations into a single unit, making it easier to manage and modify
the data structure.

• Abstraction: ADTs allow users to work with data structures without

having to know the implementation details, which can simplify
programming and reduce errors.

• Data Structure Independence: ADTs can be implemented using

different data structures, which can make it easier to adapt to
changing needs and requirements.

• Information Hiding: ADTs can protect the integrity of data by controlling

access and preventing unauthorized modifications.
 • Modularity: ADTs can be combined with other ADTs to form more
complex data structures, which can increase flexibility and modularity
in programming.

Disadvantages:

The disadvantages are listed below:

• Overhead: Implementing ADTs can add overhead in terms of memory

and processing, which can affect performance.

• Complexity: ADTs can be complex to implement, especially for large

and complex data structures.

• Learning Curve: Using ADTs requires knowledge of their implementation

and usage, which can take time and effort to learn.

• Limited Flexibility: Some ADTs may be limited in their functionality or

may not be suitable for all types of data structures.

• Cost: Implementing ADTs may require additional resources and

investment, which can increase the cost of development.
 Array
Array is a linear data structure where all elements are arranged sequentially.
It is a collection of elements of same data type stored at contiguous memory
locations.

For simplicity, we can think of an array as a flight of stairs where on each step
is placed a value (let's say one of your friends). Here, you can identify the
location of any of your friends by simply knowing the count of the step they
are on.

This makes it easier to calculate the position of each element by simply

adding an offset to a base value, i.e., the memory location of the first element
of the array (generally denoted by the name of the array). The base value is
index 0 and the difference between the two indexes is the offset.

Is the array always of a fixed size?

Arrays at core are of fixed size only, but most of the languages provide
dynamic sized arrays using the underlying fixed sized arrays. For example,
vector in C++, ArrayList in Java and list in Python. In C language, the array has
a fixed size meaning once the size is given to it, it cannot be changed i.e. you
can’t shrink it nor can you expand it.

Array is a collection of items of the same variable type that are stored at
contiguous memory locations. It is one of the most popular and simple data
structures used in programming.

Basic terminologies of Array

• Array Index: In an array, elements are identified by their indexes. Array

index starts from 0.

• Array element: Elements are items stored in an array and can be

accessed by their index.

• Array Length: The length of an array is determined by the number of

elements it can contain.

Memory representation of Array

In an array, all the elements are stored in contiguous memory locations. So, if
we initialize an array, the elements will be allocated sequentially in memory.
This allows for efficient access and manipulation of elements.
Declaration of Array

Arrays can be declared in various ways in different languages. For better

illustration, below are some language-specific array declarations:

// This array will store integer type element

int arr[5];

// This array will store char type element

char arr[10];

// This array will store float type element

float arr[20];

Initializations of Array

Arrays can be initialized in different ways in different languages. Below are

some language-specific array initializations:
int arr[] = { 1, 2, 3, 4, 5 };

char arr[5] = { 'a', 'b', 'c', 'd', 'e' };

float arr[10] = { 1.4, 2.0, 24, 5.0, 0.0 };

Why do we Need Arrays?

Assume there is a class of five students and if we have to keep records of their
marks in examination then, we can do this by declaring five variables
individual and keeping track of records but what if the number of students
becomes very large, it would be challenging to manipulate and maintain the
data.

What it means is that, we can use normal variables (v1, v2, v3, ..) when we
have a small number of objects. But if we want to store a large number of
instances, it becomes difficult to manage them with normal variables.

The idea of an array is to represent many instances in one variable.

Types of Arrays

Arrays can be classified in two ways:

• On the basis of Size

• On the basis of Dimensions

Types of Arrays on the basis of Size

1. Fixed Sized Arrays

We cannot alter or update the size of this array. Here only a fixed size (i,e. the
size that is mentioned in square brackets []) of memory will be allocated for
storage. In case, we don't know the size of the array then if we declare a larger
size and store a lesser number of elements will result in a wastage of memory
or we declare a lesser size than the number of elements then we won't get
enough memory to store all the elements. In such cases, static memory
allocation is not preferred.

// Method 1 to create a fixed sized array.

// Here the memory is allocated at compile time.

int arr1[5];
// Another way (creation and initialization both)

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

// Method 2 to create a fixed sized array

// Here memory is allocated at run time (Also

// known as dynamically allocated arrays)

int *arr = (int*)malloc(n * sizeof(int));

2. Dynamic Sized Arrays

The size of the array changes as per user requirements during execution of
code so the coders do not have to worry about sizes. They can add and
removed the elements as per the need. The memory is mostly dynamically
allocated and de-allocated in these arrays.

// C does not seem to support

// dynamic sized arrays as of now

Types of Arrays on the basis of Dimensions

1. One-dimensional Array(1-D Array): You can imagine a 1d array as a row,

where elements are stored one after another.
2. Multi-dimensional Array: A multi-dimensional array is an array with more
than one dimension. We can use multidimensional array to store complex
data in the form of tables, etc. We can have 2-D arrays, 3-D arrays, 4-D arrays
and so on.

• Two-Dimensional Array(2-D Array or Matrix): 2-D Multidimensional

arrays can be considered as an array of arrays or as a matrix consisting
of rows and columns.
• Three-Dimensional Array(3-D Array): A 3-D Multidimensional
array contains three dimensions, so it can be considered an array of
two-dimensional arrays.
Operations on Array

1. Array Traversal

Array traversal refers to the process of accessing and processing each

element of an array sequentially. This is one of the most fundamental
operations in programming, as arrays are widely used data structures for
storing multiple elements in a single variable.

How Array Traversal Works?

When an array is created, it occupies a contiguous block of memory where

elements are stored in an indexed manner. Each element can be accessed
using its index, which starts from 0 in most programming languages.

For example, consider an array containing five integers:

arr = [10, 20, 30, 40, 50]

Here:

• The first element (10) is at index 0.

• The second element (20) is at index 1.

• The last element (50) is at index 4.

Array traversal means accessing each element from start to end (or
sometimes in reverse order), usually by using a loop.

Types of Array Traversal

Array traversal can be done in multiple ways based on the requirement:

1. Sequential (Linear) Traversal

• This is the most common way of traversing an array.

• It involves iterating through the array one element at a time from

the first index to the last.

• Used for printing elements, searching, or performing calculations

(such as sum or average).

2. Reverse Traversal

• Instead of starting from index 0, the traversal begins from the last
element and moves towards the first.

• This is useful in cases where we need to process elements from

the end.

2. Insertion in Array

Insertion in an array refers to the process of adding a new element at a

specific position while maintaining the order of the existing elements. Since
arrays have a fixed size in static implementations, inserting an element often
requires shifting existing elements to make space.

How Insertion Works in an Array?

Arrays are stored in contiguous memory locations, meaning elements are
arranged in a sequential block. When inserting a new element, the following
happens:

1. Identify the Position: Determine where the new element should be

inserted.

2. Shift Elements: Move the existing elements one position forward to

create space for the new element.

3. Insert the New Element: Place the new value in the correct position.

4. Update the Size (if applicable): If the array is dynamic, its size is
increased.

For example, if we have the array:

arr = [10, 20, 30, 40, 50]

and we want to insert 25 at index 2, the new array will be:

arr = [10, 20, 25, 30, 40, 50]

Here, elements 30, 40, and 50 have shifted right to make space.

Types of Insertion

1. Insertion at the Beginning (Index 0)

• Every element must shift one position right.

• This is the least efficient case for large arrays as it affects all elements.

2. Insertion at a Specific Index

• Elements after the index shift right.

• If the index is in the middle, half of the array moves.

3. Insertion at the End

 • The simplest case since no shifting is required.

• Used in dynamic arrays where size increases automatically (e.g., Python

lists, Java ArrayList).

3. Deletion in Array

Deletion in an array refers to the process of removing an element from a

specific position while maintaining the order of the remaining elements.
Unlike linked lists, where deletion is efficient, removing an element from an
array requires shifting elements to fill the gap.

How Deletion Works in an Array?

Since arrays have contiguous memory allocation, deleting an element does

not reduce the allocated memory size. Instead, it involves:

1. Identify the Position: Find the index of the element to be deleted.

2. Shift Elements: Move the elements after the deleted element one
position to the left.

3. Update the Size (if applicable): If using a dynamic array, the size might
be reduced.

For example, consider the array:

arr = [10, 20, 30, 40, 50]

If we delete the element 30 (index 2), the new array will be:

arr = [10, 20, 40, 50]

Here, elements 40 and 50 shifted left to fill the gap.

Types of Deletion

1. Deletion at the Beginning (Index 0)

• Every element shifts left by one position.

• This is the most expensive case as it affects all elements.

2. Deletion at a Specific Index

• Only elements after the index shift left.

• If the index is in the middle, half of the array moves.

3. Deletion at the End

• The simplest case since no shifting is required.

• The size of the array is reduced (in dynamic arrays).

4. Searching in Array

Searching in an array refers to the process of finding a specific element in a

given list of elements. The goal is to determine whether the element exists in
the array and, if so, find its index (position).

Searching is a fundamental operation in programming, as it is used in data

retrieval, filtering, and processing.

Types of Searching in an Array

There are two main types of searching techniques in an array:

1. Linear Search (Sequential Search)

• This is the simplest search algorithm.

• It traverses the array one element at a time and compares each

element with the target value.

• If a match is found, it returns the index of the element.

 • If the element is not found, the search continues until the end of the
array.

Example:

Consider an array:

arr = [10, 20, 30, 40, 50]

If we search for 30, the algorithm will:

1. Compare 10 with 30 → No match.

2. Compare 20 with 30 → No match.

3. Compare 30 with 30 → Match found at index 2.

2. Binary Search (Efficient Search for Sorted Arrays)

• Works only on sorted arrays (in increasing or decreasing order).

• Uses a divide and conquer approach.

• It repeatedly divides the search space in half until the target element is
found.

How Binary Search Works?

1. Find the middle element of the array.

2. If the target is equal to the middle element, return its index.

3. If the target is less than the middle element, search the left half.

4. If the target is greater than the middle element, search the right half.

5. Repeat until the element is found or the search space is empty.

Example:

Consider a sorted array:

arr = [10, 20, 30, 40, 50]

If we search for 30:

1. Middle element = 30 → Match found!

2. The search ends in just one step, making it much faster than linear
search.

Structure
C programming, a structure (struct) is a user-defined data type that allows
grouping together items of potentially different data types under a single
name. This contrasts with arrays, which store collections of elements of the
same data type.

Here's how structures are used in Data Structures and Algorithms (DSA) in C:

1. Defining a Structure:

Structures are defined using the struct keyword, followed by a tag name
(optional) and a list of members enclosed in curly braces. Each member has
a data type and a name.

struct Student {
char name[50];
int roll_number;
float marks;
};

2. Creating Structure Variables:

Once defined, you can declare variables of that structure type, similar to
declaring variables of primitive data types.

struct Student s1; // Declares a structure variable named s1

3. Accessing Structure Members:

Members of a structure are accessed using the dot (.) operator.

s1.roll_number = 101;
strcpy([Link], "Alice");
[Link] = 85.5;

4. Structures in DSA:

Structures are fundamental building blocks for implementing various data

structures in C:

• Linked Lists: Structures are used to define the nodes of a linked list, where
each node contains data and a pointer to the next node.

struct Node {
int data;
struct Node* next;
};

• Trees: Similar to linked lists, tree nodes are defined using structures,
containing data and pointers to child nodes.

struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};

• Queues and Stacks:

While arrays can be used, linked list implementations of queues and stacks
rely on structures for their nodes.

• Graphs:

Structures can represent vertices and edges in a graph, often involving

adjacency lists where each list element is a structure representing a neighbor.

Advantages of using Structures in DSA:

 • Organization: Structures allow logically related data of different types
to be grouped together, improving code readability and maintainability.

• Data Abstraction: They encapsulate data, making it easier to manage

complex data entities.

• Building Blocks: Structures serve as the foundation for creating more

complex and dynamic data structures like linked lists, trees, and graphs,
which are essential for efficient data management and algorithm
implementation.

In C, a structure is a user-defined data type that can be used to group items

of possibly different types into a single type. The struct keyword is used to
define a structure. The items in the structure are called its members and they
can be of any valid data type. Applications of structures involve creating data
structures Linked List and Tree. Structures in C are also used to represent real
world objects in a software like Students and Faculty in a college
management software.

Example:

#include <stdio.h>

// Defining a structure
struct A {
int x;
};

int main() {

// Creating a structure variable

struct A a;

// Initializing member
a.x = 11;
 printf("%d", a.x);
return 0;
}

Output

11

Explanation: In this example, a structure A is defined to hold an integer

member x. A variable a of type struct A is created and its member x is
initialized to 11 by accessing it using dot operator. The value of a.x is then
printed to the console.

Structures are used when you want to store a collection of different data
types, such as integers, floats, or even other structures under a single name.
To understand how structures are foundational to building complex data
structures.

Syntax of Structure

There are two steps of creating a structure in C:

1. Structure Definition

2. Creating Structure Variables

Structure Definition

A structure is defined using the struct keyword followed by the structure

name and its members. It is also called a structure template or
structure prototype, and no memory is allocated to the structure in the
declaration.

struct structure_name {
data_type1 member1;
data_type2 member2;
...
};

• structure_name: Name of the structure.

• member1, member2, ...: Name of the members.

• data_type1, data_type2, ...: Type of the members.

Be careful not to forget the semicolon at the end.

Creating Structure Variable

After structure definition, we have to create variable of that structure to use it.
It is similar to the any other type of variable declaration:

struct structure_name var;

We can also declare structure variables with structure definition.

struct structure_name {
...
}var1, var2....;

Basic Operations of Structure

Following are the basic operations commonly used on structures:

1. Access Structure Members

To access or modify members of a structure, we use the ( . ) dot operator. This

is applicable when we are using structure variables directly.

structure_name . member1;
structure_name . member2;

In the case where we have a pointer to the structure, we can also use
the arrow operator to access the members.
structure_ptr -> member1
structure_ptr -> member2

2. Initialize Structure Members

Structure members cannot be initialized with the declaration. For example,

the following C program fails in the compilation.

struct structure_name {
data_type1 member1 = value1; // COMPILER ERROR: cannot initialize members
here
data_type2 member2 = value2; // COMPILER ERROR: cannot initialize
members here
...
};

The reason for the above error is simple. When a datatype is declared, no
memory is allocated for it. Memory is allocated only when variables are
created. So there is no space to store the value assigned.

#include <stdio.h>
// Defining a structure to represent a student
struct Student {
char name[50];
int age;
float grade;
};
int main()
{
// Declaring and initializing a structure
// variable
struct Student s1 = {"Rahul",20, 18.5};
 // Designated Initializing another structure
struct Student s2 = {.age = 18, .name =
"Vikas", .grade = 22};

// Accessing structure members

printf("%s\t%d\t%.2f\n", [Link], [Link],
[Link]);
printf("%s\t%d\t%.2f\n", [Link], [Link],
[Link]);

return 0;
}

Output
Rahul 20 18.50
Vikas 18 22.00
We can initialize structure members in 4 ways which are as follows:

Default Initialization

By default, structure members are not automatically initialized to 0 or NULL.

Uninitialized structure members will contain garbage values. However, when a
structure variable is declared with an initializer, all members not explicitly
initialized are zero-initialized.

struct structure_name s = {0}; // Both x and y are initialized to 0

Initialization using Assignment Operator

struct structure_name str;

str.member1 = value1;
....
Note: We cannot initialize the arrays or strings using assignment operator
after variable declaration.

Initialization using Initializer List

struct structure_name str = {value1, value2, value3 ....};

In this type of initialization, the values are assigned in sequential order as they
are declared in the structure template.

Initialization using Designated Initializer List

Designated Initialization allows structure members to be initialized in any

order. This feature has been added in the C99 standard.

struct structure_name str = { .member1 = value1, .member2 = value2,

.member3 = value3 };

The Designated Initialization is only supported in C but not in C++.

3. Copy Structure

Copying structure is simple as copying any other variables. For example, s1 is

copied into s2 using assignment operator.

s2 = s1;

But this method only creates a shallow copy of s1 i.e. if the structure s1 have
some dynamic resources allocated by malloc, and it contains pointer to that
resource, then only the pointer will be copied to s2. If the dynamic resource is
also needed, then it has to be copied manually (deep copy).

#include <stdio.h>
#include <stdlib.h>
struct Student
{
int id;
char grade;
};

int main() {
struct Student s1 = {1, 'A'};

// Create a copy of student s1

struct Student s1c = s1;

printf("Student 1 ID: %d\n", [Link]);

printf("Student 1 Grade: %c", [Link]);
return 0;
}

Output
Student 1 ID: 1
Student 1 Grade: A

4. Passing Structure to Functions

Structure can be passed to a function in the same way as normal variables.

Though, it is recommended to pass it as a pointer to avoid copying a large
amount of data.

#include <stdio.h>
// Structure definition
struct A {
int x;
};
// Function to increment values
void increment(struct A a, struct A* b) {
a.x++;
b->x++;
}

int main() {
struct A a = { 10 };
struct A b = { 10 };

// Passing a by value and b by pointer

increment(a, &b);

printf("a.x: %d \tb.x: %d", a.x, b.x);

return 0;
}

Output
a.x: 10 b.x: 11

5. typedef for Structures

The typedef keyword is used to define an alias for the already existing
datatype. In structures, we have to use the struct keyword along with the
structure name to define the variables. Sometimes, this increases the length
and complexity of the code. We can use the typedef to define some new
shorter name for the structure.
#include <stdio.h>
// Defining structure
typedef struct {
int a;
} str1;

// Another way of using typedef with structures

typedef struct {
int x;
} str2;

int main() {

// Creating structure variables using new names

str1 var1 = { 20 };
str2 var2 = { 314 };

printf("var1.a = %d\n", var1.a);

printf("var2.x = %d\n", var2.x);
return 0;
}

Output
var1.a = 20
var2.x = 314
Explanation: In this code, str1 and str2 are defined as aliases for the unnamed
structures, allowing the creation of structure variables (var1 and var2) using
these new names. This simplifies the syntax when declaring variables of the
structure.

Size of Structures
Technically, the size of the structure in C should be the sum of the sizes of its
members. But it may not be true for most cases. The reason for this is
Structure Padding.

Structure padding is the concept of adding multiple empty bytes in the

structure to naturally align the data members in the memory. It is done to
minimize the CPU read cycles to retrieve different data members in the
structure.

There are some situations where we need to pack the structure tightly by
removing the empty bytes. In such cases, we use Structure Packing. C
language provides two ways for structure packing:

1. Using #pragma pack(1)

2. Using __attribute((packed))__

Nested Structures

In C, a nested structure refers to a structure that contains another structure

as one of its members. This allows you to create more complex data types by
grouping multiple structures together, which is useful when dealing with
related data that needs to be grouped within a larger structure.

There are two ways in which we can nest one structure into another:

• Embedded Structure Nesting: The structure being nested is also

declared inside the parent structure.

• Separate Structure Nesting: Two structures are declared separately

and then the member structure is nested inside the parent structure.

Accessing Nested Members

We can access nested Members by using the same ( . ) dot operator two
times as shown:

str_parent . str_child . member;

Example

#include <stdio.h>

// Child structure declaration

struct child {
int x;
char c;
};

// Parent structure declaration

struct parent {
int a;
struct child b;
};

int main() {
struct parent p = { 25, 195, 'A' };

// Accessing and printing nested members

printf("p.a = %d\n", p.a);
printf("p.b.x = %d\n", p.b.x);
printf("p.b.c = %c", p.b.c);
return 0;
}

Output
p.a = 25
p.b.x = 195
p.b.c = A
Explanation: In this code, the structure parent contains another
structure child as a member. The parent structure is then initialized with
values, including the values for the child structure's members.

Structure Pointer
A pointer to a structure allows us to access structure members using the ( -> )
arrow operator instead of the dot operator.

#include <stdio.h>

// Structure declaration

struct Point {

int x, y;

};

int main() {

struct Point p = { 1, 2 };

// ptr is a pointer to structure p

struct Point* ptr = &p;

// Accessing structure members using structure pointer

printf("%d %d", ptr->x, ptr->y);

return 0;

}
Output

12

Explanation: In this example, ptr is a pointer to the structure Point. It holds the
address of the structure variable p. The structure members x and y are
accessed using the -> operator, which is used to dereference the pointer and
access the members of the structure.

Self-Referential Structures

The self-referential structures are those structures that contain references to

the same type as themselves i.e. they contain a member of the type pointer
pointing to the same structure type.

Example:

struct str {
int mem1;

// Reference to the same type

struct str* next;
};

Such kinds of structures are used in different data structures such as to define
the nodes of linked lists, trees, etc.

Bit Fields

Bit Fields are used to specify the length of the structure members in bits.
When we know the maximum length of the member, we can use bit fields to
specify the size and reduce memory consumption.

Syntax
struct structure_name {
data_type member_name: width_of_bit-field;
};

Uses of Structure in C

C structures are used for the following:

1. The structure can be used to define the custom data types that can be
used to create some complex data types such as dates, time, complex
numbers, etc. which are not present in the language.

2. It can also be used in data organization where a large amount of data

can be stored in different fields.

3. Structures are used to create data structures such as trees, linked lists,
etc.

4. They can also be used for returning multiple values from a function.

A pointer is a variable that stores the memory address of another variable.

Instead of holding a direct value, it holds the address where the value is
stored in memory. It is the backbone of low-level memory manipulation in C.
Accessing the pointer directly will just give us the address that is stored in the
pointer. For example,

#include <stdio.h>

int main() {

// Normal Variable

int var = 10;

 // Pointer Variable ptr that

// stores address of var

int* ptr = &var;

// Directly accessing ptr will

// give us an address

printf("%d", ptr);

return 0;

Output

0x7fffa0757dd4

This hexadecimal integer (starting with 0x) is the memory address.

Let us understand different steps of the above program.

Declare a Pointer

A pointer is declared by specifying its name and type, just like simple variable
declaration but with an asterisk (*) symbol added before the pointer's name.

data_type* name

Here, data_type defines the type of data that the pointer is pointing to. An
integer type pointer can only point to an integer. Similarly, a pointer of float
type can point to a floating-point data, and so on.

Example:

int *ptr;

In the above statement, pointer ptr can store the address of an integer. It is
pronounced as pointer to integer.

Initialize the Pointer

Pointer initialization means assigning some address to the pointer variable. In

C, the (&) addressof operator is used to get the memory address of any
variable. This memory address is then stored in a pointer variable.

Example:

int var = 10;

// Initializing ptr

int *ptr = &var;

In the above statement, pointer ptr store the address of variable var which
was determined using address-of operator (&).

Note: We can also declare and initialize the pointer in a single step. This is
called pointer definition.

Dereference a Pointer
We have to first dereference the pointer to access the value present at the
memory address. This is done with the help of dereferencing
operator(*) (same operator used in declaration).

#include <stdio.h>

int main() {

int var = 10;

// Store address of var variable

int* ptr = &var;

// Dereferencing ptr to access the value

printf("%d", *ptr);

return 0;

Output

10

Note: Earlier, we used %d for printing pointers, but C provides a separate

format specifier %p for printing pointers.

Size of Pointers

The size of a pointer in C depends on the architecture (bit system) of the

machine, not the data type it points to.
 • On a 32-bit system, all pointers typically occupy 4 bytes.

• On a 64-bit system, all pointers typically occupy 8 bytes.

The size remains constant regardless of the data type (int*, char*, float*,
etc.). We can verify this using the sizeof operator.

#include <stdio.h>

int main() {

int *ptr1;

char *ptr2;

// Finding size using sizeof()

printf("%zu\n", sizeof(ptr1));

printf("%zu", sizeof(ptr2));

return 0;

Output

The reason for the same size is that the pointers store the memory addresses,
no matter what type they are. As the space required to store the addresses of
the different memory locations is the same, the memory required by one
pointer type will be equal to the memory required by other pointer types.
Note: The actual size of the pointer may vary depending on the compiler and
system architecture, but it is always uniform across all data types on the
same system.

Special Types of Pointers

There are 4 special types of pointers that used or referred to in different

contexts:

NULL Pointer

The NULL Pointers are those pointers that do not point to any memory
location. They can be created by assigning NULL value to the pointer. A
pointer of any type can be assigned the NULL value.

#include <stdio.h>

int main() {

// Null pointer

int *ptr = NULL;

return 0;

NULL pointers are generally used to represent the absence of any address.
This allows us to check whether the pointer is pointing to any valid memory
location by checking if it is equal to NULL.

Void Pointer

The void pointers in C are the pointers of type void. It means that they do not
have any associated data type. They are also called generic pointers as they
can point to any type and can be typecasted to any type.
#include <stdio.h>

int main() {

// Void pointer

void *ptr;

return 0;

Wild Pointers

The wild pointers are pointers that have not been initialized with something
yet. These types of C-pointers can cause problems in our programs and can
eventually cause them to crash. If values are updated using wild pointers,
they could cause data abort or data corruption.

#include <stdio.h>

int main() {

// Wild Pointer

int *ptr;

return 0;

Dangling Pointer
A pointer pointing to a memory location that has been deleted (or freed) is
called a dangling pointer. Such a situation can lead to unexpected behavior
in the program and also serve as a source of bugs in C programs.

#include <stdio.h>
#include <stdlib.h>

int main() {
int* ptr = (int*)malloc(sizeof(int));

// After below free call, ptr becomes a dangling pointer

free(ptr);
printf("Memory freed\n");

// removing Dangling Pointer

ptr = NULL;

return 0;
}

Output
Memory freed

C Pointer Arithmetic

The pointer arithmetic refers to the arithmetic operations that can be

performed on a pointer. It is slightly different from the ones that we generally
use for mathematical calculations as only a limited set of operations can be
performed on pointers. These operations include:

• Increment/Decrement

• Addition/Subtraction of Integer
 • Subtracting Two Pointers of Same Type

• Comparing/Assigning Two Pointers of Same Type

• Comparing/Assigning with NULL

C Pointers and Arrays

In C programming language, pointers and arrays are closely related. An array

name acts like a pointer constant. The value of this pointer constant is the
address of the first element. For example, if we have an array
named val, then val and &val[0] can be used interchangeably.

If we assign this value to a non-constant pointer to array of the same type,

then we can access the elements of the array using this pointer. Not only that,
as the array elements are stored continuously, we can use pointer arithmetic
operations such as increment, decrement, addition, and subtraction of
integers on pointer to move between array elements.

This concept is not limited to the one-dimensional array, we can refer to a

multidimensional array element as well using pointers.

Constant Pointers

In constant pointers, the memory address stored inside the pointer is

constant and cannot be modified once it is defined. It will always point to the
same memory address.

Example:

#include <stdio.h>

int main() {
int a = 90;
int b = 50;
 // Creating a constant pointer
int* const ptr = &a;

// Trying to reassign it to b
ptr = &b;

return 0;
}

Output
solution.c: In function ‘main’:
solution.c:11:9: error: assignment of read-only variable ‘ptr’
11 | ptr = &b;
| ^

Pointer to Function

A function pointer is a type of pointer that stores the address of a function,

allowing functions to be passed as arguments and invoked dynamically. It is
useful in techniques such as callback functions, event-driven programs.

Example:
#include <stdio.h>

int add(int a, int b) {

return a + b;
}

int main() {

// Declare a function pointer that matches

// the signature of add() fuction
 int (*fptr)(int, int);

// Assign address of add()

fptr = &add;

// Call the function via ptr

printf("%d", fptr(10, 5));

return 0;
}

Output
15

Multilevel Pointers

In C, we can create multi-level pointers with any number of levels such as –

***ptr3, ****ptr4, ******ptr5 and so on. Most popular of them is double
pointer (pointer to pointer). It stores the memory address of another pointer.
Instead of pointing to a data value, they point to another pointer.

Example:

#include <stdio.h>

int main() {
int var = 10;

// Pointer to int
int *ptr1 = &var;

// Pointer to pointer (double pointer)

 int **ptr2 = &ptr1;

// Accessing values using all three

printf("var: %d\n", var);
printf("*ptr1: %d\n", *ptr1);
printf("**ptr2: %d", **ptr2);

return 0;
}

Output
var: 10
*ptr1: 10
**ptr2: 10

Uses of Pointers in C

The C pointer is a very powerful tool that is widely used in C programming to

perform various useful operations. It is used to achieve the following
functionalities in C:

• Pass Arguments by Pointers

• Accessing Array Elements

• Return Multiple Values from Function

• Dynamic Memory Allocation

• Implementing Data Structures

• In System-Level Programming where memory addresses are useful.

• To use in Control Tables.

Advantages of Pointers

Following are the major advantages of pointers in C:

• Pointers are used for dynamic memory allocation and deallocation.

• An Array or a structure can be accessed efficiently with pointers

• Pointers are useful for accessing memory locations.

• Pointers are used to form complex data structures such as linked lists,
graphs, trees, etc.

• Pointers reduce the length of the program and its execution time as
well.

Issues with Pointers

Pointers are vulnerable to errors and have following disadvantages:

• Memory corruption can occur if an incorrect value is provided to

pointers.

• Pointers are a little bit complex to understand.

• Pointers are majorly responsible for memory leaks in C.

• Accessing using pointers are comparatively slower than variables in C.

• Uninitialized pointers might cause a segmentation fault.

 Dynamic Memory Allocation in C

Dynamic memory allocation techniques give programmer control of memory

when to allocate, how much to allocate and when to de-allocate.

• Normal local variable defined in a function is stored in the stack

memory.

• The limitations of such allocations are, size needs to known at compile

time, we cannot change the size or delete the memory.

The following images show issues with the normal stack based allocation for
an integer array.

• If we restrict the array size, then we might not be able to store more
elements later.

• If we allocate extra space for array, then this causes memory wastage.

Imagine this problem if you have an array of large objects like students in a
college.
With dynamic memory allocation,

• You allocate memory at runtime, giving you the ability to handle data of
varying sizes. Dynamic resources are stored in the heap memory
instead of the stack.

• The size of the array can be increased if more elements are to be

inserted and decreased of less elements are inserted.

• There is no need to estimate the max possible size. The size can be
decided at runtime according to the requirement.

Dynamic Memory Allocation in C

Dynamic memory allocation is possible in C by using the following 4 library

functions provided by <stdlib.h> library:

malloc()

The malloc() (stands for memory allocation) function is used to allocate a

single block of contiguous memory on the heap at runtime. The memory
allocated by malloc() is uninitialized, meaning it contains garbage values.
Syntax

malloc(size);

where size is the number of bytes to allocate.

This function returns a void pointer to the allocated memory that needs to be
converted to the pointer of required type to be usable. If allocation fails, it
returns NULL pointer.

Example

Assume that we want to create an array to store 5 integers. Since the size of
int is 4 bytes, we need 5 * 4 bytes = 20 bytes of memory. This can be done as
shown:

#include <stdio.h>
#include <stdlib.h>

int main() {
int *ptr = (int *)malloc(20);

// Populate the array

for (int i = 0; i < 5; i++)
ptr[i] = i + 1;

// Print the array

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

Output
12345
In the above malloc call, we hardcoded the number of bytes we need to store
5 integers. But we know that the size of the integer in C depends on the
architecture. So, it is better to use the sizeof operator to find the size of type
you want to store.
#include <stdio.h>
#include <stdlib.h>

int main() {
int *ptr = (int *)malloc(sizeof(int) * 5);

// Populate the array

for (int i = 0; i < 5; i++)
ptr[i] = i + 1;

// Print the array

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

Output
12345
Moreover, if there is no memory available, the malloc will fail and return NULL.
So, it is recommended to check for failure by comparing the ptr to NULL.
#include <stdio.h>
#include <stdlib.h>

int main() {
int *ptr = (int *)malloc(sizeof(int) * 5);

// Checking if failed or pass

 if (ptr == NULL) {
printf("Allocation Failed");
exit(0);
}

// Populate the array

for (int i = 0; i < 5; i++)
ptr[i] = i + 1;

// Print the array

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

Output
12345
calloc()

The calloc() (stands for contiguous allocation) function is similar to malloc(),

but it initializes the allocated memory to zero. It is used when you need
memory with default zero values.

Syntax

calloc(n, size);

where n is the number of elements and size is the size of each element in
bytes.

This function also returns a void pointer to the allocated memory that is
converted to the pointer of required type to be usable. If allocation fails, it
returns NULL pointer.

Example

We can take the example of malloc() and try to do it with calloc() function.

#include <stdio.h>
#include <stdlib.h>

int main() {
int *ptr = (int *)calloc(5, sizeof(int));

// Checking if failed or pass

if (ptr == NULL) {
printf("Allocation Failed");
exit(0);
}

// No need to populate as already

// initialized to 0
 // Print the array
for (int i = 0; i < 5; i++)
printf("%d ", ptr[i]);
return 0;
}

Output
00000

free()
The memory allocated using functions malloc() and calloc() is not de-
allocated on their own. The free() function is used to release dynamically
allocated memory back to the operating system. It is essential to free
memory that is no longer needed to avoid memory leaks.
Syntax
free(ptr);
where ptr is the pointer to the allocated memory.
After freeing a memory block, the pointer becomes invalid, and it is no longer
pointing to a valid memory location.
Example
#include <stdio.h>
#include <stdlib.h>

int main() {
int *ptr = (int *)calloc(5, sizeof(int));

// Do some operations.....
for (int i = 0; i < 5; i++)
printf("%d ", ptr[i]);

// Free the memory after completing

// operations
free(ptr);

return 0;
}

Output
00000
After calling free(), it is a good practice to set the pointer to NULL to avoid
using a "dangling pointer," which points to a memory location that has been
deallocated.
ptr = NULL;
realloc()

realloc() function is used to resize a previously allocated memory block. It

allows you to change the size of an existing memory allocation without
needing to free the old memory and allocate a new block.

Syntax

realloc(ptr, new_size);

where, ptr is the pointer to the previously allocated memory block

and new_size is the reallocated size that the memory block should have in
bytes.

This function returns a pointer to the newly allocated memory, or NULL if the
reallocation fails. If it fails, the original memory block remains unchanged.

Example

Suppose we initially allocate memory for 5 integers but later need to expand
the array to hold 10 integers. We can use realloc() to resize the memory block:

#include <stdio.h>

#include <stdlib.h>

int main() {
int *ptr = (int *)malloc(5 * sizeof(int));

// Resize the memory block to hold 10 integers

ptr = (int *)realloc(ptr, 10 * sizeof(int));

// Check for allocation failure

if (ptr == NULL) {
printf("Memory Reallocation Failed");
exit(0);
 }

return 0;
}

It is important to note that if realloc() fails and returns NULL, the original
memory block is not freed, so you should not overwrite the original pointer
until you've successfully allocated a new block. To prevent memory leaks, it’s
a good practice to handle the NULL return value carefully:
#include <stdio.h>
#include <stdlib.h>

int main() {
int *ptr = (int *)malloc(5 * sizeof(int));

// Reallocation
int *temp = (int *)realloc(ptr, 10 * sizeof(int));

// Only update the pointer if reallocation is successful

if (temp == NULL)
 printf("Memory Reallocation Failed\n");
else
ptr = temp;

return 0;
}
Asymptotic Notations for Analysis of Algorithms
We have discussed Asymptotic Analysis, and Worst, Average, and Best Cases
of Algorithms. The main idea of asymptotic analysis is to have a measure of
the efficiency of algorithms that don't depend on machine-specific constants
and don't require algorithms to be implemented and time taken by programs
to be compared. Asymptotic notations are mathematical tools to represent
the time complexity of algorithms for asymptotic analysis.
Asymptotic Notations:
• Asymptotic Notations are mathematical tools used to analyze the
performance of algorithms by understanding how their efficiency
changes as the input size grows.
• These notations provide a concise way to express the behavior of an
algorithm's time or space complexity as the input size approaches
infinity.
• Rather than comparing algorithms directly, asymptotic analysis focuses
on understanding the relative growth rates of algorithms' complexities.
• It enables comparisons of algorithms' efficiency by abstracting away
machine-specific constants and implementation details, focusing
instead on fundamental trends.
• Asymptotic analysis allows for the comparison of algorithms' space and
time complexities by examining their performance characteristics as
the input size varies.
• By using asymptotic notations, such as Big O, Big Omega, and Big Theta,
we can categorize algorithms based on their worst-case, best-case, or
 average-case time or space complexities, providing valuable insights
into their efficiency.
There are mainly three asymptotic notations:
1. Big-O Notation (O-notation)
2. Omega Notation (Ω-notation)
3. Theta Notation (Θ-notation)
1. Theta Notation (Θ-Notation):
Theta notation encloses the function from above and below. Since it
represents the upper and the lower bound of the running time of an
algorithm, it is used for analyzing the average-case complexity of an
algorithm.
.Theta (Average Case) You add the running times for each possible input
combination and take the average in the average case.
Let g and f be the function from the set of natural numbers to itself. The
function f is said to be Θ(g), if there are constants c1, c2 > 0 and a natural
number n0 such that c1* g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0

Mathematical Representation of Theta notation:

Θ (g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 ≤ c1 *
g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0}
Note: Θ(g) is a set
The above expression can be described as if f(n) is theta of g(n), then the
value f(n) is always between c1 * g(n) and c2 * g(n) for large values of n (n ≥
n0). The definition of theta also requires that f(n) must be non-negative for
values of n greater than n0.
The execution time serves as both a lower and upper bound on the
algorithm's time complexity.
It exist as both, most, and least boundaries for a given input value.
A simple way to get the Theta notation of an expression is to drop low-order
terms and ignore leading constants. For example, Consider the
expression 3n3 + 6n2 + 6000 = Θ(n3), the dropping lower order terms is always
fine because there will always be a number(n) after which Θ(n3) has higher
values than Θ(n2) irrespective of the constants involved. For a given function
g(n), we denote Θ(g(n)) is following set of functions.
Examples :
{ 100 , log (2000) , 10^4 } belongs to Θ(1)
{ (n/4) , (2n+3) , (n/100 + log(n)) } belongs to Θ(n)
{ (n^2+n) , (2n^2) , (n^2+log(n))} belongs to Θ( n2)
Note: Θ provides exact bounds.
2. Big-O Notation (O-notation):
Big-O notation represents the upper bound of the running time of an
algorithm. Therefore, it gives the worst-case complexity of an algorithm.
.It is the most widely used notation for Asymptotic analysis.
.It specifies the upper bound of a function.
.The maximum time required by an algorithm or the worst-case time
complexity.
.It returns the highest possible output value(big-O) for a given input.
.Big-O(Worst Case) It is defined as the condition that allows an algorithm to
complete statement execution in the longest amount of time possible.

If f(n) describes the running time of an algorithm, f(n) is O(g(n)) if there exist
a positive constant C and n0 such that, 0 ≤ f(n) ≤ cg(n) for all n ≥ n0
It returns the highest possible output value (big-O)for a given input.
The execution time serves as an upper bound on the algorithm's time
complexity.

Mathematical Representation of Big-O Notation:

O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤
cg(n) for all n ≥ n0 }
For example, Consider the case of Insertion Sort. It takes linear time in the best
case and quadratic time in the worst case. We can safely say that the time
complexity of the Insertion sort is O(n2).
Note: O(n2) also covers linear time.
If we use Θ notation to represent the time complexity of Insertion sort, we have
to use two statements for best and worst cases:
• The worst-case time complexity of Insertion Sort is Θ(n2).
• The best case time complexity of Insertion Sort is Θ(n).
The Big-O notation is useful when we only have an upper bound on the time
complexity of an algorithm. Many times we easily find an upper bound by
simply looking at the algorithm.
Examples :
{ 100 , log (2000) , 10^4 } belongs to O(1)
U { (n/4) , (2n+3) , (n/100 + log(n)) } belongs to O(n)
U { (n^2+n) , (2n^2) , (n^2+log(n))} belongs to O( n^2)
Note: Here, U represents union, we can write it in these manner because O
provides exact or upper bounds .
3. Omega Notation (Ω-Notation):
Omega notation represents the lower bound of the running time of an
algorithm. Thus, it provides the best case complexity of an algorithm.
The execution time serves as a lower bound on the algorithm's time
complexity.
It is defined as the condition that allows an algorithm to complete
statement execution in the shortest amount of time.
Let g and f be the function from the set of natural numbers to itself. The
function f is said to be Ω(g), if there is a constant c > 0 and a natural number
n0 such that c*g(n) ≤ f(n) for all n ≥ n0

Mathematical Representation of Omega notation :

Ω(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤
f(n) for all n ≥ n0 }
Let us consider the same Insertion sort example here. The time complexity of
Insertion Sort can be written as Ω(n), but it is not very useful information about
insertion sort, as we are generally interested in worst-case and sometimes in
the average case.
Examples :
{ (n^2+n) , (2n^2) , (n^2+log(n))} belongs to Ω( n^2)
U { (n/4) , (2n+3) , (n/100 + log(n)) } belongs to Ω(n)
U { 100 , log (2000) , 10^4 } belongs to Ω(1)
Note: Here, U represents union, we can write it in these manner because Ω
provides exact or lower bounds.

Stack - Linked List Implementation

To implement a stack using a singly linked list, we follow the LIFO (Last In, First
Out) principle by inserting and removing elements from the head of the list,
where each node stores data and a pointer to the next node.
In the stack Implementation, a stack contains a top pointer. which is the
"head" of the stack where pushing and popping items happens at the head of
the list. The first node has a null in the link field and second node-link has the
first node address in the link field and so on and the last node address is in
the "top" pointer.
• The main advantage of using a linked list over arrays is that it is
possible to implement a stack that can shrink or grow as much as
needed.
 • Using an array will put a restriction on the maximum capacity of the
array which can lead to stack overflow. Here each new node will be
dynamically allocated. so overflow is not possible.
• If we use built in dynamic sized arrays like vector in C++, list in Python or
ArrayList in Java, we get automatically growing stack, but the worst
case time complexity is not O(1) for push() and pop() as there might be
a resizing step once in a while. With Linked List, we get worst case O(1).
Stack Operations
• push(): Insert a new element into the stack (i.e just insert a new
element at the beginning of the linked list.)
• pop(): Return the top element of the Stack (i.e simply delete the first
element from the linked list.)
• peek(): Return the top element.
• display(): Print all elements in Stack.
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// Node structure
struct Node {
int data;
struct Node* next;
};

// Check if stack is empty

int isEmpty(struct Node* head) {
return head == NULL;
}

// Push an element onto stack

void push(struct Node** head, int new_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
 new_node->next = *head;
*head = new_node;
}

// Pop the top element

void pop(struct Node** head) {
if (isEmpty(*head)) return;
struct Node* temp = *head;
*head = (*head)->next;
free(temp);
}

// Return the top element

int peek(struct Node* head) {
if (!isEmpty(head)) return head->data;
return INT_MIN;
}

int main() {
struct Node* head = NULL;

push(&head, 11);
push(&head, 22);
push(&head, 33);
push(&head, 44);

printf("%d\n", peek(head));

pop(&head);
pop(&head);

printf("%d\n", peek(head));

return 0;
}
Output : 44 22
Time Complexity: O(1), for all push(), pop(), and peek(), as we are not
performing any kind of traversal over the list.
Auxiliary Space: O(n), where n is the size of the stack

Applications of stacks
A stack is a linear data structure in which the insertion of a new element and
removal of an existing element takes place at the same end represented as
the top of the stack.

application of Stacks:
• Function calls: Stacks are used to keep track of the return addresses of
function calls, allowing the program to return to the correct location
after a function has finished executing.
• Recursion: Stacks are used to store the local variables and return
addresses of recursive function calls, allowing the program to keep
track of the current state of the recursion.
• Expression evaluation: Stacks are used to evaluate expressions in
postfix notation (Reverse Polish Notation).
• Syntax parsing: Stacks are used to check the validity of syntax in
programming languages and other formal languages.
• Memory management: Stacks are used to allocate and manage
memory in some operating systems and programming languages.
• Used to solve popular problems like Next Greater, Previous Greater, Next
Smaller, Previous Smaller, Largest Area in a Histogram and Stock Span
Problems.

• Example – infix, postfix and prefix.

Infix, Postfix and Prefix Expressions/Notations
Mathematical formulas often involve complex expressions that require
a clear understanding of the order of operations. To represent these
expressions, we use different notations, each with its own advantages
and disadvantages. In this article, we will explore three common
expression notations: infix, prefix, and postfix.
Infix Expressions
Infix expressions are mathematical expressions where the operator is
placed between its operands. This is the most common mathematical
notation used by humans. For example, the expression "2 + 3" is an infix
expression, where the operator "+" is placed between the operands "2"
and "3".
Infix notation is easy to read and understand for humans, but it can be
difficult for computers to evaluate efficiently. This is because the order
of operations must be taken into account, and parentheses can be
used to override the default order of operations.
Common way of writing Infix expressions:
• Infix notation is the notation that we are most familiar with. For example,
the expression "2 + 3" is written in infix notation.
• In infix notation, operators are placed between the operands they
operate on. For example, in the expression "2 + 3", the addition operator
"+" is placed between the operands "2" and "3".
• Parentheses are used in infix notation to specify the order in which
operations should be performed. For example, in the expression "(2 + 3)
* 4", the parentheses indicate that the addition operation should be
performed before the multiplication operation.
Operator precedence rules:
Infix expressions follow operator precedence rules, which determine
the order in which operators are evaluated. For example, multiplication
and division have higher precedence than addition and subtraction.
This means that in the expression "2 + 3 * 4", the multiplication operation
will be performed before the addition operation.
Here's the table summarizing the operator precedence rules for
common mathematical operators:

Precedence
Operator

Parentheses () Highest

Exponents ^ High

Multiplication * Medium

Division / Medium

Addition + Low

Subtraction - Low

Evaluating Infix Expressions

Evaluating infix expressions requires additional processing to handle the
order of operations and parentheses. First convert the infix
expression to postfix notation. This can be done using a stack or a
recursive algorithm. Then evaluate the postfix expression.
Advantages of Infix Expressions
• More natural and easier to read and understand for humans.
• Widely used and supported by most programming languages and
calculators.
Disadvantages Infix Expressions
• Requires parentheses to specify the order of operations.
• Can be difficult to parse and evaluate efficiently.
Prefix Expressions (Polish Notation)
Prefix expressions are also known as Polish notation, are a
mathematical notation where the operator precedes its operands. This
differs from the more common infix notation, where the operator is
placed between its operands.
In prefix notation, the operator is written first, followed by its operands.
For example, the infix expression "a + b" would be written as "+ a b" in
prefix notation.
Evaluating Prefix Expressions
Evaluating prefix expressions can be useful in certain scenarios, such as
when dealing with expressions that have a large number of nested
parentheses or when using a stack-based programming language.
Advantages of Prefix Expressions
• No need for parentheses, as the operator always precedes its operands.
• Easier to parse and evaluate using a stack-based algorithm.
• Can be more efficient in certain situations, such as when dealing with
expressions that have a large number of nested parentheses.
Disadvantages of Prefix Expressions
• Can be difficult to read and understand for humans.
• Not as commonly used as infix notation.
Postfix Expressions (Reverse Polish Notation)
Postfix expressions are also known as Reverse Polish Notation (RPN),
are a mathematical notation where the operator follows its operands.
This differs from the more common infix notation, where the operator is
placed between its operands.
 Postfix
Notation
Prefix
(Reverse
Notation
Polish
Infix (Polish
Notation)
spect Notation Notation)

Less Less

human- human-
Human-
readable, readable,
readable
requires requires
Readabili
familiarity familiarity
ty

Operator
Between Before After
Placeme
operands operands operands
nt

Parenthe
ses Often Not Not

Requirem required required required

ent

Required, Not Not

parenthes required, required,

es operators operators
Operator
determine have fixed have fixed
Preceden
precedenc precedenc precedenc
ce
e e e
Tracking

Left-to- Right-to- Left-to-

Evaluatio
right left right
n Method
 Postfix
Notation
Prefix
(Reverse
Notation
Polish
Infix (Polish
Notation)
spect Notation Notation)

May
Ambiguity Ambiguity
require
rare, rare,
explicit use
straightfor straightfor
Ambiguit of
ward ward
y parenthes
evaluation evaluation
Handling es

Simplified Simplified

Requires handling handling

careful due to due to

Unary
placement explicit explicit
Operator
notation notation
Handling

Less
More More
efficient
efficient efficient
due to
due to fixed due to fixed
precedenc
precedenc precedenc
e tracking
e and e and
and
absence of absence of
Compute parenthes
parenthese parenthese
r es
s s
Efficiency handling
 Postfix
Notation
Prefix
(Reverse
Notation
Polish
Infix (Polish
Notation)
spect Notation Notation)

Common
Common in Common in
in
computer computer
everyday
science science
arithmetic
and and
and
programmi programmi
mathemat
ng ng
ical
languages languages
Usage notation

In postfix notation, operands are written first, followed by the operator.

For example, the infix expression "5 + 2" would be written as "5 2 +" in
postfix notation.
Evaluating Postfix Expressions (Reverse Polish Notation)
Evaluating postfix expressions can be useful in certain scenarios, such
as when dealing with expressions that have a large number of nested
parentheses or when using a stack-based programming language.
Advantages of Postfix Notation
• Also eliminates the need for parentheses.
• Easier to read and understand for humans.
• More commonly used than prefix notation.
Disadvantages of Postfix Expressions
• Requires a stack-based algorithm for evaluation.
• Can be less efficient than prefix notation in certain situations.
Comparison of Infix, Prefix and Postfix Expressions
Let's compare infix, prefix, and postfix notations across various criteria:
 Queues and Link List
Linked Representation of queues
Queue - Linked List Implementation
In this article, the Linked List implementation of the queue data structure is
discussed and implemented. Print '-1' if the queue is empty.
Approach: To solve the problem follow the below idea:
we maintain two pointers, front and rear. The front points to the first item of
the queue and rear points to the last item.
• enQueue(): This operation adds a new node after the rear and moves
the rear to the next node.
• deQueue(): This operation removes the front node and moves the front
to the next node.

Follow the below steps to solve the problem:

• Create a class Node with data members integer data and Node* next
o A parameterized constructor that takes an integer x value as a
parameter and sets data equal to x and next as NULL
• Create a class Queue with data members Node front and rear
• Enqueue Operation with parameter x:
o Initialize Node* temp with data = x
o If the rear is set to NULL then set the front and rear to temp and
return(Base Case)
o Else set rear next to temp and then move rear to temp
• Dequeue Operation:
 o If the front is set to NULL return(Base Case)
o Initialize Node temp with front and set front to its next
o If the front is equal to NULL then set the rear to NULL
o Delete temp from the memory
#include <stdio.h>
#include <stdlib.h>

// Node structure definition

struct Node {
int data;
struct Node* next;
};

// Queue structure definition

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

// Function to create a new node

struct Node* newNode(int new_data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = new_data;
node->next = NULL;
return node;
}

// Function to initialize the queue

struct Queue* createQueue() {
struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
q->front = q->rear = NULL;
return q;
}

// Function to check if the queue is empty

int isEmpty(struct Queue* q) {
 return q->front == NULL;
}

// Function to add an element to the queue

void enqueue(struct Queue* q, int new_data) {
struct Node* new_node = newNode(new_data);
if (isEmpty(q)) {
q->front = q->rear = new_node;
printQueue(q);
return;
}
q->rear->next = new_node;
q->rear = new_node;
printQueue(q);
}

// Function to remove an element from the queue

void dequeue(struct Queue* q) {
if (isEmpty(q)) {
return;
}
struct Node* temp = q->front;
q->front = q->front->next;
if (q->front == NULL) q->rear = NULL;
free(temp);
printQueue(q);
}

// Function to print the current state of the queue

void printQueue(struct Queue* q) {
if (isEmpty(q)) {
printf("Queue is empty\n");
return;
}
struct Node* temp = q->front;
printf("Current Queue: ");
 while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}

// Driver code to test the queue implementation

int main() {
struct Queue* q = createQueue();

// Enqueue elements into the queue

enqueue(q, 10);
enqueue(q, 20);

// Dequeue elements from the queue

dequeue(q);
dequeue(q);

// Enqueue more elements into the queue

enqueue(q, 30);
enqueue(q, 40);
enqueue(q, 50);

// Dequeue an element from the queue (this should print 30)

dequeue(q);

return 0;
}
Output
Current Queue: 10
Current Queue: 10 20
Current Queue: 20
Queue is empty
Current Queue: 30
Current Queue: 30 40
Current Queue: 30 40 50
Current Queue: 40 50
Time Complexity: O(1), The time complexity of both operations enqueue()
and dequeue() is O(1) as it only changes a few pointers in both operations
Auxiliary Space: O(1), The auxiliary Space of both operations enqueue() and
dequeue() is O(1) as constant extra space is required.

Queue Data Structure

A Queue Data Structure is a fundamental concept in computer science used
for storing and managing data in a specific order.
• It follows the principle of "First in, First out" (FIFO), where the first
element added to the queue is the first one to be removed.
• It is used as a buffer in computer systems where we have speed
mismatch between two devices that communicate with each other. For
example, CPU and keyboard and two devices in a network
• Queue is also used in Operating System algorithms like CPU Scheduling
and Memory Management, and many standard algorithms like Breadth
First Search of Graph, Level Order Traversal of a Tree.
A Queue is a linear data structure that follows the FIFO (First In, First Out)
principle.
• The first element added to the queue will be the first one to be
removed.
• Think of it like a line at a ticket counter.

ADT Perspective (Abstract View)

A Queue ADT defines:
• A collection of elements
• Basic operations like:
o enqueue(x) → Insert an element at the rear
o dequeue() → Remove element from the front
o isEmpty() → Check if the queue is empty
o isFull() → Check if the queue is full (in case of array)
o peek() or front() → Get the front element

Basic Queue Operations:

Operation Description
enqueue Add element to the rear of queue
dequeue Remove element from the front
peek View the element at the front
isEmpty Check if queue is empty
isFull Check if queue is full (for arrays)

Programs:
#include <stdio.h>
#define SIZE 5

int queue[SIZE];
int front = -1, rear = -1;

// Enqueue function
void enqueue(int value) {
if(rear == SIZE - 1)
 printf("Queue is Full\n");
else {
if(front == -1) front = 0;
rear++;
queue[rear] = value;
printf("Inserted %d\n", value);
}
}

// Dequeue function
void dequeue() {
if(front == -1 || front > rear)
printf("Queue is Empty\n");
else {
printf("Deleted: %d\n", queue[front]);
front++;
}
}

// Display Queue
void display() {
if(front == -1 || front > rear)
printf("Queue is Empty\n");
else {
printf("Queue Elements: ");
for(int i = front; i <= rear; i++)
printf("%d ", queue[i]);
printf("\n");
}
}

int main() {
enqueue(10);
enqueue(20);
enqueue(30);
display();
 dequeue();
display();
enqueue(40);
enqueue(50);
enqueue(60); // Queue is full
display();
return 0;
}

Output:
Inserted 10
Inserted 20
Inserted 30
Queue Elements: 10 20 30
Deleted: 10
Queue Elements: 20 30
Inserted 40
Inserted 50
Queue is Full
Queue Elements: 20 30 40 50
Types of Queues
A queue is a useful data structure in programming. It is similar to the ticket
queue outside a cinema hall, where the first person entering the queue is the
first person who gets the ticket.
There are four different types of queues:
• Simple Queue
• Circular Queue
• Priority Queue
• Double Ended Queue

1) Simple Queue
In a simple queue, insertion takes place at the rear and removal occurs at the
front. It strictly follows the FIFO (First in First out) rule.

Simple Queue Representation

To learn more, visit Queue Data Structure.

2) Circular Queue
In a circular queue, the last element points to the first element making a
circular link.

Circular Queue
Representation
The main advantage of a circular queue over a simple queue is better
memory utilization. If the last position is full and the first position is empty, we
can insert an element in the first position. This action is not possible in a
simple queue.
To learn more, visit Circular Queue Data Structure.
3) Priority Queue
A priority queue is a special type of queue in which each element is
associated with a priority and is served according to its priority. If elements
with the same priority occur, they are served according to their order in the
queue.

Priority Queue Representation

Insertion occurs based on the arrival of the values and removal occurs based
on priority.
To learn more, visit Priority Queue Data Structure.

4) Deque (Double Ended Queue)

In a double ended queue, insertion and removal of elements can be
performed from either from the front or rear. Thus, it does not follow the FIFO
(First In First Out) rule.

Deque Representation

1. Circular Queue

Definition:
A circular queue overcomes the limitations of a linear queue using arrays. In
a circular queue, the last position connects back to the first, forming a circle.
It uses modulo arithmetic to manage wrap-around.
Real-World Example:
• Round-robin CPU scheduling
• Traffic light control systems
Circular Queue Operations:
Operation Description
enqueue(x) Add element at rear position
dequeue() Remove element from front position
isFull() (front == (rear + 1) % SIZE)
isEmpty() (front == -1)

Circular Queue Using Array – C Code:

#include <stdio.h>
#define SIZE 5

int queue[SIZE];
int front = -1, rear = -1;

void enqueue(int value) {

if ((front == 0 && rear == SIZE - 1) || (rear + 1) % SIZE == front) {
printf("Queue is Full\n");
return;
}
if (front == -1) front = 0;
rear = (rear + 1) % SIZE;
queue[rear] = value;
printf("Inserted %d\n", value);
}

void dequeue() {
if (front == -1) {
printf("Queue is Empty\n");
return;
}
printf("Deleted: %d\n", queue[front]);
if (front == rear)
 front = rear = -1;
else
front = (front + 1) % SIZE;
}

void display() {
if (front == -1) {
printf("Queue is Empty\n");
return;
}
printf("Queue: ");
int i = front;
while (1) {
printf("%d ", queue[i]);
if (i == rear) break;
i = (i + 1) % SIZE;
}
printf("\n");
}

int main() {
enqueue(10);
enqueue(20);
enqueue(30);
enqueue(40);
enqueue(50); // Full
display();
dequeue();
dequeue();
enqueue(60);
enqueue(70);
display();
return 0;
}
2. Priority Queue

Definition:
A priority queue is a special type of queue in which each element has a
priority. Elements are served based on priority, not just arrival time.
• Higher priority = served first
• If priorities are equal, follow FIFO

Real-World Example:
• Task scheduling in operating systems
• Emergency room patient triage
• Job queue in printers

Priority Queue Types:

Type Rule
Max-Priority Queue Highest priority has highest value
Min-Priority Queue Lowest priority has highest importance (smallest val)

Simple Priority Queue Using Array – C Code (Max Priority):

#include <stdio.h>
#define SIZE 100

struct Item {
int data;
int priority;
};

struct Item pq[SIZE];

int count = 0;

void enqueue(int data, int priority) {

int i = count - 1;
while (i >= 0 && pq[i].priority < priority) {
pq[i + 1] = pq[i];
i--;
 }
pq[i + 1].data = data;
pq[i + 1].priority = priority;
count++;
printf("Inserted %d with priority %d\n", data, priority);
}

void dequeue() {
if (count == 0) {
printf("Priority Queue is Empty\n");
return;
}
printf("Deleted: %d with priority %d\n", pq[0].data, pq[0].priority);
for (int i = 1; i < count; i++) {
pq[i - 1] = pq[i];
}
count--;
}

void display() {
if (count == 0) {
printf("Priority Queue is Empty\n");
return;
}
printf("Priority Queue: ");
for (int i = 0; i < count; i++) {
printf("(%d, P=%d) ", pq[i].data, pq[i].priority);
}
printf("\n");
}

int main() {
enqueue(10, 2);
enqueue(30, 3);
enqueue(20, 1);
display();
 dequeue();
display();
return 0;
}

Applications of Queue Data Structure

Introduction :
A queue is a linear data structure that follows the "first-in, first-out" (FIFO)
principle. It is a collection of elements that supports two primary operations -
enqueue and dequeue. In the enqueue operation, an element is added to the
back of the queue, while in the dequeue operation, an element is removed
from the front of the queue.
Queues are used to manage data flow and handle tasks in various
applications, such as operating systems, network protocols, and data
processing systems. They are also used to implement algorithms like
breadth-first search, which involves exploring nodes in a graph level-by-level.
Queue is used when things don't have to be processed immediately, but have
to be processed in First In First Out order.
The basic operations of a queue include:
1. Enqueue: Add an element to the back of the queue.
2. Dequeue: Remove the element at the front of the queue.
3. Peek: Return the element at the front of the queue without removing it.
4. Size: Return the number of elements in the queue.
5. isEmpty: Check if the queue is empty.
Some common applications of Queue data structure :
1. Task Scheduling: Queues can be used to schedule tasks based on
priority or the order in which they were received.
2. Resource Allocation: Queues can be used to manage and allocate
resources, such as printers or CPU processing time.
3. Batch Processing: Queues can be used to handle batch processing
jobs, such as data analysis or image rendering.
 4. Message Buffering: Queues can be used to buffer messages in
communication systems, such as message queues in messaging
systems or buffers in computer networks.
5. Event Handling: Queues can be used to handle events in event-driven
systems, such as GUI applications or simulation systems.
6. Traffic Management: Queues can be used to manage traffic flow in
transportation systems, such as airport control systems or road
networks.
7. Operating systems: Operating systems often use queues to manage
processes and resources. For example, a process scheduler might use a
queue to manage the order in which processes are executed.
8. Network protocols: Network protocols like TCP and UDP use queues to
manage packets that are transmitted over the network. Queues can
help to ensure that packets are delivered in the correct order and at the
appropriate rate.
9. Printer queues :In printing systems, queues are used to manage the
order in which print jobs are processed. Jobs are added to the queue as
they are submitted, and the printer processes them in the order they
were received.
10. Web servers: Web servers use queues to manage incoming requests
from clients. Requests are added to the queue as they are received, and
they are processed by the server in the order they were received.
11. Breadth-first search algorithm: The breadth-first search algorithm
uses a queue to explore nodes in a graph level-by-level. The algorithm
starts at a given node, adds its neighbors to the queue, and then
processes each neighbor in turn.
Useful Applications of Queue
• When a resource is shared among multiple consumers. Examples
include CPU scheduling, Disk Scheduling.
• When data is transferred asynchronously (data not necessarily
received at the same rate as sent) between two processes. Examples
include IO Buffers, pipes, etc.

Applications of Queue in Operating systems:

• Semaphores
 • FCFS ( first come first serve) scheduling, example: FIFO queue
• Spooling in printers
• Buffer for devices like keyboard
• CPU Scheduling
• Memory management
Applications of Queue in Networks:
• Queues in routers/ switches
• Mail Queues
• Variations: ( Deque, Priority Queue, Doubly Ended Priority Queue )
Some other applications of Queue:
• Applied as waiting lists for a single shared resource like CPU, Disk, and
Printer.
• Applied as buffers on MP3 players and portable CD players.
• Applied on Operating system to handle the interruption.
• Applied to add a song at the end or to play from the front.
• Applied on WhatsApp when we send messages to our friends and they
don't have an internet connection then these messages are queued on
the server of WhatsApp.
• Traffic software ( Each light gets on one by one after every time of
interval of time.)
Issues in applications of Queue :
1. Queue overflow: If a queue has a fixed size, it can become full, leading
to a queue overflow. This can happen if elements are added to the
queue faster than they are removed. To prevent overflow, some
implementations use dynamic resizing or circular buffers.
2. Queue underflow: If a queue is empty and an attempt is made to
remove an element, this can lead to a queue underflow. This can
happen if elements are removed from the queue faster than they are
added. To prevent underflow, some implementations use sentinel
values or null pointers to represent an empty queue.
3. Blocking queues: In some applications, a queue may become blocked
if it is full or empty. This can cause delays in processing or deadlock. To
address this, some implementations use bounded queues or non-
blocking queues.
4. Priority inversion: In some applications, a higher priority element can
get stuck behind a lower priority element in the queue. This can lead to
 priority inversion and result in reduced performance. To prevent this,
some implementations use priority queues or multiple queues with
different priorities.
5. Synchronization issues: In concurrent applications, multiple threads
may access the same queue simultaneously. This can lead to
synchronization issues like race conditions, deadlocks, and livelocks. To
address this, some implementations use locking mechanisms like
mutexes or semaphores.
6. Memory management: In some implementations, a queue may
allocate and deallocate memory frequently, leading to memory
fragmentation and reduced performance. To address this, some
implementations use memory pools or pre-allocated buffers.

Linked List
Linked List Data Structure
A linked list is a fundamental data structure in computer science. It mainly
allows efficient insertion and deletion operations compared to arrays. Like
arrays, it is also used to implement other data structures like stack, queue and
deque. Here’s the comparison of Linked List vs Arrays
Linked List:
• Data Structure: Non-contiguous
• Memory Allocation: Typically allocated one by one to individual
elements
• Insertion/Deletion: Efficient
• Access: Sequential
Array:
• Data Structure: Contiguous
• Memory Allocation: Typically allocated to the whole array
• Insertion/Deletion: Inefficient
• Access: Random

A Linked List is a linear data structure where elements (called nodes) are
stored in non-contiguous memory locations. Each node contains:
1. Data – the value stored.
2. Pointer (link) – address/reference to the next node in the list.

Types of Linked Lists:

Type Description
Singly Linked List Each node points to the next node only.
Each node points to both the next and previous
Doubly Linked List
nodes.
Circular Linked List The last node points back to the first node.
Circular Doubly Linked Like doubly, but links form a circle (last → first, first
List → last).

Structure of Node (C Language)

struct Node {
int data;
struct Node* next;
};

Basic Operations on Linked List (with C programs):

1. Create a Linked List Node
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

struct Node* createNode(int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}

2. Insert at Beginning
void insertAtBeginning(struct Node** head, int value) {
struct Node* newNode = createNode(value);
newNode->next = *head;
*head = newNode;
}

3. Insert at End
void insertAtEnd(struct Node** head, int value) {
struct Node* newNode = createNode(value);
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
}

4. Delete a Node by Value

void deleteNode(struct Node** head, int key) {
struct Node *temp = *head, *prev = NULL;

if (temp != NULL && temp->data == key) {

*head = temp->next;
free(temp);
return;
}

while (temp != NULL && temp->data != key) {

prev = temp;
temp = temp->next;
}

if (temp == NULL) return;

prev->next = temp->next;
free(temp);
}

5. Display the Linked List

void displayList(struct Node* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}

Applications of Linked List:

• Dynamic memory allocation
• Implementing stacks and queues
• Symbol tables in compilers
• Representing graphs and adjacency lists
• Undo functionality in editors
 Variants:
1. Doubly Linked List
struct DNode {
int data;
struct DNode* prev;
struct DNode* next;
};
2. Circular Linked List
// last node’s next points to head

searching a linked list

Search an element in a Linked List (Iterative and Recursive)
Given a linked list and a key, the task is to check if key is present in the linked
list or not.
Examples:
Input: 14 -> 21 -> 11 -> 30 -> 10, key = 14
Output: Yes
Explanation: 14 is present in the linked list.
Input: 6 -> 21 -> 17 -> 30 -> 10 -> 8, key = 13
Output: No
Explanation: No node in the linked list has value = 13.
Input: 9 -> 18 -> 27 -> 36 -> 45, key = 27
Output: Yes
Explanation: 27 is present in the linked list.

• Search an element in a Linked List (Iterative Approach) - O(N) Time and

O(1) Space
The idea is to traverse all the nodes of the linked list, starting from the head.
While traversing, if we find a node whose value is equal to key then print
"Yes", otherwise print "No".
Follow the below steps to solve the problem:
• Initialize a node pointer, curr = head.
• Do following while current is not NULL
 o If the current value (i.e., curr->key) is equal to the key being
searched return true.
o Otherwise, move to the next node (curr = curr->next).
• If the key is not found, return false
// Iterative C program to search
// an element in linked list

#include <stdio.h>
#include <stdbool.h>

// A linked list node

struct Node {
int data;
struct Node* next;
};

// Function to create a new node

struct Node* createNode(int new_data) {
struct Node* new_node =
(struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = NULL;
return new_node;
}

// Checks whether key is present in linked list

bool searchKey(struct Node* head, int key) {

// Initialize curr with the head of linked list

struct Node* curr = head;

// Iterate over all the nodes

while (curr != NULL) {

// If the current node's value is equal to key,

// return true
 if (curr->data == key)
return true;

// Move to the next node

curr = curr->next;
}

// If there is no node with value as key, return false

return false;
}

// Driver code
int main() {

// Create a hard-coded linked list:

// 14 -> 21 -> 13 -> 30 -> 10
struct Node* head = createNode(14);
head->next = createNode(21);
head->next->next = createNode(13);
head->next->next->next = createNode(30);
head->next->next->next->next = createNode(10);

// Key to search in the linked list

int key = 14;

if (searchKey(head, key))
printf("Yes");
else
printf("No");

return 0;
}
Output
Yes
• Search an element in a Linked List (Recursive Approach) - O(N) Time and
O(N) Space
The idea is to recursively traverse all the nodes starting from the head of
linked list. For any node, if the value is equal to key, then return true.
Otherwise, recursively search the next node. If at any point the head reaches
NULL, it means that we have reached the end of linked list so return false.
Follow the below steps to solve the problem:
• If the head is NULL, return false.
• If the head's key is the same as X, return true;
• Else recursively search in the next node.
// Recursive C program to search
// an element in linked list

#include <stdio.h>
#include <stdbool.h>

// A linked list node

struct Node {
int data;
struct Node* next;
};

// Function to create a new node

struct Node* createNode(int new_data) {
struct Node* new_node =
(struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = NULL;
return new_node;
}

// Checks whether the key is present in linked list

bool searchKey(struct Node* head, int key) {

// Base case
if (head == NULL)
 return 0;

// If key is present in current node, return true

if (head->data == key)
return 1;

// Recur for remaining list

return searchKey(head->next, key);
}

// Driver code
int main() {

// Create a hard-coded linked list:

// 14 -> 21 -> 13 -> 30 -> 10
struct Node* head = createNode(14);
head->next = createNode(21);
head->next->next = createNode(13);
head->next->next->next = createNode(30);
head->next->next->next->next = createNode(10);

// Key to search in the linked list

int key = 14;

if (searchKey(head, key))
printf("Yes");
else
printf("No");

return 0;
}
Output
Yes
 Insertion in Linked List
Insertion in a linked list involves adding a new node at a specified position in
the list. There are several types of insertion based on the position where the
new node is to be added:
• At the front of the linked list
• Before a given node.
• After a given node.
• At a specific position.
• At the end of the linked list.
1. Insert a Node at the Front/Beginning of the Linked List
To insert a new node at the front, we create a new node and point
its next reference to the current head of the linked list. Then, we update
the head to be this new node. This operation is efficient because it only
requires adjusting a few pointers.

Algorithm:
• Make the first node of Linked List linked to the new node
• Remove the head from the original first node of Linked List
• Make the new node as the Head of the Linked List.
2. Insert a Node after a Given Node in Linked List
• If we want to insert a new node after a specific node, we first locate
that node. Once we find it, we set the new node's next reference to
point to the node that follows the given node. Then, we update the
given node's next to point to the new node. This requires traversing the
list to find the specified node.
Algorithm:
• Initialize a pointer curr to traverse the list starting from head.
• Loop through the list to find the node with data equal to key.
o If not found then return from function.
• Create a new node, say new_node initialized with the given data.
• Make the next pointer of new_node as next of given node.
• Update the next pointer of given node point to the new_node.
3. Insert a Node before a Given Node in Linked List
• If we want to insert a new node before a given node, we first locate
that node while keeping the track of previous node also. Once we find
it, we set the previous node's next reference the new node. Then, we
update the node's next reference to point to the given node.
Algorithm:
• Traverse the linked list while keeping track of the previous node until
given node is reached.
• Once node is found, allocate memory for a new node and set according
to given data .
• Point the next pointer of the new node to node given node.
• Point the next pointer of the previous node to the new node.
• If given key is the head, update the head to point to the new node.
4. Insert a Node At a Specific Position in Linked List
• To insert a new node at a specific position, we need to traverse the
list to position - 1. If the position is valid, we adjust the pointers
similarly such that the next pointer of the new node points to the next
of current nod and next pointer of current node points to the new
node.

5. Insert a Node at the End of Linked List

Inserting at the end involves traversing the entire list until we reach the last
node. We then set the last node's next reference to point to the new node,
making the new node the last element in the list.
Algorithm:
• Go to the last node of the Linked List
• Change the next pointer of last node from NULL to the new node
• Make the next pointer of new node as NULL to show the end of Linked List

C Programs for Each Type:

Node Structure
struct Node {
int data;
struct Node* next;
};

Insert at the Beginning

void insertAtBeginning(struct Node** head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = *head;
*head = newNode;
}

Insert at the End

void insertAtEnd(struct Node** head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;

if (*head == NULL) {
*head = newNode;
return;
}

struct Node* temp = *head;

while (temp->next != NULL)
temp = temp->next;

temp->next = newNode;
}

Insert at a Specific Position

void insertAtPosition(struct Node** head, int value, int position) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;

if (position == 1) {
newNode->next = *head;
*head = newNode;
return;
}

struct Node* temp = *head;

for (int i = 1; temp != NULL && i < position - 1; i++) {
temp = temp->next;
}

if (temp == NULL) {
printf("Position out of range\n");
free(newNode);
return;
}

newNode->next = temp->next;
temp->next = newNode;
}

Display Function
void displayList(struct Node* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
 Main Function Example
int main() {
struct Node* head = NULL;

insertAtBeginning(&head, 20);
insertAtBeginning(&head, 10); // List: 10 -> 20

insertAtEnd(&head, 30); // List: 10 -> 20 -> 30

insertAtPosition(&head, 25, 3); // List: 10 -> 20 -> 25 -> 30

displayList(head); // Output: 10 -> 20 -> 25 -> 30 -> NULL

return 0;
}

Deletion in Linked List

Deleting a node in a Linked List is an important operation and can be done in
three main ways: removing the first node, removing a node in the middle, or
removing the last node.
Types of Deletion in Linked List
• Deletion at the Beginning of Linked List
• Deletion at Specific Position of Linked List
• Deletion at the End of Linked List
1. Deletion at the Beginning of Linked List
Deletion at the Beginning operation involves removing the first node of the
linked list.
Step-by-Step Approach:
1. Check if the list is empty: If the head is NULL, the list is empty, and
there's nothing to delete.
2. Update the head pointer: Set the head to the second node (head =
head->next).
3. Delete the original head node: The original head node is now
unreferenced, and it can be freed/deleted if necessary (in languages
like C++ where memory management is manual).
2. Deletion at Specific Position of Linked List
Deletion at a specified position in a linked list involves removing a node from
a specific index/position, which can be the first, middle, or last node.
Step-by-Step Approach:
1. Check if the position is valid: If the position is out of bounds (greater
than the length of the list), return an error or handle appropriately.
2. Traverse the list to find the node just before the one to be deleted: Start
from the head and move through the list until reaching the node at
position n-1 (one before the target position).
3. Update the next pointer: Set the next pointer of the (n-1)ᵗʰ node to point
to the node after the target node (node_to_delete->next).
4. Delete the target node: The node to be deleted is now unreferenced,
and in languages like C++ or Java, it can be safely deallocated.
3. Deletion at the End of Linked List
Deletion at the end operation involves removing the last node of the linked list.
Step-by-Step Approach:
1. Check if the list is empty: If the head is NULL, the list is empty, and
there's nothing to delete.
2. If the list has only one node: Simply set the head to NULL (the list
becomes empty).
3. Traverse the list to find the second-last node: Start from the head and
iterate through the list until you reach the second-last node (where
the next of the node is the last node).
4. Update the next pointer of the second-last node: Set the second-last
node’s next to NULL (removing the link to the last node).
5. Delete the last node: The last node is now unreferenced and can be
deleted or freed, depending on the language used.

Deletion in a Singly Linked List (with C Code)

Deletion in a linked list means removing a node. Just like insertion, deletion
can occur at:
1. Beginning
2. End
3. Specific Position / By Value

Important:
• Always free memory of the deleted node.
• Update pointers carefully to avoid memory leaks or broken links.

Node Structure (C)

struct Node {
int data;
struct Node* next;
};

Delete from Beginning

void deleteFromBeginning(struct Node** head) {
if (*head == NULL) {
printf("List is empty.\n");
 return;
}

struct Node* temp = *head;

*head = (*head)->next;
free(temp);
}

Delete from End

void deleteFromEnd(struct Node** head) {
if (*head == NULL) {
printf("List is empty.\n");
return;
}

struct Node* temp = *head;

// If only one node

if (temp->next == NULL) {
free(temp);
*head = NULL;
return;
}

// Traverse to second last

while (temp->next->next != NULL) {
temp = temp->next;
}

free(temp->next);
temp->next = NULL;
}

Delete by Value (First Occurrence)

void deleteByValue(struct Node** head, int key) {
struct Node* temp = *head;
 struct Node* prev = NULL;

// If head holds the key

if (temp != NULL && temp->data == key) {
*head = temp->next;
free(temp);
return;
}

// Search for the key

while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}

// If key not found

if (temp == NULL) {
printf("Value %d not found.\n", key);
return;
}

prev->next = temp->next;
free(temp);
}

Display Function

void displayList(struct Node* head) {

while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
 Full Example (Main Function)
int main() {
struct Node* head = NULL;

// Add some nodes (same insert functions from before)

insertAtEnd(&head, 10);
insertAtEnd(&head, 20);
insertAtEnd(&head, 30);
insertAtEnd(&head, 40);

displayList(head); // 10 -> 20 -> 30 -> 40 -> NULL

deleteFromBeginning(&head);
displayList(head); // 20 -> 30 -> 40 -> NULL

deleteFromEnd(&head);
displayList(head); // 20 -> 30 -> NULL

deleteByValue(&head, 20);
displayList(head); // 30 -> NULL

return 0;
}

Time Complexity:
Operation Time Complexity
Delete at beginning O(1)
Delete at end O(n)
Delete by value O(n)
Header Linked List
A header linked list is a special type of linked list which consists of
a header node in the beginning of the list. The header node can store meta
data about the linked list. This type of list is useful when information other
than that found in each node is needed. For example, suppose there is an
application in which the number of items in a list is often calculated. Usually,
a list is always traversed to find the length of the list. However, information
can be easily obtained if the current length is maintained in an additional
header node.
Types of Header Linked List
1. Singly or Doubly Header Linked List
It is a list whose last node contains the NULL pointer. In the header linked list
the start pointer always points to the header node. start -> next =
NULL indicates that the header linked list is empty. The operations that are
possible on this type of linked list are Insertion, Deletion, and Traversing.

This structure can be implemented using a singly linked list or a doubly

linked list. When using a doubly linked list, the header node
simplifies bidirectional traversal and manipulation of the list, further
enhancing the efficiency of operations like insertion and deletion.
// C program to implement header linked list.

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

struct Node* createNode(int newData);

// Inserts a node into the linked list.

void insert(struct Node* header, int x) {
 struct Node* curr = header;
while (curr->next != NULL)
curr = curr->next;

struct Node* newNode = createNode(x);

curr->next = newNode;
}

void printList(struct Node* header) {

struct Node* curr = header->next;
while (curr != NULL) {
printf("%d ", curr->data);
curr = curr->next;
}
printf("\n");
}

struct Node* createNode(int newData) {

struct Node* node =
(struct Node*)malloc(sizeof(struct Node));
node->data = newData;
node->next = NULL;
return node;
}

int main() {

// Create a hard-coded header linked list:

// header -> 1 -> 2 -> 3 -> 4
struct Node* header = createNode(0);
insert(header, 1);
insert(header, 2);
insert(header, 3);
insert(header, 4);
 printList(header);

return 0;
}
Output
1234
2. Singly or Doubly Circular Header Linked List
A list in which the last node points back to the header node is called circular
header linked list. The chains do not indicate first or last nodes. In this case,
external pointers provide a frame of reference because last node of a circular
linked list does not contain the NULL pointer. The possible operations on this
type of linked list are Insertion, Deletion and Traversing.

// C program to implement circular header linked list.

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

struct Node* createNode(int x);

// Inserts a node into the linked list.

void insert(struct Node* header, int x) {

// If list is empty
 if (header->next == NULL) {
struct Node* newNode = createNode(x);
header->next = newNode;
newNode->next = newNode;
return;
}

struct Node* curr = header->next;

while (curr->next != header->next)
curr = curr->next;

struct Node* newNode = createNode(x);

// Update the previous and new Node

// next pointers
curr->next = newNode;
newNode->next = header->next;
}

void printList(struct Node* header) {

if (header->next == NULL)
return;

struct Node* curr = header->next;

do {
printf("%d ", curr->data);
curr = curr->next;
} while (curr != header->next);
printf("\n");
}

struct Node* createNode(int x) {

struct Node* node =
(struct Node*)malloc(sizeof(struct Node));
node->data = x;
node->next = NULL;
 return node;
}

int main() {

// Create a hard-coded circular header linked list:

// header -> 1 -> 2 -> 3 -> 4
struct Node* header = createNode(0);
insert(header, 1);
insert(header, 2);
insert(header, 3);
insert(header, 4);

printList(header);

return 0;
}
Output
1234
Applications of Header Linked List
Header linked lists, which use dummy nodes, simplify complex linked list tasks.
For example, when merging two sorted linked lists, a dummy node at the start
makes the process smoother by avoiding extra steps for the head node and
ensuring all nodes are merged correctly. Similarly, when segregating even
and odd nodes in a list, dummy nodes make it easier to organize and join the
two lists. These uses show how header linked lists can make linked list
operations more straightforward and manageable.

Introduction to Circular Linked List

A circular linked list is a data structure where the last node connects back to
the first, forming a loop. This structure allows for continuous traversal without
any interruptions. Circular linked lists are especially helpful for tasks like
scheduling and managing playlists, allowing for smooth navigation. In this
tutorial, we’ll cover the basics of circular linked lists, how to work with them,
their advantages and disadvantages, and their applications.
What is a Circular Linked List?
A circular linked list is a special type of linked list where all the nodes are
connected to form a circle. Unlike a regular linked list, which ends with a node
pointing to NULL, the last node in a circular linked list points back to the first
node. This means that you can keep traversing the list without ever reaching
a NULL value.
Types of Circular Linked Lists
We can create a circular linked list from both singly linked lists and doubly
linked lists. So, circular linked lists are basically of two types:
1. Circular Singly Linked List
In Circular Singly Linked List, each node has just one pointer called the "next"
pointer. The next pointer of the last node points back to the first node and this
results in forming a circle. In this type of Linked list, we can only move through
the list in one direction.

2. Circular Doubly Linked List:

In circular doubly linked list, each node has two pointers prev and next, similar
to doubly linked list. The prev pointer points to the previous node and the next
points to the next node. Here, in addition to the last node storing the address
of the first node, the first node will also store the address of the last node.
Note: In this article, we will use the singly linked list to explain the working of
circular linked lists.
Representation of a Circular Singly Linked List

Create/Declare a Node of Circular Linked List

Syntax to Declare a Circular Linked List in Different Languages:
// Node structure
struct Node
{
int data;
struct Node *next;
};

// Function to create a new node

struct Node *createNode(int value){

// Allocate memory
struct Node *newNode =
(struct Node *)malloc(sizeof(struct Node));

// Set the data

newNode->data = value;

// Initialize next to NULL

 newNode->next = NULL;

// Return the new node

return newNode;
}
In the code above, each node has data and a pointer to the next node. When
we create multiple nodes for a circular linked list, we only need to connect the
last node back to the first one.
Example of Creating a Circular Linked List
Here’s an example of creating a circular linked list with three nodes (2, 3, 4):

// Allocate memory for nodes

struct Node *first =
(struct Node *)malloc(sizeof(struct Node));
struct Node *second =
(struct Node *)malloc(sizeof(struct Node));
struct Node *last =
(struct Node *)malloc(sizeof(struct Node));

// Initilize nodes
first->data = 2;
second->data = 3;
last->data = 4;

// Connect nodes
first->next = second;
second->next = last;
last->next = first;

In the above code, we have created three nodes first, second, and last having
values 2, 3, and 4 respectively.
 • After creating three nodes, we have connected these node in a series.
• Connect the first node "first" to "second" node by storing the address of
"second" node into first's next
• Connect the second node "second" to "third" node by storing the
address of "third" node into second's next
• After connecting all the nodes, we reach the key characteristic of a
circular linked list: linking the last node back to the first node. Therefore,
we store the address of the "first" node in the "last" node.

Operations on the Circular Linked list

We can do some operations on the circular linked list similar to the singly and
doubly linked list which are:
1. Insertion
• Insertion at the empty list
• Insertion at the beginning
• Insertion at the end
• Insertion at the given position
2. Deletion
• Delete the first node
• Delete the last node
• Delete the node from any position
3. Searching
Insertion in the circular linked list
Insertion is a fundamental operation in linked lists that involves adding a new
node to the list. The only extra step is connecting the last node to the first one.
In the circular linked list mentioned below, we can insert nodes in four ways:
1. Insertion in an empty List in the circular linked list
To insert a node in empty circular linked list, creates a new node with the
given data, sets its next pointer to point to itself, and updates the last pointer
to reference this new node.
2. Insertion at the beginning in circular linked list
To insert a new node at the beginning of a circular linked list, we create a
new node and check if the list is empty. If empty, the new node points to
itself. If not, we make the new node's next pointer point to the current head
(last->next) and update the last node's next to the new node, preserving the
circular structure.

3. Insertion at the end in circular linked list

To insert a node at the end of a circular linked list, we create the new node
and, if the list is empty, make it point to itself. Otherwise, we update the tail's
next pointer to the new node and then set the tail to the new node,
preserving the circular linkage.
4. Insertion at specific position in circular linked list
To insert a node at a specific position in a circular linked list, we handle edge
cases for an empty list and invalid positions. For valid positions, we traverse
the list and adjust the pointers to insert the new node, updating the tail if it's
inserted at the end.

#include <stdio.h>
#include <stdlib.h>

// Define the Node structure

struct Node {
int data;
struct Node *next;
};

struct Node* createNode(int value);

// Function to insert a node at a specific position in a circular linked list

struct Node* insertAtPosition(struct Node *last, int data, int pos) {
if (last == NULL) {
// If the list is empty
if (pos != 1) {
printf("Invalid position!\n");
return last;
}
// Create a new node and make it point to itself
struct Node *newNode = createNode(data);
 last = newNode;
last->next = last;
return last;
}

// Create a new node with the given data

struct Node *newNode = createNode(data);

// curr will point to head initially

struct Node *curr = last->next;

if (pos == 1) {
// Insert at the beginning
newNode->next = curr;
last->next = newNode;
return last;
}

// Traverse the list to find the insertion point

for (int i = 1; i < pos - 1; ++i) {
curr = curr->next;

// If position is out of bounds

if (curr == last->next) {
printf("Invalid position!\n");
return last;
}
}

// Insert the new node at the desired position

newNode->next = curr->next;
curr->next = newNode;

// Update last if the new node is inserted at the end

if (curr == last) last = newNode;
 return last;
}

// Function to print the circular linked list

void printList(struct Node *last) {
if (last == NULL) return;

struct Node *head = last->next;

while (1) {
printf("%d ", head->data);
head = head->next;
if (head == last->next) break;
}
printf("\n");
}

// Function to create a new node

struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}

int main() {

// Create circular linked list: 2, 3, 4

struct Node *first = createNode(2);
first->next = createNode(3);
first->next->next = createNode(4);

struct Node *last = first->next->next;

last->next = first;

printf("Original list: ");

printList(last);
 // Insert elements at specific positions
int data = 5, pos = 2;
last = insertAtPosition(last, data, pos);
printf("List after insertions: ");
printList(last);

return 0;
}
Output
Original list: 2 3 4
List after insertions: 2 5 3 4

Deletion from a Circular Linked List

Deletion involves removing a node from the linked list. The main difference is
that we need to ensure the list remains circular after the deletion. We can
delete a node in a circular linked list in three ways:
1. Delete the first node in circular linked list
To delete the first node of a circular linked list, we check if the list is empty or
has only one node. If so, we handle those cases by deleting the node and
updating the last pointer. For multiple nodes, we update the last node’s next
pointer to skip the head and free the head node, returning the updated last
pointer.

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

struct Node* deleteFirstNode(struct Node* last) {

if (last == NULL) {
// If the list is empty
printf("List is empty\n");
return NULL;
}

struct Node* head = last->next;

if (head == last) {
// If there is only one node in the list
free(head);
last = NULL;
} else {
// More than one node in the list
last->next = head->next;
free(head);
}

return last;
}

void printList(struct Node* last) {

if (last == NULL) return;

struct Node* head = last->next;

while (1) {
printf("%d ", head->data);
head = head->next;
if (head == last->next) break;
}
printf("\n");
}
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}

int main() {
struct Node* first = createNode(2);
first->next = createNode(3);
first->next->next = createNode(4);

struct Node* last = first->next->next;

last->next = first;

printf("Original list: ");

printList(last);

last = deleteFirstNode(last);

printf("List after deleting first node: ");

printList(last);

return 0;
}
Output
Original list: 2 3 4
List after deleting first node: 3 4
2. Delete a specific node in circular linked list
To delete a specific node from a circular linked list, we handle empty list and
single node cases. For other nodes, we use two pointers to find the node,
update the previous node’s next pointer to skip the target, and delete it,
updating the last pointer if needed.
#include <stdio.h>
#include <stdlib.h>

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

struct Node {
int data;
struct Node* next;
};

// Function to delete a specific node in the circular linked list

struct Node* deleteSpecificNode(struct Node* last, int key) {
if (last == NULL) {
// If the list is empty
printf("List is empty, nothing to delete.\n");
return NULL;
}

struct Node* curr = last->next;

struct Node* prev = last;

// If the node to be deleted is the only node in the list

if (curr == last && curr->data == key) {
free(curr);
last = NULL;
return last;
}

// If the node to be deleted is the first node

 if (curr->data == key) {
last->next = curr->next;
free(curr);
return last;
}

// Traverse the list to find the node to be deleted

while (curr != last && curr->data != key) {
prev = curr;
curr = curr->next;
}

// If the node to be deleted is found

if (curr->data == key) {
prev->next = curr->next;
if (curr == last) {
last = prev;
}
free(curr);
} else {
// If the node to be deleted is not found
printf("Node with data %d not found.\n", key);
}

return last;
}

void printList(struct Node* last) {

if (last == NULL) {
printf("List is Empty");
return;
}

struct Node* head = last->next;

while (1) {
printf("%d ", head->data);
 head = head->next;
if (head == last->next) break;
}
printf("\n");
}

struct Node* createNode(int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}

int main() {
// Create circular linked list: 2, 3, 4
struct Node* first = createNode(2);
first->next = createNode(3);
first->next->next = createNode(4);

struct Node* last = first->next->next;

last->next = first;

printf("Original list: ");

printList(last);

// Delete a specific node

int key = 3;
last = deleteSpecificNode(last, key);

printf("List after deleting node %d: ", key);

printList(last);

return 0;
}
Output
Original list: 2 3 4
List after deleting node 3: 2 4
3. Deletion at the end of Circular linked list
To delete the last node in a circular linked list, we handle the empty and
single node cases. For multiple nodes, we traverse to find the second last
node, update its next pointer to the head, delete the last node, and return the
updated last pointer.

#include <stdio.h>
#include <stdlib.h>

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

struct Node {
int data;
struct Node* next;
};

// Function to delete the last node in the circular linked list

struct Node* deleteLastNode(struct Node* last) {
if (last == NULL) {
// If the list is empty
printf("List is empty, nothing to delete.\n");
return NULL;
}
struct Node* head = last->next;

// If there is only one node in the list

if (head == last) {
 free(last);
last = NULL;
return last;
}
// Traverse the list to find the second last node
struct Node* curr = head;
while (curr->next != last) {
curr = curr->next;
}
// Update the second last node's next pointer to point to head
curr->next = head;
free(last);
last = curr;

return last;
}

void printList(struct Node* last) {

if (last == NULL) return;

struct Node* head = last->next;

while (1) {
printf("%d ", head->data);
head = head->next;
if (head == last->next) break;
}
printf("\n");
}

struct Node* createNode(int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}
int main() {
// Create circular linked list: 2, 3, 4
struct Node* first = createNode(2);
first->next = createNode(3);
first->next->next = createNode(4);

struct Node* last = first->next->next;

last->next = first;

printf("Original list: ");

printList(last);

// Delete the last node

last = deleteLastNode(last);

printf("List after deleting last node: ");

printList(last);

return 0;
}
Output
Original list: 2 3 4
List after deleting last node: 2

Introduction to Circular Linked List

A circular linked list is a data structure where the last node connects back to
the first, forming a loop. This structure allows for continuous traversal without
any interruptions. Circular linked lists are especially helpful for tasks like
scheduling and managing playlists, allowing for smooth navigation. In this
tutorial, we’ll cover the basics of circular linked lists, how to work with them,
their advantages and disadvantages, and their applications.
What is a Circular Linked List?
A circular linked list is a special type of linked list where all the nodes are
connected to form a circle. Unlike a regular linked list, which ends with a node
pointing to NULL, the last node in a circular linked list points back to the first
node. This means that you can keep traversing the list without ever reaching
a NULL value.
Types of Circular Linked Lists
We can create a circular linked list from both singly linked lists and doubly
linked lists. So, circular linked lists are basically of two types:
1. Circular Singly Linked List
In Circular Singly Linked List, each node has just one pointer called the "next"
pointer. The next pointer of the last node points back to the first node and this
results in forming a circle. In this type of Linked list, we can only move through
the list in one direction.

2. Circular Doubly Linked List:

In circular doubly linked list, each node has two pointers prev and next, similar
to doubly linked list. The prev pointer points to the previous node and the next
points to the next node. Here, in addition to the last node storing the address
of the first node, the first node will also store the address of the last node.

Note: In this article, we will use the singly linked list to explain the working of
circular linked lists.
Representation of a Circular Singly Linked List
Let's take a look on the structure of a circular linked list.
Create/Declare a Node of Circular Linked List
// Node structure
struct Node
{
int data;
struct Node *next;
};

// Function to create a new node

struct Node *createNode(int value){

// Allocate memory
struct Node *newNode =
(struct Node *)malloc(sizeof(struct Node));

// Set the data

newNode->data = value;

// Initialize next to NULL

newNode->next = NULL;

// Return the new node

return newNode;
}
In the code above, each node has data and a pointer to the next node. When
we create multiple nodes for a circular linked list, we only need to connect the
last node back to the first one.
Example of Creating a Circular Linked List
Here’s an example of creating a circular linked list with three nodes (2, 3, 4):
// Allocate memory for nodes
struct Node *first =
(struct Node *)malloc(sizeof(struct Node));
struct Node *second =
(struct Node *)malloc(sizeof(struct Node));
struct Node *last =
(struct Node *)malloc(sizeof(struct Node));

// Initilize nodes
first->data = 2;
second->data = 3;
last->data = 4;

// Connect nodes
first->next = second;
second->next = last;
last->next = first;
In the above code, we have created three nodes first, second, and last having
values 2, 3, and 4 respectively.
• After creating three nodes, we have connected these node in a series.
• Connect the first node "first" to "second" node by storing the address of
"second" node into first's next
• Connect the second node "second" to "third" node by storing the
address of "third" node into second's next
• After connecting all the nodes, we reach the key characteristic of a
circular linked list: linking the last node back to the first node. Therefore,
we store the address of the "first" node in the "last" node.
Doubly Linked List Tutorial
A doubly linked list is a more complex data structure than a singly linked list,
but it offers several advantages. The main advantage of a doubly linked list is
that it allows for efficient traversal of the list in both directions. This is because
each node in the list contains a pointer to the previous node and a pointer to
the next node. This allows for quick and easy insertion and deletion of nodes
from the list, as well as efficient traversal of the list in both directions.

Representation of Doubly Linked List in Data Structure

In a data structure, a doubly linked list is represented using nodes that have
three fields:
1. Data
2. A pointer to the next node (next)
3. A pointer to the previous node (prev)

Node Definition
struct Node {

// To store the Value or data.

int data;

// Pointer to point the Previous Element

Node* prev;
 // Pointer to point the Next Element
Node* next;
};

// Function to create a new node

struct Node *createNode(int new_data) {
struct Node *new_node = (struct Node *)
malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = NULL;
new_node->prev = NULL;
return new_node;
}
Each node in a Doubly Linked List contains the data it holds, a pointer to
the next node in the list, and a pointer to the previous node in the list. By
linking these nodes together through the next and prev pointers, we can
traverse the list in both directions (forward and backward), which is a key

feature of a Doubly Linked List.

1. Traversal in Doubly Linked List
Traversal in a Doubly Linked List involves visiting each node, processing its
data, and moving to the next or previous node using the forward (next) and
backward (prev) pointers.
Step-by-Step Approach for Traversal:
1. Start from the head of the list.
2. Traverse forward:
• Visit the current node and process its data (e.g., print it).
• Move to the next node using current = current->next.
•Repeat the process until the end of the list (current == NULL).
3. Optionally, traverse backward:
• Start from the tail (last node).
• Visit the current node and process its data.
• Move to the previous node using current = current->prev.
• Repeat the process until the beginning of the list (current ==
NULL).
Traversal is useful for displaying or processing all nodes in a doubly linked list.
2. Finding Length of Doubly Linked List
A Doubly Linked List (DLL) is a type of linked list where each node has two
pointers:
1. One pointing to the next node in the sequence.
2. One pointing to the previous node in the sequence.
To find the length of a doubly linked list, we need to traverse the list while
counting the nodes.

Step-by-Step Approach for finding length:

1. Initialize a counter: Start with a counter variable (count = 0).
2. Set a pointer to the head node: Use a pointer (current) and initialize it to
the head of the linked list.
3. Traverse the list:
• While the pointer (current) is not NULL, increment the count by 1.
• Move to the next node (current = [Link]).
4. Stop at the end of the list: When the pointer reaches NULL, stop the loop.
5. Return the count: The final value of count gives the length of the doubly
linked list.

3. Insertion in a Doubly Linked List

Insertion in a Doubly Linked List (DLL) involves adding a new node at a
specific position while maintaining the connections between nodes. Since
each node contains a pointer to both the previous and next node, insertion
requires adjusting these pointers carefully.
There are three primary types of insertion in a DLL:
1. Insertion at the Beginning
1. Create a new node with the given data.
2. Set the next pointer of the new node to the current head.
3. If the list is not empty, update the prev pointer of the current head to
point to the new node.
4. Update the head of the list to the new node.

2. Insertion at the End

1. Create a new node with the given data.
 2. If the list is empty, set the new node as the head.
3. Traverse the list until the last node is found.
4. Set the next pointer of the last node to the new node.
5. Set the prev pointer of the new node to the last node.

3. Insertion at a Specific Position

1. Create a new node with the given data.
2. If inserting at the beginning, follow the steps for insertion at the start.
3. Traverse the list to find the node after which insertion is needed.
4. Set the next pointer of the new node to the next node of the current
position.
5. Set the prev pointer of the new node to the current node.
6. Update the prev pointer of the next node to point to the new node (if it
exists).
7. Update the next pointer of the previous node to point to the new node.

4. Deletion in a Doubly Linked List

Deletion in a Doubly Linked List (DLL) involves removing a node while
maintaining the integrity of the list. Since each node contains pointers to both
its previous and next nodes, deletion requires careful pointer adjustments to
ensure no broken links occur.

Types of Deletion in a Doubly Linked List

1. Deletion at the Beginning
1. Check if the list is empty; if it is, return as there is nothing to delete.
2. Store the current head node in a temporary variable.
3. Move the head pointer to the next node.
4. If the new head exists, update its prev pointer to NULL.
5. Delete the old head node to free memory.
2. Deletion at the End
1. Check if the list is empty; if it is, return.
2. Traverse the list to find the last node.
3. Store the last node in a temporary variable.
4. Update the next pointer of the second-last node to NULL, making it the
new tail.
 5. Delete the last node to free memory.
3. Deletion at a Specific Position
1. Check if the list is empty; if it is, return.
2. Traverse the list to find the node to be deleted.
3. Store the node to be deleted in a temporary variable.
4. Update the next pointer of the previous node to point to the next node.
5. Update the prev pointer of the next node to point to the previous node
(if it exists).
6. Delete the target node to free memory.
Advantages of Doubly Linked List
• Efficient traversal in both directions: Doubly linked lists allow for
efficient traversal of the list in both directions, making it suitable for
applications where frequent insertions and deletions are required.
• Easy insertion and deletion of nodes: The presence of pointers to both
the previous and next nodes makes it easy to insert or delete nodes
from the list, without having to traverse the entire list.
• Can be used to implement a stack or queue: Doubly linked lists can be
used to implement both stacks and queues, which are common data
structures used in programming.
Disadvantages of Doubly Linked List
• More complex than singly linked lists: Doubly linked lists are more
complex than singly linked lists, as they require additional pointers for
each node.
• More memory overhead: Doubly linked lists require more memory
overhead than singly linked lists, as each node stores two pointers
instead of one.
Applications of Doubly Linked List
• Implementation of undo and redo functionality in text editors.
• Cache implementation where quick insertion and deletion of elements
are required.
• Browser history management to navigate back and forth between
visited pages.
• Music player applications to manage playlists and navigate through
songs efficiently.
• Implementing data structures like Deque (double-ended queue) for
efficient insertion and deletion at both ends.
What is the Buddy System?
Buddy System is a memory allocation technique used in computer OS to
allocate and manage memory efficiently. This technique by dividing the
memory into fixed-size blocks, and whenever a process requests memory,
the system finds the smallest available block that can accommodate the
requested memory size.
It splits memory blocks, called “buddies,” to minimize fragmentation and
ensure efficient allocation. When a process is deallocated, its buddy can be
merged back into a larger block, reducing wasted space.
The Buddy System is a reminiscence control method utilized in working
systems to allocate memory dynamically. It is by and large applied in systems
wherein reminiscence is allocated and deallocated frequently, inclusive in
multitasking environments or structures with varying memory demands. In
the Buddy System, the memory is split into fixed-length blocks, regularly in
powers of (e.g., 1KB, 2KB, 4KB, and so on.). When a request for memory
allocation is made, the device seems for the correct-sized block. If an
appropriate block is determined, it's far allocated to the inquiring manner.
However, if the asked size doesn't shape any existing block precisely, the
device allocates a bigger block after which splits it into smaller blocks till an
accurately sized one is received.
Types of Buddy System
The Buddy System in memory control generally refers to a selected method
used to allocate and deallocate memory blocks. However, within this
framework, versions or adaptations may additionally exist relying on specific
necessities or optimizations wished for distinctive structures. Here are a few
types of Buddy Systems:
• Fibonacci Buddy System : A Fibonacci buddy system has block sizes of
16, 32, 48, 80, 128, and 208 bytes, with each block size equal to the total
of the two blocks previous it. When a block is divided from one free list,
its two portions are added to the two free lists that came before it. It can
be minimized by bringing the allowable block sizes close together. Now,
let's look at an example to better grasp the Fibonacci buddy system.
Assume the memory size is 377 kb. Then, 377 kb will be partitioned into
144 kb and 233 kb. Following that, 144 will be divided into (55 + 89),
 whereas 233 will be divided into (89 + 144). This separation will continue
based on memory requirements.
• Binary Buddy System : The buddy system keeps track of the free blocks
of each size (known as a free list) so that you can easily discover a
block of the necessary size if one is available. If no blocks of the
requested size are available, Allocate examines the first non-empty list
for blocks of at least the requested size. In both cases, a block is deleted
from the free list. For ex: The 512 KB memory size is initially partitioned
into two active partitions of 256 KB each, with additional subdivisions
based on a capacity of 2 to handle memory requests.
• Weighted Buddy System: In a weighted peer system, each memory
block is associated with a weight, which represents its size relative to
other blocks. When a memory allocation request occurs, the system
searches for the appropriate block considering the size of the requested
memory and the weight of the available blocks.
• Tertiary Buddy System : In a traditional buddy system, memory is
divided into blocks of fixed size, usually a power of 2, and allocated to
these blocks but the tertiary buddy system introduces a third memory
structure, which allows flexibility large in memory allocation.
Algorithm of Buddy System Memory Allocation Technique
Below are the steps involved in the Buddy System Memory Allocation
Technique:
• The first step includes the division of memory into fixed-sized blocks
that have a power of 2 in size (such as 2, 4, 8, 16, 32, 64, 128, etc. ).
• Each block is labeled with its size and unique identification.
• Initially, all the memory blocks are free and are linked together in a
binary tree structure, with each node representing a block and the tree's
leaves representing the smallest available blocks.
• When a process requests memory, the system finds the smallest
available block that can accommodate the requested size. If the block
is larger than the requested size, the system splits the block into two
equal-sized "buddy" blocks.
• The system marks one of the buddy blocks as allocated and adds it to
the process's memory allocation table, while the other buddy block is
returned to the free memory pool and linked back into the binary tree
structure.
 • When a process releases memory, the system marks the corresponding
block as free and looks for its buddy block. If the buddy block is also
free, the system merges the two blocks into a larger block and links it
back into the binary tree structure.
The Buddy System technique has several advantages, including efficient use
of memory, reduced fragmentation, and fast allocation and deallocation of
memory blocks. However, it also has some drawbacks, such as internal
fragmentation, where a block may be larger than what the process requires,
leading to a waste of memory. Overall, the Buddy System is a useful memory
allocation technique in operating systems, particularly for embedded
systems with limited memory.
Let the memory size be 2u and a size S is required.
• If 2 U-1 <S<=2 U : Allocate the whole block
• Else: Recursively divide the block equally and test the condition at each
time, when it satisfies, allocate the block and get out of the loop.
The system also keeps a record of all the unallocated blocks and can merge
these different-sized blocks to make one big chunk.
The following figure illustrates the implementation of buddy system,
considering a 1024k (1-megabyte) initial block and the process requests as
shown at the left of the table.
Requests should be handled in first come first serve basis. After all requests
are processed, the program should show the current state of the buddy
system, which indicates processes are using memory and which blocks are
available. When a request is made for a block of size s, the program should
assign the block of that size that was freed most recently.
when a block is split in two, the left-one (lower addresses) should be selected
before the right-one.
Example of Buddy system
Consider a system having buddy system with physical address space 128 KB.
Calculate the size of partition for 18 KB process.
Solution:

So, size of partition for 18 KB process = 32 KB. It divides by 2, till possible to get
minimum block to fit 18 KB.
Features of Buddy System
• Scalability: The Buddy System can scale nicely with growing memory
demands. It can manage huge quantities of memory efficiently by
means of dividing it into smaller blocks and dynamically adjusting
block sizes based totally on allocation and deallocation styles.
• Efficient Splitting and Merging: The Buddy System ensures that
memory blocks are split and merged effectively. When a block is
 allotted, it's divided into smaller pal blocks. Conversely, when memory is
deallocated, the gadget tests if the friend of the deallocated block is
also free. If so, they're merged back into a larger block.
• Reduced Fragmentation: By correctly splitting and merging
reminiscence blocks, the Buddy System enables reduce memory
fragmentation. Fragmentation occurs whilst memory is allotted and
deallocated in a manner that leaves small, unusable gaps between
allocated blocks. The Buddy System minimizes this by way of merging
adjacent loose blocks into large ones whenever feasible.
• Allocation Efficiency: The Buddy System presents quite speedy
allocation and deallocation of memory blocks. Since memory blocks
are pre-allotted and managed in a based manner, the overhead of
finding and allocating reminiscence is decreased compared to extra
complicated reminiscence control strategies.
• Power of Two Block Sizes: The Buddy System commonly divides
memory into blocks of sizes which can be powers of (e.g., 1KB, 2KB, 4KB,
etc.). This simplifies the splitting and merging strategies, as blocks may
be easily divided or blended.
Advantages of Buddy System
• Buddy System is easy to implement.
• It allocates block of correct size.
• It is easy to merge adjacent holes.
• Fast to allocate memory and de-allocating memory.
• It provides optimal memory performance while allocating blocks of
memory of appropriate size and prevents unnecessary memory waste,
unlike other allocation techniques which allocate larger memory blocks
than necessary.
• It provides a flexible and efficient way to manage memory allocation in
systems that require dynamic memory allocation, such as embedded
systems and operating systems.
• It can handle a large number of small memory allocations efficiently
thanks to its block partitioning mechanism, which helps prevent
fragmentation and keeps system performance up.
• It can prevent memory leaks by ensuring that all shared memory is
cleared when not in use, which can improve system stability and
reliability.
 • It provides a high level of flexibility in memory allocation and monitoring
processes, which is particularly useful in systems that require frequent
memory allocation and sharing, such as real-time systems.
Disadvantages of Buddy System
• It requires all allocation unit to be powers of 2
• It leads to internal fragmentation
• It is designed for fixed-sized memory allocations, and it is not suitable
for variable-sized allocations. This can limit its applicability in some
systems, such as databases and file systems.
• It is a general-purpose memory allocation technique and may not be
optimal for all applications. Some applications may require more
specialized memory allocation techniques to achieve the best
performance.