Introduction to Data Structures Overview
Uploaded by
sangramgaikwad7704Introduction to Data Structures Overview
Uploaded by
sangramgaikwad7704Chap- 1
Introduction to Data Structures
1. Need for Data Structures
To solve a data processing problem, four things have to be identified:
[Link] data elements that are concerned with the problem.
[Link] operations that will be performed on these data elements.
[Link] of representing the data elements in memory to retain the logical relationship
between them.
4. The programming language which suits the current requirements.
Example: Calculating area of circle
1. The data elements are radius, pi and area.
[Link] operations performed on the above data elements are multiplication, assignment etc.
[Link] can be stored in memory as bits/bytes and the user can access them in different tortms.
Example: integer, float etc.
[Link] like Pascal, C, CH, etc. can be used to solve the above problem.
●Advantages of Data Structures are
[Link] data makes it easier to access and manipulate the information as compared to
raw or unstructured data.
2.A variety of operations can be performed on structured data.
[Link] data can be stored together and in the required format.
[Link] algorithms can be used on organized data-which improves program efficiency.
●Application Areas
[Link] Design
[Link] System
[Link] Management Systems
[Link] analysis
[Link] Analysis
[Link]
[Link] Intelligence
[Link]
[Link]
[Link]:
1. Data: Data is input given to a system, which the system processes.
*Two Types of data
i) Atomic data
ii) Composite data
i) Atomic data : Atomic data is a single , elementary piece of data,which cannot be further
decomposed ..
e.g the character 'a',number 10 [Link] atomic
ii) Composite data : Composite data is a grouped data item which consists of sub-field, each of
which is atomic. For example, a telephone number consists of sub fields like country code, city
code, and telephone number. The concept of a record in Pascal or structure in "C is composite
data.
[Link] Type :
i) Simple data type : These are the primitive or built-in data types supported by a language.
The variables of this type can 'hold' only one value of that type.
Example: int, char, float, char are the simple data types in "C"
ii) Derived data type : These types are derived or constructed from the fundamenl or basic
data types. These are arrays, structures, unions, files etc. For example, it we to store many
values of the same type, we will have to use an array
iii) User defined data type : These data types are created by thneprogramer many
programming languages provide the facility of defining our own data or rename an existing
data type.
For example: enum and typedef
enumDaysoOfWeek {Sun, Mon, Tue, Wed, Thu, Fri, Sat };
DaysofWeekoneday= Sun;
[Link] object : Data object refers to a set of elements (D) of a specific data type
Example : A set of integer numbers is infinite
D= {0,+-1,+-2… }
4. Data structure:
D - denotes the data objects
F- denotes the set of operations that can be carried out onthe data objects.
A- describes the properties and rules of the operations.
5. Abstract Data type : The ADT is a mathematical or conceptual definition of a data
structure. The data structuredefined above i.e. the triple {D, F, A} is called the Abstract Data
Type because it is simply a conceptual specification of the data structure.
[Link] of Data Structures
1) Logical Data Structure and Physical Data Structure :
●Logical Data Structure: The ADT is called the logical data structure because it simply specifies
the "logical properties" of the data type. Hence, it is just a mathematical or abstract concept,
which detines the data type.
● Physical Data Structure: A physical data structure is the implemented ADT which can be
used to store elements and perform operations.
2) Primitive and Non-primitive Data structure :
●Primitive data structures : consist of a single unit of information which do not contain any
Sub-parts. These are built-in data structures. The internal representation of the data object is
fixed for a specific machine and may vary from one to another.
Example: integer, float etc.
●Non-Primnitive : data structures are derived from primitive data structures. They are
composite in nature i.e. they are "composed" of several units of information. This structure iS
a group of similar or different data items. Example: int a[10];
3)Linear and Non-Linear Data structures :
●Linear: By linear, we mean 'in a line'. The elements of a linear data structure are arranged in
a line i.e. they form a sequence or a list. There is an ordering among them such that there is a
"first element, second and so on. Their mapping is one-dimensional. The elements have a one-
to-one relationship with other elements. Example: Array, Linked list.
A1 A2 -------- An
●Non-linear: In a non-linear data structure, the elements have a one to many relationship
between them. The elements do not form a specific sequence. Sometimes, we cannot full
represent the relationship between the elements using a linear representation. For example,
show the family tree or to represent intormation about a road network, we need a Non-Linear
structure. Example: Tree, Graph Computer
C D E
Notes Programs
Folder 1 DSF EDC
4)Static and Dynamic Data Structures :
●Static: A static data structure is one in which the number of data elements remains fixed
throughout the application. The size of the data structure does not change during the entire
program. The memory is allocated during compile-time and remains allocated even when
there are no elements in the data structurę. Example: Array
●Dynamic: In a dynamic data structure, the size of the data structure grows and shrinks
dynamically i.e. during run-time. In most real-time applications, we cannot predict the number
of elements in advance. Many applications require elements to be added and [Link] such
cases, the data structure grows as elements are added and shrinks as elements are removed
from the data structure. Dynamic memory allocation is required in this case.
Example: Stack, Queue, Linked List etc.
5)Sequential Organization and Linked Organization :
●Sequential Organization: In the sequential organization, successive data elements are stored
at a fixed distance. This means that if an element Ai is stored at location Li in memory, then
the element Ai+1 will be stored at location Li+c for some constant c.
A1 A2 …… An
Example: An array uses sequential organization.
●Linked Organization: In this'organization, the elements of the data structure can be stored at
any memory location but their sequence is maintained by linking the elements.
The physical location of the element does not determine it's position in the set of elements.
A1 A2 ------- An
Li Lj Lk
for example : A linked list uses linked organization.