Application of Non-primitive Data Type

Real-Time Applications of Array:

Below are some real-time applications of arrays.
 Contact lists on mobile phones.
 Matrices use arrays which are used in different fields like image processing,
computer graphics, and many more.
 Arrays are used in online ticket booking portals.
 Pages of book.
 IoT applications use arrays as we know that the number of values in an array
will remain constant, and also that the accessing will be faster.
 It is also utilised in speech processing, where each speech signal is
represented by an array.
 The viewing screen of any desktop/laptop is also a multidimensional array of
pixels.

Advantages of Arrays
Below are some advantages of the array:
 In an array, accessing an element is very easy by using the index number.
 The search process can be applied to an array easily.
 2D Array is used to represent matrices.
 For any reason a user wishes to store multiple values of similar type then the
Array can be used and utilized efficiently.
Disadvantages of Arrays
Now let’s see some disadvantages of the array and how to overcome it:
Array size is fixed: The array is static, which means its size is always fixed.
The memory which is allocated to it cannot be increased or decreased. Below is
the program for the same:

Application of Stack in real life:

 CD/DVD stand.
 Stack of books in a book shop.
 Undo and Redo mechanism in text editors.
 The history of a web browser is stored in the form of a stack.
 Call logs, E-mails, and Google photos in any gallery are also stored in form
of a stack.
 YouTube downloads and Notifications are also shown in LIFO format(the
latest appears first ).

Advantages of Stack:
 Stack helps in managing data that follows the LIFO technique.
 Stacks are be used for systematic Memory Management.
 It is used in many virtual machines like JVM.
 When a function is called, the local variables and other function parameters
are stored in the stack and automatically destroyed once returned from the
function. Hence, efficient function management.
 Stacks are more secure and reliable as they do not get corrupted easily.
 Stack allows control over memory allocation and deallocation.
 Stack cleans up the objects automatically.
Disadvantages of Stack:
 Stack memory is of limited size.
 The total of size of the stack must be defined before.
 If too many objects are created then it can lead to stack overflow.
 Random accessing is not possible in stack.
 If the stack falls outside the memory it can lead to abnormal termination.

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

Advantages of Queue:
 A large amount of data can be managed efficiently with ease.
 Operations such as insertion and deletion can be performed with ease as it
follows the first in first out rule.
 Queues are useful when a particular service is used by multiple consumers.
 Queues are fast in speed for data inter-process communication.
 Queues can be used in the implementation of other data structures.
Disadvantages of Queue:
 The operations such as insertion and deletion of elements from the middle
are time consuming.
 Limited Space.
 In a classical queue, a new element can only be inserted when the existing
elements are deleted from the queue.
 Searching an element takes O(N) time.
 Maximum size of a queue must be defined prior.

Applications of linked list in computer science:

1. Implementation of stacks and queues
2. Implementation of graphs: Adjacency list representation of graphs is the
most popular which uses a linked list to store adjacent vertices.
3. Dynamic memory allocation: We use a linked list of free blocks.
4. Maintaining a directory of names
5. Performing arithmetic operations on long integers
6. Manipulation of polynomials by storing constants in the node of the linked list
7. representing sparse matrices

Advantages Of Linked List:

 Dynamic data structure: A linked list is a dynamic arrangement so it can
grow and shrink at runtime by allocating and deallocating memory. So there
is no need to give the initial size of the linked list.
 No memory wastage: In the Linked list, efficient memory utilization can be
achieved since the size of the linked list increase or decrease at run time so
there is no memory wastage and there is no need to pre-allocate the
memory.
 Implementation: Linear data structures like stacks and queues are often
easily implemented using a linked list.
 Insertion and Deletion Operations: Insertion and deletion operations are
quite easier in the linked list. There is no need to shift elements after the
insertion or deletion of an element only the address present in the next
pointer needs to be updated.
 Flexible: This is because the elements in Linked List are not stored in
contiguous memory locations unlike the array.
 Efficient for large data: When working with large datasets linked lists play a
crucial role as it can grow and shrink dynamically.
 Scalability: Contains the ability to add or remove elements at any position.
Disadvantages Of Linked List:
 Memory usage: More memory is required in the linked list as compared to
an array. Because in a linked list, a pointer is also required to store the
address of the next element and it requires extra memory for itself.
 Traversal: In a Linked list traversal is more time-consuming as compared to
an array. Direct access to an element is not possible in a linked list as in an
array by index. For example, for accessing a node at position n, one has to
traverse all the nodes before it.
 Reverse Traversing: In a singly linked list reverse traversing is not possible,
but in the case of a doubly-linked list, it can be possible as it contains a
pointer to the previously connected nodes with each node. For performing
this extra memory is required for the back pointer hence, there is a wastage
of memory.
 Random Access: Random access is not possible in a linked list due to
