UNIT – I
BASIC TERMINOLOGIES OF DATA STRUCTURES
INTRODUCTION
A data structure is a storage that is used to store and organize data. It is a way of
arranging data on a computer so that it can be accessed and updated efficiently. A data structure
is not only used for organizing the data. It is also used for processing, retrieving, and storing
data.
Classification of Data Structure:
1. Linear data structure: Data structure in which data elements are arranged
sequentially or linearly, where each element is attached to its previous and next adjacent
elements, is called a linear data structure. Examples of linear data structures are array,
stack, queue, linked list, etc.
a. Static data structure: Static data structure has a fixed memory size. It is easier to
access the elements in a static data structure. An example of this data structure is
an array.
b. Dynamic data structure: In dynamic data structure, the size is not fixed. It can
be randomly updated during the runtime which may be considered efficient
concerning the memory (space) complexity of the code. Examples of this data
structure are queue, stack, etc.
, 2. Non-linear data structure: Data structures where data elements are not placed
sequentially or linearly are called non-linear data structures. In a non-linear data
structure, we can’t traverse all the elements in a single run only. Examples of non-linear
data structures are trees and graphs.
Elementary Data Organization
Data: Data are simply values or sets of values.
Data items: Data items refers to a single unit of values. Data items that are divided into sub-
items are called Group items. Ex: An Employee Name may be divided into three subitems-
first name, middle name, and last name. Data items that are not able to divide into sub-items are
called Elementary items.
Entity: An entity is something that has certain attributes or properties which may be assigned
values. The values may be either numeric or non-numeric. Entities with similar attributes form
an entity set. Each attribute of an entity set has a range of values, the set of all possible values
that could be assigned to the particular attribute.
The term “information” is sometimes used for data with given attributes, of, in other words
meaningful or processed data.
Field is a single elementary unit of information representing an attribute of an entity.
Record is the collection of field values of a given entity.
File is the collection of records of the entities in a given entity set.
Each record in a file may contain many field items but the value in a certain field may
uniquely determine the record in the file. Such a field K is called a primary key and the values
k1, k2, ….. in such a field are called keys or key values.
Records may also be classified according to length. A file can have fixed-length records
or variable-length records. In fixed-length records, all the records contain the same data items
with the same amount of space assigned to each data item. In variable-length records file
records may contain different lengths.
Data Structure Operations
1. Insertion: It is the operation which we apply on all the data-structures. Insertion means
to add an element in the given data structure. The operation of insertion is successful
when the required element is added to the required data-structure. It is unsuccessful in
, some cases when the size of the data structure is full and when there is no space in the
data-structure to add any additional element.
2. Deletion: It is the operation which we apply on all the data-structures. Deletion means to
delete an element in the given data structure. The operation of deletion is successful when
the required element is deleted from the data structure.
3. Traversing: Traversing a Data Structure means to visit the element stored in it. It visits
data in a systematic manner.This can be done with any type of DS.
4. Searching: Searching means to find a particular element in the given data-structure. It is
considered as successful when the required element is found. Searching is the operation
which we can performed on data-structures like array, linked-list, tree, graph, etc.
ANALYSIS OF ALGORITHM
Algorithm:
An algorithm may be defined as a finite sequence of instructions each of which has a clear
meaning and can be performed with a finite amount of effort in a finite length of time.
Properties of Algorithm:
An algorithm is endowed with the following properties:
1. Finiteness: An algorithm must terminate after a finite number of steps.
2. Definiteness: The steps of the algorithm must be precisely defined or unambiguously
specified.
3. Generality: An algorithm must be generic enough to solve all problems of a particular
class.
4. Effectiveness: the operations of the algorithm must be basic enough to be put down on
pencil and paper. They should not be too complex to warrant writing another algorithm
for the operation.
5. Input-Output: The algorithm can take zero or more inputs and should produce at least
one output.
Efficiency of Algorithms
The performances of algorithms can be measured on the scales of time and space. The
performance of a program is the amount of computer memory and time needed to run a
program. We use two approaches to determine the performance of a program. One is analytical
and the other is experimental. In performance analysis we use analytical methods, while in
BASIC TERMINOLOGIES OF DATA STRUCTURES
INTRODUCTION
A data structure is a storage that is used to store and organize data. It is a way of
arranging data on a computer so that it can be accessed and updated efficiently. A data structure
is not only used for organizing the data. It is also used for processing, retrieving, and storing
data.
Classification of Data Structure:
1. Linear data structure: Data structure in which data elements are arranged
sequentially or linearly, where each element is attached to its previous and next adjacent
elements, is called a linear data structure. Examples of linear data structures are array,
stack, queue, linked list, etc.
a. Static data structure: Static data structure has a fixed memory size. It is easier to
access the elements in a static data structure. An example of this data structure is
an array.
b. Dynamic data structure: In dynamic data structure, the size is not fixed. It can
be randomly updated during the runtime which may be considered efficient
concerning the memory (space) complexity of the code. Examples of this data
structure are queue, stack, etc.
, 2. Non-linear data structure: Data structures where data elements are not placed
sequentially or linearly are called non-linear data structures. In a non-linear data
structure, we can’t traverse all the elements in a single run only. Examples of non-linear
data structures are trees and graphs.
Elementary Data Organization
Data: Data are simply values or sets of values.
Data items: Data items refers to a single unit of values. Data items that are divided into sub-
items are called Group items. Ex: An Employee Name may be divided into three subitems-
first name, middle name, and last name. Data items that are not able to divide into sub-items are
called Elementary items.
Entity: An entity is something that has certain attributes or properties which may be assigned
values. The values may be either numeric or non-numeric. Entities with similar attributes form
an entity set. Each attribute of an entity set has a range of values, the set of all possible values
that could be assigned to the particular attribute.
The term “information” is sometimes used for data with given attributes, of, in other words
meaningful or processed data.
Field is a single elementary unit of information representing an attribute of an entity.
Record is the collection of field values of a given entity.
File is the collection of records of the entities in a given entity set.
Each record in a file may contain many field items but the value in a certain field may
uniquely determine the record in the file. Such a field K is called a primary key and the values
k1, k2, ….. in such a field are called keys or key values.
Records may also be classified according to length. A file can have fixed-length records
or variable-length records. In fixed-length records, all the records contain the same data items
with the same amount of space assigned to each data item. In variable-length records file
records may contain different lengths.
Data Structure Operations
1. Insertion: It is the operation which we apply on all the data-structures. Insertion means
to add an element in the given data structure. The operation of insertion is successful
when the required element is added to the required data-structure. It is unsuccessful in
, some cases when the size of the data structure is full and when there is no space in the
data-structure to add any additional element.
2. Deletion: It is the operation which we apply on all the data-structures. Deletion means to
delete an element in the given data structure. The operation of deletion is successful when
the required element is deleted from the data structure.
3. Traversing: Traversing a Data Structure means to visit the element stored in it. It visits
data in a systematic manner.This can be done with any type of DS.
4. Searching: Searching means to find a particular element in the given data-structure. It is
considered as successful when the required element is found. Searching is the operation
which we can performed on data-structures like array, linked-list, tree, graph, etc.
ANALYSIS OF ALGORITHM
Algorithm:
An algorithm may be defined as a finite sequence of instructions each of which has a clear
meaning and can be performed with a finite amount of effort in a finite length of time.
Properties of Algorithm:
An algorithm is endowed with the following properties:
1. Finiteness: An algorithm must terminate after a finite number of steps.
2. Definiteness: The steps of the algorithm must be precisely defined or unambiguously
specified.
3. Generality: An algorithm must be generic enough to solve all problems of a particular
class.
4. Effectiveness: the operations of the algorithm must be basic enough to be put down on
pencil and paper. They should not be too complex to warrant writing another algorithm
for the operation.
5. Input-Output: The algorithm can take zero or more inputs and should produce at least
one output.
Efficiency of Algorithms
The performances of algorithms can be measured on the scales of time and space. The
performance of a program is the amount of computer memory and time needed to run a
program. We use two approaches to determine the performance of a program. One is analytical
and the other is experimental. In performance analysis we use analytical methods, while in
