UNIT -- I

Data:
A collection of facts, concepts, figures, observations, occurrences or instructions in a formalized manner.
Information:
The meaning that is currently assigned to data by means of the conventions applied to those data(i.e.
processed data)

Record:
Collection of related fields.

Data type:
Set of elements that share common set of properties used to solve a program.

Data Structures:
Data Structure is the way of organizing, storing, and retrieving data and their relationship with each
other.

Characteristics of data structures:

1. It depicts the logical representation of data in computer memory.
2. It represents the logical relationship between the various data elements.
3. It helps in efficient manipulation of stored data elements.
4. It allows the programs to process the data in an efficient manner.
CLASSIFICATION OF DATA STRUCTURES

Primary Data Strucutres/Primitive Data Structures:

Primitive data structures include all the fundamental data structures that can be directly
manipulated by machine-level instructions. Some of the common primitive data structures include
integer, character, real, boolean etc

Secondary Data Structures/Non Primitive Data

Structures:
Non primitive data structures, refer to all those data structures that are derived from one or
more primitive data structures. The objective of creating non-primitive data structures is to form sets of
homogeneous or heterogeneous data elements.

Linear Data Structures:

Linear data structures are data strucutres in which, all the data elements are arranged in i, linear
or sequential fashion. Examples of data structures include arrays, stacks, queues, linked lists, etc.

Non Linear Structures:

In non-linear data strucutres, there is definite order or sequence in which data elements are
arranged. For instance, a non-linear data structures could arrange data elements in a
hierarchical fashion. Examples of non-linear data structures are trees and graphs.

Static and dynamic data structure:

Static Ds:
If a ds is created using static memory allocation, ie. ds formed when the number of data items
are known in advance ,it is known as static data static ds or fixed size ds.
Dynamic Ds:
If the ds is created using dynamic memory allocation i.e ds formed when the number of data
items are not known in advance is known as dynamic ds or variable size ds.

Abstract Data Type

Data types specify the type of data structure. We can classify the data type into primitive
data types like integer, float, double, etc., or abstract data types like list, stack, queue, etc.
Abstract data type (ADT) is a concept or model of a data type. 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 gives an implementation-independent view.

Abstract Data type (ADT) is a type (or class) for objects whose behavior is defined by a set of values and
a set of operations. 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 gives
an implementation-independent view. The process of providing only the essentials and hiding the
details is known as abstraction.

In the above figure, we can see the ADT model. There are two types of models in the ADT
model:

1. the public function

2. the private function
The ADT model also contains the data structures being used in a program. Here, at first,
encapsulation is performed, i.e., all the data is wrapped in a single unit, i.e., ADT.
Afterwards, abstraction is performed i.e. showing the operations that can be performed on
the data structure and also showcasing the data structures being used in a program.

Types of Abstract Data Types (ADTs)

There are mainly three types of ADTs:

1. List ADT
Lists are linear data structures stored in a non-continuous manner. The list is made up of a
series of connected nodes that are randomly stored in the memory. Here, each node
consists of two parts, the first part is the data and the second part contains the pointer to the
address of the next node.

The first node of a linked list is called the Head, and it acts as an access point. The head
pointer points to the first element of the linked list. The last node is called the Tail, and it
marks the end of a linked list by pointing to a NULL value.

The List ADT functions/operations are as follows:

  front(): returns the value of the node present at the front of the list.
 back(): returns the value of the node present at the back of the list.
 push_front(int val): creates a pointer with value = val and keeps this pointer to the
front of the linked list.
 push_back(int val): creates a pointer with value = val and keeps this pointer to the
back of the linked list.
 pop_front(): removes the front node from the list.
 pop_back(): removes the last node from the list.
 empty(): returns true if the list is empty, otherwise returns false.
 size(): returns the number of nodes present in the list.

Example illustrating List ADT Operations

class Node:

def __init__(self, val):

self.data = val # to store the data

self.next = None # to store the address of the next List node

class List:

def __init__(self):

self.head = None # pointer to the head of the linked list

self.count = 0 # to count the number of nodes in the list

 def front(self): # returns value of the node present at the front of the list

if self.head:

return self.head.data

else:

raise Exception("List is empty")

def back(self): # returns value of the node present at the back of the list

if self.head:

temp = self.head

while temp.next:

temp = temp.next

return temp.data

else:

raise Exception("List is empty")

def push_front(self, val): # creates a pointer with value = val and keeps this pointer to the front of the
linked list

newNode = Node(val)

newNode.next = self.head

self.head = newNode

self.count += 1

def push_back(self, val): # creates a pointer with value = val and keeps this pointer to the back of the
linked list

newNode = Node(val)
 if not self.head:

self.head = newNode

else:

temp = self.head

while temp.next:

temp = temp.next

temp.next = newNode

self.count += 1

def pop_front(self): # removes the front node from the list

if self.head:

temp = self.head

self.head = self.head.next

temp.next = None

self.count -= 1

else:

raise Exception("List is empty")

def pop_back(self): # removes the last node from the list

if self.head:

if not self.head.next:

self.head = None

else:

temp = self.head

while temp.next.next:

temp = temp.next
 temp.next = None

self.count -= 1

else:

raise Exception("List is empty")

def empty(self): # returns true if list is empty, otherwise returns false

return self.count == 0

def size(self): # returns the number of nodes that are present in the list

return self.count

# Test the List class

myList = List()

# Test operations

myList.push_back(1)

myList.push_back(2)

myList.push_back(3)

print("Front of the list:", myList.front())

print("Back of the list:", myList.back())

print("List size:", myList.size())

myList.pop_front()
myList.pop_back()

print("Front of the list after pop_front():", myList.front())

print("Back of the list after pop_back():", myList.back())

Output
Front of the list: 1
Back of the list: 3
List size: 3
Front of the list after pop_front(): 2
Back of the list after pop_back(): 2

