DATA STRUCTURE AND ALGORITHM
Unit I
Arrays and sequential representations – ordered lists – Stacks and Queues – Evaluation
ofExpressions – Multiple Stacks and Queues – Singly Linked List – Linked Stacks and
queues – Polynomial addition.
Data Structure Introduction:
The data structure name indicates itself that organizing the data in memory.
There are many ways of organizing the data in the memory as we have already seen
one of the data structures, i.e., array in C language. Array is a collection of memory
elements in which data is stored sequentially, i.e., one after another. In other words,
we can say that array stores the elements in a continuous manner. This organization
of data is done with the help of an array of data structures. There are also other ways
to organize the data in memory. To structure the data in memory, 'n' number of
algorithms were proposed, and all these algorithms are known as Abstract data
types. These abstract data types are the set of rules.
Types of Data Structures
There are two types of data structures:
o Primitive data structure
o Non-primitive data structure
Primitive Data structure
The primitive data structures are primitive data types. The int, char, float, double, and
pointer are the primitive data structures that can hold a single value.
Non-Primitive Data structure
,The non-primitive data structure is divided into two types:
Linear data structure
Non-linear data structure
Linear Data Structure
The arrangement of data in a sequential manner is known as a linear data structure.
The data structures used for this purpose are Arrays, Linked list, Stacks, and Queues.
In these data structures, one element is connected to only one another element in a
linear form.
Non- Linear Structure:
When one element is connected to the 'n' number of elements known as a non-
linear data structure. The best example is trees and graphs. In this case, the elements
are arranged in a random manner.
Data structures can also be classified as:
Static data structure: It is a type of data structure where the size is allocated
at the compile time. Therefore, the maximum size is fixed.
Dynamic data structure: It is a type of data structure where the size is
allocated at the run time. Therefore, the maximum size is flexible.
Major Operations
The major or the common operations that can be performed on the data structures
are:
o Searching: We can search for any element in a data structure.
o Sorting: We can sort the elements of a data structure either in an ascending
or descending order.
o Insertion: We can also insert the new element in a data structure.
o Updation: We can also update the element, i.e., we can replace the element
with another element.
o Deletion: We can also perform the delete operation to remove the element
from the data structure.
Advantages of Data structures
The following are the advantages of a data structure:
, o Efficiency: If the choice of a data structure for implementing a particular ADT
is proper, it makes the program very efficient in terms of time and space.
o Reusability: The data structure provides reusability means that multiple client
programs can use the data structure.
o 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.
Arrays and Sequential Representation
Definition
o Arrays are defined as the collection of similar type of data items stored at contiguous
memory locations.
o Arrays are the derived data type in C programming language which can store the
primitive type of data such as int, char, double, float, etc.
o Array is the simplest data structure where each data element can be randomly
accessed by using its index number.
o For example, if we want to store the marks of a student in 6 subjects, then we don't
need to define different variable for the marks in different subject. instead of that, we
can define an array which can store the marks in each subject at a the contiguous
memory locations.
The array marks[10] defines the marks of the student in 10 different subjects where
each subject marks are located at a particular subscript in the array
i.e. marks[0] denotes the marks in first subject, marks[1] denotes the marks in 2nd
subject and so on.
Properties of the Array
1. Each element is of same data type and carries a same size i.e. int = 4 bytes.
2. Elements of the array are stored at contiguous memory locations where the first
element is stored at the smallest memory location.
3. Elements of the array can be randomly accessed since we can calculate the address of
each element of the array with the given base address and the size of data element.
Advantages of Array
o Array provides the single name for the group of variables of the same type therefore,
it is easy to remember the name of all the elements of an array.
o Traversing an array is a very simple process, we just need to increment the base
address of the array in order to visit each element one by one.
o Any element in the array can be directly accessed by using the index.
, Memory Allocation of the array
As we have mentioned, all the data elements of an array are stored at
contiguous locations in the main memory. The name of the array represents
the base address or the address of first element in the main memory. Each
element of the array is represented by a proper indexing.
The indexing of the array can be defined in three ways.
1. 0 (zero - based indexing) : The first element of the array will be arr[0].
2. 1 (one - based indexing) : The first element of the array will be arr[1].
3. n (n - based indexing) : The first element of the array can reside at any random index
number.
In the following image, we have shown the memory allocation of an array arr of size
5. The array follows 0-based indexing approach. The base address of the array is
100th byte. This will be the address of arr[0]. Here, the size of int is 4 bytes therefore
each element will take 4 bytes in the memory.
In 0 based indexing, If the size of an array is n then the maximum index number, an
element can have is n-1. However, it will be n if we use 1 based indexing.
Accessing Elements of an array
To access any random element of an array we need the following information:
1. Base Address of the array.
2. Size of an element in bytes.
3. Which type of indexing, array follows.
Address of any element of a 1D array can be calculated by using the following
formula:
Unit I
Arrays and sequential representations – ordered lists – Stacks and Queues – Evaluation
ofExpressions – Multiple Stacks and Queues – Singly Linked List – Linked Stacks and
queues – Polynomial addition.
Data Structure Introduction:
The data structure name indicates itself that organizing the data in memory.
There are many ways of organizing the data in the memory as we have already seen
one of the data structures, i.e., array in C language. Array is a collection of memory
elements in which data is stored sequentially, i.e., one after another. In other words,
we can say that array stores the elements in a continuous manner. This organization
of data is done with the help of an array of data structures. There are also other ways
to organize the data in memory. To structure the data in memory, 'n' number of
algorithms were proposed, and all these algorithms are known as Abstract data
types. These abstract data types are the set of rules.
Types of Data Structures
There are two types of data structures:
o Primitive data structure
o Non-primitive data structure
Primitive Data structure
The primitive data structures are primitive data types. The int, char, float, double, and
pointer are the primitive data structures that can hold a single value.
Non-Primitive Data structure
,The non-primitive data structure is divided into two types:
Linear data structure
Non-linear data structure
Linear Data Structure
The arrangement of data in a sequential manner is known as a linear data structure.
The data structures used for this purpose are Arrays, Linked list, Stacks, and Queues.
In these data structures, one element is connected to only one another element in a
linear form.
Non- Linear Structure:
When one element is connected to the 'n' number of elements known as a non-
linear data structure. The best example is trees and graphs. In this case, the elements
are arranged in a random manner.
Data structures can also be classified as:
Static data structure: It is a type of data structure where the size is allocated
at the compile time. Therefore, the maximum size is fixed.
Dynamic data structure: It is a type of data structure where the size is
allocated at the run time. Therefore, the maximum size is flexible.
Major Operations
The major or the common operations that can be performed on the data structures
are:
o Searching: We can search for any element in a data structure.
o Sorting: We can sort the elements of a data structure either in an ascending
or descending order.
o Insertion: We can also insert the new element in a data structure.
o Updation: We can also update the element, i.e., we can replace the element
with another element.
o Deletion: We can also perform the delete operation to remove the element
from the data structure.
Advantages of Data structures
The following are the advantages of a data structure:
, o Efficiency: If the choice of a data structure for implementing a particular ADT
is proper, it makes the program very efficient in terms of time and space.
o Reusability: The data structure provides reusability means that multiple client
programs can use the data structure.
o 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.
Arrays and Sequential Representation
Definition
o Arrays are defined as the collection of similar type of data items stored at contiguous
memory locations.
o Arrays are the derived data type in C programming language which can store the
primitive type of data such as int, char, double, float, etc.
o Array is the simplest data structure where each data element can be randomly
accessed by using its index number.
o For example, if we want to store the marks of a student in 6 subjects, then we don't
need to define different variable for the marks in different subject. instead of that, we
can define an array which can store the marks in each subject at a the contiguous
memory locations.
The array marks[10] defines the marks of the student in 10 different subjects where
each subject marks are located at a particular subscript in the array
i.e. marks[0] denotes the marks in first subject, marks[1] denotes the marks in 2nd
subject and so on.
Properties of the Array
1. Each element is of same data type and carries a same size i.e. int = 4 bytes.
2. Elements of the array are stored at contiguous memory locations where the first
element is stored at the smallest memory location.
3. Elements of the array can be randomly accessed since we can calculate the address of
each element of the array with the given base address and the size of data element.
Advantages of Array
o Array provides the single name for the group of variables of the same type therefore,
it is easy to remember the name of all the elements of an array.
o Traversing an array is a very simple process, we just need to increment the base
address of the array in order to visit each element one by one.
o Any element in the array can be directly accessed by using the index.
, Memory Allocation of the array
As we have mentioned, all the data elements of an array are stored at
contiguous locations in the main memory. The name of the array represents
the base address or the address of first element in the main memory. Each
element of the array is represented by a proper indexing.
The indexing of the array can be defined in three ways.
1. 0 (zero - based indexing) : The first element of the array will be arr[0].
2. 1 (one - based indexing) : The first element of the array will be arr[1].
3. n (n - based indexing) : The first element of the array can reside at any random index
number.
In the following image, we have shown the memory allocation of an array arr of size
5. The array follows 0-based indexing approach. The base address of the array is
100th byte. This will be the address of arr[0]. Here, the size of int is 4 bytes therefore
each element will take 4 bytes in the memory.
In 0 based indexing, If the size of an array is n then the maximum index number, an
element can have is n-1. However, it will be n if we use 1 based indexing.
Accessing Elements of an array
To access any random element of an array we need the following information:
1. Base Address of the array.
2. Size of an element in bytes.
3. Which type of indexing, array follows.
Address of any element of a 1D array can be calculated by using the following
formula:
