Shri G.S.

Institute of Technology & Science

(An Autonomous Institute, Established in 1952)

LABORATORY ASSIGNMENT
CT10212: DATA STRUCTURES

2024-2026
MCA I YEAR

Semester – I

Department of Information Technology

SUBMITTED TO: SUBMITTED BY:

Mr. Deepesh Agrawal Shruti Gupta
Ms. Parul Saxena
INDEX

S.No Questions Page No. Date Remarks

1. What is Data Structures? 2
Classification of Data Structures with
2. 3-7
Explanation.
Comparison between Linear and Non
3. 8
Linear Data Structures.
Difference between data and
4. 9
information.
What is Abstract Data Types? Explain
5. 10-11
ADT on Stack, Queue, and Linked List.

1
Question No. 1

What is Data Structure?

A data structure is a particular way of organizing data in a computer so that it can be used
effectively. The idea is to reduce the space and time complexities of different tasks.

In computer science and computer programming, a data structure might be selected or designed
to store data for the purpose of using it with various algorithms -- commonly referred to as data
structures and algorithms (DSA). In some cases, the algorithm's basic operations are tightly
coupled to the data structure's design. Each data structure contains information about the data
values; relationships between the data; and, in some cases, functions that can be applied to the
data.

Advantages of Data Structures:

The use of data structures provides several advantages, including

 Efficiency: Data structures allow for efficient storage and retrieval of data, which is
important in applications where performance is critical.

 Flexibility: Data structures provide a flexible way to organize and store data, allowing
for easy modification and manipulation.

 Reusability: Data structures can be used in multiple programs and applications, reducing
the need for redundant code.

 Maintainability: Well-designed data structures can make programs easier to understand,

modify, and maintain over time.

 Abstraction: The data structure specified by an ADT also provides the level of
abstraction. The client cannot see the internal working of the data structure, so it does not
have to worry about the implementation part. The client can only see the interface.

2
Question No. 2

Classification of Data Structures with Explanation.

A Data Structure delivers a structured set of variables related to each other in various ways. It
forms the basis of a programming tool that signifies the relationship between the data elements
and allows programmers to process the data efficiently.

We can classify Data Structures into two categories:

1. Primitive Data Structure

2. Non-Primitive Data Structure

The following figure shows the different classifications of Data Structures.

1. Primitive Data Structures:

Primitive Data Structures are the data structures consisting of the numbers and the characters that
come in-built into programs.

These data structures can be manipulated or operated directly by machine-level instructions the
Primitive Data Structures.

These data types are also called Simple data types, as they contain characters that can't be
divided further

3
2. Non-Primitive Data Structures:
Non-Primitive Data Structures are those data structures derived from Primitive Data Structures.

These data structures can't be manipulated or operated directly by machine-level instructions.

The focus of these data structures is on forming a set of data elements that is either homogeneous
(same data type) or heterogeneous (different data types).

Based on the structure and arrangement of data, we can divide these data structures into two sub-
categories -

I. Linear Data Structures

II. Non-Linear Data Structures

I. Linear Data Structures:

A data structure that preserves a linear connection among its data elements is known as a Linear
Data Structure. The arrangement of the data is done linearly, where each element consists of the
successors and predecessors except the first and the last data element. However, it is not
necessarily true in the case of memory, as the arrangement may not be sequential.

Based on memory allocation, the Linear Data Structures are further classified into two types:

a. Static Data Structures:

The data structures having a fixed size are known as Static Data Structures. The memory for
these data structures is allocated at the compiler time, and their size cannot be changed by the
user after being compiled; however, the data stored in them can be altered.
The Array is the best example of the Static Data Structure as they have a fixed size, and its data
can be modified later.

b. Dynamic Data Structures:

The data structures having a dynamic size are known as Dynamic Data Structures. The memory
of these data structures is allocated at the run time, and their size varies during the run time of the
code. Moreover, the user can change the size as well as the data elements stored in these data
structures at the run time of the code.
Linked Lists, Stacks, and Queues are common examples of dynamic data structures.

4
Types of Linear Data Structures:
The following is the list of Linear Data Structures that we generally use:

1. Arrays

An Array is a data structure used to collect multiple data elements of the same data type into one
variable. Instead of storing multiple values of the same data types in separate variable names, we
could store all of them together into one variable.