2. Queue ADT
A queue is an ordered list in which insertion is done at one end called REAR and deletion at
another end called FRONT. The first inserted element is available first for the operations to
be performed and is the first one to be deleted. Hence, it is known as First In First Out,
FIFO, or Last In Last Out, LILO.
The Queue ADT functions/operations are as follows:

 enqueue(): Insert an element at the end of the queue.

 dequeue(): Remove and return the first element of the queue, if the queue isn't
empty.
 peek(): Return the element from the queue without removing it.
 size(): Return the number of elements in the queue.
 isEmpty(): Return true if the queue is empty, otherwise return false.
 isFull(): Return true if the queue is full, otherwise return false.

Example Illustrating Queue ADT Operations

class Node:

def __init__(self, val):

self.data = val # to store data in a stack node

self.next = None # to store the address of the next node in the stack

class Queue:

def __init__(self):
 self.count = 0 # to count number of nodes in the stack

self.frontNode = None # pointer to the front of the queue

self.rearNode = None # pointer to the rear of the queue

# Returns value of the node present at the front of the queue

def front(self):

if self.frontNode is not None:

return self.frontNode.data

else:

raise IndexError("Queue is empty")

# Returns value of the node present at the back of the queue

def back(self):

if self.rearNode is not None:

return self.rearNode.data

else:

raise IndexError("Queue is empty")

# Creates a node with value = val and put it at the front of the queue

def push(self, val):

newNode = Node(val)

if self.frontNode is None:

self.frontNode = newNode

self.rearNode = newNode

else:
 self.rearNode.next = newNode

self.rearNode = newNode

self.count += 1

# Removes node from the front of the queue

def pop(self):

if self.frontNode is not None:

self.frontNode = self.frontNode.next

self.count -= 1

if self.frontNode is None:

self.rearNode = None

else:

raise IndexError("Queue is empty")

# Returns true if queue is empty, otherwise returns false

def empty(self):

return self.count == 0

# Returns the number of nodes that are present in the queue

def size(self):

return self.count

# Test the Queue class

myQueue = Queue()
# Test operations

myQueue.push(1)

myQueue.push(2)

myQueue.push(3)

print("Front of the queue:", myQueue.front())

print("Back of the queue:", myQueue.back())

print("Queue size:", myQueue.size())

myQueue.pop()

print("Front of the queue after pop():", myQueue.front())

Output
Front of the queue: 1
Back of the queue: 3
Queue size: 3
Front of the queue after pop(): 2

3. Stack ADT
A stack is an ordered list or we can say a container in which insertion and deletion can be
done from the one end known as the top of the stack. The last inserted element is available
first and is the first one to be deleted. Hence, it is known as Last In, First Out LIFO, or First
In, Last Out FILO.
In a stack, the element at the top is known as the top element. When a new element is
added to the stack, it is placed on top of the existing elements. Stacks are dynamic; this
means that they do not have a fixed size and their size can be increased or decreased
depending upon the number of elements.

The Stack ADT functions/operations are as follows:

  top(): returns the value of the node present at the top of the stack.
 push(int val): creates a node with value = val and puts it at the stack top.
 pop(): removes the node from the top of the stack.
 empty(): returns true if the stack is empty else false.
 size(): returns the number of nodes present in the stack

Example Illustrating Stack ADT Operations

class Node:

def __init__(self, val):

self.data = val # to store data in a stack node

self.next = None # to store the address of the next node in the stack

class Stack:

def __init__(self):

self.count = 0 # to count number of nodes in the stack

self.topNode = None # pointer to the top of the stack

def top(self): # returns value of the node present at the top of the stack

if self.topNode is not None:

return self.topNode.data

else:

raise IndexError("Stack is empty")

def push(self, val): # creates a node with value = val and put it at the stack top

newNode = Node(val)

newNode.next = self.topNode

self.topNode = newNode

self.count += 1
 def pop(self): # removes node from the top of the stack

if self.topNode is not None:

temp = self.topNode

self.topNode = self.topNode.next

temp.next = None

self.count -= 1

else:

raise IndexError("Stack is empty")

def empty(self): # returns true if stack is empty, otherwise returns false

return self.count == 0

def size(self): # returns the number of nodes that are present in the stack

return self.count

# Test the Stack class

myStack = Stack()

# Test operations

myStack.push(1)

myStack.push(2)

myStack.push(3)

print("Top of the stack:", myStack.top())

print("Stack size:", myStack.size())

myStack.pop()

print("Top of the stack after pop():", myStack.top())

Output
Top of the stack: 3
Stack size: 3
Top of the stack after pop(): 2

Advantages of ADT
 Encapsulation: ADTs help encapsulate data and operations into a single unit,
making managing and modifying the data structure easier.
 Abstraction: You can work with ADTs without knowing the implementation details,
which can simplify programming and reduce errors.
 Data Structure Independence: ADTs can be implemented using different data
structures, to make it easier to adapt to changing needs and requirements.
 Information Hiding: ADTs protect data integrity by controlling access and
preventing unauthorized modifications.
 Modularity: ADTs can be combined with other ADTs to form more complex data
structures increasing flexibility and modularity in programming.

Disadvantages of ADT
 Overhead: Implementing ADTs can lead to overhead in terms of memory and
processing resulting in reduced performance.
 Complexity: ADTs can be complex to implement, especially for large and complex
data structures.
 Learning Curve: To learn to implement ADTs takes a good amount of time and
effort.
 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
increasing the cost of development.

What is an Array in Data Structures?

An array is a powerful data structure that allows users to store and manipulate a collection
of elements, all of the same data type in a single variable. Simply, it is a collection of
elements of the same data type stored at contagious memory locations that can be
randomly accessed with their index number. It’s one of the most popular and simple data
structures and is often used to implement other data structures like stacks and queues.

Representation of Arrays in Data Structures

The representation of an array can be defined by its declaration. A declaration means
allocating memory for an array of a given size.

