Unit 1.

Introduction to Data Structure

Data structure
Data Structure is a particular way of storing and organizing information in a
computer so that it can be retrieved and used most productively.

Different kinds of data structures are meant for different kinds of applications, and
some are highly specialized to specific tasks.

Data structures are important for the following reasons:

1. Data structures are used in almost every program or software system.

2. Specific data structures are essential ingredients of many efficient algorithms,

and make possible the management of huge amounts of data, such as large
integrated collection of databases.

3. Some programming languages emphasize data structures, rather than algorithms,

as the key organizing factor in software design.

What is Data Structure?

Data structure is a representation of the logical relationship existing between
individual elements of data.

• Data Structure is a way of organizing all data items that considers not only
the elements stored but also
• their relationship to each other.
• We can also define data structure as a mathematical or logical model of a
particular organization of
• data items.
• The representation of particular data structure in the main memory of a
computer is called as storage
• structure.
• The storage structure representation in auxiliary memory is called as file
structure.
 • It is defined as the way of storing and manipulating data in organized form
so that it can be used
• efficiently.
• Data Structure mainly specifies the following four things
• Organization of Data
• Accessing methods
• Degree of associativity
• Processing alternatives for information
• Algorithm + Data Structure = Program

Need of Data Structures

As applications are getting complexed and amount of data is increasing day by
day, there may arrise the following problems:

Processor speed: To handle very large amout 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 106 items in a store, If our application
needs to search for a particular item, it needs to traverse 106 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

in order to solve the above problems, data structures are used. Data is organized to
form a data structure in such a way that all items are not required to be searched
and required data can be searched instantly.

Advantages of Data Structures

Efficiency: Efficiency of a program depends upon the choice of data structures.
For example: suppose, we have some data and we need to perform the search for a
perticular record. In that case, if we organize our data in an array, we will have to
search sequentially element by element. hence, using array may not be very
efficient here. There are better data structures which can make the search process
efficient like ordered array, binary search tree or hash tables.
Reusability: Data structures are reusable, i.e. once we have implemented a
particular data structure, we can use it at any other place. Implementation of data
structures can be compiled into libraries which can be used by different clients.

Abstraction: Data structure is specified by the ADT which provides a level of

abstraction. The client program uses the data structure through interface only,
without getting into the implementation details.

Data Structure Classification

Operations on data structure

1) Traversing: Every data structure contains the set of data elements. Traversing
the data structure means visiting each element of the data structure in order to
perform some specific operation like searching or sorting.

Example: If we need to calculate the average of the marks obtained by a student in

6 different subject, we need to traverse the complete array of marks and calculate
the total sum, then we will divide that sum by the number of subjects i.e. 6, in
order to find the average.

2) Insertion: Insertion can be defined as the process of adding the elements to the
data structure at any location.
If the size of data structure is n then we can only insert n-1 data elements into it.

3) Deletion: The process of removing an element from the data structure is called
Deletion. We can delete an element from the data structure at any random location.

If we try to delete an element from an empty data structure then underflow occurs.

4) Searching: The process of finding the location of an element within the data
structure is called Searching. There are two algorithms to perform searching,
Linear Search and Binary Search. We will discuss each one of them later in this
tutorial.

5) Sorting: The process of arranging the data structure in a specific order is known
as Sorting. There are many algorithms that can be used to perform sorting, for
example, insertion sort, selection sort, bubble sort, etc.

6) Merging: When two lists List A and List B of size M and N respectively, of
similar type of elements, clubbed or joined to produce the third list, List C of size
(M+N), then this process is called merging

o Time complexity: It is a way of representing the amount of time needed by

a program to run to the completion.
o Space complexity: It is the amount of memory space required by an
algorithm, during a course of its execution. Space complexity is required in
situations when limited memory is available and for the multi user system.

Abstract Data Types (ADT)

1. The Abstract data type is special kind of data type, whose behavior is
defined by a set of values and set of operations.
2. The keyword “Abstract” is used as we can use these data types, we can
perform different operations. But how those operations are working that is
 totally hidden from the user. The ADT is made of with primitive data types,
but operation logics are hidden.
3. The definition of ADT only mentions what operations are to be performed
but not how these operations will be implemented.
4. It does not specify how data will be organized in memory and what
algorithms will be used for implementing the operations.
5. It is called “abstract” because it gives an implementation-independent view.
The process of providing only the essentials and hiding the details is known
as abstraction.

Difference Between Primitive and Non-Primitive Data Structure

Primitive data structure Non Primitive Data structure

Non-Primitive data structure is a data structure

Primitive data structure is the data structure that allows
that allows you to store multiple data type
you to store only single data type values.
values.

integer, boolean, character, float, etc. are some Array, Linked List, Stack, etc. are some examples
examples of primitive data structures. of non-primitive data structures.

Primitive data structure always contains some value i.e.

You can store a NULL value in the non-primitive
these data structures do not allow you to store NULL
data structures.
values.

The size of the primitive data structures is dependent on The size of the non-primitive data structure is
the type of the primitive data structure. not fixed.

Difference Between Linear Data structure and Non-Linear Data

Structure

Sr. Key Linear Data Structures Non-linear Data Structures

No.
Sr. Key Linear Data Structures Non-linear Data Structures
No.

Data Element In linear data structure, data In non-linear data structure,

Arrangement elements are sequentially data elements are
1 connected and each element hierarchically connected and
is traversable through a single are present at various levels.
run.

Levels In linear data structure, all In non-linear data structure,

2 data elements are present at a data elements are present at
single level. multiple levels.

Implementation Linear data structures are Non-linear data structures

complexity easier to implement. are difficult to understand
3
and implement as compared
to linear data structures.

Traversal Linear data structures can be Non-linear data structures

traversed completely in a are not easy to traverse and
4
single run. needs multiple runs to be
traversed completely.

Memory Linear data structures are not Non-linear data structures

utilization very memory friendly and are uses memory very efficiently.
5
not utilizing memory
efficiently.

Time Time complexity of linear data Time complexity of non-

6 Complexity structure often increases with linear data structure often
increase in size. remain with increase in size.

7 Examples Array, List, Queue, Stack. Graph, Map, Tree.