Introduction to Data Structures

Bachelor of Computer Applications (BCA)

❖ Unit 1: Introduction \

1.1 Data Representation of data: In data structures and algorithms (DSA), data representation refers to
the various ways in which data can be organized and stored in a computer's memory. The choice of data
representation can significantly impact the efficiency of algorithms and operations performed on the data.
Here are some common data representations used in DSA:

a. Arrays: Arrays are a contiguous block of memory that store elements of the same data type.
Elements in an array are accessed using their indices. Arrays offer constant-time access to
elements but may have limitations on insertion and deletion operations, especially in the middle
of the array.
Arrays are one of the most fundamental data structures in computer science and are
widely used for storing collections of elements of the same data type. They provide a simple and efficient
way to organize data in memory. Here's a more detailed explanation of arrays:

• Contiguous Memory Allocation: Arrays allocate memory in a contiguous block, meaning that all
elements are stored in adjacent memory locations. This allows for efficient access to array
elements using their indices. Because of this contiguous allocation, arrays provide constant-time
access to elements, meaning that accessing any element takes the same amount of time regardless
of its position in the array.

• Indexing: Array elements are accessed using their indices, which are integer values that indicate
the position of the element in the array. In most programming languages, array indices start from
0, so the first element of the array is accessed using index 0, the second element with index 1, and
so on.

• Homogeneous Elements: Arrays store elements of the same data type. This means that all
elements in an array must have the same size and data type. For example, an array of integers will
only store integers, and an array of characters will only store charac ters.

• Fixed Size: In many programming languages, the size of an array is fixed at the time of
declaration. Once an array is created with a certain size, it cannot be resized dynamically. This
fixed size can be a limitation in some cases, especially if the size of the data is not known in
advance or if the size needs to change frequently.
 • Insertion and Deletion: While accessing elements in an array is efficient, inserting or deleting
elements, especially in the middle of the array, can be less efficient. This is because inserting or
deleting an element may require shifting all subsequent elements to accommodate the change. As
a result, insertion and deletion operations in arrays may have a time complexity of O(n), where n
is the number of elements in the array.

• Despite these limitations, arrays are still widely used in various applications and algorithms due
to their simplicity and efficiency in accessing elements. They are particularly useful when the size
of the data is known in advance and when random access to elements is required. Additionally,
many more complex data structures, such as lists and matrices, are implemented using arrays as
their underlying storage mechanism.

2. Linked Lists: Linked lists consist of nodes where each node contains a data element and a reference
(pointer) to the next node in the sequence. Linked lists offer efficient insertion and deletion operations at
the cost of linear-time traversal.

3. Trees: Trees are hierarchical data structures consisting of nodes connected by edges. A tree has a root
node, and each node can have zero or more child nodes. Trees are used for representing hierarchical
relationships and searching efficiently. Common types of trees include binary trees, AVL trees, red-black
trees, and B-trees.

4. Graphs: Graphs consist of vertices (nodes) connected by edges. Graphs can be directed or undirected,
and they are used to represent various types of relationships between objects. Graphs can be represented
using adjacency matrices or adjacency lists.

5. Hash Tables: Hash tables use a hash function to map keys to values, allowing for efficient retrieval,
insertion, and deletion of key-value pairs. Hash tables offer constant-time average-case performance for
these operations but may degrade to linear time in the worst-case scenario.

6. Stacks and Queues: Stacks and queues are abstract data types that can be implemented using arrays,
linked lists, or other data structures. Stacks follow the Last In, First Out (LIFO) principle, while queues
follow the First In, First Out (FIFO) principle.

7. Heaps: Heaps are binary trees that satisfy the heap property, which determines the order of elements.
Heaps are commonly used for implementing priority queues, where the highest (or lowest) priority
element can be efficiently retrieved.
 3

1.2 Data types:

1. Primitive Data Types:

- Integer: Integers represent whole numbers without any fractional part. They can be positive, negative,
or zero. Depending on the programming language, integers can have different ranges and sizes (e.g., 32 -
bit, 64-bit).

- Float/Double: Floating-point numbers represent numbers with a fractional part. They are used to store
real numbers like decimal values. Float typically refers to single-precision floating-point numbers, while
double refers to double-precision floating-point numbers, offering higher precision.

- Character: Characters represent individual symbols, letters, or digits from a character set (such as
ASCII or Unicode). They are typically enclosed within single quotes (e.g., 'A', '5', '@').