import array

# Example:

arr = array.array('i', [1, 2, 5, 6])

Types of Arrays in Data Structures

There are two types of array in Data Structures, which are:

1. Single-dimensional array: It is a collection of elements of the same data type that

are stored in a contiguous block of memory.
2. Multi-dimensional array: It is an array that contains one or more arrays as its
elements. We will see this in the next section Types of Arrays in Data Structures.
In this tutorial, we will cover all the aspects of a Single dimensional array

How to Access Elements of an Array in Data

Structures?
To access the array elements, use the index number of the required element. The array
index starts with 0. The index of the last element is n-1.

Basic Operations on Arrays in Data Structures

1. Traversal
This operation is used to traverse or move through the elements of the array.

fruits = ["Apple", "Mango", "Banana", "Orange", "Grapes"]

for fruit in fruits:

print(fruit)

Output
Apple
Mango
Banana
Orange
Grapes.

2. Insertion
We can insert one or multiple elements in an array as per the requirement at the required
positions or indexes

# array size

n=5

# index of element to be added

pos = 2

# element to be added
 item = 4

# incrementing the size of the array by 1

n=n+1

# adjusting the value of loop counter to the last index

j=n-2

# traversing balls[] from last

while j >= pos:

# copying the element to the incremented block

balls[j + 1] = balls[j]

j=j-1

# copying the element to the vacated position

balls[pos] = item

print("The chairs and the corresponding number of balls after adding a ball:")

for i in range(n):

print(" ", i + 1, "\t", balls[i])

if __name__ == "__main__":

main()

Output
The chairs and the corresponding number of balls after adding a ball:
15
22
34
48
55
67

3. Deletion
It is used to delete an element from a particular index in an array

balls = [5, 2, 8, 5, 7]

# array size

n=5

# index of element to be deleted

pos = 2

# adjusting the value of loop counter to pos

j = pos

while j < n:

balls[j - 1] = balls[j]

j=j+1

# decrementing the size of the array by 1

n=n-1

print("\nThe chairs and the corresponding number of balls after removing a ball")

for i in range(n):

print(" " + str(i + 1) + "\t " + str(balls[i]))

Output
The chairs and the corresponding number of balls after removing a ball
1 5
2 8
3 5
4 7

4. Search
It is used to search an element using the given index or by the value. We can search any
element in an array and display both, its index and value.

balls = [5, 4, 8, 5, 7]

# array size

n=5

# element to be searched

order = 4

j=0

while j < n:

if balls[j] == order:

break

j=j+1

print("The corresponding chair number of order:", order, " is ->", j + 1)

Output
The corresponding chair number of order: 4 is -> 2

5. Update
We can change the values of the elements inside an array at any position or index.
no_of_students = [5, 6, 7, 2, 4, 8, 3]

# array size

n=7

# index of the element to be updated

pos = 3

# updated number

item = 0

print("The number of students sitting on the benches in order: ")

for i in range(n):

print(no_of_students[i])

print("Bench numbers and the corresponding number of students sitting on each bench")

for i in range(n):

print(f" {i + 1}\t {no_of_students[i]}")

no_of_students[pos] = item

print("\nStudent Numbers and the updated no of Students on each bench after the 1st update")

for i in range(n):

print(f" {i + 1}\t {no_of_students[i]}")

Output
The number of students sitting on the benches in order:
5
6
7
2
4
8
3
Bench numbers and the corresponding number of students sitting on each bench
15
26
37
42
54
68
73

Student Numbers and the updated no of Students on each bench after the 1st update
15
26
37
40
54
68
73

Complexity Analysis of Operations on Arrays

 Time Complexity

Operation Best Case Average Case Worst Case

Traversal O(1) O(n) O(n)

Insertion O(1) O(n) O(n)

Deletion O(1) O(n) O(n)
Search O(1) O(n) O(n)
Update O(1) O(1) O(1)

 Space Complexity: Most of the operations on arrays have a space complexity

of O(1), except for resizing operations and certain insertions/deletions that may
require shifting elements, resulting in O(n) space complexity.
 Applications of Arrays in Data Structures
1. Storing and accessing data: Arrays are often used to store data that can be
accessed quickly and efficiently. For example, an array can be used to store the
scores of students in a class or the prices of products in a store.
2. Sorting and searching data: It is easier to sort and search data in an array using
the index. It is used for different sorting algorithms such as bubble sort, insertion
sort, merge sort, and quick sort.
3. Implementing dynamic data structures: It isused to implement dynamic data
structures like stacks, queues, and heaps.
4. Image processing: Arrays can be used to represent and process images. Each
element in the array represents a pixel in the image, and operations can be
performed on the array to manipulate the image.
5. Numerical computations: The application of an array is extensive in numerical
computations, such as in linear algebra and signal processing. For example, a matrix
can be represented as a two-dimensional array, and operations like matrix
multiplication can be performed efficiently using arrays.
6. Games and simulations: Arrays can be used to represent game boards, game
pieces, and game states. They are also used in simulations to store and manipulate
data over time.

Advantages of Arrays
 Constant time access: Each element is retrieved via index.
 Optimal memory use: There is no storage waste for links or additional information.
 Versatility: Can store any data type (integers, characters, strings, user-defined kinds).
 Flexibility: The foundation for building different data structures (stacks, queues, trees, graphs).
 Easy to remember: A single name identifies several data elements of the same type.

Disadvantages of Arrays
 Fixed-size: The array size is predetermined and cannot be modified after construction.
 Memory wastage: Unused space when there are fewer elements than the given size.
 Inefficient insertion/deletion: Shifts are necessary for insertion and deletion, particularly in big
arrays.
 Homogeneous data: Homogeneous data only contains elements of the same data type.
 No built-in scaling: Some languages do not have built-in support, requiring complicated manual
