Data structures

Unit -1: Introduction to data structures: Types of data structures-Primitive data structures,
Nonprimitive data structures – linear data structures, nonlinear data structures, real world
applications of data structures, Abstract data types-ADT for stack, queue, linked list,
Performance analysis of algorithms-time complexity, space complexity.

Q)DIFFERENCE BETWEEN ABSTRACT DATA YPES, DATA TYPES AND

DATA STRUCTURES

 To avoid the confusion between abstract data types, data types, and
data structures, it is relevant to understand the relationship between
the three
 An abstract data type is the specification of the data type
which specifies the logical and mathematical model of the data
type.
 A data type is the implementation of an abstract data type:
 Data structure refers to the collection of computer variables
that areconnected in some specific manner.

Thus, there seems to be an open relationship between the three, that is, a
data type has its root in the abstract data type and a data structure
comprises a set of computer variables of same or different data types.

Q)What is Data Structure? What are the different types ofData

Structures?

Data means collection of raw facts like 12, ‘a’, 34.45 etc., any processed
data is referred as information. Any user may require data to be processed.
In order to manage data in a most efficient manner one would require better
approaches and such approaches might be referred as data structures.

A data structure is a mathematical & logical representation of data in order

to organize the data in a most efficient manner.

Data structures are basically of following types:

 Linear Data structures

 Non linear Data structures
(OR)
 Static Data structures
 Dynamic Data structures
(OR)
 Homogeneous Data Structures
M.VIJITHA DEPT.COMPUTER SCIENCE Page 1
  Heterogeneous Data Structures
Linear Data structures: A linear data structure is a means where data may
be organized in sequential manner or in linear order.

Example: “Arrays, Stacks, Queues and linked lists” are the examplesfor
linear data structures.

Non-linear Data structures: A non-linear data structure is a means where

data may be organized in quite a different manner. It doesn’t follow any
linear form.

Example: “Trees & Graphs” are the examples for the non-linear data
structures.

Static Data structures: A static data structure is fixed in its size as it is

specified during the compile time.

Example: “Arrays, Stacks & Queues” are the examples for static data
structures.

Dynamic Data structures: A dynamic data structure is created during the

runtime. It provides better flexibility to the user as it allows the user to
increase or decrease the size during the execution of the program. Hence we
say that dynamic data structures may vary during the runtime. Moreover,
dynamic data structures allow the user to add, delete and rearrange data
items at runtime.

Example: Linked lists, Trees & Graphs

Homogeneous Data Structures: It is a data structure where items of

similar kind or same type of items are placed/arranged.

Example: Arrays, Stacks, Queues are the examples of this kind.

Heterogeneous Data Structure: It is a data structure where items of

different can be placed and operated. Linked Lists, Trees & Graphs may be
the examples of Heterogeneous data structures

M.VIJITHA DEPT.COMPUTER SCIENCE Page 2

Q)What is primitive and non-primitive data structures?

Primitive Data Structures:

Primitive Data Structures are the basic data structures that directly operate
upon the machine instructions. They have different representations on different
computers. They are:

 Integers,
 Floating point numbers,
 Character constants,
 String constants
 Pointers
Non-primitive Data Structures:

Non-primitive data structures are more complicated data structures and are
derived from primitive data structures.

They emphasize on grouping same or different data items with relationship

between each data item.

These are:

 Arrays
 Lists
 Files
Q)What is Linear and Non-Linear data structures?

Data structure is a way to organize a data in computer so that it can be

used efficiently.

M.VIJITHA DEPT.COMPUTER SCIENCE Page 3

In computer science, Data Structure is classified into two categories :

 Linear Data Structure

 Non Linear Data Structure

Linear Data Structures: The data structure where data items are organized
sequentially or linearly where data elements attached one after another is
called linear data structure. Data elements in a liner data structure are
traversed one after the other and only one element can be directly reached
while traversing. All the data items in linear data structure can be traversed
in single run.

These kind of data structures are very easy to implement because memory
of computer is also organized in linear fashion.

Examples of linear data structures are:

 Arrays,
 Stack,
 Queue
 Linked List.
 An arrays is a collection of data items having the same data types.
 A Stack is a LIFO (Last In First Out) data structure where element
that added last will be deleted first. All operations on stack are
performed from on end called TOP. A Queue is a FIFO (First In First
Out) data structure where element that added first will be deleted
first.
 In queue, insertion is performed from one end called REAR and
deletion is performed from another end called FRONT.
 A Linked list is a collection of nodes, where each node is made up of a
data element and a reference to the next node in the sequence.