Example: int arr[6] = {2, 6, 11, 7, 18, 4};

2. Linked Lists:
A Linked List is another example of a linear data structure used to store a collection of data
elements dynamically. Data elements in this data structure are represented by the Nodes,
connected using links or pointers. Each node contains two fields, the information field consists of
the actual data, and the pointer field consists of the address of the subsequent nodes in the list.
The pointer of the last node of the linked list consists of a null pointer, as it points to nothing.
Unlike the Arrays, the user can dynamically adjust the size of a Linked List as per the
requirements.

Types of linked list:

a) Singly linked list.

b) Doubly linked list.
c) Circular linked list.

3. Stacks:
A Stack is a Linear Data Structure that follows the LIFO (Last In, First Out) principle that allows
operations like insertion and deletion from one end of the Stack, i.e., Top. Stacks can be
implemented with the help of contiguous memory, an Array, and non-contiguous memory, a
Linked List. Real-life examples of Stacks are piles of books, a deck of cards, piles of money, and
many more.

5
The primary operations in the Stack are as follows:
Push: Operation to insert a new element in the Stack is termed as Push Operation.
Pop: Operation to remove or delete elements from the Stack is termed as Pop Operation.

4. Queues
A Queue is a linear data structure similar to a Stack with some limitations on the insertion and
deletion of the elements. The insertion of an element in a Queue is done at one end, and the
removal is done at another or opposite end. Thus, we can conclude that the Queue data structure
follows FIFO (First In, First Out) principle to manipulate the data elements. Implementation of
Queues can be done using Arrays, Linked Lists, or Stacks. Some real-life examples of Queues
are a line at the ticket counter, an escalator, a car wash, and many more.

Operations performed on queue:

a) Enqueue: It means insertion of element in queue.
b) Dequeue: It means deletion of element from queue.

II. Non-Linear Data Structures

Non-Linear Data Structures are data structures where the data elements are not arranged in
sequential order. Here, the insertion and removal of data are not feasible in a linear manner.
There exists a hierarchical relationship between the individual data items.

Types of Non-Linear Data Structures

The following is the list of Non-Linear Data Structures that we generally use:

1. Trees
A Tree is a Non-Linear Data Structure and a hierarchy containing a collection of nodes such that
each node of the tree stores a value and a list of references to other nodes (the "children").

6
The Tree data structure is a specialized method to arrange and collect data in the computer to be
utilized more effectively. It contains a central node, structural nodes, and sub-nodes connected
via edges. We can also say that the tree data structure consists of roots, branches, and leaves
connected.

2. Graph
A Graph is another example of a Non-Linear Data Structure comprising a finite number of nodes
or vertices and the edges connecting them. The Graphs are utilized to address problems of the
real world in which it denotes the problem area as a network such as social networks, circuit
networks, and telephone networks. For instance, the nodes or vertices of a Graph can represent a
single user in a telephone network, while the edges represent the link between them via
telephone.

The Graph data structure, G is considered a mathematical structure comprised of a set of vertices,
V and a set of edges, E as shown below:
G = (V, E)

3. Hash Table
A hash table is a structure that stores key-value pairs, allowing for fast data retrieval using a key.
It works as the key is passed through a hash function which converts it to an index that
corresponds to the location of the value in memory.

Features:
 Fast access and insertion, collision handling through chaining or open
addressing.
 A dictionary where you can quickly look up the definition of a word is an
example of hash function
 It is suitable for applications requiring fast lookups, like caching or
implementing associative arrays.

7
Question No. 3

Comparison between Linear and Non-Linear Data Structures.

S. No Linear Data Structure Non-linear Data Structure

1 In a linear data structure, data elements are In a non-linear data structure, data elements are
arranged in a linear order where each and attached in hierarchically manner.
every element is attached to its previous
and next adjacent

2 In linear data structure, single level is Whereas in non-linear data structure, multiple
involved. levels are involved.

3 Its implementation is easy in comparison to While its implementation is complex in

non-linear data structure. comparison to linear data structure.

4 In linear data structure, data elements can While in non-linear data structure, data elements
be traversed in a single run only. can’t be traversed in a single run only.

