Data Structures and Applications (23CS204) Module 1
Module1
Data types to Data structures: Data structures, Classifications: Primitive & Non-Primitive (Stack,
Queue, Linked List, Graph, Trees, and Hash Table). Data structure operations. Review of pointers,
Dynamic Memory Allocation, Functions with Programming Examples (Dynamic 1D array, 2D
array), review of structures, polynomial, sparse matrices, String pattern matching (nfind, KMP)
1.1. Introduction to Data Structures:
A data structure defines a way of organizing all data items that considers not only the elements
stored but also their relationship to each other. The term data structure is used to describe the way
data is stored.
To develop a program of an algorithm we should select an appropriate data structure for that
algorithm. Therefore, data structure is represented as: Algorithm + Data structure = Program
A data structure is said to be linear if its elements form a sequence or a linear list. The linear data
structures like an array, stacks, queues and linked lists organize data in linear order.
A data structure is said to be non-linear if its elements form a hierarchical classification where, data
items appear at various levels. Trees and Graphs are widely used non-linear data structures. Tree and
graph structures represent hierarchical relationship between individual data elements.
1.2 Classification of Data structures
Data structures are divided into two types:
• Primitive data structures.
• Non-primitive data structures.
Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 1
,Data Structures and Applications (23CS204) Module 1
Primitive Data Structures
1. Primitive Data Structures are the data structures consisting of the numbers and the characters that
come in-built into programs.
2. These data structures can be manipulated or operated directly by machine-level instructions.
3. Basic data types like Integer, Float, Character come under the Primitive Data Structures.
4. These data types are also called Simple data types, as they contain characters that can't be divided further
Non-Primitive Data Structures
1. Non-Primitive Data Structures are those data structures derived from Primitive Data Structures.
2. These data structures can't be manipulated or operated directly by machine-level instructions.
3. 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).
4. Based on the structure and arrangement of data, we can divide these data structures into two sub-
categories -
a. Linear Data Structures
b. Non-Linear Data Structures
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
Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 2
,Data Structures and Applications (23CS204) Module 1
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:
1. 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.
2. 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
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.
The data elements of the array share the same variable name; however, each carries a different index
number called a subscript. We can access any data element from the list with the help of its location in
the list. Thus, the key feature of the arrays to understand is that the data is stored in contiguous memory
locations, making it possible for the users to traverse through the data elements of the array using their
respective indexes.
Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 3
, Data Structures and Applications (23CS204) Module 1
An Array
Arrays can be classified into different types:
a) One-Dimensional Array: An Array with only one row of data elements is known as a One-Dimensional
Array. It is stored in ascending storage location.
b) Two-Dimensional Array: An Array consisting of multiple rows and columns of data elements is called a
Two-Dimensional Array. It is also known as a Matrix.
c) Multidimensional Array: We can define Multidimensional Array as an Array of Arrays.
Multidimensional Arrays are not bounded to two indices or two dimensions as they can include as many
indices are per the need.
Some Applications of Array:
a) We can store a list of data elements belonging to the same data type.
b) Array acts as an auxiliary storage for other data structures.
c) Array also acts as a storage of matrices.
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.
Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 4
Module1
Data types to Data structures: Data structures, Classifications: Primitive & Non-Primitive (Stack,
Queue, Linked List, Graph, Trees, and Hash Table). Data structure operations. Review of pointers,
Dynamic Memory Allocation, Functions with Programming Examples (Dynamic 1D array, 2D
array), review of structures, polynomial, sparse matrices, String pattern matching (nfind, KMP)
1.1. Introduction to Data Structures:
A data structure defines a way of organizing all data items that considers not only the elements
stored but also their relationship to each other. The term data structure is used to describe the way
data is stored.
To develop a program of an algorithm we should select an appropriate data structure for that
algorithm. Therefore, data structure is represented as: Algorithm + Data structure = Program
A data structure is said to be linear if its elements form a sequence or a linear list. The linear data
structures like an array, stacks, queues and linked lists organize data in linear order.
A data structure is said to be non-linear if its elements form a hierarchical classification where, data
items appear at various levels. Trees and Graphs are widely used non-linear data structures. Tree and
graph structures represent hierarchical relationship between individual data elements.
1.2 Classification of Data structures
Data structures are divided into two types:
• Primitive data structures.
• Non-primitive data structures.
Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 1
,Data Structures and Applications (23CS204) Module 1
Primitive Data Structures
1. Primitive Data Structures are the data structures consisting of the numbers and the characters that
come in-built into programs.
2. These data structures can be manipulated or operated directly by machine-level instructions.
3. Basic data types like Integer, Float, Character come under the Primitive Data Structures.
4. These data types are also called Simple data types, as they contain characters that can't be divided further
Non-Primitive Data Structures
1. Non-Primitive Data Structures are those data structures derived from Primitive Data Structures.
2. These data structures can't be manipulated or operated directly by machine-level instructions.
3. 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).
4. Based on the structure and arrangement of data, we can divide these data structures into two sub-
categories -
a. Linear Data Structures
b. Non-Linear Data Structures
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
Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 2
,Data Structures and Applications (23CS204) Module 1
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:
1. 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.
2. 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
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.
The data elements of the array share the same variable name; however, each carries a different index
number called a subscript. We can access any data element from the list with the help of its location in
the list. Thus, the key feature of the arrays to understand is that the data is stored in contiguous memory
locations, making it possible for the users to traverse through the data elements of the array using their
respective indexes.
Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 3
, Data Structures and Applications (23CS204) Module 1
An Array
Arrays can be classified into different types:
a) One-Dimensional Array: An Array with only one row of data elements is known as a One-Dimensional
Array. It is stored in ascending storage location.
b) Two-Dimensional Array: An Array consisting of multiple rows and columns of data elements is called a
Two-Dimensional Array. It is also known as a Matrix.
c) Multidimensional Array: We can define Multidimensional Array as an Array of Arrays.
Multidimensional Arrays are not bounded to two indices or two dimensions as they can include as many
indices are per the need.
Some Applications of Array:
a) We can store a list of data elements belonging to the same data type.
b) Array acts as an auxiliary storage for other data structures.
c) Array also acts as a storage of matrices.
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.
Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 4