resizing logic.
Stack in Data Structures
A stack in data structures is a linear collection that follows the Last In, First Out (LIFO)
principle, where the last element added is the first to be removed. This structure is essential
in various algorithms and applications such as expression evaluation, backtracking, and
memory management.

What is a Stack in Data Structures?

 A stack is an ordered list or we can say a container in which insertion and deletion
can be done from the one end known as the top of the stack.
 The last inserted element is available first and is the first one to be deleted.
 Hence, it is known as Last In, First Out LIFO or First In, Last Out FILO.
 In a stack, the element at the top is known as the top element.
 When a new element is added to the stack, it is placed on top of the existing
elements.
 Stacks are dynamic; this means that they do not have a fixed size and their size can
be increased or decreased depending upon the number of elements.

Standard Operations on Stack

The time complexity of all the given operations is constant, i.e. O(1).

1. Insertion: push()
The push() operation is one of the fundamental operations in a stack data structure.
Pushing means inserting an element at the top of the stack. If the stack is full, then it is said
to be an Overflow condition.

2. Deletion: pop()
The pop() operation is used to remove the topmost element of the stack and return its
value. The pop() operation modifies the state of the stack by removing the topmost element.
The items are popped in the reversed order in which they are pushed. If the Stack is empty,
it is a Underflow condition.

3. peek()
The peek() operation returns the value of the topmost element of the stack without
modifying the stack. This can be useful when you need to check the value of the top
element before deciding whether to remove it or not.
 4. isFull()
The isFull() operation is used to determine if the stack is full or not. A stack is said to be full
if it has reached its maximum capacity and there is no more space to add new elements to
the stack.

5. isEmpty()
The isEmpty() operation is used to check if the stack is empty or not. It returns a boolean
value, true when the stack is empty, otherwise false.

1. Implementation of Stack Using a 1D Array

Follow the below-given procedure to implement stack using a 1D Array in Data
Structures

 Declare a variable top to keep track of the top element in the stack.
 When initializing the stack, set the value of the top to -1 to check if the stack is full or
empty.
 Declare a function push() that takes an array, stack[]; the size of the array, n; and the
element a to be inserted as its parameters.
 Under the function: you have to check if the stack is already full. If so, return from
the function. and If the stack is not full, increment top and place the new element in
the position pointed to by the top.

 Declare a function pop() that removes the top element from the stack.
 Under the function just check if the stack is empty. If so, return from the function then
If the stack is not empty, return the element at the top index in the array stack[] and
decrement top. Here, we are not deleting the value at the top index
 during pop() because once the pointer is moved to point to the previous element, it
does not matter what is contained in that memory location.

 Declare a function topElement() that returns the element at the top index from the
array stack[].
 Declare a function size() that returns the occupied size of the array stack[]. It
returns top + 1.
 Declare a function isEmpty() to check if the top is equal to -1. If it is, it returns true,
otherwise false.
 Declare a function isFull() to check if the top is equal to the maximum size of the
array stack[]. If it is, it returns true, otherwise false.

Example of Stack Implementation in Different Languages using a

1D array
def is_empty(self):

return self.top == -1

def pop(self):

if self.is_empty():

print("Stack Underflow")

else:

self.top -= 1

def stack_size(self):

return self.top + 1

def top_element(self):

return self.stack[self.top]

if __name__ == "__main__":
 stack = Stack(6)

stack.push(5)

print("Current size of stack is", stack.stack_size())

stack.push(10)

stack.push(15)

stack.push(20)

stack.push(25)

stack.push(30)

print("Current size of stack is", stack.stack_size())

# Attempting to push into a full stack

stack.push(35)

# Accessing the top element

print("At present, the top element in stack is", stack.top_element())

# Removing all the elements from the stack

for _ in range(6):

stack.pop()

print("Current size of stack is", stack.stack_size())

# Attempting to pop from an empty stack

stack.pop()

Output
Current size of stack is 1

Current size of stack is 6

Stack Overflow

At present, the top element in stack is 30

Current size of stack is 0

Stack Underflow

Advantages of Array Implementation

 Easy to implement.
 Memory is saved as pointers are not involved.

Limitations of Array Implementation

 The maximum size of the array must be defined beforehand.
 The size of the array cannot be changed during the run time because it is not
dynamic.

2. Implementation of Stack Using a Single Linked List

Follow the below-given procedure to implement Stack using a Single Linked List in Data
Structures.

1. First of all, create a class or structure Node with instance variables, data, and next.
2. The data will contain the element to be inserted and next will contain the address of
the previous element in the linked list.
3. To keep track of the topmost element, create an instance, top of the class Node.
4. Declare a function push() that takes data as a parameter and adds it to the existing
linked list.
5. Under the function –
o A temporary instance of the class Node is created, and memory is allocated
for the same.
o Check if the heap is full. If it is, print Stack Overflow.
o If the heap is not full, add the data to the temporary instance.
6. Store the address of the previous top in the address part of the temporary instance.
7. Update the top so that it points to the temporary instance that contains the newly
inserted value.
8. Declare a function pop() that deletes the current top, and point it to the element just
before it.
9. Under the function –
o Check if the stack is empty or not. If it is, print Stack Underflow.
o If the stack is not empty, make the top point to the previous element.
o Free the memory that was used by the element that was popped.
Example of Stack Implementation in Different Languages Using a
Single Linked List
class Node:

def __init__(self, data):

self.data = data

self.link = None

class Stack:

def __init__(self):

self.top = None

def push(self, data):

temp = Node(data)

temp.link = self.top

self.top = temp

def is_empty(self):

return self.top is None

def peek(self):

if not self.is_empty():

return self.top.data

else:

exit(1)
 def pop(self):

if self.is_empty():

print("Stack Underflow")

exit(1)

else:

temp = self.top

self.top = self.top.link

temp.link = None

del temp

if __name__ == "__main__":

stack = Stack()

stack.push(5)

stack.push(10)

stack.push(15)

stack.push(20)

stack.push(25)