Non Linear Data Structures: The data structure where data items are not
organized sequentially is called non linear data structure. In other words, A

M.VIJITHA DEPT.COMPUTER SCIENCE Page 4

data elements of the non linear data structure could be connected to more
than one elements to reflect a special relationship among them. All the data
elements in non linear data structure can not be traversed in single run.

Examples of non linear data structures are:

 Trees
 Graphs
 A tree is collection of nodes where these nodes are arranged
hierarchically and form a parent child relationships.
 A Graph is a collection of a finite number of vertices and an edges that
connect these vertices. Edges represent relationships among vertices
that stores data elements.
Q)Difference Between Linear and Non Linear Data Structure:

Linear Data Structure Non-Linear Data Structure

Every item is related to its previous Every item is attached with many
and next item. other items.

Data is arranged in linear sequence. Data is not arranged in sequence.

Data items can be traversed in a Data can not be traversed in a

single run. single run.

Examples: Array, Stack, Queue,

Examples: Tree, Graph.
Linked List.

Implementation is Easy. Implementation is Difficult.

Q)Application of Data Structure:

A data structure is a particular way of organizing data in a computer so that it can be
used effectively. The real-life applications of all the data structures are as below.
Application of Arrays:
Arrays are the simplest data structures that store items of the same data type. A basic
application of Arrays can be storing data in tabular format. For example, if we wish to
store the contacts on our phone, then the software will simply place all our contacts in
an array.
Some other applications of the arrays are:
 Arrangement of the leader board of a game can be done simply through arrays
to store the score and arrange them in descending order to clearly make out the
rank of each player in the game.
 A simple question Paper is an array of numbered questions with each of them
assigned some marks.
 2D arrays, commonly known as, matrices, are used in image processing.
M.VIJITHA DEPT.COMPUTER SCIENCE Page 5
  It is also used in speech processing, in which each speech signal is an array.
 Your viewing screen is also a multidimensional array of pixels.
 Book titles in a Library Management Systems.
 Online ticket booking.
 Contacts on a cell phone.
 For CPU scheduling in computer.
 To store the possible moves of chess on a chessboard.
 To store images of a specific size on an android or laptop.

Application of Strings:
 Spam email detection.
 Plagiarism detection.
 Search engine.
 Digital forensic and information retrieval system
 Spell checkers.
 In the database to check valid information of the user
Application of Matrix:
Matrix is an ordered collection of columns and rows of elements. It is necessary to
enclose the elements of a matrix within the brackets.
Some applications of a matrix are:
 In geology, matrices are used for making seismic surveys.
 Used for plotting graphs, and statistics and also to do scientific studies and
research in almost different fields.
 Matrices are also used in representing real-world data like the population of
people, infant mortality rate, etc.
 They are the best representation methods for plotting surveys.
 For refraction and reflection in science optics.
 Electronic circuit and quantum physics.
 Media player.
 Mailing list.
 Symboltablcreation.

Application of Linked Lists:

A linked list is a sequence data structure, which connects elements, called nodes,
through links.
Some other applications of the linked list are:
 Images are linked with each other. So, an image viewer software uses a linked
list to view the previous and the next images using the previous and next
buttons.
 Web pages can be accessed using the previous and the next URL links which are
linked using a linked list.
 The music players also use the same technique to switch between music.
 To keep the track of turns in a multi-player game, a circular linked list is used.
 MS-Paint drawings and shapes are connected via a linked list on canvas.
 Social media content “feeds”.
 Used for symbol table management in a designing compiler

M.VIJITHA DEPT.COMPUTER SCIENCE Page 6

  Used in switching between applications and programs (Alt + Tab) in the
Operating system (implemented using Circular Linked List)
 Train coaches are connected to one another in a doubly-linked list fashion.
 It can be used to implement Stacks, Queues, Graphs, and Trees.
 To perform undo operation.
 Back button.[LIFO]
 Syntax in the coding editor.
 History of visited pages.
Application of Stack:
A stack is a data structure that uses LIFO order.
Some Applications of a stack are:
 Converting infix to postfix expressions.
 Undo/Redo button/operation in word processors.
 Syntaxes in languages are parsed using stacks.
 It is used in many virtual machines like JVM.
 Forward-backward surfing in the browser.
 History of visited websites.
 Message logs and all messages you get are arranged in a stack.
 Call logs, E-mails, Google photos’ any gallery, YouTube downloads, Notifications
( latest appears first ).
 Scratch card’s earned after Google pay transaction.
 Wearing/Removing Bangles, Pile of Dinner Plates, Stacked chairs.
 Changing wearables on a cold evening, first in, comes out at last.
 Last Hired, First Fired - which is typically utilized when a company reduces its