- Boolean: Boolean data type represents logical values, typically denoted as true or false. Booleans are
used in logical operations and control structures for decision -making.

2. Derived Data Types:

- Arrays: Arrays are collections of elements of the same data type stored in contiguous memory
locations. They provide indexed access to elements, allowing for efficient storage and retrieval of data.
Arrays have a fixed size determined at compile time.

- Structures/Records: Structures (or records) are user-defined data types that allow grouping together
different data types under a single name. Each element within a structure is called a member or field.
Structures are useful for organizing related data into a single unit.

- Pointers: Pointers are variables that store memory addresses of other variables. They allow dynamic
memory allocation and manipulation of data indirectly. Pointers are often used for implementing data
structures and for efficient memory management.

3. User-defined Data Types:

- Enumerations: Enumerations are user-defined data types consisting of a set of named values, also
known as enumerators. Enumerations provide a way to define a list of symbolic constants with
meaningful names.
- Classes/Objects: Classes and objects are fundamental concepts in object-oriented programming
(OOP). A class is a blueprint for creating objects, which are instances of the class. Classes define data
members (attributes) and member functions (methods) to operate on that data. Objects encapsulate data
and behavior into a single unit.
4. Abstract Data Types (ADTs):
- Abstract Data Types (ADTs) are high-level models for data structures, focusing on the behavior and
operations rather than implementation details. Examples include:
- Stacks: A stack is a data structure that follows the Last In, First Out (LIFO) principle, where
elements are inserted and removed from the same end (top).
- Queues: A queue is a data structure that follows the First In, First Out (FIFO) principle, where
elements are inserted at the rear and removed from the front.
- Linked Lists, Trees, and Graphs: These are complex data structures that organize data in different
hierarchical or non-linear ways, providing efficient operations for various applications.

Abstract Data Types (ADTs) and Data Structures are fundamental concepts in computer science,
particularly in the context of organizing and manipulating data efficiently.

1.3 Abstract Data Types (ADTs):

- Definition: ADTs are high-level models that define a set of operations on data without specifying the
underlying implementation details. They provide a logical description of how data can be manipulated
and what operations can be performed on it.
- Characteristics:
- Encapsulation: ADTs encapsulate data and operations into a single unit, hiding the internal details of
the implementation.
- Interface: ADTs define a set of operations (or methods) that can be performed on the data, known as
the interface. Users interact with ADTs through this interface without knowing the internal workings.
- Modularity: ADTs promote modularity by separating the concerns of data representation and
operations. This allows for easier maintenance and code reuse.
- Examples:
- Stack: A stack is an ADT that follows the Last In, First Out (LIFO) principle. It supports operations
like push (to add an element), pop (to remove the top element), and peek (to view the top element without
removing it).
- Queue: A queue is an ADT that follows the First In, First Out (FIFO) principle. It supports operations
like enqueue (to add an element to the rear), dequeue (to remove an element from the front), and peek (to
view the front element without removing it).
- Priority Queue: A priority queue is an ADT that maintains a set of elements with associated
priorities. It supports operations like insert (to add an element with a priority), deleteMin (to remove the
element with the minimum priority), and findMin (to retrieve the element with the minimum priority).
- Usage: ADTs provide an abstraction layer that allows programmers to focus on the functionality of
data structures without worrying about their implementation details. They are used to design and
implement various data structures and algorithms.
 5

1.3.1 Data Structures:

- Definition: Data structures are concrete implementations of ADTs that specify how data is organized,
stored, and accessed in memory. They define the physical representation of data and the algorithms for
performing operations on that data.
- Characteristics:
- Storage: Data structures define how data is stored in memory, including the layout, organization, and
allocation of memory.
- Operations: Data structures provide operations for accessing, inserting, deleting, and manipulating
data elements. These operations are typically based on the underlying ADT.
- Efficiency: Data structures aim to optimize various performance metrics such as time complexity,
space complexity, and execution speed for different operations.
- Examples:
- Array: An array is a data structure that stores a fixed-size sequential collection of elements of the
same type. It supports constant-time access to elements but may have limitations on insertion and deletion
operations.
- Linked List: A linked list is a data structure that consists of a sequence of elements, where each
element points to the next element in the sequence. It supports efficient insertion and deletion operations
but may require linear-time traversal to access elements.
- Tree: A tree is a hierarchical data structure that consists of nodes connected by edges. It is used to
represent hierarchical relationships and supports efficient searching, insertion, and deletion operations.
- Graph: A graph is a non-linear data structure that consists of vertices (nodes) connected by edges. It
is used to represent various types of relationships between objects and supports operations like traversal,
shortest path finding, and cycle detection.
- Usage: Data structures are essential building blocks in software development and are used to solve a
wide range of computational problems efficiently. They form the backbone of algorithms and applications
in areas such as databases, operating systems, compilers, and artificial intelligence.