stack.push(30)

# Print top element of stack

print("\nThe Top element is", stack.peek())

# Delete top elements of stack

stack.pop()

stack.pop()
 stack.pop()

stack.pop()

stack.pop()

# Print top element of stack

print("\nThe Top element is", stack.peek())

Output
Top element is: 30

Top element is: 5

Advantages of Linked List Implementation

 A linked list is dynamic, i.e. the size of the linked list can be changed during the run
time.
 It is used in many virtual machines like JVM.

Limitations of Linked List Implementation

 There's an extra requirement of memory due to the involvement of pointers.
 Random accessing of elements is not possible in a stack.

Applications of Stack
There are some applications of stacks in the data structure:

1. Function Calls and Recursion: When a function is called, the compiler stores
information about the return address and the values of any parameters, in the stack.
When the function is finished, the information is retrieved from the stack and the
program continues executing from the point where it left off.
2. Recursion: To maintain the previous states, the compiler creates a system stack in
which all the previous records of the function are maintained
3. Expression Evaluation: A stack can be used to evaluate arithmetic expressions in
which parentheses are used to group sub-expressions. The operands and operators
are pushed into the stack, and when a closing parenthesis is encountered, the sub-
expression is evaluated using the operators and operands in the stack.
4. The A list of the expression conversion is given below:
o infix to prefix
o Infix to postfix
o Prefix to infix
o Prefix to postfix
o Postfix to infix
5. Parsing: A stack is often used in parsing algorithms to keep track of the nesting of
symbols such as parentheses, brackets, and braces.
6. Undo/Redo Operations: Many applications, such as text editors and graphic design
software, allow users to undo and redo previous operations. A stack can be used to
store the state of the application before each operation, allowing the user to undo or
redo the operation by popping or pushing elements from the stack.
7. Backtracking: When searching for a solution to a problem, it may be necessary to
backtrack and try a different path if the current path does not lead to a solution. A
stack can be used to store information about the current path, allowing the algorithm
to backtrack by popping elements from the stack.

Advantages of Stack
 Easy to implement: The implementation of a stack is simple, making it easy to use
and understand.
 Efficient memory management: A stack uses a contiguous block of memory, which
is allocated when the stack is created. This makes it efficient in terms of memory
utilization.
 Accessibility: A stack allows quick access to its elements as the elements are
added and removed from the top of the stack, which is useful in many applications,
such as parsing expressions and reversing a string.
 Recursive algorithms: A stack is used to store function calls and their states, which
helps in the efficient implementation of recursive function calls.
 Compiler Design: Stack is used in compiler design for parsing and syntax analysis
of programming languages.
Disadvantages of Stack
 Limited storage: Stacks can store only a fixed number of elements. In the case of
stack overflow, there can be a loss of data.
 No random access: Unlike other data structures like arrays, stacks do not provide
direct access to elements in the middle of the stack. You can only add and remove
elements from the top of the stack. The user has to remove all the elements above
the middle element to access it.
 Stack overflow and underflow: Adding or removing too many elements into and
from the stack can cause stack overflow or underflow respectively causing the
program to crash.
 Memory management: Stack uses a contiguous block of memory, which can result
in memory fragmentation or memory leaks if there's a frequent addition or removal of
elements.

Queue in Data Structures

Queue in Data Structures is a type of non-primitive, linear, and dynamic data structure. It
works according to the FIFO principle. This principle is widely used in various applications of
Queue in data structures, such as task scheduling, buffering, and handling asynchronous
data. There are different types of queues in data structures, including simple
queues, circular queues, and priority queues. To implement queues in data
structures, arrays, and linked lists are commonly used, with array queues in data
structures being one of the fundamental implementations.

What is a Queue in Data Structures?

A queue is an ordered list in which insertion is done at one end called REAR and deletion at
another end called FRONT. The first inserted element is available first for the operations to
be performed and is the first one to be deleted. Hence, it is known as First In First
Out, FIFOor Last In Last Out, LILO.

Representation of a Queue in Data Structures

We know that a queue can be accessed from both sides i.e. at the front for deletion and
back or rear for insertion.
Standard Operations on Queue in Data Structures
1. Insertion: enqueue()
The enqueue() Operation is used to insert an element at the back of a queue to the end of a
queue or the rear end of the queue.

2. Deletion: dequeue()
The dequeue() Operation is used to remove and return the element from the front of a
queue.

3. peek()
The peek()The operation returns the value at the front end of the queue without removing it.

4. isFull()
The isFull() operation is used to determine if the queue is full or not. A queue is said to be
full if it has reached its maximum capacity and there is no more space to add new elements
to it.

5. isEmpty()
The isEmpty() operation is used to check if the queue is empty or not. It returns a boolean
value, true when the queue is empty, otherwise false.

Working of Queue in Data Structures

 .Queue
operations work as follows:

 Two pointers are there denoting two ends, FRONT and REAR.
 FRONT Tracks the first element of the queue.
 REAR Tracks the last element of the queue.
 Initially, set the value of FRONT and REAR to -1.
 Afterward, follow the above-given algorithms for the basic operations.

Types of Queues in Data Structures

here are 4 types of queues in data structures:

1. Simple or Linear Queue
 As we mentioned above, a Simple queue follows the First-In-First-Out (FIFO)
principle.
 In this, Items are taken out of the front and put in the back.
 It is necessary to remove outdated elements in order to add new ones.

Circular Queue
 A circular queue is similar to a simple queue, but the last element is connected to
the first element which creates a circular structure.
 This allows for efficient use of memory.
 It is also known as a Ring Buffer.
Priority Queue
 It is a special type of queue in which each element has a priority assigned to it.
 The element with the highest priority is removed first.
 This is useful in situations where certain elements need to be processed before
others.

Dequeue (Double-Ended Queue)

 In this, the elements can be added or removed from both ends front and rear of the