workforce in an economic recession.
 Loading bullets into the magazine of a gun. The last one to go in is fired first.
Bam!
 Java Virtual Machine.
 Recursion.
 Used in IDEs to check for proper parentheses matching
 Media playlist. T o play previous and next song
Application of Queue:
A queue is a data structure that uses FIFO order.
Some applications of a queue are:
 Operating System uses queues for job scheduling.
 To handle congestion in the networking queue can be used.
 Data packets in communication are arranged in queue format.
 Sending an e-mail, it will be queued.
 Server while responding to request
 Uploading and downloading photos, first kept for uploading/downloading will
be completed first (Not if there is threading)
 Most internet requests and processes use queue.
 While switching multiple applications, windows use circular queue.
 In Escalators, Printer spooler, Car washes queue.
 A circular queue is used to maintain the playing sequence of multiple players in
a game.
 A queue can be implemented in - Linked List-based Queue, Array-based Queue,
Stack-based Queue.

M.VIJITHA DEPT.COMPUTER SCIENCE Page 7

  Uploading and downloading photos, first kept for uploading/downloading will
be completed first (Not if there is threading).
 Handle website traffic
 CPU scheduling
Application of Priority Queue:
 Process scheduling in the kernel.
 Priority queues are used in file-downloading operations in a browser
 Vehicle at the toll center.
Application of Graph:
Graph is a data structure where data is stored in a collection of interconnected
vertices (nodes) and edges (paths).
Some applications of a graph are:
 Facebook’s Graph API uses the structure of Graphs.
 Google’s Knowledge Graph also has to do something with Graph.
 Dijkstra algorithm or the shortest path first algorithm also uses graph structure
to find the smallest path between the nodes of the graph.
 The GPS navigation system also uses shortest path APIs.
 Networking components have a huge application for graph
 Facebook, Instagram, and all social media networking sites every user is Node
 Data organization
 React’s virtual DOM uses graph data structures.
 MS Excel uses DAG (Directed Acyclic Graphs).
 Path Optimization Algorithms, BFS, DFS.
 Recommendation Engines.
 Scientific Computations, Flight Networks, Page ranking.
 Google map to find nearest location.
 Facebook to suggest mutual friends
Application of Tree:
Trees are hierarchical structures having a single root node.
Some applications of the trees are:
 XML Parser uses tree algorithms.
 The decision-based algorithm is used in machine learning which works upon
the algorithm of the tree.
 Databases also use tree data structures for indexing.
 Domain Name Server(DNS) also uses tree structures.
 File explorer/my computer of mobile/any computer
 BST used in computer Graphics
 Posting questions on websites like Quora, the comments are a child of
questions.
 Parsers(XML parser).
 Code Compression(zip).
 DOM in Html.
 Evaluate an expression (i.e., parse).
 Integral to compilers/automata theory.
 To store the possible moves in a chess game.
 To store the genealogy information of biological species.
 Used by JVM (Java Virtual Machine) to store Java objects.
Application of Binary Search Tree:
 D Game Engine.

M.VIJITHA DEPT.COMPUTER SCIENCE Page 8

  Computer Graphics Rendering.
 Routing table.
Q)Abstract Data Types
ADT is different in-built data types. Data types such as int, float, double, long, etc. are
considered to be in-built data types and we can perform basic operations with them
such as addition, subtraction, division, multiplication, etc. Now there might be a
situation when we need operations for our user-defined data type which have to be
defined. These operations can be defined only as and when we require them. So, in
order to simplify the process of solving problems, we can create data structures along
with their operations, and such data structures that are not in-built are known as
Abstract Data Type (ADT).
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.

The user of data type does not need to know how that data type is implemented, for
example, we have been using Primitive values like int, float, char data types only with
the knowledge that these data type can operate and be performed on without any idea
of how they are implemented.
So a user only needs to know what a data type can do, but not how it will be
implemented. Think of ADT as a black box which hides the inner structure and design of
the data type. Now we’ll define three ADTs namely List ADT, Stack ADT, Queue ADT.
1. List ADT

Vies of list

M.VIJITHA DEPT.COMPUTER SCIENCE Page 9

 The data is generally stored in key sequence in a list which has a head structure
consisting of count, pointers and address of compare function needed to compare the
data in the list.
 The data node contains the pointer to a data structure and a self-referential
pointer which points to the next node in the list.
 The List ADT Functions is given below:
 get() – Return an element from the list at any given position.
 insert() – Insert an element at any position of 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 by 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.
