Download Latest All
Books Midterm Past Papers virtual university of Pakistan
CS301 Handouts complete updated 2024 Download, We are providing the latest virtual
university Midterm Past Papers short notes in PDF to
facilitate students in their studies. Short Notes covered most of the main
topics from handouts and lectures.
“As you know, most students prepare these Midterm
Past Papers to clear concepts and study smart in an easy
way.
This note explains very importantly long and short questions, MCQS with their
answers, lecture concept, and details covered in provided short notes.
Short notes are arranged according to VU subjects. Easy to download yours
subjects most important short notes that help you in virtual university exams.
Dear
Students Here we Provided Virtual University All Books Short
Notes Assignment
Solutions PDF Updated & Highlighted at one place according to
subjects. Download the latest VU Handouts in your required
subject. Download virtual university all subjects Handouts, handouts mean
a document given to students that contains information about a particular
subject, so here I will provide you with Virtual University All Subjects
Handouts in PDF Format. But at this page you will get all subjects or
courses handouts. After a huge research, these handouts are designed to
help you people in such way that will help you to get more than 75%
marks Insha’Allah. DOWNLOAD THE Latest Vu Assignment Solutions
in your required subjects.
Table of Contents
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
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.
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.
Selecting a Data Structure
How can we select the data structure needed to solve a problem? You have already studied where to use array and the size of array and when and where to use the pointers etc. First of all, we have to analyze the problem to determine the resource constraints that a solution must meet. Suppose, the data is so huge i.e. in Gega bytes (GBs) while the disc space available with us is just 200 Mega bytes. This problem can not be solved with programming. Rather, we will have to buy a new disk.
Secondly, it is necessary to determine the basic operations that must be supported. Quantify the resource constraints for each operation. What does it mean? Suppose you have to insert the data in the computer or database and have to search some data item. Let’s take the example of telephone directory. Suppose there are eight million names in the directory. Now someone asks you about the name of some particular person. You want that this query should be answered as soon as possible. You may add or delete some data. It will be advisable to consider all these operations when you select some data structure.
Finally select the data structure that meets these requirements the maximum. Without, sufficient experience, it will be difficult to determine which one is the best data structure. We can get the help from internet, books or from someone whom you know for already getting the problems solved. We may find a similar example and try to use it. After this course, you will be familiar with the data structures and algorithms that are used to solve the computer problems.
Now you have selected the data structure. Suppose a programmer has inserted some data and wants to insert more data. This data will be inserted in the beginning of the existing data, or in the middle or in the end of the data. Let’s talk about the arrays and suppose you have an array of size hundred. Data may be lying in the first fifty locations of this array. Now you have to insert data in the start of this array. What will you do? You have to move the existing data (fifty locations) to the right so that we get space to insert new data. Other way round, there is no space in the start. Suppose you have to insert the data at 25th location. For this purpose, it is better to move the data from 26th to 50th locations; otherwise we will not have space to insert this new data at 25th location.
Now we have to see whether the data can be deleted or not. Suppose you are asked to delete the data at 27th position. How can we do that? What will we do with the space created at 27th position?
Thirdly, is all the data processed in some well-defined order or random access allowed? Again take the example of arrays. We can get the data from 0th position and traverse the array till its 50th position. Suppose we want to get the data, at first from 50th location and then from 13th. It means that there is no order or sequence. We want to access the data randomly. Random access means that we can’t say what will be the next position to get the data or insert the data.
Data Structure
Philosophy
Let’s talk about the philosophy of data structure. Each data structure has costs and benefits. Any data structure used in your program will have some benefits. For this,
you have to pay price. That can be computer resources or the time. Also keep in mind that you are solving this problem for some client. If the program is not efficient, the client will not buy it.
In rare cases, a data structure may be better than another one in all situations. It means that you may think that the array is good enough for all the problems. Yet this is not necessary. In different situations, different data structures will be suitable. Sometimes you will realize that two different data structures are suitable for the problem. In such a case, you have to choose the one that is more appropriate. An important skill this course is going to lend to the students is use the data structure according to the situation. You will learn the programming in a way that it will be possible to replace the one data structure with the other one if it does not prove suitable. We will replace the data structure so that the rest of the program is not affected. You will also have to attain this skill as a good programmer.
There are three basic things associated with data structures. A data structure requires:
– space for each data item it stores
– time to perform each basic operation
– programming effort
Goals of this Course
Reinforce the concept that costs and benefits exist for every data structure. We will learn this with practice.
Learn the commonly used data structures. These form a programmer's basic data structure “toolkit”. In the previous course, you have learned how to form a loop, functions, use of arrays, classes and how to write programs for different problems. In this course, you will make use of data structures and have a feeling that there is bag full of different data structures. In case of some problem, you will get a data structure from the toolkit and use some suitable data structure.
Understand how to measure the cost of a data structure or program. These techniques also allow you to judge the merits of new data structures that you or others might develop. At times, you may have two suitable data structures for some problem. These can be tried one by one to adjudge which one is better one. How can you decide which data structure is better than other. Firstly, a programmer can do it by writing two programs using different data structure while solving the same problem. Now execute both data structures. One gives the result before the other. The data structure that gives results first is better than the other one. But sometimes, the data grows too large in the problem. Suppose we want to solve some problem having names and the data of names grows to10 lakhs (one million). Now when you run both programs, the second program runs faster. What does it mean? Is the data structure used in program one not correct? This is not true. The size of the data, being manipulated in the program can grow or shrink. You will also see that some data structures are good for small data while the others may suit to huge data. But the problem is how can we determine that the data in future will increase or decrease. We should have some way to take decision in this regard. In this course we will do some mathematical analysis and see which data structure is better one.
Arrays
You have already studied about arrays and are well-versed with the techniques to utilize these data structures. Here we will discuss how arrays can be used to solve computer problems. Consider the following program:
main( int argc, char** argv )
{
int x[6]; int j;
for(j = 0; j < 6; j++)
x[j] = 2 * j;
}
We have declared an int array of six elements and initialized it in the loop.
Let’s revise some of the array concepts. The declaration of array is as int x[6]; or float x[6]; or double x[6]; You have already done these in your programming assignments. An array is collection of cells of the same type. In the above program, we have array x of type int of six elements. We can only store integers in this array. We cannot put int in first location, float in second location and double in third location. What is x? x is a name of collection of items. Its individual items are numbered from zero to one less than array size. To access a cell, use the array name and an index as under:
x[0], x[1], x[2], x[3], x[4], x[5]
To manipulate the first element, we will use the index zero as x[0] and so on. The arrays look like in the memory as follows:
Array cells are contiguous in computer memory
X[0]
|
X[2]
X[3]
X[4]
X[5]
Array occupies contiguous memory area in the computer. In case of the above example, if some location is assigned to x[0], the next location can not contain data other than x[1]. The computer memory can be thought of as an array. It is a very big array. Suppose a computer has memory of 2MB, you can think it as an array of size 2 million and the size of each item is 32 bits. You will study in detail about it in the computer organization, and Assembly language courses. In this array, we will put our programs, data and other things.
In the above program, we have declared an array named x. ‘x’ is an array’s name but there is no variable x. ‘x’ is not an lvalue. If some variable can be written on the left- hand side of an assignment statement, this is lvalue variable. It means it has some memory associated with it and some value can be assigned to it. For example, if we have the code int a, b; it can be written as b = 2; it means that put 2 in the memory location named b. We can also write as a = b; it means whatever b has assign it to a, that is a copy operation. If we write as a = 5; it means put the number 5 in the memory location which is named as a. But we cannot write 2 = a; that is to put at number 2 what ever the value of a is. Why can’t we do that? Number 2 is a constant. If we allow assignment to constants what will happen? Suppose ‘a’ has the value number 3. Now we assigned number 2 the number 3 i.e. all the number 2 will become number 3 and the result of 2 + 2 will become 6. Therefore it is not allowed.
‘x’ is a name of array and not an lvalue. So it cannot be used on the left hand side in an assignment statement. Consider the following statements
int x[6]; int n;
x[0] = 5; x[1] = 2;
x = 3; //not allowed
x = a + b; // not allowed
x = &n; // not allowed
In the above code snippet, we have
declared an array x of int. Now we can assign values
to the elements of x as
x[0] = 5 or x[1] = 2 and so on. The last three statements are not allowed. What does the statement x = 3; mean? As x is a name of array and this statement is not clear, what we are trying
to do here? Are we trying to assign 3 to each element of the array? This statement
is not clear. Resultantly, it can not be allowed.
The statement x = a + b is also
not allowed. There is nothing
wrong with a
+ b. But we cannot assign the sum of values of a and b to x. In the statement x = &n, we are trying to assign the memory address of n to x which is not allowed. The reason is the name x is not lvalue and we cannot assign any value to it. For understanding purposes, consider x as a constant. Its name or memory location can not be changed. This is a collective name for six locations. We can access these locations as x[0], x[1] up to x[5]. This is the way arrays are manipulated.
Sometimes, you would like to use an array data structure but may lack the information about the size of the array at compile time. Take the example of telephone directory. You have to store one lakh (100,000) names in an array. But you never know that the number of entries may get double or decline in future. Similarly, you can not say that the total population of the country is one crore (10 million) and declare an array of one crore names. You can use one lakh locations now and remaining will be used as the need arrives. But this is not a good way of using the computer resources. You have declared a very big array while using a very small chunk of it. Thus the remaining space goes waste which can, otherwise, be used by some other programs. We will see what can be the possible solution of this problem?
Suppose you need an integer array of size n after the execution of the program. We have studied that if it is known at the execution of the program that an array of size 20 or 30 is needed, it is allocated dynamically. The programming statement is as follows:
int* y = new int[20];
It means we are requesting computer to find twenty memory locations. On finding it, the computer will give the address of first location to the programmer which will be stored in y. Arrays locations are contiguous i.e. these are adjacent. These twenty locations will be contiguous, meaning that they will be neighbors to each other. Now y has become an array and we can say y[0] =1 or y[5] = 15. Here y is an lvalue. Being a pointer, it is a variable where we can store the address of some variable. When we said int* y = new int[20]; the new returns the memory address of first of the twenty locations and we store that address into y. As y is a pointer variable, so it can be used on the left-hand side. We can write it as:
y = &x[0];
In the above statement, we get the address of the fist location of the array x and store it in y. As y is lvalue, so it can be used on left hand side. This means that the above statement is correct.
y = x;
Similarly, the statement y = x is also correct. x is an array of six elements that holds the address of the first element. But we cannot change this address. However we can get that address and store it in some other variable. As y is a pointer variable and lvalue so the above operation is legal. We have dynamically allocated the memory for the array. This memory, after the use, can be released so that other programs can use it. We can use the delete keyword to release the memory. The syntax is:
delete[ ] y;
We are releasing the memory, making it available for use by other programs. We will not do it in case of x array, as ‘new’ was not used for its creation. So it is not our responsibility to delete x.
List data structure
This is a new data structure for you. The List data structure is among the most generic of data structures. In daily life, we use shopping list, groceries list, list of people to invite to a dinner, list of presents to give etc. In this course, we will see how we use lists in programming.
A list is the collection of items of the same type (grocery items, integers, names). The data in arrays are also of same type. When we say int x[6]; it means that only the integers can be stored in it. The same is true for list. The data which we store in list should be of same nature. The items, or elements of the list, are stored in some particular order. What does this mean? Suppose in the list, you have the fruit first which are also in some order. You may have names in some alphabetical order i.e. the names which starts with A should come first followed by the name starting with B and so on. The order will be reserved when you enter data in the list.
It is possible to insert new elements at various positions in the list and remove any
element of the list. You have done the same thing while dealing with arrays. You enter the data in the array, delete data from the array. Sometimes the array size grows and at times, it is reduced. We will do this with the lists too.
List is a set of elements in a linear order. Suppose we have four names a1, a2, a3, a4 and their order is as (a3, a1, a2, a4) i.e. a3, is the first element, a1 is the second element, and so on. We want to maintain that order in the list when data is stored in the list. We don’t want to disturb this order. The order is important here; this is not just a random collection of elements but an ordered one. Sometimes, this order is due to sorting i.e. the things that start with A come first. At occasions, the order may be due to the importance of the data items. We will discuss this in detail while dealing with the examples.
Now we will see what kind of operations a programmer performs with a list data structure. Following long list of operations may help you understand the things in a comprehensive manner.
Operation Name |
Description |
createList() |
Create a new list (presumably empty) |
copy() |
Set one list to be a copy of another |
clear(); |
Clear a list (remove all elements) |
insert(X, ?) |
Insert element X at a particular position in the list |
remove(?) |
Remove element at some position in the list |
get(?) |
Get element at a given position |
update(X, ?) |
Replace the element at a given position with X |
find(X) |
Determine if the element X is in the list |
length() |
Returns the length of the list. |
createList() is a function which creates a new list. For example to create an array, we use int x[6] or int* y = new int[20]; we need similar functionality in lists too. The copy() function will create a copy of a list. The function clear() will remove all the elements from a list. We want to insert a new element in the list, we also have to tell where to put it in the list. For this purpose insert(X, position) function is used. Similarly the function remove(position) will remove the element at position. To get an element from the list get(position) function is used which will return the element at position. To replace an element in the list at some position the function update(X, position) is used. The function find(X) will search X in the list. The function length() tells us about the number of elements in the list.
We need to know what is meant by “particular position” we have used “?” for this in the above table. There are two possibilities:
§ Use the actual index of element: i.e. insert it after element 3, get element number 6. This approach is used with arrays
§ Use a “current” marker or pointer to refer to a particular position in the list.
The first option is used in the data structures like arrays. When we have to manipulate the arrays, we use index like x[3], x[6]. In the second option we do not use first, second etc for position but say wherever is the current pointer. Just think of a pointer in the list that we can move forward or backward. When we say get, insert or update
while using the current pointer, it means that wherever is the current pointer, get data from that position, insert data after that position or update the data at that position. In this case, we need not to use numbers. But it is our responsibility that current pointer is used in a proper way.
If we use the “current” marker, the following four methods would be useful:
Functions |
Description |
start() |
Moves the “current” pointer to the very first element |
tail() |
Moves the “current” pointer to the very last element |
next() |
Move the current position forward one element |
back() |
Move the current position backward one element |
In the next lecture, we will discuss the implementation of the list data structure and write the functions discussed today, in C++ language.
Data Structures Lecture No. 02
Reading Material
Data Structures and Algorithm Analysis in C++ Chapter. 3
Summary
3.1, 3.2, 3.2.1, 3.2.2
1) List Implementation
· add Method
· next Method
· remove Method
· find Method
· Other Methods
2) Analysis Of Array List
3) List Using Linked Memory
4) Linked List
Today, we will discuss the concept of list operations. You may have a fair idea of ‘ start operation’ that sets the current pointer to the first element of the list while the tail operation moves the current pointer to the last element of the list. In the previous lecture, we discussed the operation next that moves the current pointer one element forward. Similarly, there is the ‘back operation’ which moves the current pointer one element backward.
List Implementation
Now we will see what the implementation of the list is and how one can create a list in C++. After designing the interface for the list, it is advisable to know how to implement that interface. Suppose we want to create a list of integers. For this purpose, the methods of the list can be implemented with the use of an array inside. For example, the list of integers (2, 6, 8, 7, 1) can be represented in the following manner where the current position is 3.
A |
2 |
6 |
8 |
7 |
1 |
|
|
|
current |
size |
|
1 |
2 |
3 |
4 |
5 |
|
|
|
3 |
5 |
In this case, we start the index of the array from 1 just for simplification against the usual practice in which the index of an array starts from zero in C++. It is not necessary to always start the indexing from zero. Sometimes, it is required to start the indexing from 1. For this, we leave the zeroth position and start using the array from index 1 that is actually the second position. Suppose we have to store the numbers from 1 to 6 in the array. We take an array of 7 elements and put the numbers from the
index 1. Thus there is a correspondence between index and the numbers stored in it. This is not very useful. So, it does not justify the non-use of zeroth position of the array out-rightly. However for simplification purposes, it is good to use the index from 1.
add Method
Now we will talk about adding an element to the list. Suppose there is a call to add an element in the list i.e. add(9). As we said earlier that the current position is 3, so by adding the element 9 to the list, the new list will be (2, 6, 8, 9, 7, 1).
To add the new element (9) to the list at the current position, at first, we have to make space for this element. For this purpose, we shift every element on the right of 8 (the current position) to one place on the right. Thus after creating the space for new element at position 4, the array can be represented as
A |
2 |
6 |
8 |
|
7 |
1 |
|
|
current |
size |
|
1 |
2 |
3 |
4 |
5 |
|
|
|
3 |
5 |
Now in the second step, we put the element 9 at the empty space i.e. position 4. Thus the array will attain the following shape. The figure shows the elements in the array in the same order as stored in the list.
A |
2 |
6 |
8 |
9 |
7 |
1 |
|
|
current |
size |
|
1 |
2 |
3 |
4 |
5 |
6 |
|
|
4 |
6 |
We have moved the current position to 4 while increasing the size to 6. The size shows that the elements in the list. Where as the size of the array is different that we have defined already to a fixed length, which may be 100, 200 or even greater.
next Method
Now let’s see another method, called ‘next’. We have talked that the next method moves the current position one position forward. In this method, we do not add a new element to the list but simply move the pointer one element ahead. This method is required while employing the list in our program and manipulating it according to the requirement. There is also an array to store the list in it. We also have two variables- current and size to store the position of current pointer and the number of elements in the list. By looking on the values of these variables, we can find the state of the list
i.e. how many elements are in the list and at what position the current pointer is.
The method next is used to know about the boundary conditions of the list i.e. the array being used by us to implement the list. To understand the boundary conditions, we can take the example of an array of size 100 to implement the list. Here, 100 elements are added to the array. Let’s see what happens when we want to add 101st element to the array? We used to move the current position by next method and reached the 100th position. Now, in case of moving the pointer to the next position (i.e. 101st), there will be an error as the size of the array is 100, having no position after this point. Similarly if we move the pointer backward and reach at the first position regardless that the index is 0 or 1. But what will happen if we want to move backward from the first position? These situations are known as boundary conditions and need attention during the process of writing programs when we write the code to use the list. We will take care of these things while implementing the list in C++
programs.
remove Method
A |
2 |
6 |
8 |
9 |
|
1 |
|
|
current |
size |
|
1 |
2 |
3 |
4 |
5 |
6 |
|
|
5 |
5 |
A |
2 |
6 |
8 |
9 |
1 |
|
|
|
current |
size |
|
1 |
2 |
3 |
4 |
5 |
|
|
|
5 |
5 |
find Method
Now lets talk about a function, used to find a specific
element in the array. The find
(x) function is used to find a specific element in the array. We pass the element, which is to be found, as an argument to the find function. This function then traverses the array until the specific element is found. If the element is found, this function sets the current position to it and returns 1 i.e. true. On the other hand, if the element is not found, the function returns 0 i.e. false. This indicates that the element was not found. Following is the code of this find(x) function in C++.
int find (int x)
{
int j ;
for (j = 1; j < size + 1; j++ )
if (A[j] == x )
break ;
if ( j < size + 1) // x is found
{
current = j ; //current points to the position where x found return 1 ; // return true
}
return 0 ; //return false, x is not found
}
In the above code, we execute a for loop to traverse the array. The number of execution of this loop is equal to the size of the list. This for loop gets terminated when the value of loop variable (j) increases from the size of the list. However we terminate the loop with the break statement if the element is found at a position. When the control comes out from the loop, we check the value of j. If the value of j is less than the size of the array, it means that the loop was terminated by the break statement. We use the break statement when we find the required element (x) in the list. The execution of break statement shows that the required element was found at the position equal to the value of j. So the program sets the current position to j and comes out the function by returning 1 (i.e. true). If the value of j is greater than the size of the array, it means that the whole array has traversed and the required element is not found. So we simply return 0 (i.e. false) and come out of the function.
Other Methods
There are some other methods to implement the list using an array. These methods are very simple, which perform their task just in one step (i.e. in one statement). There is a get() method , used to get the element from the current position in the array. The syntax of this function is of one line and is as under
return A[current] ;
This statement returns the element to which the current is pointing to (i.e. the current position) in the list A.
Another function is update(x). This method is used to change (set) the value at the current position. A value is passed to this method as an argument. It puts that value at the current position. The following statement in this method carries out this process.
A [current] = x ;
Then there is a method length( ).This method returns the size of the list. The syntax of this method is
return size ;
You may notice here that we are returning the size of the list and not the size of the array being used internally to implement the list. This size is the number of the elements of the list, stored in the array.
The back() method decreases the value of variable current by 1. In other words, it moves the current position one element backward. This is done by writing the statement.
current -- ;
The -- is a decrement operator in C++ that decreases the value of the operand by one. The above statement can also be written as
current = current -1 ;
The start() method sets the current position to the first element of the list. We know that the index of the array starts from 0 but we use the index 1 for the starting position. We do not use the index zero. So we set the current position to the first element by writing
current = 1 ;
Similarly, the end() method sets the current position to the last element of the list i.e.
size. So we write
current = size ;
Analysis of Array List
Now we analyze the implementation of the list while using an array internally. We analyze different methods used for the implementation of the list. We try to see the level upto which these are efficient in terms of CPU’s time consumption. Time is the major factor to see the efficiency of a program.
Add
First of all, we have talked about the add method. When we add an element to the list, every element is moved to the right of the current position to make space for the new element. So, if the current position is the start of the list and we want to add an element in the beginning, we have to shift all the elements of the list to the right one place. This is the worst case of adding an element to the list. Suppose if the size of the list is 10000 or 20000, we have to do the shift operation for all of these 10000 or 20000 elements. Normally, it is done by shifting of elements with the use of a for loop. This operation takes much time of the CPU and thus it is not a good practice to add an element at the beginning of a list. On the other hand, if we add an element at the end of the list, it can be done by carrying out ‘no shift operation’. It is the best case of adding an element to the list. However, normally we may have to move half of the elements. The usage of add method is the matter warranting special care at the time of implementation of the list in our program. To provide the interface of the list, we just define these methods.
Remove
When we remove an element at the current position in the list, its space gets empty. The current pointer remains at the same position. To fill this space, we shift the elements on the right of this empty space one place to the left. If we remove an element from the beginning of the list, then we have to shift the entire remaining elements one place to the left. Suppose there is a large number of elements, say 10000 or 20000, in the list. We remove the first element from the list. Now to fill this space, the remaining elements are shifted (that is a large number). Shifting such a large number of elements is time consuming process. The CPU takes time to execute the for loop that performs this shift operation. Thus to remove an element at the beginning of the list is the worst case of remove method. However it is very easy to remove an
element at the end of the list. In average cases of the remove method we expect to shift half of the elements. This average does not mean that in most of the cases, you will have to shift half the elements. It is just the average. We may have to shift all the elements in one operation (if we remove at the beginning) and in the second operation, we have to shift no element (if we remove at the end). Similarly, in certain operations, we have to shift just 10, 15 elements.
Find
We have discussed that the find method takes an element and traverses the list to find that element. The worst case of the find method is that it has to search the entire list from beginning to end. So, it finds the element at the end of the array or the element is not found. On average the find method searches at most half the list.
The other methods get (), length () etc are one-step methods. They carry out their operation in one instruction. There is no need of any loop or other programming structures to perform the task. The get() method gets the value from the specified position just in one step. Similarly the update() method sets a value at the specific position just in one-step. The length () method returns the value of the size of the list. The other methods back(), start() and end() also perform their tasks only in one step.
List using Linked Memory
We have seen the implementation of the list with the use of an array. Now we will discuss the implementation of the list while using linked memory. In an array, the memory cells of the array are linked with each other. It means that the memory of the array is contiguous. In an array, it is impossible that one element of the array is located at a memory location while the other element is located somewhere far from it in the memory. It is located in very next location in the memory. It is a property of the array that its elements are placed together with one another in the memory. Moreover, when we have declared the size of the array, it is not possible to increase or decrease it during the execution of the program. If we need more elements to store in the array, there is need of changing its size in the declaration. We have to compile the program again before executing it. Now array will be of the new size. But what happens if we again need to store more elements? We will change the code of our program to change the declaration of the array while recompiling it.
Suppose we have used the dynamic memory allocation and created an array of 100 elements with the use of new operator. In case of need of 200 elements, we will release this array and allocate a new array of 200 elements. Before releasing the previous array, it will wise to copy its elements to the new array so that it does not lose any information. Now this new array is in ‘ready for use’ position. Thus the procedure of creating a new array is not an easy task.
To avoid such problems, usually faced by the programmers while using an array, there is need of using linked memory in which the various cells of memory, are not located continuously. In this process, each cell of the memory not only contains the value of the element but also the information where the next element of the list is residing in the memory. It is not necessary that the next element is at the next location in the memory. It may be anywhere in the memory. We have to keep a track of it. Thus, in this way, the first element must explicitly have the information about the location of the second element. Similarly, the second element must know where the
third element is located and the third should know the position of the fourth element and so on. Thus, each cell (space) of the list will provide the value of the element along with the information about where the next element is in the memory. This information of the next element is accomplished by holding the memory address of the next element. The memory address can be understood as the index of the array. As in case of an array, we can access an element in the array by its index. Similarly, we can access a memory location by using its address, normally called memory address.
Linked List
For the utilization of the concept of linked memory, we usually define a structure, called linked list. To form a linked list, at first, we define a node. A node comprises two fields. i.e. the object field that holds the actual list element and the next that holds the starting location of the next node.
next |
object |
A chain of these nodes forms a linked list. Now let’s consider our previous list, used with an array i.e. 2, 6, 8, 7, 1. Following is the figure which represents the list stored as a linked list.
current |
size = 5 |
1 |
7 |
8 |
6 |
2 |
Head |
This diagram just represents the linked list. In the memory, different nodes may occur at different locations but the next part of each node contains the address of the next node. Thus it forms a chain of nodes which we call a linked list.
While using an array we knew that the array started from index 1that means the first element of the list is at index 1. Similarly in the linked list we need to know the starting point of the list. For this purpose, we have a pointer head that points to the first node of the list. If we don’t use head, it will not be possible to know the starting position of the list. We also have a pointer current to point to the current node of the list. We need this pointer to add or remove current node from the list. Here in the linked list, the current is a pointer and not an index as we used while using an array. The next field of the last node points to nothing .It is the end of the list. We place the memory address NULL in the last node. NULL is an invalid address and is inaccessible.
Now again consider the list 2, 6, 8, 7, 1. The previous figure represents this list as a linked list. In this linked list, the head points to 2, 2 points to 6, 6 points to 8, 8 points to 7 and 7 points to 1. Moreover we have the current position at element 8.
This linked list is stored in the memory. The following diagram depicts the process
|
1051 |
6 |
|
1052 |
1063 |
current |
1053 |
|
|
1054 |
2 |
|
1055 |
1051 |
|
1056 |
|
|
1057 |
7 |
|
1058 |
1060 |
|
1059 |
|
|
1060 |
1 |
|
1061 |
0 |
head |
1062 |
1054 |
|
1063 |
8 |
|
1064 |
1057 |
|
1065 |
|
Step 1
You can see file PDF Given
below
Step 2
Select Your File and Click to Download
CS301 Handouts 2024
0 Comments