queue.
 Dequeue allows insertion and deletion at both front and rear ends.
 It provides flexibility in managing data with operations from both ends.

Dequeue (Double-Ended Queue)

 In this, the elements can be added or removed from both ends front and rear of the
queue.
 Dequeue allows insertion and deletion at both front and rear ends.
 It provides flexibility in managing data with operations from both ends.
 1. Implementation of Queue Using a 1D Array
It is the simplest implementation of a Queue in Data Structures. We usually use arrays to
implement queues in Java and C++. In the case of Python, we use lists.
The time complexity of all the operations is the same i.e. O(1) here.

class Queue:
def __init__(self, capacity):
self.capacity = capacity
self.front = self.size = 0
self.rear = capacity - 1
self.array = [0] * self.capacity

def is_full(self):
return self.size == self.capacity

def is_empty(self):
return self.size == 0

def enqueue(self, item):

if self.is_full():
return
self.rear = (self.rear + 1) % self.capacity
self.array[self.rear] = item
self.size += 1
print(f"{item} enqueued to queue")

def dequeue(self):
if self.is_empty():
return float('-inf')
item = self.array[self.front]
self.front = (self.front + 1) % self.capacity
self.size -= 1
return item
 def get_front(self):
return self.array[self.front] if not self.is_empty() else float('-inf')

def get_rear(self):
return self.array[self.rear] if not self.is_empty() else float('-inf')

if __name__ == "__main__":
# Create a queue with a capacity of 100
queue = Queue(100)

# Enqueue elements into the queue

queue.enqueue(10)
queue.enqueue(15)
queue.enqueue(20)
queue.enqueue(25)
queue.enqueue(30)

# Dequeue elements from the queue

print(f"{queue.dequeue()} dequeued from queue")
print(f"{queue.dequeue()} dequeued from queue")
print(f"{queue.dequeue()} dequeued from queue")

# Display the front and rear elements of the queue

print("Front item is", queue.get_front())
print("Rear item is", queue.get_rear())

Output
10 enqueued to queue

15 enqueued to queue

20 enqueued to queue

25 enqueued to queue

30 enqueued to queue

10 dequeued from queue

15 dequeued from queue

20 dequeued from queue

Front item is 25

Rear item is 30
Advantages of Array Implementation
 Easy to implement.
 A large amount of data can be managed efficiently with ease.
 Operations such as insertion and deletion can be performed with ease as a queue
follows the FIFO rule.

Limitations of Array Implementation

 The maximum size of the queue must be defined beforehand.
 The size of the array cannot be changed during the run time because it is not
dynamic.
 If the queue has a large number of enqueue and dequeue operations, at some point
(in case of linear increment of front and rear indexes) it may happen that we may not
be able to insert elements in the queue even if the queue is empty.

2. Implementation of a Queue Using a Linked List

We discussed the disadvantages of array implementation above. Due to this, the array
cannot be used for large-scale applications of queues. One of the solutions to overcome
this limitation is linked list implementation of queues in data structures
.

The storage requirement of the linked representation of a queue with n elements is O(n).
The time complexity of all the operations is the same i.e. O(1) here.
In a linked queue, each node of the queue consists of two parts i.e. data part and
the link part. Each element of the queue points to its immediate next element in the
memory. There are two pointers maintained in the memory i.e. front pointer
and rear pointer. The front pointer contains the address of the starting element of the queue
while the rear pointer contains the address of the last element of the queue.

class Node:
def __init__(self, data):
self.data = data
self.next = None

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

def enqueue(self, data):

new_node = Node(data)
if not self.rear:
self.front = self.rear = new_node
else:
self.rear.next = new_node
 self.rear = new_node
self.size += 1

def dequeue(self):
if not self.front:
print("Queue is empty")
return None
temp = self.front
self.front = self.front.next
if not self.front:
self.rear = None
self.size -= 1
return temp.data

def peek(self):
return self.front.data if self.front else None

def is_empty(self):
return self.size == 0

# Example usage
queue = Queue()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
print(queue.dequeue()) # 10
print(queue.peek()) # 20

Output
10

20

Complexity Analysis of Queue Operations

Stack Vs Queue
Parameters Stack Queue

It follows the LIFO (Last In First

It follows the FIFO (First In First Out) order to
Out) order to store the
Working store the elements, which means the
elements, which means the
Principle element that is inserted first will come out
element that is inserted last will
first.
come out first.
It has two ends,rear and front, which are
It has only one end, known as used for insertion and deletion. The rear end
Pointers the top, at which both insertion is used to insert the elements, whereas
and deletion take place. the front end is used to delete the elements
from the queue.
The insertion operation is The insertion operation is known
Operations known as push and the deletion as enqueue and the deletion operation is
operation is known as pop. known as dequeue.
The condition for checking
Empty whether the stack is empty The condition for checking whether the
Condition is top ==-1 as -1 refers to no queue is empty is front == -1
element in the stack.
The condition for checking if the
The condition for checking if the queue is full
stack is full is top==max-
is rear==max-1 as max refers to the
Full Condition 1 as max refers to the maximum
maximum number of elements that can be in
number of elements that can be
the queue.
in the stack.
There are three types of queues: circular
There are no other variants or
Variants queue, double-ended queue, and priority
types of the stack.
queue.
It has a simple implementation It has a complex implementation compared
Implementation compared to queues as no two to stacks as two pointers front and rear are
pointers are involved. involved.
Data Often implemented Can also be implemented
Representation with arrays or linked lists. with arrays or doubly linked lists.
the Undo/Redo operation in operating system process scheduling
Example
Word or Excel. queues.
It is used to solve recursion- It is used to solve sequential processing-
Application
based problems. based problems.
A stack can be visualized as a Queue can be visualized as a horizontal
Visualization
vertical collection. collection.

Applications of Queue
 1. Multi-programming: It is essential to organize the multiple programs running in the