2. Stack ADT

View of stack

 In Stack ADT Implementation instead of data being stored in each node, the
pointer to data is stored.
 The program allocates memory for the data and address is passed to the stack
ADT.
 The head node and the data nodes are encapsulated in the ADT. The calling
function can only see the pointer to the stack.
 The stack head structure also contains a pointer to top and count of number of
entries currently in stack.
 push() – Insert an element at one end of the stack called 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.
3. Queue ADT

M.VIJITHA DEPT.COMPUTER SCIENCE Page 10

View of Queue

 The queue abstract data type (ADT) follows the basic design of the stack abstract
data type.
 Each node contains a void pointer to the data and the link pointer to the next
element in the queue. The program’s responsibility is to allocate memory for
storing the data.
 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.
 isFull() – Return true if the queue is full, otherwise return false.
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:
1. Abstraction: The user does not need to know the implementation of the data
structure only essentials are provided.
2. Better Conceptualization: ADT gives us a better conceptualization of the real
world.
3. Robust: The program is robust and has the ability to catch errors.
4. 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.
5. 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.
6. Data Structure Independence: ADTs can be implemented using different data
structures, such as arrays or linked lists, without affecting the functionality of the
ADT.
7. 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.
8. Modularity: ADTs can be combined with other ADTs to form larger, more
complex data structures. This allows for greater flexibility and modularity in
programming.

M.VIJITHA DEPT.COMPUTER SCIENCE Page 11

 9. Overall, ADTs provide a powerful tool for organizing and manipulating data in a
structured and efficient manner.
10. Abstract data types (ADTs) have several advantages and disadvantages that
should be considered when deciding to use them in software development.

Main advantages and disadvantages of using ADTs:

Advantages:
 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:
 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.

Q)Algorithm Analysis

Analysis of efficiency of an algorithm can be performed at two different stages, before

implementation and after implementation, as

A priori analysis − This is de ined as theoretical analysis of an algorithm. Ef iciency of

algorithm is measured by assuming that all other factors e.g. speed of processor, are
constant and have no effect on implementation.

A posterior analysis − This is defined as empirical analysis of an algorithm. The chosen

algorithm is implemented using programming language. Next the chosen algorithm is
executed on target computer machine. In this analysis, actual statistics like running time
and space needed are collected.

M.VIJITHA DEPT.COMPUTER SCIENCE Page 12

Algorithm analysis is dealt with the execution or running time of various operations
involved. Running time of an operation can be defined as number of computer
instructions executed per operation.

Algorithm Complexity

Suppose X is treated as an algorithm and N is treated as the size of input data, the time
and space implemented by the Algorithm X are the two main factors which determine
the efficiency of X.

Time Factor − The time is calculated or measured by counting the number of key
operations such as comparisons in sorting algorithm.

Space Factor − The space is calculated or measured by counting the maximum memory
space required by the algorithm.

The complexity of an algorithm f(N) provides the running time and / or storage space
needed by the algorithm with respect of N as the size of input data.

Space Complexity

Space complexity of an algorithm represents the amount of memory space needed the
algorithm in its life cycle.

Space needed by an algorithm is equal to the sum of the following two components

A fixed part that is a space required to store certain data and variables (i.e. simple
variables and constants, program size etc.), that are not dependent of the size of the
problem.

A variable part is a space required by variables, whose size is totally dependent on the
size of the problem. For example, recursion stack space, dynamic memory allocation etc.

Space complexity S(p) of any algorithm p is S(p) = A + Sp(I) Where A is treated as the
fixed part and S(I) is treated as the variable part of the algorithm which depends on
instance characteristic I. Following is a simple example that tries to explain the concept

Algorithm
SUM(P, Q)
Step 1 - START
Step 2 - R ← P + Q + 10

M.VIJITHA DEPT.COMPUTER SCIENCE Page 13

Step 3 - Stop

Here we have three variables P, Q and R and one constant. Hence S(p) = 1+3. Now space
is dependent on data types of given constant types and variables and it will be
multiplied accordingly.

Time Complexity

Time Complexity of an algorithm is the representation of the amount of time required

by the algorithm to execute to completion. Time requirements can be denoted or
defined as a numerical function t(N), where t(N) can be measured as the number of
steps, provided each step takes constant time.

For example, in case of addition of two n-bit integers, N steps are taken. Consequently,
the total computational time is t(N) = c*n, where c is the time consumed for addition of
two bits. Here, we observe that t(N) grows linearly as input size increases.

M.VIJITHA DEPT.COMPUTER SCIENCE Page 14