Data Structure

UNIT- 1
1.1 Data Structure
A data structure is a set of data values along with the relationship between the data values. Since,
the operations that can be performed on the data values depend on what kind of relationships
exists among them, we can specify the relationship amongst the data values by specifying the
operations permitted on the data values. Therefore, we can say that a data structure is a set of
values along with the set of operations permitted on them. It is also required to specify the
semantics of the operations permitted on the data values, and this is done by using a set of axioms,
which describes how these operations work, and therefore a data structure is made of:
1. A set of data values.
2. A set of functions specifying the operations permitted on the data values.
3. A set of axioms describing how these operations work.
Hence, we conclude that a data structure is a triple (D,F,A), where
1. D is a set of data values
2. F is a set of functions
3. A is a set of axioms
A triple (D, F, A) is referred to as an abstract data structure because it does not tell anything about
its actual implementation. It does not tell anything about how these values will be physically
represented in the computer memory and these functions will be actually implemented.
Therefore, every abstract data structure is required to be implemented, and the implementation of
an abstract data structure requires mapping of the abstract data structure to be implemented into
the data structure supported by the computer. For example, if the abstract data structure to be
implemented is integer, then it can be implemented by mapping into bits which is a data structure
supported by hardware. This requires that every integer data value is to be represented using
suitable bit patterns and expressing the operations on integer data values in terms of operations for
manipulating bits.
Data Structure mainly two types:
1. Linear type data structure
2. Non-linear type data structure
Linear data structure: A linear data structure traverses the data elements sequentially, in
which onlyone data element can directly be reached. Ex: Arrays, Linked Lists
Arrays: An array is a collection of similar type of data items and each data item is called an element
of the array.
The data type of the element may be any valid data type like char, int, float or double. — The
individual elements of the array age are: — age[0], age[1], age[2], age[3], age[98], age[99].
Linked List: Linked list is a linear data structure which is used to maintain a list in the memory.
It can be seen as the collection of nodes stored at non-contiguous memory locations. Each node of
the list contains a pointer to its adjacent node
Stack: Stack is a linear list in which insertion and deletions are allowed only at one end, called top.
A stack is an abstract data type, can be implemented in most of the programming languages. It is
named as stack because it behaves like a real-world stack, for example: - piles of plates or deck of
cards etc.
Queue is a linear list in which element can be inserted only at one end called rear and deleted only
at other end called front.
It is abstract data structure, similar to stack. It is open at both end therefore if follows first-in-first-
out (FIFO) technique for storing the data items.
 Non-linear data structure: Every data item is attached to several other data items in a way that is
specific for reflecting relationships. The data items are not arranged in a sequential structure.
Ex: Trees, Graphs.
Trees: Trees are multilevel data structures with a hierarchical relationship among its elements
known as nodes.

Graphs: Graphs can be defined as the pictorial representation of the set of elements (represented by
vertices) connected by the links known as edges

Basic Terminology
Data: Data can be defined as an elementary value or the collection of values, for example, student's
name and its id are the data about the student.
Group Items: Data items which have subordinate data items are called Group item, for example,
name of a student can have first name and the last name.
Record: Record can be defined as the collection of various data items, for example, if we talk about
the student entity, then its name, address, course and marks can be grouped together to form the
record for the student.
Field: A File is a collection of various records of one type of entity, for example, if there are 60
students in the class, then there will be 20 records in the related file where each record contains the
data about each student.

Need of Data Structures

As applications are getting complex and amount of data is increasing day by day, there may arises
many problems:
Processor speed: To handle very large amount of data, high speed processing is required, but as the
data is growing day by day to the billions of files per entity, processor may fail to deal with that
much amount of data.
Data Search: Consider an inventory size of 100 items in a store, If our application needs to search
for a particular item, it needs to traverse 100 items every time, results in slowing down the search
process.
Multiple requests: If thousands of users are Searching the data simultaneously on a web server,
then there are the chances that a very large server can be failed during that process To solve these
problems data structures are used.
 Basic Concept of Data