main memory so they are organized as queues.
2. Network: In a network, a queue is used in devices such as a router or a switch.
3. Job Scheduling: The computer has a task to execute a particular number of jobs
that are scheduled to be executed one after another. These jobs are assigned to the
processor one by one which is organized using a queue. E.g. CPU scheduling, Disk
Scheduling
4. Synchronization: The queue is used for synchronization when data is transferred
asynchronously between two processes. E.g. IO Buffers, pipes, file IO, etc
5. Interrupts: Handling of interrupts in real-time systems.
6. Shared resources: Queues are used as waiting lists for a single shared resource.
7. Operation on data structures: Certain operations like BFS (Breadth First
Search), and tree traversal use Queue. The sequence of traversal of inputs is set
using queues.

Advantages of Queue
1. Efficient data processing: A queue can be used to efficiently process data in the
order it was received. For example, in a computer system, a queue can be used to
schedule processes in the order they were submitted.
2. Resource management: A queue can be used to manage resources that are
shared among multiple processes or threads. For example, a printer can use a
queue to manage print jobs.
3. Buffering: A queue can be used to buffer incoming data so that it can be processed
at a later time. For example, a network device can use a queue to buffer incoming
data packets before forwarding them to their destination.
4. Memory management: A queue can be used to manage memory by allocating and
deallocating memory blocks in sequential order.

Disadvantages of Queue
1. Limited flexibility: Queues follow a strict FIFO order, meaning the element that
enters first is the first one to be removed. This lack of flexibility can be a
disadvantage in some use cases where other priorities or requirements must be
considered.
2. No random access: Unlike arrays or linked lists, queues do not allow random
access to the elements. The user can only access the first element in the queue, and
to access any other element, they need to remove all the elements that come before
it. This can be a disadvantage when the user needs to access an element in the
middle of the queue.
3. Overhead: Queues require extra overhead to maintain the order of elements.
Whenever an element is added or removed from the queue, all the other elements
must be shifted accordingly, which can be time-consuming for large queues.
4. Limited size: In some implementations, queues have a limited size, which can be a
disadvantage when dealing with large amounts of data. Once the queue reaches its
maximum size, it can no longer accept new elements.
 5. No search operation: Queues do not provide a search operation. The user cannot
search for a specific element in the queue they can only remove the elements in the
order they were added and hope to find the element they are looking for.

Linked Lists in Data Structures

Linked List in data structures is a non-primitive, linear, and dynamic data structure. It is a
chain of nodes where each node is a different element.

What is a Linked List in Data Structures?

A Linked List is a linear data structure consisting of a series of connected nodes that are
randomly stored in the memory. Here, each node consists of two parts, the first part is
the data and the second part contains the pointer to the address of the next node.
The first node of a linked list is called the Head, and it acts as an access point.
The head pointer points to the first element of the linked list. The last node is called the Tail,
and it marks the end of a linked list by pointing to a NULL value. After arrays, linked lists are
the second most used data structure.

Representation of Linked Lists in Data Structures

A linked list can be represented as the connection of nodes in which each node points to
the next node of the list.

Types of Linked Lists in Data Structures

1. Singly-linked list: Here, each node has data and a pointer that contains a reference
to the next node in the list. This means that we can traverse in only one direction,
from the head to the tail. It is the most common linked list.
2. Doubly linked list: In this type of linked list, each interconnected node contains
three fields that contain references to both the next and previous nodes in the list
along with the data. This allows traversal in both directions, making it easier to insert
or delete nodes at any point in the list.
3. Circular linked list: Here, the last node in the list contains a reference to the first
node instead of NULL, creating a loop. This means that traversal can continue
indefinitely, until the program crashes.
How to declare/create a Singly-Linked List in Data
Structures?
We now very well know that a node in a linked list contains two parts, a data item and
the address of another node. So, both parts are of different types, i.e., one is a simple
variable, while another is the pointer variable. We can declare the linked list by using the
user-defined data type structure.
struct node

int data;

struct node *next;

};

Here, we have created a structure named node that contains two variables, data of integer
type, and a pointer, next that contains the address of the next node.

Standard Operations on Linked Lists in Data

Structures
1. Traversal
We can access each element of the linked list starting from the head node. Just keep
moving a temp node to the next one and display its contents. When temp is NULL, it means
we have reached the end of the linked list so we get out of the while loop.

2. Insertion
We can insert elements to either the beginning, middle, or end of the linked list. Inserting a
new node at any given position is done by manipulating at most two next pointers,
the prevNode and the newNode.
Set newNode's next pointer to the prevNode's next pointer and set prevNode's next pointer
to the newNode where prevNode denotes a pointer to the node after which newNode is to be
inserted. However, to access any given position, we have to traverse starting from
the head till the prevNode.
The order of execution matters in case of insertion. If we interchange the steps i.e. first
set prevNode's next pointer to the newNode then we lose the reference to the remaining of
the linked list previously occurring after the prevNode.