its dynamic memory allocation.
 Lower efficiency at times: For certain operations, such as searching for an
element or iterating through the list, can be slower in a linked list.
 Complex implementation: The linked list implementation is more complex
when compared to array. It requires a complex programming understanding.
 Difficult to share data: This is because it is not possible to directly access
the memory address of an element in a linked list.
 Not suited for small dataset: Cannot provide any significant benefits on
small dataset compare to that of an array.

Applications of Graph Data Structure

 In Computer science graphs are used to represent the flow of computation.
 Google maps uses graphs for building transportation systems, where
intersection of two(or more) roads are considered to be a vertex and the
road connecting two vertices is considered to be an edge, thus their
navigation system is based on the algorithm to calculate the shortest path
between two vertices.
 In Facebook, users are considered to be the vertices and if they are friends
then there is an edge running between them. Facebook’s Friend suggestion
algorithm uses graph theory. Facebook is an example of undirected graph.
 In World Wide Web, web pages are considered to be the vertices. There is
an edge from a page u to other page v if there is a link of page v on page u.
This is an example of Directed graph. It was the basic idea behind Google
Page Ranking Algorithm.
 In Operating System, we come across the Resource Allocation Graph
where each process and resources are considered to be vertices. Edges are
drawn from resources to the allocated process, or from requesting process
to the requested resource. If this leads to any formation of a cycle then a
deadlock will occur.
 In mapping system we use graph. It is useful to find out which is an
excellent place from the location as well as your nearby location. In GPS we
also use graphs.
 Facebook uses graphs. Using graphs suggests mutual friends. it shows a
list of the f following pages, friends, and contact list.
 Microsoft Excel uses DAG means Directed Acyclic Graphs.
 In the Dijkstra algorithm, we use a graph. we find the smallest path
between two or many nodes.
 On social media sites, we use graphs to track the data of the users. liked
showing preferred post suggestions, recommendations, etc.
 Graphs are used in biochemical applications such as structuring of
protein, DNA etc.

Advantages of Graph:
 By using graphs we can easily find the shortest path, neighbors of the
nodes, and many more.
 Graphs are used to implement algorithms like DFS and BFS.
 It is used to find minimum spanning tree which has many practical
applications.
 It helps in organizing data.
 Because of its non-linear structure, helps in understanding complex
problems and their visualization.
Disadvantages of Graph:
 Graphs use lots of pointers which can be complex to handle.
 It can have large memory complexity.
 If the graph is represented with an adjacency matrix then it does not allow
parallel edges and multiplication of the graph is also difficult.

Applications of Tree Data Structure:

1. Store hierarchical data, like folder structure, organization structure,
XML/HTML data.
2. Binary Search Tree is a tree that allows fast search, insert, delete on a
sorted data. It also allows finding closest item
3. Heap is a tree data structure which is implemented using arrays and used to
implement priority queues.
4. B-Tree and B+ Tree : They are used to implement indexing in databases.
5. Syntax Tree: Scanning, parsing , generation of code and evaluation of
arithmetic expressions in Compiler design.
6. K-D Tree: A space partitioning tree used to organize points in K dimensional
space.
7. Trie : Used to implement dictionaries with prefix lookup.
8. Suffix Tree : For quick pattern searching in a fixed text.
9. Spanning Trees and shortest path trees are used in routers and bridges
respectively in computer networks
10. As a workflow for compositing digital images for visual effects.
11. Decision trees.
12. Organization chart of a large organization.
13. In XML parser.
14. Machine learning algorithm.
15. For indexing in database.
16. IN server like DNS (Domain Name Server)
17. In Computer Graphics.
18. To evaluate an expression.
19. In chess game to store defense moves of player.
20. In java virtual machine.
Advantages of Tree:
 Trees provide hierarchical representation for the data.
 Trees are dynamic in nature so the number of nodes are not limited.
 Insertion and deletion in a tree can be done in moderate time.
Disadvantages of Tree:
 Some trees can only be stored using sequential or chained storage.
Depth-First Search Algorithm

Step 1: Create a stack with the total number of vertices in the

graph as the size.

Step 2: Choose any vertex as the traversal's beginning point.

Push a visit to that vertex and add it to the stack.

Step 3 - Push any non-visited adjacent vertices of a vertex at the

top of the stack to the top of the stack.

Step 4 - Repeat steps 3 and 4 until there are no more vertices to

visit from the vertex at the top of the stack.

Step 5 - If there are no new vertices to visit, go back and pop one
from the stack using backtracking.

Step 6 - Continue using steps 3, 4, and 5 until the stack is empty.