The memory (also called storage or core) of a computer is simply a group of bits (switches). At any
instant of the computer’s operation any particular bit in memory is either 0 or 1 (off or on).
The setting or state of a bit is called its value and that is the smallest unit of information. A set of
bit values form data.
Some logical properties can be imposed on the data. According to the logical properties data can be
segregated into different categories. Each category having unique set of logical properties is known
as data type.
Data type are of two types:
1. Simple data type or elementary item like integer, character.
2. Composite data type or group item like array, structure, union.
Data structures are of two types:
1. Primitive Data Structures: Data can be structured at the most primitive level, wherethey are
directly operated upon by machine-level instructions. At this level, data may becharacter or
numeric, and numeric data may consist of integers or real numbers.
2. Non-primitive Data Structures: Non-primitive data structures can be classified as arrays,lists, and fi
les.
An array is an ordered set which contains a fixed number of objects. No deletions or insertionsare
performed on arrays i.e. the size of the array cannot be changed. At best, elements may bechanged.
A list, by contrast, is an ordered set consisting of a variable number of elements to whichinsertions
and deletions can be made, and on which other operations can be performed. When alist displays
the relationship of adjacency between elements, it is said to be linear; otherwise, it issaid to be non-
linear.
A file is typically a large list that is stored in the external memory of a computer. Additionally, afile
may be used as a repository for list items (records) that are accessed infrequently.
From a real world perspective, very often we have to deal with structured data items whichare
related to each other. For instance, let us consider the address of an employee. We can takeaddress
to be one variable of character type or structured into various fields, as shown below:

As shown above Address1 is unstructured address data. In this form you cannot access individual
items from it. You can at best refer to the entire address at one time. While in the second from, i.e.,
Address2, you can access and manipulate individual fi elds of the address – House No., Street, PIN
etc. Given hereunder are two instances of the address1 and address2 variables.

1.2 Asymptotic Notations

To measure the efficiency of an algorithm asymptotic analysis is used.
The efficiency of an algorithm depends on the amount of time, storage and other resources required
to execute the algorithm.
Performance of algorithm is change with different type of inputs.
The study of change in performance of the algorithm with the change in the order of the input size
is defined as asymptotic analysis.
Asymptotic notations are the mathematical notations used to describe the running time of an
algorithm when the input tends towards a particular value or a limiting value.
Types of asymptotic notations
There are three major asymptotic notations

 Big-O notation
 Omega notation
 Theta notation
 Big-O notation represents the upper bound of the running time of an algorithm. It gives the worst- case
complexity of an algorithm.
 O(n) is useful when we only have an upper bound on the time complexity of an algorithm.
 It is widely used to analyses an algorithm as we are always interested in the worst-case scenario.


 O(g(n)) = { f(n): there exist positive constants c and n0 such that 0

≤ f(n) ≤ cg(n) for all n ≥ n0 }
 Omega notation represents the lower bound of the running time of an algorithm. It provides the best-case
complexity of an algorithm.
 Omega Notation can be useful when we have lower bound on time complexity of an
 [Link] notation is the least used notation among all three.


 Ω (g(n)) = {f(n): there exist positive constants c and n0 such that

0 <= c*g(n) <= f(n) forall n >= n0}.
 Theta notation encloses the function from above and below. It represents the upper and the lower bound of the
running time of an algorithm, it is used for analysing the average-case complexity of an algorithm.

  Θ(g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 <= c1*g(n) <=
f(n) <= c2*g(n) for all n >= n0}

Properties of Asymptotic Notations

If f(n) is O(g(n)) then a*f(n) is also O(g(n)) ; where a is a constant.
General Properties

If f(n) is O(g(n)) then a*f(n) is also O(g(n)) ; where a is a constant.

Transitive Properties

If f(n) is O(g(n)) and g(n) is O(h(n)) then f(n) = O(h(n))

Reflexive Properties

If f(n) is given then f(n) is O(f(n))

Symmetric Properties

If f(n) is Θ(g(n)) then g(n) is Θ(f(n))

Transpose Symmetric Properties

If f(n) is O(g(n)) then g(n) is Ω (f(n))

1.3 Data Structure Operations

The data appearing in our data structure is processed by means of certain operations. The
particular data structure that one chooses for a given situation depends largely on the frequency
with which specific operations are performed. The following four operations play a major role:
1. Traversing: Accessing each record exactly once so that certain items in the record may be
processed. (This accessing or processing is sometimes called ‘visiting” the records.)
2. Searching: Finding the location of the record with a given key value, or finding the
locations of all records, which satisfy one or more conditions.

3. Inserting: Adding new records to the structure.

4. Deleting: Removing a record from the structure.
Sometimes two or more data structure of operations may be used in a given situation; e.g., we may
want to delete the record with a given key, which may mean we first need to search for the location
of the record.