3. Deletion
Same as insertion, you can delete either from the beginning, end, or a particular position.
Deleting a node located at a specified index is done by manipulating at most
two next pointers, the prevNode, and the targetNode.
Set prevNode's next pointer to the targetNode's next pointer and set targetNode's next
pointer to NULL where prevNode denotes a pointer to the node after which targetNode is to
be deleted.
Just like insertion, the order is important here also. It's important to realize that
setting targetNode's next pointer to NULL as the first step would cost us the reference to the
remaining of the linked list (if the targetNode wasn't the Tail).

4. Search
It is performed to search for an element from the list using the given key.
The following are the steps to search for an element

 Make head as the current node.

 Run a loop until the current node is NULL because the last element points to NULL.
 In each iteration, check if the key of the node is equal to the item. If the key matches
the item, return true otherwise return false.

Implementation of Linked Lists in Different

Programming Languages
class Node:
def __init__(self, data=0, next_node=None):
self.data = data
self.next = next_node

class LinkedList:
def __init__(self):
self.head = None

def traversal(self):
itr = self.head
while itr:
print(itr.data)
itr = itr.next

def insertion(self, prev_node, new_node):

new_node.next = prev_node.next
prev_node.next = new_node
 def deletion(self, prev_node, target_node):
prev_node.next = target_node.next

def search(self, key):

itr = self.head
while itr:
if itr.data == key:
return True
itr = itr.next
return False # key not found!

linked_list = LinkedList()
linked_list.head = Node(1)
second = Node(2)
third = Node(3)

linked_list.head.next = second
second.next = third

# Print the initial linked list

print("Initial Linked List:")
linked_list.traversal()

# Insert a new node (4) after the second node

new_node = Node(4)
linked_list.insertion(second, new_node)

# Print the linked list after insertion

print("\nLinked List after Insertion:")
linked_list.traversal()

# Delete the second node

linked_list.deletion(linked_list.head, second)

# Print the linked list after deletion

print("\nLinked List after Deletion:")
linked_list.traversal()

# Search for a key (3) in the linked list

key = 3
print(f"\nKey {key} is {'found' if linked_list.search(key) else 'not found'} in the linked list.")

Run Code >>

Output
Initial Linked List:
1

Linked List after Insertion:

Linked List after Deletion:

Key 3 is found in the linked list.

Complexity Analysis of Linked List Operations

 Time Complexity

Operations Best Case Average Case Worst case

Traversal O(n) O(n) O(n)

Insertion
O(1) O(1) O(n)

Deletion
O(1) O(1) O(n)

Search
O(1) O(n) O(n)
  Space Complexity: The space complexity of the linked list for all operations is O(n).

Arrays vs Linked Lists in terms of Time Complexity

Operations Array Linked List

Random Access O(1) O(n)

Insertion and Deletion at the beginning O(n) O(1)

Insertion and Deletion at the end O(1) O(n)

Insertion and Deletion from any random location O(n) O(n)

Differences between Arrays and Linked Lists

Array Linked List

It is a group of objects called nodes, which

It is a collection of elements of a similar data
consists of two fields: data and address to the
type.
next node

An array stores elements in a contiguous Linked lists store elements randomly at any
memory location. address in the memory.

In an array, memory size is fixed while Linked lists utilize dynamic memory, i.e.
declaration and cannot be altered at run time. memory size can be altered at run time.
 Elements in a linked list are dependent on
Elements in an array are not dependent on
each other, as each node stores the address
each other.
of its next node.

Operations like insertion, deletion, etc., take Operations like insertion, deletion, etc., take
more time in an array. less time than arrays.

Memory is allocated at compile time. Memory is allocated at run time.

Accessing an element in a linked list is time-

It is easier and faster to access the element in
consuming as we have to start traversing from
an array with the help of Indices.
the first element.

Memory utilization is ineffective in arrays. E.g. if In linked lists, memory utilization is effective,
the array size is 5 and contains only 3 elements, as it can be allocated or deallocated at the run
the rest of the space will be wasted. time according to our requirements.

Linked lists are typically used for one-

Arrays support multi-dimensional structures.
dimensional structures.

Arrays are commonly used in low-level Linked lists are often used for specific data
programming and for implementing data management needs like task scheduling and
structures. memory allocation.

After seeing the above comparisons in general and in terms of time complexity, we observe
that a linked list is not superior to an array or vice-versa. These data structures complement
each other and sometimes become superior to the other in certain use cases.

Applications of Linked Lists

Linked lists are commonly used in computer programming for their ability to efficiently store
and manipulate collections of data. Here are some common applications of linked lists:

1. Implementing data structures: Linked lists are commonly used to implement data
structures like stacks, queues, graphs, and hash tables.
2. Dynamic Memory allocation:A linked list of free memory blocks is maintained, and
new memory is allocated by removing blocks from the free list.
3. File systems: Linked lists are used in file systems to represent directories and files.
 4. Music and video players: The list of songs in the music player is linked to the
previous and next songs. Linked lists maintain playlists.
5. Graphs:Adjacency list representation of graphs uses linked lists to store adjacent
vertices.
6. Games: Linked lists are used to represent game boards where each element in the
list represents a cell on the board.

Advantages of Linked Lists

1. Dynamic: Linked lists can be resized during runtime, which means that anyone can
add or remove elements from the list without worrying about the size limitations of
the underlying data structure.
2. Efficient insertion and deletion: Adding or removing elements to and from a linked
list is very easy because the user only needs to update the address of the pointer of
the node as the nodes are stored in random locations.
3. Flexibility: Linked lists can be used to implement a variety of advanced data
structures, such as stacks, queues, and hash tables. This flexibility makes linked lists
a versatile tool for many programming tasks.
4. Memory efficiency:Memory consumption of a linked list is efficient as its size can
grow or shrink dynamically according to our requirements, which means effective
memory utilization hence, no memory wastage.
5. Easy implementation: Implementing a linked list is relatively easy, as the developer
only needs to define a node structure and a few functions to manipulate the links
between nodes.

Disadvantages of Linked Lists

1. Memory Consumption: The use of pointers is more in linked lists hence, complex
and requires more memory.
2. Traversal: Unlike arrays, linked lists do not allow direct access to individual nodes.
Traversing a linked list requires iterating through all the nodes from the beginning of
the list until the desired node is found. This can be inefficient and slow, especially for
large linked lists. Traversing in reverse order is not possible in singly linked lists.
3. No Random Access: Linked lists do not support random access, i.e., accessing a
specific node directly without traversing the list. This can be a significant
disadvantage for some applications that require fast access to individual elements.
4. Cache Misses: Linked lists can suffer from cache misses, i.e., when the CPU needs
to access data that is not in the cache. This can slow down the execution of
programs that frequently access data from linked lists.
5. Search: Linked lists are not efficient for searching large amounts of data, which can
be better handled by other data structures such as trees or hash tables.