Step 7 - When the stack is entirely unoccupied, create the final

spanning tree by deleting the graph's unused edges.

Application Of Depth-First Search Algorithm

The minor spanning tree is produced by the DFS traversal of an

unweighted graph.

1. Detecting a graph's cycle: A graph has a cycle if and only if a

back edge is visible during DFS. As a result, you may run DFS
on the graph to look for rear edges.
2. Topological Sorting: Topological Sorting is mainly used to
schedule jobs based on the dependencies between them. In
computer science, sorting arises in instruction scheduling,
ordering formula cell evaluation when recomputing formula
values in spreadsheets, logic synthesis, determining the order
of compilation tasks to perform in makefiles, data serialization,
and resolving symbols dependencies linkers.
3. To determine if a graph is bipartite: You can use either BFS or
DFS to color a new vertex opposite its parents when you first
discover it. And check that each other edge does not connect
two vertices of the same color. A connected component's first
vertex can be either red or black.
4. Finding Strongly Connected Components in a Graph: A directed
graph is strongly connected if each vertex in the graph has a
path to every other vertex.
5. Solving mazes and other puzzles with only one solution:By only
including nodes the current path in the visited set, DFS is used
to locate all keys to a maze.
6. Path Finding: The DFS algorithm can be customized to
discover a path between two specified vertices, a and b.

DFS:
Time complexity is again O(|V|), you need to traverse all nodes.
Space complexity - depends on the implementation, a recursive
implementation can have a O(h) space complexity [worst case],
where h is the maximal depth of your tree.
Using an iterative solution with a stack is actually the same as BFS,
just using a stack instead of a queue - so you get both O(|V|) time
and space complexity.
Breadth-First Search Algorithm
Step 1: In the graph, every vertex or node is known. First, initialize
a queue.

Step 2: In the graph, start from source node A and mark it as

visited.
Step 3: Then you can observe B and E, which are unvisited
nearby nodes from A. You have two nodes in this example, but
here choose B, mark it as visited, and enqueue it alphabetically.
Step 4: Node E is the next unvisited neighboring node from A.
You enqueue it after marking it as visited.

Step 5: A now has no unvisited nodes in its immediate vicinity. As

a result, you dequeue and locate A.
Step 6: Node C is an unvisited neighboring node from B. You
enqueue it after marking it as visited.
Step 7: Node D is an unvisited neighboring node from C. You
enqueue it after marking it as visited.

Step 8: If all of D's adjacent nodes have already been visited,

remove D from the queue.
Step 9: Similarly, all nodes near E, B, and C nodes have already
been visited; therefore, you must remove them from the queue.
Step 10: Because the queue is now empty, the bfs traversal has
ended.

Application Of Breadth-First Search Algorithm

The breadth-first search algorithm has the following applications:

 For Unweighted Graphs, You Must Use the Shortest Path and
Minimum Spacing Tree.

The shortest path in an unweighted graph is the one with the

fewest edges. You always reach a vertex from a given source
using the fewest amount of edges when utilizing breadth-first. In
unweighted graphs, any spanning tree is the Minimum Spanning
Tree, and you can identify a spanning tree using either depth or
breadth-first traversal.

 Peer to Peer Network

Breadth-First Search is used to discover all neighbor nodes in

peer-to-peer networks like BitTorrent.

 Crawlers in Search Engine

Crawlers create indexes based on breadth-first. The goal is to

start at the original page and follow all of the links there, then
repeat. Crawlers can also employ Depth First Traversal. However,
the benefit of breadth-first traversal is that the depth or layers of
the created tree can be limited.

 Social Networking Websites

You can use a breadth-first search to identify persons within a
certain distance 'd' from a person in social networks up to 'd's
levels.

 GPS Navigation System

To find all nearby locations, utilize the breadth-first search

method.

 Broadcasting Network

A broadcast packet in a network uses breadth-first search to

reach all nodes.

 Garbage Collection

Cheney's technique uses the breadth-first search for duplicating

garbage collection. Because of the better locality of reference,
breadth-first search is favored over the Depth First Search
algorithm.

 Cycle Detection in Graph

Cycle detection in undirected graphs can be done using either

Breadth-First Search or Depth First Search. BFS can also be
used to find cycles in a directed graph.

 Identifying Routes

To see if there is a path between two vertices, you can use either
Breadth-First or Depth First Traversal.
 Finding All Nodes Within One Connected Component

To locate all nodes reachable from a particular node, you can use
either Breadth-First or Depth First Traversal.

BFS:
Time complexity is O(|V|), where |V| is the number of nodes. You
need to traverse all nodes.
Space complexity is O(|V|) as well - since at worst case you need
to hold all vertices in the queue.