1.4 Abstract Data Type

Before we move to abstract data type let us understand what data type is. Most of the languages
support basic data types viz. integer, real, character etc. At machine level, the data is stored as
strings containing 1’s and 0’s. Every data type interprets the string of bits in different ways and
gives different results. In short, data type is a method of interpreting bit patterns.
Every data type has a fixed type and range of values it can operate on. For example, an integer
variable can hold values between the min and max values allowed and carry out operations like
addition, subtraction etc. For character data type, the valid values are defined in the character set
and the operations performed are like comparison, conversion from one case to another etc.
There are fixed operations, which can be carried out on them. We can formally defi ne data types
as a formal description of the set of values and operations that a variable of a given type may take.
That was about the inbuilt data types. One can also create user defined data types, decide the
range of values as well as operations to be performed on them. The first step towards creating a
user defined data type or a data structure is to defi ne the logical properties. A tool to specify the
logical properties of a data type is Abstract Data Type.
Data abstraction can be defined as separation of the logical properties of the organization of
programs’ data from its implementation. This means that it states what the data should be like.
It does not consider the implementation details. ADT is the logical picture of a data type; in
addition, the specifications of the operations required to create and manipulate objects of this data
type.
While defining an ADT, we are not concerned with time and space efficiency or any other
implementation details of the data structure. ADT is just a useful guideline to use and implement
the data type.
An ADT has two parts:
1. Value definition
2. Operation definition.
Value definition is again divided into two parts:
1. Definition clause
2. Condition clause
As the name suggests the definition clause states the contents of the data type and condition
clause defines any condition that applies to the data type. Definition clause is mandatory while
condition clause is optional.
In operation definition, there are three parts:
1. Function
2. Precondition
3. Postcondition
The function clause defines the role of the operation. If we consider the addition operation
inintegers the function clause will state that two integers can be added using this function.
Ingeneral, precondition specifies any restrictions that must be satisfied before the operation canbe
applied.
This clause is optional. If we consider the division operation on integers then theprecondition will
state that the divisor should not be zero. So any call for divide operation, whichdoes not satisfy this
condition, will not give the desired output.

Precondition specifies any condition that may apply as a pre-requisite for the operation
[Link] are certain operations that can be carried out if certain conditions are satisfied.
For example,in case of division operation the divisor should never be equal to zero. Only if this
condition issatisfied the division operation is carried out. Hence, this becomes a precondition. In
that case &(ampersand) should be mentioned in the operation definition.
Postcondition specifies what the operation does. One can say that it specifies the state after
theoperation is performed. In the addition operation, the post condition will give the addition of
thetwo integers.

Component of ADT
As an example, let us consider the representation of integer data type as an ADT. We will consider
only two operations addition and division.
Value Definition
 1. Definition clause: The values must be in between the minimum and maximum
values specified for the particular computer.
2. Condition clause: Values should not include decimal point.
Operations
1. add (a, b)
Function: add the two integers a and b.
Precondition: no precondition.
Postcondition: output = a + b
2. Div (a, b)
Function: Divide a by b.
Precondition: b != 0
Postcondition: output = a/b.
There are two ways of implementing a data structure viz. static and dynamic. In static
implementation, the memory is allocated at the compile time. If there are more elements than the
specified memory then the program crashes. In dynamic implementation, the memory is allocated
as and when required during run time.
Any type of data structure will have certain basic operations to be performed on its data like insert,
delete, modify, sort, search etc. depending on the requirement. These are the entities that decide the
representation of data and distinguish data structures from each other.
Let us see why user defined data structures are essential. Consider a problem where we need to
create a list of elements. Any new element added to the list must be added at the end of the list and
whenever an element is retrieved, it should be the last element of the list. One can compare this to a
pile of plates kept on a table. Whenever one needs a plate, the last one on the pile is taken and if a
plate is to be added on the pile, it will be kept on the top. The description wants us to implement a
stack. Let us try to solve this problem using arrays.
We will have to keep track of the index of the last element entered in the list. Initially, it will be set
to –1. Whenever we insert an element into the list, we will increment the index and insert the value
into the new index position. To remove an element, the value of current index will be the output

