Data structures Lecture Notes Unit - I

UNIT – I
Introduction to Data Structures
1.1 Definition
 A data structure is an aggregation of atomic and composite data into a set with defined
relationships.
 Structure means a set of rules that holds data together
 Data structure can be nested
 We can have a data structure that consists of other data structures for ex, we can define the two
structures array and record as shown in table:
Array Record
Homogeneous sequence of data or data types Heterogeneous combination of data into a
known as elements single structure with an identified key
Position associated among the elements No association
Fig: Data structure examples
 Modern programming languages allow programmers to create new data structures for an
application.
Data structure
1. A combination of elements in which each is either a data type or another data structure
2. A set of associations or relationships (structure) involving the combined elements

Atomic and Composite data

 Atomic data are data that consist of a single piece of information; that is, they cannot be divided
into other meaningful pieces of data.
 The opposite of atomic data is composite data.
 Composite data can be broken into subfields that have meaning.
Data type
 A data type consists of two parts:
o A set of values
o A set of operations on values
 Table shows three data types found in all systems.
Type Values Operations
integer -∞, . . . , -2, -1, 0, 1, 2, . . . , ∞ *, +, -, %, /, ++, --, . . .
floating point -∞, . . . , 0.0, . . . , ∞ *, +, -, /, . . .
character \0, . . . , ‘A’, ‘B’, . . . , ‘a’, ‘b’, . . . , ~ <, >, . . .
Table: Three Data Types
1.2 Abstract Data Type
 When we first started programming, there were no abstract data types.
 If we wanted to read a file, we wrote the code to read the physical file device.
 It did not take long to realize that we were writing the same code over and over again.
 So we created what is known today as an abstract data type (ADT).
 We wrote the code to read a file and placed it in a library for all programmers to use.
 This concept is found in modern languages today.

1
Prepared by: G. B. Hima Bindu, Asst. Prof., Dept. of IT, SVCET, CTR
Data structures Lecture Notes Unit - I

 ADT users are not concerned with how the task is done but rather with what it can do.
 The ADT consists of a set of definitions that allow programmers to use the functions while hiding
the implementation.
 This generalization of operations with unspecified implementations is known as abstraction.
The concept of abstraction means:
1. We know what a data type can do.
2. How it is done is hidden.
 An abstract data type is a data declaration packaged together with the operations that are
meaningful for the data type.
 In other words, we encapsulate the data and the operations on the data, and then we hide
them from the user.
Abstract Data Type
1. Declaration of data
2. Declaration of operations
3. Encapsulation of data and operations
1.3 Classification of Data Structures:
 The data structure can be divided into two basic types: preliminary data structure and
secondary data structure.
 The primitive data structures are the basic data types such as int, char, float where the non
primitive data structures are the data structures which are basically derived from primitive data
structures.
 They can be further categorized into linear and non linear data structures.
 Linear data structures are the data structures in which the data is arranged in a list or a straight
sequence.
For ex: arrays, lists, stacks, queues
 Non linear data structures are the data structures in which data may be arranged in hierarchical
manner.
For ex: trees, graphs
Linear data structures:
Arrays:
An array is a group of homogeneous data which shares the same name.
List
 List is basically the collection of elements arranged in a sequential manner.
 In memory we can store the list in two ways –
o List of sequentially stored elements – using arrays
o List of elements with associated pointers – using linked lists
Stack
 A stack is a last in – first out (LIFO) data structure in which all insertions and deletions
are restricted to one end, called the top.
Queue

2
Prepared by: G. B. Hima Bindu, Asst. Prof., Dept. of IT, SVCET, CTR
Data structures Lecture Notes Unit - I

 A Queue is a list in which data can be inserted at one end, called the rear and deleted
from the other end, called the front. It is a first in first out(FIFO) restricted data
structure.
Non Linear data structures:
Trees
 A tree consists of a finite set of elements, called nodes, and a finite set of directed lines,
called branches that connect the nodes.
Graphs
 A graph is a collection of nodes, called vertices, and line segments , called arcs or edges,
that connect pairs of nodes.
1.4. Applications :
Data Structures applications are enormous. There primary purpose is to store the data most effectively.
So that they can easily accessible, modified. In most applications of data structures, we wish to perform
not just a single operations, possibly having correlated behaviour and are fundamentals of any software
application. Data Structures are used in our daily life and in many number of computer applications such
as,
 Searching
 Sorting
 Graph traversing
 Finding the shortest path from one city to another
 Resolving traffic problems
 In processing online requests or online transactions
 Alerting users of stock market prices
 Scheduling of jobs in operating systems
 Searching details of a student in a university data base
 File systems(trees)
 CPU scheduling and IO scheduling(queues)
 RAM is structured into a stack and heap
 Facebook uses trees for the sentiment analysis and other things that they do... and so on.

3
Prepared by: G. B. Hima Bindu, Asst. Prof., Dept. of IT, SVCET, CTR