Downloaded from be.rgpvnotes.in
Subject Notes
CS-302 – Data Structure
Unit -1
REVIEW OF C PROGRAMMING LANGUAGE:
C is a general-purpose, imperative computer programming language, supporting structured programming,
lexical variable scope and recursion, while a static type system prevents many unintended operations. By
design, C provides constructs that map efficiently to typical machine instructions, and therefore it has found
lasting use in applications that had formerly been coded in assembly language, including operating systems, as
well as various application software for computers ranging from supercomputers to embedded systems.
C was originally developed by Dennis Ritchie between 1969 and 1973 at Bell Labs.C is an imperative
procedural language. It was designed to be compiled using a relatively straightforward compiler, to provide
low-level access to memory, to provide language constructs that map efficiently to machine instructions, and
to require minimal run-time support.
INTRODUCTION:
Computer Science is the study of data, its representation and transformation by Computer. For every data
object, we consider the class of operations to be performed and then the way to represent the object so that
Devise alternative forms of data representation
these operations may be efficiently carried out. We require two techniques for this:
Analyse the algorithm which operates on the structure.
These are several terms involved above which we need to know carefully before we proceed. These include
data structure, data type and data representation.
A data type is a term which refers to the kinds of data that variables may hold. With every programming
language there is a set of built-in data types. This means that the language allows variables to name data of
that type and provides a set of operations which meaningfully manipulates these variables. Some data types
are easy to provide because they are built-i i to the o puter s a hi e la guage i stru tio set, such as
integer, character etc. Other data types require considerably more efficient to implement. In some languages,
these are features which allow one to construct combinations of the built-in types like stru tures i C .
However, it is necessary to have such mechanism to create the new complex data types which are not
provided by the programming language. The new type also must be meaningful for manipulations. Such
meaningful data types are referred as abstract data type.
DATA STRUCTURE:
Data Structures are the programmatic way of storing data so that data can be used efficiently. Almost every
enterprise application uses various types of data structures in one or the other way.
Thus, a data structure is the portion of memory allotted for a model, in which the required data can
be arranged in a proper fashion.:Data Structure is a way of collecting and organising data in such a way that
we can perform operations on these data in an effective way. Data Structures is about rendering data
elements in terms of some relationship, for better organization and storage. For example, we have data
player's name "Virat" and age 26. Here "Virat" is of String data type and 26 is of integer data type.
Programming: Programming is the process of taking an algorithm and encoding it into a notation, a
programming language, so that it can be executed by a computer. Although many programming languages and
many different types of computers exist, the important first step is the need to have the solution. Without an
Page no: 1 Follow us on facebook to get real-time updates from RGP
,Downloaded from be.rgpvnotes.in
algorithm there can be no program.Computer science is not the study of programming. Programming,
however, is an important part of what a computer scientist does. Programming is often the way that we create
a representation for our solutions. Therefore, this language representation and the process of creating it
becomes a fundamental part of the discipline.
CONCEPTS OF DATA AND INFORMATION:
Data: Data are simply values or set of values. A data item refers to a single unit of item.
Information: Information is any entity or form that provides the answer to a question of some kind or resolves
uncertainty. It is thus related to data and knowledge, as data represents values attributed to parameters, and
knowledge signifies understanding of real things or abstract concepts.
CLASSIFICATION OF DATA STRUCTURES: -
Figure 1.1: Classification of Data Structure
A data structure can be broadly classified into
(i) Built-in/Primitive data structure
(ii) User Defined/Non-primitive data structure
(i)Primitive data structure
The data structures, typically those data structure that are directly operated upon by machine level
i stru tio s i.e. the fu da e tal data types su h as i t, float, dou le i ase of are k o as primitive data
structures.
(ii) Non-primitive data structure
The data structures, which are not primitive, are called non-primitive data structures.
There are two types of non-primitive data structures.
Linear Data Structures:-
A list, which shows the relationship of adjacency between elements, is said to be linear data structure. The
most, simplest linear data structure is a 1-D array, but because of its deficiency, list is frequently used for
different kinds of data.
Page no: 2 Follow us on facebook to get real-time updates from RGP
,Downloaded from be.rgpvnotes.in
Non-linear data structure:-
A list, hi h does t sho the relatio ship of adja e y et ee ele e ts, is said to e o -linear data
structure.
Linear Data Structure:
A list is an ordered list, which consists of different data items connected by means of a link or pointer. This
Single linked list: - A single linked list is used to traverse among the nodes in one direction.
type of list is also called a linked list. A linked list may be a single list or double linked list.
Double linked list: - A double linked list is used to traverse among the nodes in both the directions.
A linked list is normally used to represent any data used in word-processing applications, also applied in
different DBMS packages.
Stack: - It is also called as last-in-first-out (LIFO) system. It is a linear list in which insertion and deletion take
A list has two subsets. They are: -
Queue: - It is also called as first-in-first-out (FIFO) system. It is a linear list in which insertion takes place at
place only at one end. It is used to evaluate different expressions.
once end and deletion takes place at other end. It is generally used to schedule a job in operating systems
and networks.
Non-linear data structure:-
The frequently used non-linear data structures are
Trees: - It maintains hierarchical relationship between various elements
Graphs: - It maintains random relationship or point-to-point relationship between various elements.
The data structures can also be classified on the basis of the following characteristics:
ABSTRACT DATA TYPES:
Abstract Data type (ADT) is a type or class for objects whose behavior is defined by a set of value and a set of
operations.ADT only mentions what operations are to be performed but not how these operations will be
implemented. It does not specify how data will be organized in memory and what algorithms will be used for
i ple e ti g the operatio s. It is alled a stra t e ause it gi es a i ple e tatio i depe de t ie . The
process of providing only the essentials and hiding the details is known as abstraction.
Example: Stack, Queue etc.
IMPLEMENTATION ASPECTS:
MEMORY REPRESENTATION:
There are 2 types of memory allocations possible in C:
Compile time or static allocation
Runtime or Dynamic allocation
1. Compile time or static allocation: Compile time memory allocation means reserving memory for variables,
constants during the compilation process. So you must exactly know how many bytes you require? This
type of allocation is done with the help of Array.The biggest disadvantage of compile time memory
allocation, we do not have control on allocated memory. You cannot increase, decrease or free memory,
the compiler takes care of memory management. We can also refer compile time memory allocation as
static or stack memory allocation.
2. Runtime or Dynamic allocation: Memory allocated at runtime either through malloc(),calloc() or
realloc().You can also refer runtime memory allocation as dynamic or heap memory allocation. Professional
Page no: 3 Follow us on facebook to get real-time updates from RGP
, Downloaded from be.rgpvnotes.in
programmers prefer dynamic memory allocation more over static memory allocation. Since, we have full
control over the allocated memory. Which means we can allocate, de-allocate and can also reallocate
memory when needed.
a. malloc():allocates requested size of bytes and return a void pointer pointing to the first byte the
allocated space.
Syntax: malloc (no. of elements* size of each element);
For example:
int *ptr;
ptr=(int*)malloc(10*sizeof(int));
b. calloc(): allocate space for an array of element and initialize them to zero and then return a void
pointer to memory.
Syntax: malloc (no. of elements, size of data type);
For example:
int *ptr;
ptr=(int*)calloc(10,2);
c. realloc(): modify the size of previously allocated space.
Syntax: ptr=realloc(ptr,newsize);
d. free(): releases previously allocated memory.
Global variable, static variable and program instruction get their memory in permanent storage and
Memory Allocation Process:
The memory space between 2 regions is known as Heap area. This region is used for dynamic memory
where local variable are stored in memory area called stack.
allocation during execution of program. The sizes of heap keep changing.
OPERATION ON DATA STRUCTURESAND ITS COST ESTIMATION:
Insertion: - Insertion means adding new details or new node into the data structure.
The four major operations performed on data structures are:
Deletion: - Deletion means removing a node from the data structure.
Traversal: - Traversing means accessing each node exactly once so that the nodes of a data structure
Searching: - Searching means finding the location of node for a given key value.
can be processed. Traversing is also called as visiting.
Apart from the four operations mentioned above, there are two more operations occasionally performed on
Sorting: -Sorting means arranging the data in a particular order.
data structures. They are:
Merging: -Merging means joining two lists.
INTRODUCTION TO LINEAR DATA STRUCTURES:
ARRAYS:
Array is set of homogenous data items represented in contiguous memory locations using a common name
and sequence of indices starting from 0. Array is a simplest data structure that makes use of computed
address to locate its elements. An array size is fixed and therefore requires a fixed number of memory
locations.
Suppose A is an array of n elements and the starting address is given then the location and element I will be
LOC(Ai) = Base address of A + (i – 1) * W
Where W is the width of each element.
Page no: 4 Follow us on facebook to get real-time updates from RGP
Subject Notes
CS-302 – Data Structure
Unit -1
REVIEW OF C PROGRAMMING LANGUAGE:
C is a general-purpose, imperative computer programming language, supporting structured programming,
lexical variable scope and recursion, while a static type system prevents many unintended operations. By
design, C provides constructs that map efficiently to typical machine instructions, and therefore it has found
lasting use in applications that had formerly been coded in assembly language, including operating systems, as
well as various application software for computers ranging from supercomputers to embedded systems.
C was originally developed by Dennis Ritchie between 1969 and 1973 at Bell Labs.C is an imperative
procedural language. It was designed to be compiled using a relatively straightforward compiler, to provide
low-level access to memory, to provide language constructs that map efficiently to machine instructions, and
to require minimal run-time support.
INTRODUCTION:
Computer Science is the study of data, its representation and transformation by Computer. For every data
object, we consider the class of operations to be performed and then the way to represent the object so that
Devise alternative forms of data representation
these operations may be efficiently carried out. We require two techniques for this:
Analyse the algorithm which operates on the structure.
These are several terms involved above which we need to know carefully before we proceed. These include
data structure, data type and data representation.
A data type is a term which refers to the kinds of data that variables may hold. With every programming
language there is a set of built-in data types. This means that the language allows variables to name data of
that type and provides a set of operations which meaningfully manipulates these variables. Some data types
are easy to provide because they are built-i i to the o puter s a hi e la guage i stru tio set, such as
integer, character etc. Other data types require considerably more efficient to implement. In some languages,
these are features which allow one to construct combinations of the built-in types like stru tures i C .
However, it is necessary to have such mechanism to create the new complex data types which are not
provided by the programming language. The new type also must be meaningful for manipulations. Such
meaningful data types are referred as abstract data type.
DATA STRUCTURE:
Data Structures are the programmatic way of storing data so that data can be used efficiently. Almost every
enterprise application uses various types of data structures in one or the other way.
Thus, a data structure is the portion of memory allotted for a model, in which the required data can
be arranged in a proper fashion.:Data Structure is a way of collecting and organising data in such a way that
we can perform operations on these data in an effective way. Data Structures is about rendering data
elements in terms of some relationship, for better organization and storage. For example, we have data
player's name "Virat" and age 26. Here "Virat" is of String data type and 26 is of integer data type.
Programming: Programming is the process of taking an algorithm and encoding it into a notation, a
programming language, so that it can be executed by a computer. Although many programming languages and
many different types of computers exist, the important first step is the need to have the solution. Without an
Page no: 1 Follow us on facebook to get real-time updates from RGP
,Downloaded from be.rgpvnotes.in
algorithm there can be no program.Computer science is not the study of programming. Programming,
however, is an important part of what a computer scientist does. Programming is often the way that we create
a representation for our solutions. Therefore, this language representation and the process of creating it
becomes a fundamental part of the discipline.
CONCEPTS OF DATA AND INFORMATION:
Data: Data are simply values or set of values. A data item refers to a single unit of item.
Information: Information is any entity or form that provides the answer to a question of some kind or resolves
uncertainty. It is thus related to data and knowledge, as data represents values attributed to parameters, and
knowledge signifies understanding of real things or abstract concepts.
CLASSIFICATION OF DATA STRUCTURES: -
Figure 1.1: Classification of Data Structure
A data structure can be broadly classified into
(i) Built-in/Primitive data structure
(ii) User Defined/Non-primitive data structure
(i)Primitive data structure
The data structures, typically those data structure that are directly operated upon by machine level
i stru tio s i.e. the fu da e tal data types su h as i t, float, dou le i ase of are k o as primitive data
structures.
(ii) Non-primitive data structure
The data structures, which are not primitive, are called non-primitive data structures.
There are two types of non-primitive data structures.
Linear Data Structures:-
A list, which shows the relationship of adjacency between elements, is said to be linear data structure. The
most, simplest linear data structure is a 1-D array, but because of its deficiency, list is frequently used for
different kinds of data.
Page no: 2 Follow us on facebook to get real-time updates from RGP
,Downloaded from be.rgpvnotes.in
Non-linear data structure:-
A list, hi h does t sho the relatio ship of adja e y et ee ele e ts, is said to e o -linear data
structure.
Linear Data Structure:
A list is an ordered list, which consists of different data items connected by means of a link or pointer. This
Single linked list: - A single linked list is used to traverse among the nodes in one direction.
type of list is also called a linked list. A linked list may be a single list or double linked list.
Double linked list: - A double linked list is used to traverse among the nodes in both the directions.
A linked list is normally used to represent any data used in word-processing applications, also applied in
different DBMS packages.
Stack: - It is also called as last-in-first-out (LIFO) system. It is a linear list in which insertion and deletion take
A list has two subsets. They are: -
Queue: - It is also called as first-in-first-out (FIFO) system. It is a linear list in which insertion takes place at
place only at one end. It is used to evaluate different expressions.
once end and deletion takes place at other end. It is generally used to schedule a job in operating systems
and networks.
Non-linear data structure:-
The frequently used non-linear data structures are
Trees: - It maintains hierarchical relationship between various elements
Graphs: - It maintains random relationship or point-to-point relationship between various elements.
The data structures can also be classified on the basis of the following characteristics:
ABSTRACT DATA TYPES:
Abstract Data type (ADT) is a type or class for objects whose behavior is defined by a set of value and a set of
operations.ADT only mentions what operations are to be performed but not how these operations will be
implemented. It does not specify how data will be organized in memory and what algorithms will be used for
i ple e ti g the operatio s. It is alled a stra t e ause it gi es a i ple e tatio i depe de t ie . The
process of providing only the essentials and hiding the details is known as abstraction.
Example: Stack, Queue etc.
IMPLEMENTATION ASPECTS:
MEMORY REPRESENTATION:
There are 2 types of memory allocations possible in C:
Compile time or static allocation
Runtime or Dynamic allocation
1. Compile time or static allocation: Compile time memory allocation means reserving memory for variables,
constants during the compilation process. So you must exactly know how many bytes you require? This
type of allocation is done with the help of Array.The biggest disadvantage of compile time memory
allocation, we do not have control on allocated memory. You cannot increase, decrease or free memory,
the compiler takes care of memory management. We can also refer compile time memory allocation as
static or stack memory allocation.
2. Runtime or Dynamic allocation: Memory allocated at runtime either through malloc(),calloc() or
realloc().You can also refer runtime memory allocation as dynamic or heap memory allocation. Professional
Page no: 3 Follow us on facebook to get real-time updates from RGP
, Downloaded from be.rgpvnotes.in
programmers prefer dynamic memory allocation more over static memory allocation. Since, we have full
control over the allocated memory. Which means we can allocate, de-allocate and can also reallocate
memory when needed.
a. malloc():allocates requested size of bytes and return a void pointer pointing to the first byte the
allocated space.
Syntax: malloc (no. of elements* size of each element);
For example:
int *ptr;
ptr=(int*)malloc(10*sizeof(int));
b. calloc(): allocate space for an array of element and initialize them to zero and then return a void
pointer to memory.
Syntax: malloc (no. of elements, size of data type);
For example:
int *ptr;
ptr=(int*)calloc(10,2);
c. realloc(): modify the size of previously allocated space.
Syntax: ptr=realloc(ptr,newsize);
d. free(): releases previously allocated memory.
Global variable, static variable and program instruction get their memory in permanent storage and
Memory Allocation Process:
The memory space between 2 regions is known as Heap area. This region is used for dynamic memory
where local variable are stored in memory area called stack.
allocation during execution of program. The sizes of heap keep changing.
OPERATION ON DATA STRUCTURESAND ITS COST ESTIMATION:
Insertion: - Insertion means adding new details or new node into the data structure.
The four major operations performed on data structures are:
Deletion: - Deletion means removing a node from the data structure.
Traversal: - Traversing means accessing each node exactly once so that the nodes of a data structure
Searching: - Searching means finding the location of node for a given key value.
can be processed. Traversing is also called as visiting.
Apart from the four operations mentioned above, there are two more operations occasionally performed on
Sorting: -Sorting means arranging the data in a particular order.
data structures. They are:
Merging: -Merging means joining two lists.
INTRODUCTION TO LINEAR DATA STRUCTURES:
ARRAYS:
Array is set of homogenous data items represented in contiguous memory locations using a common name
and sequence of indices starting from 0. Array is a simplest data structure that makes use of computed
address to locate its elements. An array size is fixed and therefore requires a fixed number of memory
locations.
Suppose A is an array of n elements and the starting address is given then the location and element I will be
LOC(Ai) = Base address of A + (i – 1) * W
Where W is the width of each element.
Page no: 4 Follow us on facebook to get real-time updates from RGP