and the index will be decremented by one. In the above representation, we have satisfied the
insertion and deletion conditions.
Using arrays we could handle our data properly, but arrays do allow access to other values in
addition to the top most one. We can insert an element at the end of the list but there is no way to
ensure that insertion will be done only at the end. This is because array as a data structure allows
access to any of its values. At this point we can think of another representation, a list of elements
where one can add at the end, remove from the end and elements other than the top one are not
accessible. As already discussed, this data structure is called as STACK. The insertion operation is
known as push and removal as pop. You can try to write an ADT for stacks.
Another situation where we would like to create a data structure is while working with complex
numbers. The operations add, subtract division and multiplication will have to be created as per
the rules of complex numbers. The ADT for complex numbers is given below. Only addition and
multiplication operations are considered here, you can try to write the remaining operations.
Abstract Data Type (ADT)
1. A framework for an object interface
2. What kind of stuff it’d be made of (no details)?
3. What kind of messages it would receive and kind of action it’ll perform when
properly triggered?
From this we figure out
1. Object make-up (in terms of data)
2. Object interface (what sort of messages it would handle?)
3. How and when it should act when triggered from outside (public trigger) and by another
object friendly to it?
These concerns lead to an ADT – a definition for the object.
An Abstract Data Type (ADT) is a set of data items and the methods that work on them.
An implementation of an ADT is a translation into statements of a programming language, of the
declaration that defines a variable to be of that ADT, plus a procedure in that language for each
operation of the ADT. An implementation chooses a data structure to represent the ADT; each data
structure is built up from the basic data types of the underlying programming language.
Thus, if we wish to change the implementation of an ADT, only the procedures implementing the
operations would change. This change would not affect the users of the ADT.
Although the terms ‘data type’, ‘data structure’ and ‘abstract data type’ sound alike, they have
different meanings. In a programming language, the data type of a variable is the set of values that
the variable may assume. For example, a variable of type Boolean can assume either the value true
or the value false, but no other value. An abstract data type is a mathematical model, together with
various operations defined on the model. As we have indicated, we shall design algorithms in
terms of ADTs, but to implement an algorithm in a given programming language.
we must find some way of representing the ADTs in terms of the data types and operators
supported by the programming language itself. To represent the mathematical model underlying
an ADT, we use data structures, which are a collection of variables, possibly of several data types,
connected in various ways.

The cell is the basic building block of data structures. We can picture a cell as a box that is capable
of holding a value drawn from some basic or composite data type. Data structures are created by
giving names to aggregates of cells and (optionally) interpreting the values of some cells as
representing relationships or connections (e.g., pointers) among cells.

1.5 Algorithm
Algorithm is set of rules/ instructions that step-by-step define how a work is to be executed upon
in order to get the expected results.
systematic procedure that produces in a finite number of steps the answer to a question or the
solution of a problem.
Computer algorithms work via input and output. They take the input and apply each step of the
algorithm to that information to generate an output.
E.g. a search engine is an algorithm that takes a search query as an input and searches its database
for items relevant to the words in the query. It then outputs the results.
Financial companies use algorithms in areas such as loan pricing, stock trading, asset-liability
management, and many automated functions. For example, algorithmic trading, known as algo
trading, is used for deciding the timing, pricing, and quantity of stock orders. Also referred to as
automated trading or black-box trading, algo trading uses computer programs to buy or sell
securities at a pace not possible for humans.
Computer algorithms make life easier by trimming the time it takes to manually do things. In the
world of automation, algorithms allow workers to be more proficient and focused. Algorithms
make slow processes more proficient. In many cases, especially in automation, algos can save
companies money.
1.6 Characteristics of an Algorithm
 Well defined Input and output
 Clear and Unambiguous
 Finite-ness
 Feasible
 Language Independent
Input and output should be defined precisely.
Each step in the algorithm should be clear and unambiguous.
Algorithms should be most effective among many different ways to solve a problem.
An algorithm shouldn't include computer code. Instead, the algorithm should be written in such a
way that it can be used in different programming languages.
The algorithm must be finite, i.e. it should not end up in an infinite loops or similar.
The algorithm must be simple, generic and practical, such that it can be executed upon will the
available resources. It must not contain some future technology, or anything.
The Algorithm designed must be language-independent, i.e. it must be just plain instructions that
can be implemented in any language, and yet the output will be same, as expected.

1.7 Types of Algorithms

Algorithms are categorized based on the concepts that they use to accomplish a task.

 Divide and conquer algorithms

 Brute force algorithms
 Greedy algorithms
 Backtracking algorithms
 Randomized algorithms