In summary, Abstract Data Types provide a high-level specification of data and operations, while Data
Structures provide concrete implementations that define how data is organized and manipulated in
memory. Understanding both concepts is crucial for designing efficient algorithms and building robust
software systems.

1.4 Linear and non – linear data structures.

Linear and non-linear data structures are fundamental concepts in computer science and are often covered
in Bachelor of Computer Applications (BCA) programs.

• Linear Data Structures:

 - Definition: Linear data structures are data structures where data elements are arranged in a sequential
manner, with each element having a unique predecessor and successor, except for the first and last
elements. This means that elements are accessed in a linear or sequential order.
- Characteristics:
▪ - Sequential Access: In linear data structures, elements are accessed one after the other in a
sequential manner. This makes traversal straightforward and efficient.
▪ - Fixed Relationships: Elements in linear data structures have fixed relationships with their
adjacent elements. For example, in an array or a linked list, each element points to the next
element in the sequence.
- Examples: Common examples of linear data structures include:
→ Arrays:
i. Arrays are one of the simplest linear data structures.
ii. They consist of a contiguous block of memory where elements are stored, and each element can
be accessed using its index.
iii. Arrays offer constant-time access to elements but may have limitations on insertion and deletion
operations, especially in the middle of the array.

→ Linked Lists:
i. Linked lists are another type of linear data structure.
ii. They consist of nodes where each node contains a data element and a reference (pointer) to the
next node in the sequence.
iii. Linked lists offer efficient insertion and deletion operations, but accessing elements requires
traversal from the beginning of the list, resulting in linear-time access.

→ Stacks:
i. Stacks are linear data structures that follow the Last In, First Out (LIFO) principle.
ii. Elements are added and removed from the same end of the stack, known as the top.
iii. Stacks are commonly used in programming language syntax parsing, expression evaluation, and
backtracking algorithms.

→ Queues:
i. Queues are linear data structures that follow the First In, First Out (FIFO) principle.
ii. Elements are added at one end of the queue (rear) and removed from the other end (front).
iii. Queues are used in scenarios such as task scheduling, job processing, and breadth -first search
(BFS) algorithms.
- Usage: Linear data structures are commonly used for tasks that involve sequential processing or
ordered storage of data, such as list processing, text processing, and implementing algorithms like depth -
first search (DFS) or breadth-first search (BFS).

• Non-linear Data Structures:

 7

- Definition: Non-linear data structures are data structures where data elements are not arranged in a
sequential or linear order. Instead, elements may have multiple predecessors and successors, forming
complex relationships.
- Characteristics:
▪ - Complex Relationships: In non-linear data structures, elements may have multiple
predecessors and successors, leading to complex relationships between elements.

▪ - Hierarchical Structure: Non-linear data structures often exhibit hierarchical relationships,

where elements are organized in a hierarchical or tree-like structure.
- Examples: Common examples of non-linear data structures include:

→ Trees:

i. Trees are hierarchical data structures consisting of nodes connected by edges.

ii. They have a root node at the top, and each node can have zero or more child nodes.
iii. Common types of trees include binary trees, binary search trees, AVL trees, and red -black trees.
iv. Trees are used for organizing hierarchical data, implementing search algorithms, and representing
hierarchical relationships.

→ Graphs:

i. Graphs are non-linear data structures consisting of vertices (nodes) connected by edges.
ii. They can be directed or undirected, and edges may have weights.
iii. Graphs are used for modeling relationships between entities in various domains, such as social
networks, transportation networks, and computer networks.
iv. Common graph algorithms include depth-first search (DFS), breadth-first search (BFS), shortest
path algorithms (Dijkstra's algorithm), and minimum spanning tree algorithms (Prim's algorithm,
Kruskal's algorithm).
- Usage: Non-linear data structures are used for modeling complex relationships and networks in
various applications, such as social networks, network routing, and hierarchical data representation (e.g.,
file systems).

In summary, linear data structures are characterized by sequential access to elements with fixed
relationships, whereas non-linear data structures have complex relationships between elements and often
exhibit hierarchical structures. Both types of data structures are essential in computer science and are used
for different types of data organization and manipulation tasks.