5 In a linear data structure, memory is not While in a non-linear data structure, memory is
utilized in an efficient way utilized in an efficient way.

6 Performance is usually good for simple Performance can vary depending on the structure
operations like adding or removing at the and the operation, but can be optimized for
ends, but slower for operations like specific operations.
searching or removing elements in the
middle.

7 Its examples are: array, stack, queue, linked While its examples are: trees and graphs.
list, etc.

8 Applications of linear data structures are Applications of non-linear data structures are in
mainly in application software Artificial Intelligence and image processing.
development.

8
Question No. 4

Difference between data and information

Data and Information

Usually, the terms “data” and “information” are used interchangeably. However, there is a
subtle difference between the two.

In a nutshell, data can be a number, symbol, character, word, codes, graphs, etc. On the other
hand, information is data put into context. Information is utilized by humans in some significant
way (such as to make decisions, forecasts etc.).

A basic example of information would be a computer. A computer uses programming scripts,

formulas, or software applications to turn data into information.

Data Information
Data is unorganized and unrefined facts Information comprises processed, organized
data presented in a meaningful context

Data is an individual unit that contains raw Information is a group of data that collectively
materials which do not carry any specific carries a logical meaning
meaning

Data doesn’t depend on information Information depends on data.

Raw data alone is insufficient for decision Information is sufficient for decision making
making

An example of data is a student’s test score The average score of a class is the information
derived from the given data.

9
Question No. 5

What is Abstract Data Type? Explain ADT on Stack, Queue, and Linked List .

Abstract Data Type:

An Abstract Data Type in data structures is a data type whose behavior is defined with the help
of some attributes and some functions. Generally, we write these attributes and functions inside a
class or a structure to use an object of the class to use that particular abstract data type.

In other words, an ADT provides only the interface to which the data structure must adhere. The
interface does not give specific details about what should be implemented or in what
programming language.

In every programming language, ADTs are implemented using different methods and logic. In C
that ADTs are implemented mostly using structure. Whereas in C++ or JAVA, they’re
implemented using class. However, operations are common in all languages.

1. Stack ADT
A stack is a special type of list that allows insertions and removals to be performed only to the
front of the list. Therefore, it enforces Last-in–First out (LIFO) behavior on the list. Think of a
stack of dishes at the salad bar. When you put a dish on the stack, it goes onto the top of the stack.
When you remove a dish from the stack, it comes from the top of the stack.

The stack operations are conventionally called push, for insert, and pop, for remove, respectively.
Thus, the stack ADT stores a list of data and supports the following operations:

1. Push: Adds an element to the top of the stack.

Example: push(10) → `[10]` (added 10 on top)
push(20) → `[20, 10]` (added 20 on top)

2. Pop: Removes the top element from the stack and returns it.
Example: pop() → returns 20, stack is now [10]
3. Peek/Top: Looks at the top element of the stack without removing it.
Example: peek() → returns 10 (top element)
4. isEmpty: Checks if the stack has no elements.
Example: isEmpty() → returns false (because the stack still has elements)

10
5. isFull: For stacks with a fixed capacity, this checks if the stack has reached its
maximum size.
Example: isEmpty() → returns false (because the stack is not full)

2. Queue ADT
A queue is a linear data structure where elements are stored in the FIFO (First In First Out)
principle where the first element inserted would be the first element to be accessed. A queue is
an Abstract Data Type (ADT) similar to stack, the thing that makes queue different from stack is
that a queue is open at both its ends. The data is inserted into the queue through one end and
deleted from it using the other end. Queue is very frequently used in most programming
languages.

Operations of a Queue:

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

Example: enqueue(5) → [5] (5 is added to the end of the queue)

enqueue(10) → [5, 10] (10 is added after 5)
enqueue(15) → [5, 10, 15] (15 is added after 10)

2. Dequeue: Removes the element from the front of the queue and returns it.
Example: dequeue() → returns 5, queue becomes [10, 15]

3. Front/Peek: Returns the element at the front of the queue without removing it.
Example: peek() → returns 10 (the current front element), queue remains [10, 15]

4. isEmpty: Checks if the queue has no elements.

Example: peek() → returns 10 (the current front element), queue remains [10, 15]

5. isFull: For queues with a fixed capacity, this checks if the queue has reached its maximum
size.

11