CS301 – Data Structures
___________________________________________________________________
Data Structures
Page 1 of 505
,CS301 – Data Structures
___________________________________________________________________
Table of Contents
Data Structures .......................................................................................................... 1
Lecture No. 01 ............................................................................................................ 3
Lecture No. 02 ........................................................................................................... 12
Lecture No. 03 .......................................................................................................... 20
Lecture No. 04 .......................................................................................................... 32
Lecture No. 05 .......................................................................................................... 46
Lecture No. 06 .......................................................................................................... 56
Lecture No. 07 .......................................................................................................... 63
Lecture No. 08 .......................................................................................................... 71
Lecture No. 09 .......................................................................................................... 82
Lecture No. 10 .......................................................................................................... 93
Lecture No. 11 ........................................................................................................ 105
Lecture No. 12 ........................................................................................................ 123
Lecture No. 13 ........................................................................................................ 135
Lecture No. 14 ........................................................................................................ 146
Lecture No. 15 ........................................................................................................ 158
Lecture No. 16 ........................................................................................................ 170
Lecture No. 17 ........................................................................................................ 189
Lecture No. 18 ........................................................................................................ 203
Lecture No. 19 ........................................................................................................ 211
Lecture No. 20 ........................................................................................................ 220
Lecture No. 21 ........................................................................................................ 231
Lecture No. 22 ........................................................................................................ 240
Lecture No. 23 ........................................................................................................ 257
Lecture No. 24 ........................................................................................................ 273
Lecture No. 25 ........................................................................................................ 284
Lecture No. 26 ........................................................................................................ 296
Lecture No. 27 ........................................................................................................ 307
Lecture No. 28 ........................................................................................................ 321
Lecture No. 29 ........................................................................................................ 333
Lecture No. 30 ........................................................................................................ 348
Lecture No. 31 ........................................................................................................ 360
Lecture No. 32 ........................................................................................................ 370
Lecture No. 33 ........................................................................................................ 379
Lecture No. 34 ........................................................................................................ 386
Lecture No. 35 ........................................................................................................ 393
Lecture No. 36 ........................................................................................................ 404
Lecture No. 37 ........................................................................................................ 416
Lecture No. 38 ........................................................................................................ 424
Lecture No. 39 ........................................................................................................ 430
Lecture No. 40 ........................................................................................................ 441
Lecture No. 41 ........................................................................................................ 449
Lecture No. 42 ........................................................................................................ 459
Lecture No. 43 ........................................................................................................ 468
Lecture No. 44 ........................................................................................................ 474
Lecture No. 45 ........................................................................................................ 485
Page 2 of 505
,CS301 – Data Structures Lecture No. 01
___________________________________________________________________
Data Structures
Lecture No. 01
Reading Material
Data Structures and algorithm analysis in C++ Chapter. 3
3.1, 3.2, 3.2.1
Summary
• Introduction to Data Structures
• Selecting a Data Structure
• Data Structure Philosophy
• Goals of this Course
• Array
• List data structure
Welcome to the course of data structure. This is very important subject as the topics
covered in it will be encountered by you again and again in the future courses. Due to
its great applicability, this is usually called as the foundation course. You have
already studied Introduction to programming using C and C++ and used some data
structures. The focus of that course was on how to carry out programming with the
use of C and C++ languages besides the resolution of different problems. In this
course, we will continue problem solving and see that the organization of data in
some cases is of immense importance. Therefore, the data will be stored in a special
way so that the required result should be calculated as fast as possible.
Following are the goals of this course:
Prepare the students for (and is a pre-requisite for) the more advanced material
students will encounter in later courses.
Cover well-known data structures such as dynamic arrays, linked lists, stacks,
queues, trees and graphs.
Implement data structures in C++
You have already studied the dynamic arrays in the previous course. We will now
discuss linked lists, stacks, queues, trees and graphs and try to resolve the problems
with the help of these data structures. These structures will be implemented in C++
language. We will also do programming assignments to see the usage and importance
of these structures.
Page 3 of 505
, CS301 – Data Structures Lecture No. 01
___________________________________________________________________
Information about Data Structure subject is available at: “http://www.vu.edu.pk/ds”.
Introduction to Data Structures
Let’s discuss why we need data structures and what sort of problems can be solved
with their use. Data structures help us to organize the data in the computer, resulting
in more efficient programs. An efficient program executes faster and helps minimize
the usage of resources like memory, disk. Computers are getting more powerful with
the passage of time with the increase in CPU speed in GHz, availability of faster
network and the maximization of disk space. Therefore people have started solving
more and more complex problems. As computer applications are becoming complex,
so there is need for more resources. This does not mean that we should buy a new
computer to make the application execute faster. Our effort should be to ensue that the
solution is achieved with the help of programming, data structures and algorithm.
What does organizing the data mean? It means that the data should be arranged in a
way that it is easily accessible. The data is inside the computer and we want to see it.
We may also perform some calculations on it. Suppose the data contains some
numbers and the programmer wants to calculate the average, standard deviation etc.
May be we have a list of names and want to search a particular name in it. To solve
such problems, data structures and algorithm are used. Sometimes you may realize
that the application is too slow and taking more time. There are chances that it may be
due to the data structure used, not due to the CPU speed and memory. We will see
such examples. In the assignments, you will also check whether the data structure in
the program is beneficial or not. You may have two data structures and try to decide
which one is more suitable for the resolution of the problem.
As discussed earlier, a solution is said to be efficient if it solves the problem within its
resource constraints. What does it mean? In the computer, we have hard disk, memory
and other hardware. Secondly we have time. Suppose you have some program that
solves the problem but takes two months. It will be of no use. Usually, you don’t have
this much time and cannot wait for two months. Suppose the data is too huge to be
stored in disk. Here we have also the problem of resources. This means that we have
to write programs considering the resources to achieve some solution as soon as
possible. There is always cost associated with these resources. We may need a faster
and better CPU which can be purchased. Sometimes, we may need to buy memory.
As long as data structures and programs are concerned, you have to invest your own
time for this. While working in a company, you will be paid for this. All these
requirements including computer, your time and computer time will decide that the
solution you have provided is suitable or not. If its advantages are not obtained, then
either program or computer is not good.
So the purchase of a faster computer, while studying this course, does not necessarily
help us in the resolution of the problem. In the course of “Computer Architecture”
you will see how the more efficient solutions can be prepared with the hardware. In
this course, we will use the software i.e. data structures, algorithms and the recipes
through which the computer problems may be resolved with a faster solution.
Page 4 of 505
___________________________________________________________________
Data Structures
Page 1 of 505
,CS301 – Data Structures
___________________________________________________________________
Table of Contents
Data Structures .......................................................................................................... 1
Lecture No. 01 ............................................................................................................ 3
Lecture No. 02 ........................................................................................................... 12
Lecture No. 03 .......................................................................................................... 20
Lecture No. 04 .......................................................................................................... 32
Lecture No. 05 .......................................................................................................... 46
Lecture No. 06 .......................................................................................................... 56
Lecture No. 07 .......................................................................................................... 63
Lecture No. 08 .......................................................................................................... 71
Lecture No. 09 .......................................................................................................... 82
Lecture No. 10 .......................................................................................................... 93
Lecture No. 11 ........................................................................................................ 105
Lecture No. 12 ........................................................................................................ 123
Lecture No. 13 ........................................................................................................ 135
Lecture No. 14 ........................................................................................................ 146
Lecture No. 15 ........................................................................................................ 158
Lecture No. 16 ........................................................................................................ 170
Lecture No. 17 ........................................................................................................ 189
Lecture No. 18 ........................................................................................................ 203
Lecture No. 19 ........................................................................................................ 211
Lecture No. 20 ........................................................................................................ 220
Lecture No. 21 ........................................................................................................ 231
Lecture No. 22 ........................................................................................................ 240
Lecture No. 23 ........................................................................................................ 257
Lecture No. 24 ........................................................................................................ 273
Lecture No. 25 ........................................................................................................ 284
Lecture No. 26 ........................................................................................................ 296
Lecture No. 27 ........................................................................................................ 307
Lecture No. 28 ........................................................................................................ 321
Lecture No. 29 ........................................................................................................ 333
Lecture No. 30 ........................................................................................................ 348
Lecture No. 31 ........................................................................................................ 360
Lecture No. 32 ........................................................................................................ 370
Lecture No. 33 ........................................................................................................ 379
Lecture No. 34 ........................................................................................................ 386
Lecture No. 35 ........................................................................................................ 393
Lecture No. 36 ........................................................................................................ 404
Lecture No. 37 ........................................................................................................ 416
Lecture No. 38 ........................................................................................................ 424
Lecture No. 39 ........................................................................................................ 430
Lecture No. 40 ........................................................................................................ 441
Lecture No. 41 ........................................................................................................ 449
Lecture No. 42 ........................................................................................................ 459
Lecture No. 43 ........................................................................................................ 468
Lecture No. 44 ........................................................................................................ 474
Lecture No. 45 ........................................................................................................ 485
Page 2 of 505
,CS301 – Data Structures Lecture No. 01
___________________________________________________________________
Data Structures
Lecture No. 01
Reading Material
Data Structures and algorithm analysis in C++ Chapter. 3
3.1, 3.2, 3.2.1
Summary
• Introduction to Data Structures
• Selecting a Data Structure
• Data Structure Philosophy
• Goals of this Course
• Array
• List data structure
Welcome to the course of data structure. This is very important subject as the topics
covered in it will be encountered by you again and again in the future courses. Due to
its great applicability, this is usually called as the foundation course. You have
already studied Introduction to programming using C and C++ and used some data
structures. The focus of that course was on how to carry out programming with the
use of C and C++ languages besides the resolution of different problems. In this
course, we will continue problem solving and see that the organization of data in
some cases is of immense importance. Therefore, the data will be stored in a special
way so that the required result should be calculated as fast as possible.
Following are the goals of this course:
Prepare the students for (and is a pre-requisite for) the more advanced material
students will encounter in later courses.
Cover well-known data structures such as dynamic arrays, linked lists, stacks,
queues, trees and graphs.
Implement data structures in C++
You have already studied the dynamic arrays in the previous course. We will now
discuss linked lists, stacks, queues, trees and graphs and try to resolve the problems
with the help of these data structures. These structures will be implemented in C++
language. We will also do programming assignments to see the usage and importance
of these structures.
Page 3 of 505
, CS301 – Data Structures Lecture No. 01
___________________________________________________________________
Information about Data Structure subject is available at: “http://www.vu.edu.pk/ds”.
Introduction to Data Structures
Let’s discuss why we need data structures and what sort of problems can be solved
with their use. Data structures help us to organize the data in the computer, resulting
in more efficient programs. An efficient program executes faster and helps minimize
the usage of resources like memory, disk. Computers are getting more powerful with
the passage of time with the increase in CPU speed in GHz, availability of faster
network and the maximization of disk space. Therefore people have started solving
more and more complex problems. As computer applications are becoming complex,
so there is need for more resources. This does not mean that we should buy a new
computer to make the application execute faster. Our effort should be to ensue that the
solution is achieved with the help of programming, data structures and algorithm.
What does organizing the data mean? It means that the data should be arranged in a
way that it is easily accessible. The data is inside the computer and we want to see it.
We may also perform some calculations on it. Suppose the data contains some
numbers and the programmer wants to calculate the average, standard deviation etc.
May be we have a list of names and want to search a particular name in it. To solve
such problems, data structures and algorithm are used. Sometimes you may realize
that the application is too slow and taking more time. There are chances that it may be
due to the data structure used, not due to the CPU speed and memory. We will see
such examples. In the assignments, you will also check whether the data structure in
the program is beneficial or not. You may have two data structures and try to decide
which one is more suitable for the resolution of the problem.
As discussed earlier, a solution is said to be efficient if it solves the problem within its
resource constraints. What does it mean? In the computer, we have hard disk, memory
and other hardware. Secondly we have time. Suppose you have some program that
solves the problem but takes two months. It will be of no use. Usually, you don’t have
this much time and cannot wait for two months. Suppose the data is too huge to be
stored in disk. Here we have also the problem of resources. This means that we have
to write programs considering the resources to achieve some solution as soon as
possible. There is always cost associated with these resources. We may need a faster
and better CPU which can be purchased. Sometimes, we may need to buy memory.
As long as data structures and programs are concerned, you have to invest your own
time for this. While working in a company, you will be paid for this. All these
requirements including computer, your time and computer time will decide that the
solution you have provided is suitable or not. If its advantages are not obtained, then
either program or computer is not good.
So the purchase of a faster computer, while studying this course, does not necessarily
help us in the resolution of the problem. In the course of “Computer Architecture”
you will see how the more efficient solutions can be prepared with the hardware. In
this course, we will use the software i.e. data structures, algorithms and the recipes
through which the computer problems may be resolved with a faster solution.
Page 4 of 505
