Data Structures CS301 book HANDOUTS in pdf

<br /><b><span style="font-size: large;">Data Structures CS301 book HANDOUTS in pdf</span></b><br />Data Structures (CS301)<br /><br />Handouts | Lectures | Contents | Books<div> <b><span style="font-size: large;"><br /></span></b></div> <div style="text-align: center;"> <b><span style="font-size: large;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjEhg2BcttHjw0gRgKqKecgA6kh1MIXGF_642EwSh-CkTS8BOLEP9M0pDFECSF-BbgDEvHJ8KL9m8AvMo_hpc_mxmLsCgGSrYm5CTPaHsm-Qd-HxKgCehbuRt8RdlDlUjP63xG6g3z_X3E/s1600/images.jpg" imageanchor="1"><img border="0" height="457" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjEhg2BcttHjw0gRgKqKecgA6kh1MIXGF_642EwSh-CkTS8BOLEP9M0pDFECSF-BbgDEvHJ8KL9m8AvMo_hpc_mxmLsCgGSrYm5CTPaHsm-Qd-HxKgCehbuRt8RdlDlUjP63xG6g3z_X3E/s640/images.jpg" width="640" /></a></span></b></div> <div> <b><span style="font-size: large;"><br /></span></b></div> <div> <b><span style="font-size: large;"><br /></span></b></div> <div> <span style="font-size: large;"><div> Data Structures</div> <div> Lecture No. 01</div> <div> Reading Material</div> <div> Data Structures and algorithm analysis in C++ Chapter. 3</div> <div> 3.1, 3.2, 3.2.1</div> <div> Summary</div> <div> • Introduction to Data Structures</div> <div> • Selecting a Data Structure</div> <div> • Data Structure Philosophy</div> <div> • Goals of this Course</div> <div> • Array</div> <div> • List data structure</div> <div> Welcome to the course of data structure. This is very important subject as the topics</div> <div> covered in it will be encountered by you again and again in the future courses. Due to</div> <div> its great applicability, this is usually called as the foundation course. You have</div> <div> already studied Introduction to programming using C and C++ and used some data</div> <div> structures. The focus of that course was on how to carry out programming with the</div> <div> use of C and C++ languages besides the resolution of different problems. In this</div> <div> course, we will continue problem solving and see that the organization of data in</div> <div> some cases is of immense importance. Therefore, the data will be stored in a special</div> <div> way so that the required result should be calculated as fast as possible.</div> <div> Following are the goals of this course:</div> <div> 􀂃 Prepare the students for (and is a pre-requisite for) the more advanced material</div> <div> students will encounter in later courses.</div> <div> 􀂃 Cover well-known data structures such as dynamic arrays, linked lists, stacks,</div> <div> queues, trees and graphs.</div> <div> 􀂃 Implement data structures in C++</div> <div> You have already studied the dynamic arrays in the previous course. We will now</div> <div> discuss linked lists, stacks, queues, trees and graphs and try to resolve the problems</div> <div> with the help of these data structures. These structures will be implemented in C++</div> <div> language. We will also do programming assignments to see the usage and importance</div> <div> of these structures.</div> <div> CS301 – Data Structures Lecture No. 01</div> <div> ___________________________________________________________________</div> <div> Page 4 of 505</div> <div> Information about Data Structure subject is available at: “http://www.vu.edu.pk/ds”.</div> <div> Introduction to Data Structures</div> <div> Let’s discuss why we need data structures and what sort of problems can be solved</div> <div> with their use. Data structures help us to organize the data in the computer, resulting</div> <div> in more efficient programs. An efficient program executes faster and helps minimize</div> <div> the usage of resources like memory, disk. Computers are getting more powerful with</div> <div> the passage of time with the increase in CPU speed in GHz, availability of faster</div> <div> network and the maximization of disk space. Therefore people have started solving</div> <div> more and more complex problems. As computer applications are becoming complex,</div> <div> so there is need for more resources. This does not mean that we should buy a new</div> <div> computer to make the application execute faster. Our effort should be to ensue that the</div> <div> solution is achieved with the help of programming, data structures and algorithm.</div> <div> What does organizing the data mean? It means that the data should be arranged in a</div> <div> way that it is easily accessible. The data is inside the computer and we want to see it.</div> <div> We may also perform some calculations on it. Suppose the data contains some</div> <div> numbers and the programmer wants to calculate the average, standard deviation etc.</div> <div> May be we have a list of names and want to search a particular name in it. To solve</div> <div> such problems, data structures and algorithm are used. Sometimes you may realize</div> <div> that the application is too slow and taking more time. There are chances that it may be</div> <div> due to the data structure used, not due to the CPU speed and memory. We will see</div> <div> such examples. In the assignments, you will also check whether the data structure in</div> <div> the program is beneficial or not. You may have two data structures and try to decide</div> <div> which one is more suitable for the resolution of the problem.</div> <div> As discussed earlier, a solution is said to be efficient if it solves the problem within its</div> <div> resource constraints. What does it mean? In the computer, we have hard disk, memory</div> <div> and other hardware. Secondly we have time. Suppose you have some program that</div> <div> solves the problem but takes two months. It will be of no use. Usually, you don’t have</div> <div> this much time and cannot wait for two months. Suppose the data is too huge to be</div> <div> stored in disk. Here we have also the problem of resources. This means that we have</div> <div> to write programs considering the resources to achieve some solution as soon as</div> <div> possible. There is always cost associated with these resources. We may need a faster</div> <div> and better CPU which can be purchased. Sometimes, we may need to buy memory.</div> <div> As long as data structures and programs are concerned, you have to invest your own</div> <div> time for this. While working in a company, you will be paid for this. All these</div> <div> requirements including computer, your time and computer time will decide that the</div> <div> solution you have provided is suitable or not. If its advantages are not obtained, then</div> <div> either program or computer is not good.</div> <div> So the purchase of a faster computer, while studying this course, does not necessarily</div> <div> help us in the resolution of the problem. In the course of “Computer Architecture”</div> <div> you will see how the more efficient solutions can be prepared with the hardware. In</div> <div> this course, we will use the software i.e. data structures, algorithms and the recipes</div> <div> through which the computer problems may be resolved with a faster solution.</div> <div> CS301 – Data Structures Lecture No. 01</div> <div> ___________________________________________________________________</div> <div> Page 5 of 505</div> <div> Selecting a Data Structure</div> <div> How can we select the data structure needed to solve a problem? You have already</div> <div> studied where to use array and the size of array and when and where to use the</div> <div> pointers etc. First of all, we have to analyze the problem to determine the resource</div> <div> constraints that a solution must meet. Suppose, the data is so huge i.e. in Gega bytes</div> <div> (GBs) while the disc space available with us is just 200 Mega bytes. This problem can</div> <div> not be solved with programming. Rather, we will have to buy a new disk.</div> <div> Secondly, it is necessary to determine the basic operations that must be supported.</div> <div> Quantify the resource constraints for each operation. What does it mean? Suppose you</div> <div> have to insert the data in the computer or database and have to search some data item.</div> <div> Let’s take the example of telephone directory. Suppose there are eight million names</div> <div> in the directory. Now someone asks you about the name of some particular person.</div> <div> You want that this query should be answered as soon as possible. You may add or</div> <div> delete some data. It will be advisable to consider all these operations when you select</div> <div> some data structure.</div> <div> Finally select the data structure that meets these requirements the maximum. Without,</div> <div> sufficient experience, it will be difficult to determine which one is the best data</div> <div> structure. We can get the help from internet, books or from someone whom you know</div> <div> for already getting the problems solved. We may find a similar example and try to use</div> <div> it. After this course, you will be familiar with the data structures and algorithms that</div> <div> are used to solve the computer problems.</div> <div> Now you have selected the data structure. Suppose a programmer has inserted some</div> <div> data and wants to insert more data. This data will be inserted in the beginning of the</div> <div> existing data, or in the middle or in the end of the data. Let’s talk about the arrays and</div> <div> suppose you have an array of size hundred. Data may be lying in the first fifty</div> <div> locations of this array. Now you have to insert data in the start of this array. What will</div> <div> you do? You have to move the existing data (fifty locations) to the right so that we get</div> <div> space to insert new data. Other way round, there is no space in the start. Suppose you</div> <div> have to insert the data at 25th location. For this purpose, it is better to move the data</div> <div> from 26th to 50th locations; otherwise we will not have space to insert this new data at</div> <div> 25th location.</div> <div> Now we have to see whether the data can be deleted or not. Suppose you are asked to</div> <div> delete the data at 27th position. How can we do that? What will we do with the space</div> <div> created at 27th position?</div> <div> Thirdly, is all the data processed in some well-defined order or random access</div> <div> allowed? Again take the example of arrays. We can get the data from 0th position and</div> <div> traverse the array till its 50th position. Suppose we want to get the data, at first from</div> <div> 50th location and then from 13th. It means that there is no order or sequence. We want</div> <div> to access the data randomly. Random access means that we can’t say what will be the</div> <div> next position to get the data or insert the data.</div> <div> Data Structure Philosophy</div> <div> Let’s talk about the philosophy of data structure. Each data structure has costs and</div> <div> benefits. Any data structure used in your program will have some benefits. For this,</div> <div> CS301 – Data Structures Lecture No. 01</div> <div> ___________________________________________________________________</div> <div> Page 6 of 505</div> <div> you have to pay price. That can be computer resources or the time. Also keep in mind</div> <div> that you are solving this problem for some client. If the program is not efficient, the</div> <div> client will not buy it.</div> <div> In rare cases, a data structure may be better than another one in all situations. It means</div> <div> that you may think that the array is good enough for all the problems. Yet this is not</div> <div> necessary. In different situations, different data structures will be suitable. Sometimes</div> <div> you will realize that two different data structures are suitable for the problem. In such</div> <div> a case, you have to choose the one that is more appropriate. An important skill this</div> <div> course is going to lend to the students is use the data structure according to the</div> <div> situation. You will learn the programming in a way that it will be possible to replace</div> <div> the one data structure with the other one if it does not prove suitable. We will replace</div> <div> the data structure so that the rest of the program is not affected. You will also have to</div> <div> attain this skill as a good programmer.</div> <div> There are three basic things associated with data structures. A data structure requires:</div> <div> – space for each data item it stores</div> <div> – time to perform each basic operation</div> <div> – programming effort</div> <div> Goals of this Course</div> <div> Reinforce the concept that costs and benefits exist for every data structure. We will</div> <div> learn this with practice.</div> <div> Learn the commonly used data structures. These form a programmer's basic data</div> <div> structure “toolkit”. In the previous course, you have learned how to form a loop,</div> <div> functions, use of arrays, classes and how to write programs for different problems. In</div> <div> this course, you will make use of data structures and have a feeling that there is bag</div> <div> full of different data structures. In case of some problem, you will get a data structure</div> <div> from the toolkit and use some suitable data structure.</div> <div> Understand how to measure the cost of a data structure or program. These techniques</div> <div> also allow you to judge the merits of new data structures that you or others might</div> <div> develop. At times, you may have two suitable data structures for some problem. These</div> <div> can be tried one by one to adjudge which one is better one. How can you decide</div> <div> which data structure is better than other. Firstly, a programmer can do it by writing</div> <div> two programs using different data structure while solving the same problem. Now</div> <div> execute both data structures. One gives the result before the other. The data structure</div> <div> that gives results first is better than the other one. But sometimes, the data grows too</div> <div> large in the problem. Suppose we want to solve some problem having names and the</div> <div> data of names grows to10 lakhs (one million). Now when you run both programs, the</div> <div> second program runs faster. What does it mean? Is the data structure used in program</div> <div> one not correct? This is not true. The size of the data, being manipulated in the</div> <div> program can grow or shrink. You will also see that some data structures are good for</div> <div> small data while the others may suit to huge data. But the problem is how can we</div> <div> determine that the data in future will increase or decrease. We should have some way</div> <div> to take decision in this regard. In this course we will do some mathematical analysis</div> <div> and see which data structure is better one.</div> <div> CS301 – Data Structures Lecture No. 01</div> <div> ___________________________________________________________________</div> <div> Page 7 of 505</div> <div> Arrays</div> <div> You have already studied about arrays and are well-versed with the techniques to</div> <div> utilize these data structures. Here we will discuss how arrays can be used to solve</div> <div> computer problems. Consider the following program:</div> <div> main( int argc, char** argv )</div> <div> {</div> <div> int x[6];</div> <div> int j;</div> <div> for(j = 0; j < 6; j++)</div> <div> x[j] = 2 * j;</div> <div> }</div> <div> We have declared an int array of six elements and initialized it in the loop.</div> <div> Let’s revise some of the array concepts. The declaration of array is as int x[6]; or float</div> <div> x[6]; or double x[6]; You have already done these in your programming assignments.</div> <div> An array is collection of cells of the same type. In the above program, we have array x</div> <div> of type int of six elements. We can only store integers in this array. We cannot put int</div> <div> in first location, float in second location and double in third location. What is x? x is a</div> <div> name of collection of items. Its individual items are numbered from zero to one less</div> <div> than array size. To access a cell, use the array name and an index as under:</div> <div> x[0], x[1], x[2], x[3], x[4], x[5]</div> <div> To manipulate the first element, we will use the index zero as x[0] and so on. The</div> <div> arrays look like in the memory as follows:</div> <div> Array occupies contiguous memory area in the computer. In case of the above</div> <div> example, if some location is assigned to x[0], the next location can not contain data</div> <div> other than x[1]. The computer memory can be thought of as an array. It is a very big</div> <div> array. Suppose a computer has memory of 2MB, you can think it as an array of size 2</div> <div> million and the size of each item is 32 bits. You will study in detail about it in the</div> <div> computer organization, and Assembly language courses. In this array, we will put our</div> <div> programs, data and other things.</div> <div> X[0]</div> <div> X[1]</div> <div> X[2]</div> <div> X[3]</div> <div> X[4]</div> <div> X[5]</div> <div> Array cells are</div> <div> contiguous in</div> <div> computer memory</div> <div> CS301 – Data Structures Lecture No. 01</div> <div> ___________________________________________________________________</div> <div> Page 8 of 505</div> <div> In the above program, we have declared an array named x. ‘x’ is an array’s name but</div> <div> there is no variable x. ‘x’ is not an lvalue. If some variable can be written on the lefthand</div> <div> side of an assignment statement, this is lvalue variable. It means it has some</div> <div> memory associated with it and some value can be assigned to it. For example, if we</div> <div> have the code int a, b; it can be written as b = 2; it means that put 2 in the memory</div> <div> location named b. We can also write as a = b; it means whatever b has assign it to a,</div> <div> that is a copy operation. If we write as a = 5; it means put the number 5 in the</div> <div> memory location which is named as a. But we cannot write 2 = a; that is to put at</div> <div> number 2 what ever the value of a is. Why can’t we do that? Number 2 is a constant.</div> <div> If we allow assignment to constants what will happen? Suppose ‘a’ has the value</div> <div> number 3. Now we assigned number 2 the number 3 i.e. all the number 2 will become</div> <div> number 3 and the result of 2 + 2 will become 6. Therefore it is not allowed.</div> <div> ‘x’ is a name of array and not an lvalue. So it cannot be used on the left hand side in</div> <div> an assignment statement. Consider the following statements</div> <div> int x[6];</div> <div> int n;</div> <div> x[0] = 5; x[1] = 2;</div> <div> x = 3; //not allowed</div> <div> x = a + b; // not allowed</div> <div> x = &n; // not allowed</div> <div> In the above code snippet, we have declared an array x of int. Now we can assign</div> <div> values to the elements of x as x[0] = 5 or x[1] = 2 and so on. The last three statements</div> <div> are not allowed. What does the statement x = 3; mean? As x is a name of array and</div> <div> this statement is not clear, what we are trying to do here? Are we trying to assign 3 to</div> <div> each element of the array? This statement is not clear. Resultantly, it can not be</div> <div> allowed. The statement x = a + b is also not allowed. There is nothing wrong with a</div> <div> + b. But we cannot assign the sum of values of a and b to x. In the statement x = &n,</div> <div> we are trying to assign the memory address of n to x which is not allowed. The reason</div> <div> is the name x is not lvalue and we cannot assign any value to it. For understanding</div> <div> purposes, consider x as a constant. Its name or memory location can not be changed.</div> <div> This is a collective name for six locations. We can access these locations as x[0], x[1]</div> <div> up to x[5]. This is the way arrays are manipulated.</div> <div> Sometimes, you would like to use an array data structure but may lack the information</div> <div> about the size of the array at compile time. Take the example of telephone directory.</div> <div> You have to store one lakh (100,000) names in an array. But you never know that the</div> <div> number of entries may get double or decline in future. Similarly, you can not say that</div> <div> the total population of the country is one crore (10 million) and declare an array of</div> <div> one crore names. You can use one lakh locations now and remaining will be used as</div> <div> the need arrives. But this is not a good way of using the computer resources. You</div> <div> have declared a very big array while using a very small chunk of it. Thus the</div> <div> remaining space goes waste which can, otherwise, be used by some other programs.</div> <div> We will see what can be the possible solution of this problem?</div> <div> Suppose you need an integer array of size n after the execution of the program. We</div> <div> have studied that if it is known at the execution of the program that an array of size 20</div> <div> or 30 is needed, it is allocated dynamically. The programming statement is as follows:</div> <div> CS301 – Data Structures Lecture No. 01</div> <div> ___________________________________________________________________</div> <div> Page 9 of 505</div> <div> int* y = new int[20];</div> <div> It means we are requesting computer to find twenty memory locations. On finding it,</div> <div> the computer will give the address of first location to the programmer which will be</div> <div> stored in y. Arrays locations are contiguous i.e. these are adjacent. These twenty</div> <div> locations will be contiguous, meaning that they will be neighbors to each other. Now</div> <div> y has become an array and we can say y[0] =1 or y[5] = 15. Here y is an lvalue.</div> <div> Being a pointer, it is a variable where we can store the address of some variable.</div> <div> When we said int* y = new int[20]; the new returns the memory address of first of</div> <div> the twenty locations and we store that address into y. As y is a pointer variable, so it</div> <div> can be used on the left-hand side. We can write it as:</div> <div> y = &x[0];</div> <div> In the above statement, we get the address of the fist location of the array x and store</div> <div> it in y. As y is lvalue, so it can be used on left hand side. This means that the above</div> <div> statement is correct.</div> <div> y = x;</div> <div> Similarly, the statement y = x is also correct. x is an array of six elements that holds</div> <div> the address of the first element. But we cannot change this address. However we can</div> <div> get that address and store it in some other variable. As y is a pointer variable and</div> <div> lvalue so the above operation is legal. We have dynamically allocated the memory for</div> <div> the array. This memory, after the use, can be released so that other programs can use</div> <div> it. We can use the delete keyword to release the memory. The syntax is:</div> <div> delete[ ] y;</div> <div> We are releasing the memory, making it available for use by other programs. We will</div> <div> not do it in case of x array, as ‘new’ was not used for its creation. So it is not our</div> <div> responsibility to delete x.</div> <div> List data structure</div> <div> This is a new data structure for you. The List data structure is among the most generic</div> <div> of data structures. In daily life, we use shopping list, groceries list, list of people to</div> <div> invite to a dinner, list of presents to give etc. In this course, we will see how we use</div> <div> lists in programming.</div> <div> A list is the collection of items of the same type (grocery items, integers, names). The</div> <div> data in arrays are also of same type. When we say int x[6]; it means that only the</div> <div> integers can be stored in it. The same is true for list. The data which we store in list</div> <div> should be of same nature. The items, or elements of the list, are stored in some</div> <div> particular order. What does this mean? Suppose in the list, you have the fruit first</div> <div> which are also in some order. You may have names in some alphabetical order i.e. the</div> <div> names which starts with A should come first followed by the name starting with B and</div> <div> so on. The order will be reserved when you enter data in the list.</div> <div> It is possible to insert new elements at various positions in the list and remove any</div> <div> CS301 – Data Structures Lecture No. 01</div> <div> ___________________________________________________________________</div> <div> Page 10 of 505</div> <div> element of the list. You have done the same thing while dealing with arrays. You</div> <div> enter the data in the array, delete data from the array. Sometimes the array size grows</div> <div> and at times, it is reduced. We will do this with the lists too.</div> <div> List is a set of elements in a linear order. Suppose we have four names a1, a2, a3, a4</div> <div> and their order is as (a3, a1, a2, a4) i.e. a3, is the first element, a1 is the second</div> <div> element, and so on. We want to maintain that order in the list when data is stored in</div> <div> the list. We don’t want to disturb this order. The order is important here; this is not</div> <div> just a random collection of elements but an ordered one. Sometimes, this order is due</div> <div> to sorting i.e. the things that start with A come first. At occasions, the order may be</div> <div> due to the importance of the data items. We will discuss this in detail while dealing</div> <div> with the examples.</div> <div> Now we will see what kind of operations a programmer performs with a list data</div> <div> structure. Following long list of operations may help you understand the things in a</div> <div> comprehensive manner.</div> <div> Operation Name Description</div> <div> createList() Create a new list (presumably empty)</div> <div> copy() Set one list to be a copy of another</div> <div> clear(); Clear a list (remove all elements)</div> <div> insert(X, ?) Insert element X at a particular position in the list</div> <div> remove(?) Remove element at some position in the list</div> <div> get(?) Get element at a given position</div> <div> update(X, ?) Replace the element at a given position with X</div> <div> find(X) Determine if the element X is in the list</div> <div> length() Returns the length of the list.</div> <div> createList() is a function which creates a new list. For example to create an array, we</div> <div> use int x[6] or int* y = new int[20]; we need similar functionality in lists too. The</div> <div> copy() function will create a copy of a list. The function clear() will remove all the</div> <div> elements from a list. We want to insert a new element in the list, we also have to tell</div> <div> where to put it in the list. For this purpose insert(X, position) function is used.</div> <div> Similarly the function remove(position) will remove the element at position. To get an</div> <div> element from the list get(position) function is used which will return the element at</div> <div> position. To replace an element in the list at some position the function update(X,</div> <div> position) is used. The function find(X) will search X in the list. The function length()</div> <div> tells us about the number of elements in the list.</div> <div> We need to know what is meant by “particular position” we have used “?” for this in</div> <div> the above table. There are two possibilities:</div> <div> 􀂃 Use the actual index of element: i.e. insert it after element 3, get element</div> <div> number 6. This approach is used with arrays</div> <div> 􀂃 Use a “current” marker or pointer to refer to a particular position in the list.</div> <div> The first option is used in the data structures like arrays. When we have to manipulate</div> <div> the arrays, we use index like x[3], x[6]. In the second option we do not use first,</div> <div> second etc for position but say wherever is the current pointer. Just think of a pointer</div> <div> in the list that we can move forward or backward. When we say get, insert or update</div> <div> CS301 – Data Structures Lecture No. 01</div> <div> ___________________________________________________________________</div> <div> Page 11 of 505</div> <div> while using the current pointer, it means that wherever is the current pointer, get data</div> <div> from that position, insert data after that position or update the data at that position. In</div> <div> this case, we need not to use numbers. But it is our responsibility that current pointer</div> <div> is used in a proper way.</div> <div> If we use the “current” marker, the following four methods would be useful:</div> <div> Functions Description</div> <div> start() Moves the “current” pointer to the very first element</div> <div> tail() Moves the “current” pointer to the very last element</div> <div> next() Move the current position forward one element</div> <div> back() Move the current position backward one element</div> <div> In the next lecture, we will discuss the implementation of the list data structure and</div> <div> write the functions discussed today, in C++ language.</div> <div> CS301 – Data Structures Lecture No. 02</div> <div> ___________________________________________________________________</div> <div> Page 12 of 505</div> <div> Data Structures</div> <div> Lecture No. 02</div> <div> Reading Material</div> <div> Data Structures and Algorithm Analysis in C++ Chapter. 3</div> <div> 3.1, 3.2, 3.2.1, 3.2.2</div> <div> Summary</div> <div> 1) List Implementation</div> <div> • add Method</div> <div> • next Method</div> <div> • remove Method</div> <div> • find Method</div> <div> • Other Methods</div> <div> 2) Analysis Of Array List</div> <div> 3) List Using Linked Memory</div> <div> 4) Linked List</div> <div> Today, we will discuss the concept of list operations. You may have a fair idea of ‘</div> <div> start operation’ that sets the current pointer to the first element of the list while the</div> <div> tail operation moves the current pointer to the last element of the list. In the previous</div> <div> lecture, we discussed the operation next that moves the current pointer one element</div> <div> forward. Similarly, there is the ‘back operation’ which moves the current pointer one</div> <div> element backward.</div> <div> List Implementation</div> <div> Now we will see what the implementation of the list is and how one can create a list</div> <div> in C++. After designing the interface for the list, it is advisable to know how to</div> <div> implement that interface. Suppose we want to create a list of integers. For this</div> <div> purpose, the methods of the list can be implemented with the use of an array inside.</div> <div> For example, the list of integers (2, 6, 8, 7, 1) can be represented in the following</div> <div> manner where the current position is 3.</div> <div> A 2 6 8 7 1 current size</div> <div> 1 2 3 4 5 3 5</div> <div> In this case, we start the index of the array from 1 just for simplification against the</div> <div> usual practice in which the index of an array starts from zero in C++. It is not</div> <div> necessary to always start the indexing from zero. Sometimes, it is required to start the</div> <div> indexing from 1. For this, we leave the zeroth position and start using the array from</div> <div> index 1 that is actually the second position. Suppose we have to store the numbers</div> <div> from 1 to 6 in the array. We take an array of 7 elements and put the numbers from the</div> <div> CS301 – Data Structures Lecture No. 02</div> <div> ___________________________________________________________________</div> <div> Page 13 of 505</div> <div> index 1. Thus there is a correspondence between index and the numbers stored in it.</div> <div> This is not very useful. So, it does not justify the non-use of zeroth position of the</div> <div> array out-rightly. However for simplification purposes, it is good to use the index</div> <div> from 1.</div> <div> add Method</div> <div> Now we will talk about adding an element to the list. Suppose there is a call to add an</div> <div> element in the list i.e. add(9). As we said earlier that the current position is 3, so by</div> <div> adding the element 9 to the list, the new list will be (2, 6, 8, 9, 7, 1).</div> <div> To add the new element (9) to the list at the current position, at first, we have to make</div> <div> space for this element. For this purpose, we shift every element on the right of 8 (the</div> <div> current position) to one place on the right. Thus after creating the space for new</div> <div> element at position 4, the array can be represented as</div> <div> A 2 6 8 7 1 current size</div> <div> 1 2 3 4 5 3 5</div> <div> Now in the second step, we put the element 9 at the empty space i.e. position 4. Thus</div> <div> the array will attain the following shape. The figure shows the elements in the array in</div> <div> the same order as stored in the list.</div> <div> A 2 6 8 9 7 1 current size</div> <div> 1 2 3 4 5 6 4 6</div> <div> We have moved the current position to 4 while increasing the size to 6. The size</div> <div> shows that the elements in the list. Where as the size of the array is different that we</div> <div> have defined already to a fixed length, which may be 100, 200 or even greater.</div> <div> next Method</div> <div> Now let’s see another method, called ‘next’. We have talked that the next method</div> <div> moves the current position one position forward. In this method, we do not add a new</div> <div> element to the list but simply move the pointer one element ahead. This method is</div> <div> required while employing the list in our program and manipulating it according to the</div> <div> requirement. There is also an array to store the list in it. We also have two variablescurrent</div> <div> and size to store the position of current pointer and the number of elements in</div> <div> the list. By looking on the values of these variables, we can find the state of the list</div> <div> i.e. how many elements are in the list and at what position the current pointer is.</div> <div> The method next is used to know about the boundary conditions of the list i.e. the</div> <div> array being used by us to implement the list. To understand the boundary conditions,</div> <div> we can take the example of an array of size 100 to implement the list. Here, 100</div> <div> elements are added to the array. Let’s see what happens when we want to add 101st</div> <div> element to the array? We used to move the current position by next method and</div> <div> reached the 100th position. Now, in case of moving the pointer to the next position</div> <div> (i.e. 101st), there will be an error as the size of the array is 100, having no position</div> <div> after this point. Similarly if we move the pointer backward and reach at the first</div> <div> position regardless that the index is 0 or 1. But what will happen if we want to move</div> <div> backward from the first position? These situations are known as boundary conditions</div> <div> and need attention during the process of writing programs when we write the code to</div> <div> use the list. We will take care of these things while implementing the list in C++</div> <div> CS301 – Data Structures Lecture No. 02</div> <div> ___________________________________________________________________</div> <div> Page 14 of 505</div> <div> programs.</div> <div> remove Method</div> <div> We have seen that the add method adds an element in the list. Now we are going to</div> <div> discuss the remove method. The remove method removes the element residing at the</div> <div> current position. The removal of the element will be carried out as follows. Suppose</div> <div> there are 6 elements (2, 6, 8, 9, 7, 1) in the list. The current pointer is pointing to the</div> <div> position 5 that has the value 7. We remove the element, making the current position</div> <div> empty. The size of the list will become 5. This is represented in the following figure.</div> <div> A 2 6 8 9 1 current size</div> <div> 1 2 3 4 5 6 5 6</div> <div> 5</div> <div> We fill in the blank position left by the removal of 7 by shifting the values on the right</div> <div> of position 5 to the left by one space. This means that we shift the remaining elements</div> <div> on the right hand side of the current position one place to the left so that the element</div> <div> next to the removed element (i.e. 1) takes its place (the fifth position) and becomes</div> <div> the current position element. We do not change the current pointer that is still pointing</div> <div> to the position 5. Thus the current pointer remains pointing to the position 5 despite</div> <div> the fact that there is now element 1 at this place instead of 7. Thus in the remove</div> <div> method, when we remove an element, the element next to it on the right hand side</div> <div> comes at its place and the remaining are also shifted one place to the right. This step is</div> <div> represented by the following figure.</div> <div> A 2 6 8 9 1 current size</div> <div> 1 2 3 4 5 5 5</div> <div> find Method</div> <div> Now lets talk about a function, used to find a specific element in the array. The find</div> <div> (x) function is used to find a specific element in the array. We pass the element, which</div> <div> is to be found, as an argument to the find function. This function then traverses the</div> <div> array until the specific element is found. If the element is found, this function sets the</div> <div> current position to it and returns 1 i.e. true. On the other hand, if the element is not</div> <div> found, the function returns 0 i.e. false. This indicates that the element was not found.</div> <div> Following is the code of this find(x) function in C++.</div> <div> int find (int x)</div> <div> {</div> <div> int j ;</div> <div> for (j = 1; j < size + 1; j++ )</div> <div> if (A[j] == x )</div> <div> break ;</div> <div> if ( j < size + 1) // x is found</div> <div> {</div> <div> current = j ; //current points to the position where x found</div> <div> return 1 ; // return true</div> <div> CS301 – Data Structures Lecture No. 02</div> <div> ___________________________________________________________________</div> <div> Page 15 of 505</div> <div> }</div> <div> return 0 ; //return false, x is not found</div> <div> }</div> <div> In the above code, we execute a for loop to traverse the array. The number of</div> <div> execution of this loop is equal to the size of the list. This for loop gets terminated</div> <div> when the value of loop variable (j) increases from the size of the list. However we</div> <div> terminate the loop with the break statement if the element is found at a position.</div> <div> When the control comes out from the loop, we check the value of j. If the value of j is</div> <div> less than the size of the array, it means that the loop was terminated by the break</div> <div> statement. We use the break statement when we find the required element (x) in the</div> <div> list. The execution of break statement shows that the required element was found at</div> <div> the position equal to the value of j. So the program sets the current position to j and</div> <div> comes out the function by returning 1 (i.e. true). If the value of j is greater than the</div> <div> size of the array, it means that the whole array has traversed and the required element</div> <div> is not found. So we simply return 0 (i.e. false) and come out of the function.</div> <div> Other Methods</div> <div> There are some other methods to implement the list using an array. These methods are</div> <div> very simple, which perform their task just in one step (i.e. in one statement). There is</div> <div> a get() method , used to get the element from the current position in the array. The</div> <div> syntax of this function is of one line and is as under</div> <div> return A[current] ;</div> <div> This statement returns the element to which the current is pointing to (i.e. the current</div> <div> position) in the list A.</div> <div> Another function is update(x). This method is used to change (set) the value at the</div> <div> current position. A value is passed to this method as an argument. It puts that value at</div> <div> the current position. The following statement in this method carries out this process.</div> <div> A [current] = x ;</div> <div> Then there is a method length( ).This method returns the size of the list. The syntax of</div> <div> this method is</div> <div> return size ;</div> <div> You may notice here that we are returning the size of the list and not the size of the</div> <div> array being used internally to implement the list. This size is the number of the</div> <div> elements of the list, stored in the array.</div> <div> The back() method decreases the value of variable current by 1. In other words, it</div> <div> moves the current position one element backward. This is done by writing the</div> <div> statement.</div> <div> current -- ;</div> <div> The -- is a decrement operator in C++ that decreases the value of the operand by one.</div> <div> The above statement can also be written as</div> <div> CS301 – Data Structures Lecture No. 02</div> <div> ___________________________________________________________________</div> <div> Page 16 of 505</div> <div> current = current -1 ;</div> <div> The start() method sets the current position to the first element of the list. We know</div> <div> that the index of the array starts from 0 but we use the index 1 for the starting</div> <div> position. We do not use the index zero. So we set the current position to the first</div> <div> element by writing</div> <div> current = 1 ;</div> <div> Similarly, the end() method sets the current position to the last element of the list i.e.</div> <div> size. So we write</div> <div> current = size ;</div> <div> Analysis of Array List</div> <div> Now we analyze the implementation of the list while using an array internally. We</div> <div> analyze different methods used for the implementation of the list. We try to see the</div> <div> level upto which these are efficient in terms of CPU’s time consumption. Time is the</div> <div> major factor to see the efficiency of a program.</div> <div> Add</div> <div> First of all, we have talked about the add method. When we add an element to the list,</div> <div> every element is moved to the right of the current position to make space for the new</div> <div> element. So, if the current position is the start of the list and we want to add an</div> <div> element in the beginning, we have to shift all the elements of the list to the right one</div> <div> place. This is the worst case of adding an element to the list. Suppose if the size of the</div> <div> list is 10000 or 20000, we have to do the shift operation for all of these 10000 or</div> <div> 20000 elements. Normally, it is done by shifting of elements with the use of a for</div> <div> loop. This operation takes much time of the CPU and thus it is not a good practice to</div> <div> add an element at the beginning of a list. On the other hand, if we add an element at</div> <div> the end of the list, it can be done by carrying out ‘no shift operation’. It is the best</div> <div> case of adding an element to the list. However, normally we may have to move half of</div> <div> the elements. The usage of add method is the matter warranting special care at the</div> <div> time of implementation of the list in our program. To provide the interface of the list,</div> <div> we just define these methods.</div> <div> Remove</div> <div> When we remove an element at the current position in the list, its space gets empty.</div> <div> The current pointer remains at the same position. To fill this space, we shift the</div> <div> elements on the right of this empty space one place to the left. If we remove an</div> <div> element from the beginning of the list, then we have to shift the entire remaining</div> <div> elements one place to the left. Suppose there is a large number of elements, say 10000</div> <div> or 20000, in the list. We remove the first element from the list. Now to fill this space,</div> <div> the remaining elements are shifted (that is a large number). Shifting such a large</div> <div> number of elements is time consuming process. The CPU takes time to execute the for</div> <div> loop that performs this shift operation. Thus to remove an element at the beginning of</div> <div> the list is the worst case of remove method. However it is very easy to remove an</div> <div> CS301 – Data Structures Lecture No. 02</div> <div> ___________________________________________________________________</div> <div> Page 17 of 505</div> <div> element at the end of the list. In average cases of the remove method we expect to</div> <div> shift half of the elements. This average does not mean that in most of the cases, you</div> <div> will have to shift half the elements. It is just the average. We may have to shift all the</div> <div> elements in one operation (if we remove at the beginning) and in the second</div> <div> operation, we have to shift no element (if we remove at the end). Similarly, in certain</div> <div> operations, we have to shift just 10, 15 elements.</div> <div> Find</div> <div> We have discussed that the find method takes an element and traverses the list to find</div> <div> that element. The worst case of the find method is that it has to search the entire list</div> <div> from beginning to end. So, it finds the element at the end of the array or the element is</div> <div> not found. On average the find method searches at most half the list.</div> <div> The other methods get (), length () etc are one-step methods. They carry out their</div> <div> operation in one instruction. There is no need of any loop or other programming</div> <div> structures to perform the task. The get() method gets the value from the specified</div> <div> position just in one step. Similarly the update() method sets a value at the specific</div> <div> position just in one-step. The length () method returns the value of the size of the list.</div> <div> The other methods back(), start() and end() also perform their tasks only in one step.</div> <div> List using Linked Memory</div> <div> We have seen the implementation of the list with the use of an array. Now we will</div> <div> discuss the implementation of the list while using linked memory. In an array, the</div> <div> memory cells of the array are linked with each other. It means that the memory of the</div> <div> array is contiguous. In an array, it is impossible that one element of the array is</div> <div> located at a memory location while the other element is located somewhere far from it</div> <div> in the memory. It is located in very next location in the memory. It is a property of the</div> <div> array that its elements are placed together with one another in the memory. Moreover,</div> <div> when we have declared the size of the array, it is not possible to increase or decrease</div> <div> it during the execution of the program. If we need more elements to store in the array,</div> <div> there is need of changing its size in the declaration. We have to compile the program</div> <div> again before executing it. Now array will be of the new size. But what happens if we</div> <div> again need to store more elements? We will change the code of our program to</div> <div> change the declaration of the array while recompiling it.</div> <div> Suppose we have used the dynamic memory allocation and created an array of 100</div> <div> elements with the use of new operator. In case of need of 200 elements, we will</div> <div> release this array and allocate a new array of 200 elements. Before releasing the</div> <div> previous array, it will wise to copy its elements to the new array so that it does not</div> <div> lose any information. Now this new array is in ‘ready for use’ position. Thus the</div> <div> procedure of creating a new array is not an easy task.</div> <div> To avoid such problems, usually faced by the programmers while using an array,</div> <div> there is need of using linked memory in which the various cells of memory, are not</div> <div> located continuously. In this process, each cell of the memory not only contains the</div> <div> value of the element but also the information where the next element of the list is</div> <div> residing in the memory. It is not necessary that the next element is at the next location</div> <div> in the memory. It may be anywhere in the memory. We have to keep a track of it.</div> <div> Thus, in this way, the first element must explicitly have the information about the</div> <div> location of the second element. Similarly, the second element must know where the</div> <div> CS301 – Data Structures Lecture No. 02</div> <div> ___________________________________________________________________</div> <div> Page 18 of 505</div> <div> third element is located and the third should know the position of the fourth element</div> <div> and so on. Thus, each cell (space) of the list will provide the value of the element</div> <div> along with the information about where the next element is in the memory. This</div> <div> information of the next element is accomplished by holding the memory address of</div> <div> the next element. The memory address can be understood as the index of the array. As</div> <div> in case of an array, we can access an element in the array by its index. Similarly, we</div> <div> can access a memory location by using its address, normally called memory address.</div> <div> Linked List</div> <div> For the utilization of the concept of linked memory, we usually define a structure,</div> <div> called linked list. To form a linked list, at first, we define a node. A node comprises</div> <div> two fields. i.e. the object field that holds the actual list element and the next that holds</div> <div> the starting location of the next node.</div> <div> object next</div> <div> A chain of these nodes forms a linked list. Now let’s consider our previous list, used</div> <div> with an array i.e. 2, 6, 8, 7, 1. Following is the figure which represents the list stored</div> <div> as a linked list.</div> <div> Head</div> <div> 2 6 8 7 1 size = 5</div> <div> current</div> <div> This diagram just represents the linked list. In the memory, different nodes may occur</div> <div> at different locations but the next part of each node contains the address of the next</div> <div> node. Thus it forms a chain of nodes which we call a linked list.</div> <div> While using an array we knew that the array started from index 1that means the first</div> <div> element of the list is at index 1. Similarly in the linked list we need to know the</div> <div> starting point of the list. For this purpose, we have a pointer head that points to the</div> <div> first node of the list. If we don’t use head, it will not be possible to know the starting</div> <div> position of the list. We also have a pointer current to point to the current node of the</div> <div> list. We need this pointer to add or remove current node from the list. Here in the</div> <div> linked list, the current is a pointer and not an index as we used while using an array.</div> <div> The next field of the last node points to nothing .It is the end of the list. We place the</div> <div> memory address NULL in the last node. NULL is an invalid address and is</div> <div> inaccessible.</div> <div> Now again consider the list 2, 6, 8, 7, 1. The previous figure represents this list as a</div> <div> linked list. In this linked list, the head points to 2, 2 points to 6, 6 points to 8, 8 points</div> <div> to 7 and 7 points to 1. Moreover we have the current position at element 8.</div> <div> This linked list is stored in the memory. The following diagram depicts the process</div> <div> CS301 – Data Structures Lecture No. 02</div> <div> ___________________________________________________________________</div> <div> Page 19 of 505</div> <div> through which this linked list is stored in the memory.</div> <div> 1051 6</div> <div> 1052 1063</div> <div> current 1053</div> <div> 1054 2</div> <div> 1055 1051</div> <div> 1056</div> <div> 1057 7</div> <div> 1058 1060</div> <div> 1059</div> <div> 1060 1</div> <div> 1061 0</div> <div> head 1062 1054</div> <div> 1063 8</div> <div> 1064 1057</div> <div> 1065</div> <div> We can see in the figure that each memory location has an address. Normally in</div> <div> programming, we access the memory locations by some variable names. These</div> <div> variable names are alias for these locations and are like labels that are put to these</div> <div> memory locations. We use head and current variable names instead of using the</div> <div> memory address in numbers for starting and the current nodes. In the figure, we see</div> <div> that head is the name of the memory location 1062 and the name current is used for</div> <div> the memory address 1053. The head holds the address 1054 and the element 2, the</div> <div> first one in the list, is stored in the location 1054. Similarly current holds the address</div> <div> 1063 where the element 8 is stored which is our current position in the list. In the</div> <div> diagram, two memory locations comprise a node. So we see that the location 1054</div> <div> holds the element 2 while the next location 1055 holds the address of the memory</div> <div> location (1051) where the next element of the list (i.e. 6) is stored. Similarly the next</div> <div> part of the node that has value 6 holds the memory address of the location occupied</div> <div> by the next element (i.e. 8) of the list. The other nodes are structured in a similar</div> <div> fashion. Thus, by knowing the address of the next element we can traverse the whole</div> <div> list.</div> <div> CS301 – Data Structures Lecture No. 03</div> <div> ___________________________________________________________________</div> <div> Page 20 of 505</div> <div> Data Structures</div> <div> Lecture No. 03</div> <div> Reading Material</div> <div> Data Structures and algorithm analysis in C++ Chapter. 3</div> <div> 3.2.2, 3.2.3, 3.2.5</div> <div> Summary</div> <div> • Linked List inside Computer Memory</div> <div> • Linked List Operations</div> <div> • Linked List Using C++</div> <div> • Example Program</div> <div> In the previous lectures, we used an array to construct a list data structure and</div> <div> observed the limitation that array being of fixed size can only store a fixed number of</div> <div> elements. Therefore, no more elements can be stored after the size of the array is</div> <div> reached.</div> <div> In order to resolve this, we adopted a new data structure called linked list. We started</div> <div> discussing, how linked lists are stored in computer memory and how memory chains</div> <div> are formed.</div> <div> CS301 – Data Structures Lecture No. 03</div> <div> ___________________________________________________________________</div> <div> Page 21 of 505</div> <div> Linked List inside Computer Memory</div> <div> Fig 1. Linked list in memory</div> <div> There are two parts of this figure. On the left is the linked list chain that is actually the</div> <div> conceptual view of the linked list and on the right is the linked list inside the computer</div> <div> memory. Right part is a snapshot of the computer memory with memory addresses</div> <div> from 1051 to 1065. The head pointer is pointing to the first element in the linked list.</div> <div> Note that head itself is present in the memory at address 1062. It is actually a pointer</div> <div> containing the memory address 1054. Each node in the above linked list has two parts</div> <div> i.e. the data part of the node and the pointer to the next node. The first node of the</div> <div> linked list pointed by the head pointer is stored at memory address 1054. We can see</div> <div> the data element 2 present at that address. The second part of the first node contains</div> <div> the memory address 1051. So the second linked list’s node starts at memory address</div> <div> 1051. We can use its pointer part to reach the third node of the list and in this way, we</div> <div> can traverse the whole list. The last node contains 1 in its data part and 0 in its pointer</div> <div> part. 0 indicates that it is not pointing to any node and it is the last node of the linked</div> <div> list.</div> <div> Linked List Operations</div> <div> The linked list data structure provides operations to work on the nodes inside the list.</div> <div> The first operation we are going to discuss here is to create a new node in the</div> <div> memory. The Add(9) is used to create a new node in the memory at the current</div> <div> 1051 6</div> <div> 1052 1063</div> <div> 1053 1063</div> <div> 1054 2</div> <div> 1055 1051</div> <div> 1056</div> <div> 1057 7</div> <div> 1058 1060</div> <div> 1059</div> <div> 1060 1</div> <div> 1061 0</div> <div> 1062 1054</div> <div> 1063 8</div> <div> 1064 1057</div> <div> 1065</div> <div> currentent</div> <div> headent</div> <div> head</div> <div> 2 6 8 7 1</div> <div> CS301 – Data Structures Lecture No. 03</div> <div> ___________________________________________________________________</div> <div> Page 22 of 505</div> <div> position to hold ‘9’. You must remember while working with arrays, to add an</div> <div> element at the current position that all the elements after the current position were</div> <div> shifted to the right and then the element was added to the empty slot.</div> <div> Here, we are talking about the internal representation of the list using linked list. Its</div> <div> interface will remain the same as in case of arrays.</div> <div> We can create a new node in the following manner in the add() operation of the linked</div> <div> list with code in C++:</div> <div> Node * newNode = new Node(9);</div> <div> The first part of the statement that is on the left of the assignment is declaring a</div> <div> variable pointer of type Node. It may also be written as Node * newNode. On the</div> <div> right of this statement, the new operator is used to create a new Node object as new</div> <div> Node(9). This is one way in C++ to create objects of classes. The name of the class is</div> <div> provided with the new operator that causes the constructor of the class to be called.</div> <div> The constructor of a class has the same name as the class and as this a function,</div> <div> parameters can also be passed to it. In this case, the constructor of the Node class is</div> <div> called and ‘9’ is passed to it as an int parameter.</div> <div> Hence, the whole statement means:</div> <div> “Call the constructor of the Node class and pass it ‘9’ as a parameter. After</div> <div> constructing the object in memory, give me the starting memory address of the object.</div> <div> That address will be stored in the pointer variable newNode.”</div> <div> To create an object of int type in the same manner, we can write as:</div> <div> int * i = new int ;</div> <div> Previously, we used the same technique to allocate memory for an array of ints as:</div> <div> int * i = new int [10] ;</div> <div> Now after the node has been created, how the node is fit into the chain of the linked</div> <div> list.</div> <div> Fig 2. Insertion of new Node into the linked list</div> <div> In the above figure, there is a linked list that contains five nodes with data elements as</div> <div> 2, 6, 8, 7 and 1. The current pointer is pointing to the node with element as 8. We</div> <div> want to insert a new node with data element 9. This new node will be inserted at the</div> <div> current position (the position where the current pointer is pointing to). This insertion</div> <div> 2</div> <div> 6</div> <div> 8</div> <div> 7</div> <div> 1</div> <div> 9</div> <div> current 1</div> <div> newNode</div> <div> 2</div> <div> 3</div> <div> CS301 – Data Structures Lecture No. 03</div> <div> ___________________________________________________________________</div> <div> Page 23 of 505</div> <div> operation is performed in a step by step fashion.</div> <div> - The first step is to point next pointer of the new node (with data element as 9) to</div> <div> the node with data element as 7.</div> <div> - The second step is to point the next pointer of the node with data element 8 to the</div> <div> node the new node with data element 9.</div> <div> - The third step is to change the current pointer to point to the new node.</div> <div> Now, the updated linked list has nodes with data elements as 2, 6, 8, 9, 7 and 1. The</div> <div> list size has become 6.</div> <div> Linked List Using C++</div> <div> /* The Node class */</div> <div> class Node</div> <div> {</div> <div> public:</div> <div> int get() { return object; };</div> <div> void set(int object) { this->object = object; };</div> <div> Node * getNext() { return nextNode; };</div> <div> void setNext(Node * nextNode) { this->nextNode = nextNode; };</div> <div> private:</div> <div> int object;</div> <div> Node * nextNode;</div> <div> };</div> <div> Whenever, we write a class, it begins with the word class followed by the class-name</div> <div> and the body of the class enclosed within curly braces. In the body, we write its public</div> <div> variables, methods and then private variables and methods, this is normally the</div> <div> sequence.</div> <div> If there is no code to write inside the constructor function of a class, we need not to</div> <div> declare it ourselves as the compiler automatically creates a default constructor for us.</div> <div> Similarly, if there is nothing to be done by the destructor of the class, it will be better</div> <div> not to write it explicitly. Rather, the compiler writes it automatically. Remember, the</div> <div> default constructor and destructor do nothing as these are the function without any</div> <div> code statements inside.</div> <div> Let’s start with the data members first. These are given at the bottom of the class body</div> <div> with the scope mentioned as private. These data members are actually two parts of a</div> <div> linked list’s node. First variable is object of type int, present there to store the data</div> <div> part of the node. The second variable is nextNode, which is a pointer to an object of</div> <div> type Node. It has the address of the next element of the linked list.</div> <div> The very first public function given at the top is get(). We have written its code within</div> <div> the class Node. It returns back the value of the variable object i.e. of the type of int.</div> <div> When we write class in C++, normally, we make two files (.h and .cpp) for a class.</div> <div> The .h file contains the declarations of public and private members of that class. The</div> <div> public methods are essentially the interface of the class to be employed by the users of</div> <div> this class. The .cpp file contains the implementation for the class methods that has the</div> <div> CS301 – Data Structures Lecture No. 03</div> <div> ___________________________________________________________________</div> <div> Page 24 of 505</div> <div> actual code. This is usually the way that we write two files for one class. But this is</div> <div> not mandatory. In the code given above, we have only one file .cpp, instead of</div> <div> separating into two files. As the class methods are very small, so their code is written</div> <div> within the body of the class. This facilitates us in carrying on discussion. Thus instead</div> <div> of talking about two files, we will only refer to one file. On the other hand, compiler</div> <div> takes these functions differently that are called inline functions. The compiler replaces</div> <div> the code of these inline functions wherever the call to them is made.</div> <div> The second method in the above-mentioned class is set() that accepts a parameter of</div> <div> type int while returning back nothing. The accepted parameter is assigned to the</div> <div> internal data member object. Notice the use of this pointer while assigning the value</div> <div> to the internal data member. It is used whenever an object wants to talk to its own</div> <div> members.</div> <div> The next method is getNext() which returns a pointer to an object of type Node lying</div> <div> somewhere in the memory. It returns nextNode i.e. a pointer to an object of type</div> <div> Node. As discussed above, nextNode contains the address of next node in the linked</div> <div> list.</div> <div> The last method of the class is setNext() that accepts a pointer of type Node, further</div> <div> assigned to nextNode data member of the object. This method is used to connect the</div> <div> next node of the linked list with the current object. It is passed an address of the next</div> <div> node in the linked list.</div> <div> Let’s discuss a little bit about classes. A very good analogy of a class is a factory.</div> <div> Think about a car factory. On the placement of order, it provides us with the number</div> <div> of vehicles we ordered for. Similarly, you can see number of other factories in your</div> <div> daily-life that manufacture the specific products.</div> <div> Let’s take this analogy in C++ language. Suppose, we want to make a factory in C++.</div> <div> By the way, what is our Node class? It is actually a factory that creates nodes. When</div> <div> we want to make a new node, a new operator is used. By using new operator with the</div> <div> Node class, actually, we send an order to Node factory, to make as many as nodes for</div> <div> us.</div> <div> So we have a good analogy, to think about a class as a factory. The products that are</div> <div> made by the factory have their own characteristics. For example, a car made by an</div> <div> automobile factory has an engine, wheels, steering and seats etc. These variables</div> <div> inside a class are called state variables. Now the kinds of operations this car can do</div> <div> are the methods of its class. A car can be driven, engine can be started, gears can be</div> <div> shifted and an accelerator can be pressed to run it faster.</div> <div> Similarly, the Node class creates nodes, where every node has two-state variables i.e.</div> <div> object and nextNode. We have already seen its operations in the above code. We use</div> <div> new to create new object or an array of new objects, stored in memory.</div> <div> Let’s see the code below.</div> <div> /* List class */</div> <div> #include <stdlib.h></div> <div> #include "Node.cpp"</div> <div> class List</div> <div> {</div> <div> public:</div> <div> CS301 – Data Structures Lecture No. 03</div> <div> ___________________________________________________________________</div> <div> Page 25 of 505</div> <div> // Constructor</div> <div> List() {</div> <div> headNode = new Node();</div> <div> headNode->setNext(NULL);</div> <div> currentNode = NULL;</div> <div> size = 0;</div> <div> }</div> <div> We are creating a list factory here employed to create list objects. Remember the list</div> <div> operations; add, remove, next, back and start etc. Let’s see the above class declaration</div> <div> code in detail.</div> <div> There are two include statements at the start. The first line is to include a standard</div> <div> library stdlib.h while the second line includes the Node class file Node.cpp. This Node</div> <div> class is used to create nodes that form a List object. So this List factory will order</div> <div> Node class to create new nodes. The List class itself carries out the chain management</div> <div> of these Node objects.</div> <div> We have written our own constructor of List class as the default constructor is not</div> <div> sufficient enough to serve the purpose. The List constructor is parameterless. The very</div> <div> first step it is doing internally is that it is asking Node class to create a new node and</div> <div> assigning the starting address of the new Node’s object to the headNode data member.</div> <div> In the second statement, we are calling setNext() method of the Node class for the</div> <div> object pointed to by the headNode pointer. This call is to set the nextNode data</div> <div> member to NULL, i.e. Node’s object pointed to by the headNode pointer is not</div> <div> pointing to any further Node. The next statement is to set the currentNode pointer to</div> <div> NULL. So at the moment, we have initialized the currentNode pointer to NULL that is</div> <div> not pointing to any Node object. The next statement is to initialize the size data</div> <div> member to 0 indicating that there is no node present in the list. All this processing is</div> <div> done inside the constructor of List class, as we want all this done when a list object is</div> <div> created. Considering the analogy of car factory, the constructor function can perform</div> <div> certain tasks: The oil is poured into the engine, the tyres are filled-in with air etc.</div> <div> Let’s see the add method of the List class:</div> <div> /* add() class method */</div> <div> void add (int addObject)</div> <div> {</div> <div> 1. Node * newNode = new Node();</div> <div> 2. newNode->set(addObject);</div> <div> 3. if( currentNode != NULL )</div> <div> 4. {</div> <div> 5. newNode->setNext(currentNode->getNext());</div> <div> 6. currentNode->setNext( newNode );</div> <div> 7. lastCurrentNode = currentNode;</div> <div> 8. currentNode = newNode;</div> <div> 9. }</div> <div> 10. else</div> <div> 11. {</div> <div> 12. newNode->setNext(NULL);</div> <div> 13. headNode->setNext(newNode);</div> <div> CS301 – Data Structures Lecture No. 03</div> <div> ___________________________________________________________________</div> <div> Page 26 of 505</div> <div> 14. lastCurrentNode = headNode;</div> <div> 15. currentNode = newNode;</div> <div> 16. }</div> <div> 17. size ++;</div> <div> }</div> <div> The interface or signatures of add() method is similar to the one discussed in case of</div> <div> an array. This method takes the object to be added as a parameter. The</div> <div> implementation of this add() method is a bit longer as the method is being</div> <div> implemented for linked list. In the first statement, a new Node object is created with</div> <div> its address stored in the newNode pointer variable. The second statement is to call</div> <div> set() method of the Node object pointed to by the newNode pointer. You can note the</div> <div> way the method is called. A pointer variable is at the left most side then an arrow sign</div> <div> (->), then the name of the method with appropriate arguments within parenthesis. It is</div> <div> followed by the if-statement that checks the currentNode is not NULL to perform</div> <div> certain operations inside the if-code block. Inside the if-statement, at line 5, the</div> <div> nextNode pointer of the new node is being set to the nextNode of the object pointed to</div> <div> by the currentNode pointer. In order to understand the statements given in this code</div> <div> properly, consider the fig 2 above, where we added a node in the linked list. We have</div> <div> done step 1 at line5. At line 6, we are performing the second step by setting the</div> <div> newNode in the nextNode pointer of the object pointed to by the currentNode. At line</div> <div> 7, we are saving the current position (address) of the currentNode pointer in the</div> <div> pointer variable lastCurrentNode, which might be useful for backward traversing.</div> <div> Although, the fig 1 (left part) indicates movement in one direction from left to right</div> <div> but the lastCurrentNode pointer node can be used by the back() member function to</div> <div> traverse one position back from right to left. At line 8, the currentNode pointer is</div> <div> assigned the address of the object pointed to by newNode. This way, a new node is</div> <div> added in already existent linked list.</div> <div> Line 10 is start of the else part of if-statement. This is executed if the currentNode is</div> <div> NULL. It means that there is no node present in the list previously and first node is</div> <div> going to be added. At line 12, we are setting the nextNode pointer of the object</div> <div> pointed to by newNode pointer. The nextNode is being set to NULL by calling the</div> <div> setNext() method. Then at line 13, we point the head pointer (headNode) to this new</div> <div> node pointed to by newNode pointer. Note that headNode is pointing to a node that is</div> <div> there despite the fact that the size of the linked list is 0. Actually, we have allocated a</div> <div> Node object for headNode pointer. Although, we don’t need a Node object here, yet it</div> <div> will be helpful when we perform other operations like remove() and find().</div> <div> At line 14, the headNode address is being assigned to lastCurrentNode. At line 15,</div> <div> currentNode pointer is assigned the address of newNode. At the end i.e. at line 17, the</div> <div> size of the list is incremented by 1.</div> <div> CS301 – Data Structures Lecture No. 03</div> <div> ___________________________________________________________________</div> <div> Page 27 of 505</div> <div> Fig 3. Add operation of linked list</div> <div> Following is the crux of this add() operation :</div> <div> Firstly, it will make a new node by calling Node class constructor. Insert the value</div> <div> e.g. 2. of the node into the node by calling the set method. Now if the list already</div> <div> exists (has some elements inside or its size is non-zero), it will insert the node after</div> <div> the current position. If the list does not already exist, this node is added as the first</div> <div> element inside the list.</div> <div> Let’s try to add few more elements into the above linked list in the figure. The</div> <div> following are the lines of code to be executed to add nodes with values 8, 7 and 1 into</div> <div> the linked list.</div> <div> list.add(8); list.add(7); list.add(1);</div> <div> Fig 4. More Nodes added into linked list</div> <div> Now we will see the remaining methods of the linked list. The get() method of the</div> <div> List class is given below</div> <div> List list; headNode size = 0</div> <div> headNode</div> <div> currentNode</div> <div> size = 1</div> <div> lastCurrentNode</div> <div> headNodee 2</div> <div> currentNode</div> <div> size = 2</div> <div> lastCurrentNode</div> <div> list.add(2);</div> <div> list.add(6);</div> <div> 2</div> <div> 6</div> <div> 2 6 8 7 1</div> <div> headNode lastCurrentNode</div> <div> currentNode</div> <div> size = 5</div> <div> CS301 – Data Structures Lecture No. 03</div> <div> ___________________________________________________________________</div> <div> Page 28 of 505</div> <div> /* get() class method */</div> <div> int get()</div> <div> {</div> <div> if (currentNode != NULL)</div> <div> return currentNode->get();</div> <div> }</div> <div> This method firstly confirms that the currentNode pointer is not NULL. If it is not</div> <div> NULL, then it must be pointing to some Node object as inside the constructor of the</div> <div> List class, we have initialized this pointer variable to NULL. That indicates that the</div> <div> currentNode is NULL when there is no element inside the list. However, when a Node</div> <div> object is added into it, it starts pointing to it. So, this get() returns the address of the</div> <div> node pointed to by the currentNode pointer.</div> <div> Further, we have another method given below:</div> <div> /* next() class method */</div> <div> bool next()</div> <div> {</div> <div> 1. if (currentNode == NULL) return false;</div> <div> 2.</div> <div> 3. lastCurrentNode = currentNode;</div> <div> 4. currentNode = currentNode->getNext();</div> <div> 5. return true;</div> <div> };</div> <div> This is next() method, used to advance the currentNode pointer to the next node inside</div> <div> the linked list. At line 1, the currentNode is being checked to confirm that there are</div> <div> some elements present in the list to advance further. At line 1, the method is returning</div> <div> false if there is no element present in the list. At line 3, it is storing the value of the</div> <div> currentNode pointer into the lastCurrentNode. At line 4, currentNode is calling the</div> <div> getNext() method to get the address of next node to be stored in the currentNode</div> <div> pointer to advance the currentNode pointer to the next element. At line 5, it returns</div> <div> true indicating the method is successful in moving to the next node.</div> <div> Example Program</div> <div> Given below is the full source code of the example program. You can copy, paste and</div> <div> compile it right away. In order to understand the linked list concept fully, it is highly</div> <div> desirable that you understand and practice with the below code.</div> <div> #include <iostream.h></div> <div> #include <stdlib.h></div> <div> /* The Node class */</div> <div> class Node</div> <div> {</div> <div> public:</div> <div> int get() { return object; };</div> <div> void set(int object) { this->object = object; };</div> <div> CS301 – Data Structures Lecture No. 03</div> <div> ___________________________________________________________________</div> <div> Page 29 of 505</div> <div> Node * getNext() { return nextNode; };</div> <div> void setNext(Node * nextNode) { this->nextNode = nextNode; };</div> <div> private:</div> <div> int object;</div> <div> Node * nextNode;</div> <div> };</div> <div> /* The List class */</div> <div> class List</div> <div> {</div> <div> public:</div> <div> List();</div> <div> void add (int addObject);</div> <div> int get();</div> <div> bool next();</div> <div> friend void traverse(List list);</div> <div> friend List addNodes();</div> <div> private:</div> <div> int size;</div> <div> Node * headNode;</div> <div> Node * currentNode;</div> <div> Node * lastCurrentNode;</div> <div> };</div> <div> /* Constructor */</div> <div> List::List()</div> <div> {</div> <div> headNode = new Node();</div> <div> headNode->setNext(NULL);</div> <div> currentNode = NULL;</div> <div> lastCurrentNode = NULL;</div> <div> size = 0;</div> <div> }</div> <div> /* add() class method */</div> <div> void List::add (int addObject)</div> <div> {</div> <div> Node * newNode = new Node();</div> <div> newNode->set(addObject);</div> <div> if( currentNode != NULL )</div> <div> {</div> <div> newNode->setNext(currentNode->getNext());</div> <div> currentNode->setNext( newNode );</div> <div> lastCurrentNode = currentNode;</div> <div> currentNode = newNode;</div> <div> }</div> <div> else</div> <div> {</div> <div> CS301 – Data Structures Lecture No. 03</div> <div> ___________________________________________________________________</div> <div> Page 30 of 505</div> <div> newNode->setNext(NULL);</div> <div> headNode->setNext(newNode);</div> <div> lastCurrentNode = headNode;</div> <div> currentNode = newNode;</div> <div> }</div> <div> size ++;</div> <div> }</div> <div> /* get() class method */</div> <div> int List::get()</div> <div> {</div> <div> if (currentNode != NULL)</div> <div> return currentNode->get();</div> <div> }</div> <div> /* next() class method */</div> <div> bool List::next()</div> <div> {</div> <div> if (currentNode == NULL) return false;</div> <div> lastCurrentNode = currentNode;</div> <div> currentNode = currentNode->getNext();</div> <div> if (currentNode == NULL || size == 0)</div> <div> return false;</div> <div> else</div> <div> return true;</div> <div> }</div> <div> /* Friend function to traverse linked list */</div> <div> void traverse(List list)</div> <div> {</div> <div> Node* savedCurrentNode = list.currentNode;</div> <div> list.currentNode = list.headNode;</div> <div> for(int i = 1; list.next(); i++)</div> <div> {</div> <div> cout << "\n Element " << i << " " << list.get();</div> <div> }</div> <div> list.currentNode = savedCurrentNode;</div> <div> }</div> <div> /* Friend function to add Nodes into the list */</div> <div> List addNodes()</div> <div> {</div> <div> List list;</div> <div> list.add(2);</div> <div> list.add(6);</div> <div> list.add(8);</div> <div> list.add(7);</div> <div> list.add(1);</div> <div> CS301 – Data Structures Lecture No. 03</div> <div> ___________________________________________________________________</div> <div> Page 31 of 505</div> <div> cout << "\n List size = " << list.size <<'\n';</div> <div> return list;</div> <div> }</div> <div> main()</div> <div> {</div> <div> List list = addNodes();</div> <div> traverse(list);</div> <div> }</div> <div> The output of the example program is as follows:</div> <div> List size = 5</div> <div> Element 1 2</div> <div> Element 2 6</div> <div> Element 3 8</div> <div> Element 4 7</div> <div> Element 5 1</div> <div> CS301 – Data Structures Lecture No. 04</div> <div> ___________________________________________________________________</div> <div> Page 32 of 505</div> <div> Data Structures</div> <div> Lecture No. 04</div> <div> <div> Reading Material</div> <div> Data Structures and algorithm analysis in C++ Chapter. 3</div> <div> 3.2.3, 3.2.4, 3.2.5</div> <div> Summary</div> <div> • Methods of Linked List</div> <div> • Example of list usage</div> <div> • Analysis of Link List</div> <div> • Doubly-linked List</div> <div> • Circularly-linked lists</div> <div> • Josephus Problem</div> <div> Methods of Linked List</div> <div> In the previous lecture, we discussed the methods of linked list. These methods form</div> <div> the interface of the link list. For further elucidation of these techniques, we will talk</div> <div> about the start method that has the following code.</div> <div> // position currentNode and lastCurrentNode at first element</div> <div> void start() {</div> <div> lastCurrentNode = headNode;</div> <div> currentNode = headNode;</div> <div> };</div> <div> There are two statements in this method. We assign the value of headNode to both</div> <div> lastCurrentNode and currentNode. These two pointers point at different nodes of the</div> <div> list. Here we have pointed both of these pointers at the start of the list. On calling</div> <div> some other method like next, these pointers will move forward. As we can move in</div> <div> the singly-linked list in one direction, these pointers cannot go behind headNode.</div> <div> We will now see how a node can be removed from the link list. We use the method</div> <div> remove for this purpose.</div> <div> void remove() {</div> <div> if( currentNode != NULL && currentNode != headNode) {</div> <div> (step 1) lastCurrentNode->setNext(currentNode->getNext());</div> <div> (step 2) delete currentNode;</div> <div> (step 3) currentNode = lastCurrentNode;</div> <div> (step 4) size--;</div> <div> }</div> <div> };</div> <div> CS301 – Data Structures Lecture No. 04</div> <div> ___________________________________________________________________</div> <div> Page 33 of 505</div> <div> Suppose that the currentNode is pointing at the location that contains the value 6. A</div> <div> request for the removal of the node is made. Resultantly, the node pointed by</div> <div> currentNode should be removed. For this purpose, at first, the next pointer of the node</div> <div> with value 2 (the node pointed by the lastCurrentNode pointer), that is before the</div> <div> node with value 6, bypasses the node with value 6. It is, now pointing to the node with</div> <div> value 8. The code of the first step is as:</div> <div> lastCurrentNode->setNext(currentNode->getNext());</div> <div> What does the statement currentNode->getNext() do? The currentNode is pointing to</div> <div> the node with value 6 while the next of this node is pointing to the node with value 8.</div> <div> That is the next pointer of node with value 6 contains the address of the node with</div> <div> value 8. The statement lastCurrentNode->setNext(currentNode->getNext()) will set</div> <div> the next pointer of the node pointed by the lastCurrentNode to the node with value 8.</div> <div> So the next pointer of the node with value 2 is pointing to the node with value 8.</div> <div> You see that the next pointer of the node having data element 2 contains the address</div> <div> of the node having data element 8. The node with value 6 has been disconnected from</div> <div> the chain while the node with value 2 is connected to the node with the value 8.</div> <div> The code of the next step is:</div> <div> delete currentNode;</div> <div> You already know, in case of allocation of the memory with the help of the new</div> <div> keyword, the delete statement releases this memory which returns the memory to the</div> <div> system. Pictorially it can be represented as:</div> <div> 6 7 1</div> <div> headNode</div> <div> currentNode</div> <div> Size = 5</div> <div> lastCurrentNode</div> <div> 2 8</div> <div> 6 7 1</div> <div> headNode</div> <div> currentNode</div> <div> Size = 5</div> <div> lastCurrentNode</div> <div> 2 8</div> <div> Step1</div> <div> CS301 – Data Structures Lecture No. 04</div> <div> ___________________________________________________________________</div> <div> Page 34 of 505</div> <div> In the next step, we have moved the currentNode to point the next node. The code is:</div> <div> currentNode = lastCurrentNode;</div> <div> In the fourth step, the size of the list has been reduced by 1 after the deletion of one</div> <div> node i.e.</div> <div> size--;</div> <div> The next method is length() that simply returns the size of the list. The code is as</div> <div> follows:</div> <div> // returns the size of the list</div> <div> int length()</div> <div> {</div> <div> return size;</div> <div> };</div> <div> The private data members of the list are:</div> <div> private:</div> <div> int size; // contains the size of the list</div> <div> Node *headNode; // points to the first node of the list</div> <div> Node *currentNode, // current node</div> <div> Node *lastCurrentNode; // last current node</div> <div> The list class completed just now, can be termed as list factory. We have included all</div> <div> 7 1</div> <div> headNode</div> <div> currentNode</div> <div> Size = 5</div> <div> lastCurrentNode</div> <div> 2 8</div> <div> Step1</div> <div> Step2</div> <div> 7 1</div> <div> headNode</div> <div> currentNode</div> <div> Size = 4</div> <div> lastCurrentNode</div> <div> 2 8</div> <div> Step1</div> <div> Step2</div> <div> Step3</div> <div> Step4</div> <div> CS301 – Data Structures Lecture No. 04</div> <div> ___________________________________________________________________</div> <div> Page 35 of 505</div> <div> the required methods in it. We may employ more methods if required. A programmer</div> <div> can get the size of the list, add or remove nodes in it besides moving the pointers.</div> <div> Example of list usage</div> <div> Now let’s see how we use the link list. Here is an example showing the use of list:</div> <div> /* A simple example showing the use of link list */</div> <div> #include <iostream></div> <div> #include <stdlib.h></div> <div> #include "List.cpp" // This contains the definition of List class</div> <div> // main method</div> <div> int main(int argc, char *argv[])</div> <div> {</div> <div> List list; // creating a list object</div> <div> // adding values to the list</div> <div> list.add(5);</div> <div> list.add(13);</div> <div> list.add(4);</div> <div> list.add(8);</div> <div> list.add(24);</div> <div> list.add(48);</div> <div> list.add(12);</div> <div> // calling the start method of the list</div> <div> list.start();</div> <div> // printing all the elements of the list</div> <div> while (list.next())</div> <div> cout << "List Element: "<< list.get()<<endl;</div> <div> }</div> <div> The output of the program is:</div> <div> List Element: 5</div> <div> List Element: 13</div> <div> List Element: 4</div> <div> List Element: 8</div> <div> List Element: 24</div> <div> List Element: 48</div> <div> List Element: 12</div> <div> Let’s discuss the code of the above program. We have included the standard libraries</div> <div> besides having the “List.cpp” file. Usually we do not include .cpp files. Rather, the .h</div> <div> files are included. Whenever you write a class, two files will be created i.e. .h (header</div> <div> file containing the interface of the class) and .cpp (implementation file). Here for the</div> <div> sake of explanation, we have combined the two files into “List.cpp” file. At the start</div> <div> CS301 – Data Structures Lecture No. 04</div> <div> ___________________________________________________________________</div> <div> Page 36 of 505</div> <div> of the main method, we have created a list object as:</div> <div> List list;</div> <div> Here the default constructor will be called. If you understand the concept of factory,</div> <div> then it is not difficult to know that we have asked the List factory to create a List</div> <div> object and named it as list. After creating the object, nodes have been added to it. We</div> <div> have added the elements with data values 5, 13, 4, 8, 24, 48 and 12. Later, the start()</div> <div> method of list is called that will position the currentNode and lastCurrentNode at the</div> <div> start of the list. Now there is no need to worry about the implementation of the List.</div> <div> Rather, we will use the interface of the List. So the start method will take us to the</div> <div> start of the list and internally, it may be array or link list or some other</div> <div> implementation. Then there is a while loop that calls the next() method of the List. It</div> <div> moves the pointer ahead and returns a boolean value i.e. true or false. When we reach</div> <div> at the end of the list, the next() method will return false. In the while loop we have a</div> <div> cout statement that prints the value of the list elements, employing the get() method.</div> <div> The loop will continue till the next() method returns true. When the pointers reach at</div> <div> the end of the list the next() will return false. Here the loop will come to an end.</div> <div> Please keep in mind that list is a very important data structure that will be used in the</div> <div> entire programming courses.</div> <div> Analysis of Link List</div> <div> As stated earlier, we will be going to analyze each data structure. We will see whether</div> <div> it is useful or not. We will see its cost and benefit with respect to time and memory.</div> <div> Let us analyze the link list which we have created with the dynamic memory</div> <div> allocation in a chain form.</div> <div> 􀂃 add</div> <div> For the addition purposes, we simply insert the new node after the current node.</div> <div> So ‘add’ is a one-step operation. We insert a new node after the current node in</div> <div> the chain. For this, we have to change two or three pointers while changing the</div> <div> values of some pointer variables. However, there is no need of traversing too</div> <div> much in the list. In case of an array, if we have to add an element in the centre of</div> <div> the array, the space for it is created at first. For this, all the elements that are after</div> <div> the current pointer in the array, should be shifted one place to the right. Suppose if</div> <div> we have to insert the element in the start of the array, all the elements to the right</div> <div> one spot are shifted. However, for the link list, it is not something relevant. In link</div> <div> lists, we can create a new node very easily where the current pointer is pointing.</div> <div> We have to adjust two or three pointers. Its cost, in terms of CPU time or</div> <div> computing time, is not much as compared to the one with the use of arrays.</div> <div> 􀂃 remove</div> <div> Remove is also a one-step operation. The node before and after the node to be</div> <div> removed is connected to each other. Update the current pointer. Then the node to</div> <div> be removed is deleted. As a result, the node to be removed is deleted. Very little</div> <div> work is needed in this case. If you compare it with arrays, for the deletion of an</div> <div> element from the array, space is created. To fill this space, all the right elements</div> <div> are shifted one spot left. If the array size is two thousand or three thousand, we</div> <div> need to run a loop for all these elements to shift them to left.</div> <div> CS301 – Data Structures Lecture No. 04</div> <div> ___________________________________________________________________</div> <div> Page 37 of 505</div> <div> 􀂃 find</div> <div> The worst-case in find is that we may have to search the entire list. In find, we</div> <div> have to search some particular element say x. If found, the currentNode pointer is</div> <div> moved at that node. As there is no order in the list, we have to start search from</div> <div> the beginning of the list. We have to check the value of each node and compare it</div> <div> with x (value to be searched). If found, it returns true and points the currentNode</div> <div> pointer at that node otherwise returns false. Suppose that x is not in the list, in this</div> <div> case, we have to search the list from start to end and return false. This is the worst</div> <div> case scenario. Though time gets wasted, yet we find the answer that x is not in the</div> <div> list. If we compare this with array, it will be the same. We don’t know whether x</div> <div> is in the array or not. So we have to search the complete array. In case of finding</div> <div> it, we will remember that position and will return true. What is the average case? x</div> <div> can be found at the first position , in the middle or at the end of the list. So on</div> <div> average, we have to search half of the list.</div> <div> 􀂃 back</div> <div> In the back method, we move the current pointer one position back. Moving the</div> <div> current pointer back, one requires traversing the list from the start until the node</div> <div> whose next pointer points to current node. Our link list is singly linked list i.e. we</div> <div> can move in one direction from start towards end. Suppose our currentNode</div> <div> pointer and lastCurrentNode are somewhere in the middle of the list. Now we</div> <div> want to move one node back. If we have the pointer of lastCurrentNode, it will be</div> <div> easy. We will assign the value of lastCurrentNode to currentNode. But how can</div> <div> we move the lastCurrentNode one step back. We don’t have the pointer of</div> <div> previous node. So the solution for this is to go at the start of the list and traverse</div> <div> the list till the time you reach the node before the lastCurrentNode is pointing.</div> <div> That will be the node whose next pointer contains the value lastCurrentNode. If</div> <div> the currentNode and the lastCurrentNode are at the end of the list, we have to</div> <div> traverse the whole list. Therefore back operation is not a one step operation. We</div> <div> not only need a loop here but also require time.</div> <div> Doubly-linked List</div> <div> If you look at single link list, the chain is seen formed in a way that every node has a</div> <div> field next that point to the next node. This continues till the last node where we set the</div> <div> next to NULL i.e. the end of the list. There is a headNode pointer that points to the</div> <div> start of the list. We have seen that moving forward is easy in single link list but going</div> <div> back is difficult. For moving backward, we have to go at the start of the list and begin</div> <div> from there. Do you need a list in which one has to move back or forward or at the start</div> <div> or in the end very often? If so, we have to use double link list.</div> <div> In doubly-link list, a programmer uses two pointers in the node, i.e. one to point to</div> <div> next node and the other to point to the previous node. Now our node factory will</div> <div> create a node with three parts.</div> <div> First part is prev i.e. the pointer pointing to the previous node, second part is element,</div> <div> prev element next</div> <div> CS301 – Data Structures Lecture No. 04</div> <div> ___________________________________________________________________</div> <div> Page 38 of 505</div> <div> containing the data to be inserted in the list. The third part is next pointer that points to</div> <div> the next node of the list. The objective of prev is to store the address of the previous</div> <div> node.</div> <div> Let’s discuss the code of the node of the doubly-link list. This node factory will create</div> <div> nodes, each having two pointers. The interface methods are same as used in singly</div> <div> link list. The additional methods are getPrev and setPrev. The method getPrev returns</div> <div> the address of the previous node. Thus its return type is Node*. The setPrev method</div> <div> sets the prev pointer. If we have to assign some address to prev pointer, we will call</div> <div> this method. Following is the code of the doubly-linked list node.</div> <div> /* this is the doubly-linked list class, it uses the next and prev pointers */</div> <div> class Node {</div> <div> public:</div> <div> int get() { return object; }; // returns the value of the element</div> <div> void set(int object) { this->object = object; }; // set the value of the element</div> <div> Node* getNext() { return nextNode; }; // get the address of the next node</div> <div> void setNext(Node* nextNode) // set the address of the next node</div> <div> { this->nextNode = nextNode; };</div> <div> Node* getPrev() { return prevNode; }; // get the address of the prev node</div> <div> void setPrev(Node* prevNode) // set the address of the prev node</div> <div> { this->prevNode = prevNode; };</div> <div> private:</div> <div> int object; // it stores the actual value of the element</div> <div> Node* nextNode; // this points to the next node</div> <div> Node* prevNode; // this points to the previous node</div> <div> };</div> <div> Most of the methods are same as those in singly linked list. A new pointer prevNode</div> <div> is added and the methods to get and set its value i.e. getPrev and setPrev. Now we</div> <div> will use this node factory to create nodes.</div> <div> You have to be very cautious while adding or removing a node in a doubly linked list.</div> <div> The order in which pointers are reorganized is important. Let’s have a pictorial view</div> <div> of doubly-link list. The diagram can help us understand where the prevNode and</div> <div> nextNode are pointing.</div> <div> This is a doubly link list. The arrows pointing towards right side are representing</div> <div> nextNode while those pointing towards left side are representing prevNode. Suppose</div> <div> head 2 6 8 7 1 size=5</div> <div> current</div> <div> CS301 – Data Structures Lecture No. 04</div> <div> ___________________________________________________________________</div> <div> Page 39 of 505</div> <div> we are at the last node i.e. the node with value 1. In case of going back, we usually</div> <div> take the help of prevNode pointer. So we can go to the previous node i.e. the node</div> <div> with value 7 and then to the node with value 8 and so on. In this way, we can traverse</div> <div> the list from the end to start. We can move forward or backward in doubly-link list</div> <div> very easily. We have developed this facility for the users to move in the list easily.</div> <div> Let’s discuss other methods of the doubly-linked list. Suppose we have created a new</div> <div> node from the factory with value 9. We will request the node factory to create a new</div> <div> object using new keyword. The newly created node contains three fields i.e. object,</div> <div> prevNode and nextNode. We will store 9 into object and connect this new node in the</div> <div> chain. Let’s see how the pointers are manipulated to do that. Consider the above</div> <div> diagram, the current is pointing at the node with value 6. The new node will be</div> <div> inserted between the node with value 6 and the one with value 8.</div> <div> In the first step, we assign the address of the node with value 8 to the nextNode of the</div> <div> new node.</div> <div> newNode->setNext( current->getNext() );</div> <div> In the next step, a programmer points the prevNode of the newNode to the node with</div> <div> value 6.</div> <div> newNode->setprev( current );</div> <div> In the third step, we will set the previous node with value 8 to point to the newNode.</div> <div> (current->getNext())->setPrev(newNode);</div> <div> head 2 6 8 7 size=5</div> <div> current</div> <div> 1</div> <div> newNode 9 1</div> <div> 2</div> <div> head 2 6 8 7 size=5</div> <div> current</div> <div> 1</div> <div> newNode 9 1</div> <div> CS301 – Data Structures Lecture No. 04</div> <div> ___________________________________________________________________</div> <div> Page 40 of 505</div> <div> Now the prevNode of the node with value 8 is pointing to the node with value 9.</div> <div> In the fourth step, the nextNode of the node with value 6 is pointing to the newNode</div> <div> i.e. the node with value 9. Point the current to the newNode and add one to the size of</div> <div> the list.</div> <div> current->setNext( newNode );</div> <div> current = newNode;</div> <div> size++;</div> <div> Now the newNode has been inserted between node with value 6 and node with value</div> <div> 8.</div> <div> Circularly-linked lists</div> <div> Let’s talk about circularly linked list. The next field in the last node in a singly-linked</div> <div> list is set to NULL. The same is the case in the doubly-linked list. Moving along a</div> <div> singly-linked list has to be done in a watchful manner. Doubly-linked lists have two</div> <div> NULL pointers i.e. prev in the first node and next in the last node. A way around this</div> <div> potential hazard is to link the last node with the first node in the list to create a</div> <div> circularly-linked list.</div> <div> The next method in the singly-linked list or doubly-linked list moves the current</div> <div> pointer to the next node and every time it checks whether the next pointer is NULL or</div> <div> not. Similarly the back method in the double-linked list has to be employed carefully</div> <div> if the current is pointing the first node. In this case, the prev pointer is pointing to</div> <div> NULL. If we do not take care of this, the current will be pointing to NULL. So if we</div> <div> try to access the NULL pointer, it will result in an error. To avoid this, we can make a</div> <div> circularly linked list.</div> <div> head 2 6 8 7 size=6</div> <div> current</div> <div> 1</div> <div> newNode 9 1</div> <div> 2 4 3</div> <div> 9 1</div> <div> head 2 6 8 7 size=5</div> <div> current</div> <div> 1</div> <div> newNode</div> <div> 2 3</div> <div> CS301 – Data Structures Lecture No. 04</div> <div> ___________________________________________________________________</div> <div> Page 41 of 505</div> <div> We have a list with five elements. We have connected the last node with the first</div> <div> node. It means that the next of the last node is pointing towards the first node.</div> <div> The same list has been shown in a circular shape.</div> <div> You have noticed that there is no such node whose next field is NULL. What is the</div> <div> benefit of this? If you use the next or back methods that move the current pointer, it</div> <div> will never point to NULL. It may be the case that you keep on circulating in the list.</div> <div> To avoid this, we get help from the head node. If we move the head node in the</div> <div> circularly linked list, it will not be certain to say where it was pointing in the start. Its</div> <div> advantages depend on its use. If we do not have to move too much in the list and have</div> <div> no problem checking the NULL, there is little need a circularly-linked list. But this</div> <div> facility is available to us.</div> <div> In this example, we made a circular linked list from a singly link list. In a singly link</div> <div> list we move in one direction. We point the next pointer of the last node to the first</div> <div> node. We can do the same with the doubly-linked list. The prev pointer of the first</div> <div> node will point to the last node and the next pointer of the last node will point to the</div> <div> first node. If you arrange all the nodes in a circle, one of the pointers (i.e. next</div> <div> pointer) will move in clockwise direction while the prev pointers in anti-clockwise</div> <div> direction. With the help of these pointers, you can move in the clockwise direction or</div> <div> anti-clockwise direction. Head node pointer will remain at its position. You don’t</div> <div> need to change it. If there is a need to remove the node pointed by head node than you</div> <div> have to move the head pointer to other node. Now we don’t have any NULL pointer</div> <div> in the doubly-linked list. We will not get any exception due to NULL pointers.</div> <div> 2</div> <div> 8</div> <div> 7</div> <div> 1</div> <div> head</div> <div> current</div> <div> size=5</div> <div> 6</div> <div> head 2 6 8 7 1</div> <div> current</div> <div> size=5</div> <div> CS301 – Data Structures Lecture No. 04</div> <div> ___________________________________________________________________</div> <div> Page 42 of 505</div> <div> Josephus Problem</div> <div> Now we will see an example where circular link list is very useful. This is Josephus</div> <div> Problem. Consider there are 10 persons. They would like to choose a leader. The way</div> <div> they decide is that all 10 sit in a circle. They start a count with person 1 and go in</div> <div> clockwise direction and skip 3. Person 4 reached is eliminated. The count starts with</div> <div> the fifth and the next person to go is the fourth in count. Eventually, a single person</div> <div> remains.</div> <div> You might ask why someone has to choose a leader in this way. There are some</div> <div> historical stories attached to it. This problem is also studied in mathematics. Let’s see</div> <div> its pictorial view.</div> <div> We have ten numbers representing the ten persons who are in a circle. The value of M</div> <div> shows the count. As the value of M is three, the count will be three. N represents the</div> <div> number of persons. Now we start counting clockwise. After counting up to three, we</div> <div> have the number four. The number four is eliminated and put in the eliminated</div> <div> column.</div> <div> After eliminating the number four, we will start our counting from number five.</div> <div> Counting up to three, we have number eight which is eliminated and so on.</div> <div> N=10, M=3</div> <div> 4</div> <div> 5</div> <div> 6</div> <div> 7</div> <div> 9 8</div> <div> 10</div> <div> 1</div> <div> 2</div> <div> 3</div> <div> N=10, M=3</div> <div> 4</div> <div> 5</div> <div> 6</div> <div> 7</div> <div> 9 8</div> <div> 10</div> <div> 1</div> <div> 2</div> <div> 3</div> <div> Eliminated</div> <div> CS301 – Data Structures Lecture No. 04</div> <div> ___________________________________________________________________</div> <div> Page 43 of 505</div> <div> In the end, only number five will remain intact.</div> <div> If we have ten persons (N = 10) in a circle and eliminate after counting up to three (M</div> <div> = 3). If we start our count from one, who will be the leader? We have studied this</div> <div> earlier and know that the person who is sitting at the fifth position will become the</div> <div> leader.</div> <div> Suppose if the value of N is 300 or 400 and the value of M is 5 or 10. Now who will</div> <div> be the leader? This is a mathematical problem where we can change the values of N</div> <div> and M. There is a formula where the values of N, M are allotted. You can calculate</div> <div> who should become the leader. Here we will not solve it mathematically. Rather, it</div> <div> will be tackled as a computer problem. If you analyze the pictures shown above, it</div> <div> gets clear that this can be solved with the circular link list. We arrange these numbers</div> <div> in a circularly-linked list, point the head pointer at the starting number and after</div> <div> calling the next method for three times, we will reach the node which is to be</div> <div> removed. We will use the remove method to remove the node. Then the next method</div> <div> is called thrice from there and the node is removed. We will continue this till we have</div> <div> N=10, M=3 4</div> <div> 5</div> <div> 6</div> <div> 7</div> <div> 8</div> <div> 9</div> <div> 10</div> <div> 1</div> <div> 2</div> <div> 3</div> <div> Eliminated</div> <div> N=10, M=3</div> <div> 4</div> <div> 5</div> <div> 6</div> <div> 7</div> <div> 8</div> <div> 9</div> <div> 10</div> <div> 1</div> <div> 2</div> <div> 3</div> <div> Eliminated</div> <div> CS301 – Data Structures Lecture No. 04</div> <div> ___________________________________________________________________</div> <div> Page 44 of 505</div> <div> only one node.</div> <div> We are not concerned with the NULL pointers, internal to link list. However, if you</div> <div> want to solve this problem and choose the best data structure, then circular link list is</div> <div> the best option. We can also use the list to solve this.</div> <div> Let’s see the code of the program by which we can solve this problem. The code is as</div> <div> under:</div> <div> /*This program solves the Josephus Problem */</div> <div> #include <iostream.h></div> <div> #include "CList.cpp" //contains the circularly-linked list definition</div> <div> // The main method</div> <div> void main(int argc, char *argv[])</div> <div> {</div> <div> CList list; // creating an object of list</div> <div> int i, N=10, M=3;</div> <div> for(i=1; i <= N; i++ ) list.add(i); // initializing the list with values</div> <div> list.start(); // pointing the pointers at the start of the list</div> <div> // counting upto M times and removing the element</div> <div> while( list.length() > 1 ) {</div> <div> for(i=1; i <= M; i++ ) list.next();</div> <div> cout << "remove: " << list.get() << endl;</div> <div> list.remove();</div> <div> }</div> <div> cout << "leader is: " << list.get() << endl; //displaying the remaining node</div> <div> }</div> <div> We have included the “CList.cpp”. It means that we are using the circularly-linked</div> <div> list. In the main method, CList factory is called to create a circular link list as CList</div> <div> list; After this, we assign the values to N and M. We have used for loop to add the</div> <div> nodes in the list. When this loop finishes, we have ten nodes in the list having values</div> <div> from 1 to 10. But here a programmer may not pay attention to the internal details of</div> <div> the list. We have created a list and stored ten numbers in it. Then we moved the</div> <div> pointers of the list at the start of the list using the start method. It means that the</div> <div> pointers are pointing at the position from where we want to start the counting of the</div> <div> list.</div> <div> There is a while loop that will continue executing until only one node is left in the list.</div> <div> Inside this loop, we have a for loop. It will execute from 1 to M. It has only one</div> <div> statement i.e. list.next(). This will move the pointer forward three times (as the value</div> <div> of M is 3). Now the current pointer is at the 4th node. We called the remove method.</div> <div> Before removing the node, we display its value on the screen using cout. Again we</div> <div> come into the while loop, now the length of the list is 9. The ‘for loop’ will be</div> <div> executed. Now the list.next() is not starting from the start. It will start from the</div> <div> CS301 – Data Structures Lecture No. 04</div> <div> ___________________________________________________________________</div> <div> Page 45 of 505</div> <div> position where the current pointer is pointing. The current pointer is pointing at the</div> <div> next node to the node deleted. The count will start again. The list.next() will be called</div> <div> for three times. The current pointer will point at the 8th node. Again the remove</div> <div> method will be called and the current pointer moved to the next node and so on. The</div> <div> nodes will be deleted one by one until the length of the list is greater than one. When</div> <div> the length of the list is one, the while loop will be terminated. Now only one node is</div> <div> left in the list i.e. the leader. We will display its value using the get method.</div> <div> We can change the values of M and N. Similarly, these values can be read from the</div> <div> file or can use the command line arguments to get values. There are many variations</div> <div> of this problem. One variation is that the value of M keeps on changing. Sometimes, it</div> <div> is 3, sometimes 4 or 5 and so on. Due to this, it will become difficult to think that who</div> <div> will become leader. Make a picture in your mind that ten persons are sitting in a</div> <div> circle. Every time the value of M is incremented by one. Now try to ascertain which</div> <div> position you should sit to get chosen as a leader. You may like to write a program to</div> <div> solve this or use the mathematical formula.</div> <div> CS301 – Data Structures Lecture No. 05</div> <div> ___________________________________________________________________</div> <div> Page 46 of 505</div> <div> Data Structures</div> <div> Lecture No. 05</div> <div> Reading Material</div> <div> Data Structures and Algorithm Analysis in C++ Chapter. 3</div> <div> 3.1, 3.2.5, 3.3.1, 3.3.2</div> <div> (array implementation)</div> <div> Summary</div> <div> 5) Benefits of using circular list</div> <div> 6) Abstract Data Type</div> <div> 7) Stacks</div> <div> 8) Stack Implementation using arrays</div> <div> In the previous lecture, we demonstrated the use of the circular list for the resolution</div> <div> of the Josephus problem. After writing a program with the help of this data structure,</div> <div> a leader among ten persons was selected. You must have noted many things while</div> <div> trying to solve the problem. These things will help us to understand the usage of data</div> <div> structures in C++, thus making the programming easy. The code of the program is</div> <div> given below.</div> <div> #include "CList.cpp"</div> <div> void main(int argc, char *argv[])</div> <div> {</div> <div> CList list;</div> <div> int i, N=10, M=3;</div> <div> for(i=1; i <= N; i++ ) list.add(i);</div> <div> list.start();</div> <div> while( list.length() > 1 ) {</div> <div> for(i=1; i <= M; i++ ) list.next();</div> <div> cout << "remove: " << list.get() << endl;</div> <div> list.remove();</div> <div> }</div> <div> cout << "leader is: " << list.get() << endl;</div> <div> }</div> <div> In the program, we include the file of the class CList and create its object i.e. list.</div> <div> Then we solve the problem by using the add, start, length, next, remove and get</div> <div> methods of the class CList.</div> <div> CS301 – Data Structures Lecture No. 05</div> <div> ___________________________________________________________________</div> <div> Page 47 of 505</div> <div> In the program, we have included already-defined data structure CList. After defining</div> <div> its different methods, we have an interface of Clist. There is no need to be worry</div> <div> about the nature of the list i.e. whether it is linked list, doubly linked list or an array.</div> <div> For us, it is only a list to be manipulated according to our requirement. You will see</div> <div> that a programmer may use different methods of the list object to solve the problem.</div> <div> We add elements to the list by a simple call of add method and go to the first element</div> <div> of the list by start method. Here, the length method is used in the condition of the</div> <div> while loop. Then we remove elements from the list and use the next, get and remove</div> <div> methods during this process. We get the current element by using the get method, then</div> <div> remove it by calling the remove method and then go to the next element by the</div> <div> method next. This way, all the elements are removed from the list except one element,</div> <div> called the leader. This one element remains there as we execute the while loop one</div> <div> less than the length of the list.</div> <div> In singly linked list, the ‘next’ returns false when it reaches to the last node due to the</div> <div> fact that the next field of the last node is set to NULL. But in a circularly linked list</div> <div> there is no NULL. It will be there only when there is no node in the list.</div> <div> The whole process, which we carried out to solve the Josephus problem, can also be</div> <div> carried out with functions in C++. While adopting this way (of writing functions), we</div> <div> have to write these functions whenever we write another program that manipulates a</div> <div> list. In this method, we define a class of the data structure list and its different</div> <div> methods for the purpose of manipulation. This way, this class, obviously its methods</div> <div> too, can be used in any program where the manipulation of a list is needed. Thus there</div> <div> is re-usability of the code. In a class, we encapsulate the data and its methods. This</div> <div> shows that we are no longer interested in the internal process of the class. Rather, we</div> <div> simply use it wherever needed. The circular linked list, earlier used for the resolution</div> <div> of the Josephus problem, can also be employed in other problems. We have a class</div> <div> CList of this circular linked list through which any number of objects of data type of</div> <div> circular linked list can be created. Thus we can assume the class CList as a factory,</div> <div> creating as many objects of list as needed. This class and its objects in any program</div> <div> can be used to solve the problems with the help of its interface. The interface of this</div> <div> class consists of some methods like add, remove, next, back, get and some other</div> <div> simple ones. While carrying out programming, we will see that these classes (objects)</div> <div> help us very much to solve different problems.</div> <div> Benefits of using circular list</div> <div> While solving the Josephus problem, it was witnessed that the usage of circular linked</div> <div> list helped us make the solution trivial. We had to just write a code of some lines that</div> <div> solved the whole problem. In the program, we included the class CList (which is of</div> <div> our data structure i.e. circular linked list) and used all of its methods according to the</div> <div> requirements. There was no problem regarding the working of the methods. We just</div> <div> called these methods and their definition in the class CList worked well.</div> <div> Now we will see what happens if we solve the Josephus problem by using an array</div> <div> instead of the class in our program. In this case, we have to define an array and write</div> <div> code to move back and forth in the array and to remove different elements properly in</div> <div> a particular order. A programmer needs to be very careful while doing this, to reach</div> <div> the solution of the problem. Thus our code becomes very complex and difficult for</div> <div> CS301 – Data Structures Lecture No. 05</div> <div> ___________________________________________________________________</div> <div> Page 48 of 505</div> <div> someone to understand and modify it. Moreover we cannot use this code in some</div> <div> other problem. Note that here we are talking about the use of an array in the main</div> <div> program, not in the class that defines the CList data structure. There is no need to be</div> <div> worried whether an array, singly linked list, doubly linked list is used or circular</div> <div> linked list being employed internally in implementing the list in defining the class of</div> <div> list data type. We only want that it should create objects of list. The usage of the class</div> <div> of a data structure simplifies the code of the program. We can also use this class</div> <div> wherever needed in other programs. This shows that the choice of appropriate data</div> <div> structures can simplify an algorithm. It can make the algorithm much faster and</div> <div> efficient. In this course, we will see that there are different data structures, which</div> <div> makes the algorithms very easy to solve our problems. Later, we will see how some</div> <div> elegant data structures lie at the heart of major algorithms. There is also a course</div> <div> dedicated to study different algorithms and recipes that can be used to solve host of</div> <div> complex problems. Moreover, we will study different data structures in detail and see</div> <div> that with the use of a proper data structure, we can solve a problem efficiently. A</div> <div> properly constructed data structure will always help in the solution of problems.</div> <div> Abstract Data Type</div> <div> A data type is a collection of values and a set of operations on those values. That</div> <div> collection and these operations form a mathematical construct that may be</div> <div> implemented with the use of a particular hardware or software data structure. The</div> <div> term abstract data type (ADT) refers to the basic mathematical concept that defines</div> <div> the data type. We have discussed four different implementations of the list data</div> <div> structure. In case of implementation of the list with the use of an array, the size of the</div> <div> array gives difficulty if increased. To avoid this, we allocate memory dynamically for</div> <div> nodes before connecting these nodes with the help of pointers. For this purpose, we</div> <div> made a singly linked list and connected it with the next pointer to make a chain.</div> <div> Moving forward is easy but going back is a difficult task. To overcome this problem,</div> <div> we made a doubly linked list using prev and next pointers. With the help of these</div> <div> pointers, we can move forward and backward very easily. Now we face another</div> <div> problem that the prev pointer of first node and the next pointer of the last node are</div> <div> NULL. Therefore, we have to be careful in case of NULL pointers. To remove the</div> <div> NULL pointers, we made the circular link list by connecting the first and last node.</div> <div> The program employing the list data structure is not concerned with its</div> <div> implementation. We do not care how the list is being implemented whether through</div> <div> an array, singly linked list, doubly linked list or circular linked list. It has been</div> <div> witnessed that in these four implementations of the list, the interface remained the</div> <div> same i.e. it implements the same methods like add, get, next, start and remove etc.</div> <div> This proves that with this encapsulation attained by making a class, we are not</div> <div> concerned with its internal implementation. The implementation of these abstract data</div> <div> types can be changed anytime. These abstract data types are implemented using</div> <div> classes in C++. If the list is implemented using arrays while not fulfilling the</div> <div> requirements, we can change the list implementation. It can be implemented with the</div> <div> use of singly-link list or doubly link list. As long as the interface is same, a</div> <div> programmer can change the internal implementation of the list and the program using</div> <div> this list will not be affected at all. This is the abstract data type (ADT). What we care</div> <div> about is the methods that are available for use, with the List ADT i.e. add, get, and</div> <div> remove etc methods. We have not studied enough examples to understand all the</div> <div> CS301 – Data Structures Lecture No. 05</div> <div> ___________________________________________________________________</div> <div> Page 49 of 505</div> <div> benefits of abstract data types. We will follow this theme while developing other</div> <div> ADT. We will publish the interface and keep the freedom to change the</div> <div> implementation of ADT without effecting users of the ADT. The C++ classes provide</div> <div> a programmer an ability to create such ADTs. What benefits can we get with the help</div> <div> of these ADTs and classes? When we develop an ADT or a class or factory then the</div> <div> users of this factory are independent of how this factory works internally. Suppose</div> <div> that we have ordered the car factory (car class) to produce a new car and it replies</div> <div> after a long time. If we ordered the remove method to remove one node and we are</div> <div> waiting and it keeps on working and working. Then we might think that its</div> <div> implementation is not correct. Although, we are not concerned with the internal</div> <div> implementation of this ADT yet it is necessary to see whether this ADT is useful for</div> <div> solving our problem or not. It should not become a bottleneck for us. If the method we</div> <div> are using is too much time consuming or it has some problem in terms of algorithm</div> <div> used. On one side, we only use the interfaces provided by these ADTs, classes, or</div> <div> factories as long as they do what they promise. We are not concerned with the internal</div> <div> details. On the other hand, we have to be careful that these factories or methods</div> <div> should not take too much time so that these will not be useful for the problem.</div> <div> This distinction will always be there. Sometimes, the source code of classes is not</div> <div> provided. We will be provided libraries, as standard libraries are available with the</div> <div> compiler. These classes are in compiled form i.e. are in object form or in binary form.</div> <div> On opening these files, you will not see the C++ code, rather binary code. When you</div> <div> read the assembly language code, it will give some idea what this binary code is</div> <div> about. You can view the interface methods in the .h file. As an application</div> <div> programmer, you have to see that the ADTs being used are written in a better way.</div> <div> The point to be remembered here is that you should not worry about the internal</div> <div> implementation of these ADTs. If we want to change the internal implementation of</div> <div> the ADTs, it can be done without affecting the users of these ADTs. While writing a</div> <div> program, you should check its performance. If at some point, you feel that it is slow,</div> <div> check the ADTs used at that point. If some ADT is not working properly, you can ask</div> <div> the writer of the ADT to change the internal implementation of that ADT to ensure</div> <div> that it works properly.</div> <div> Stacks</div> <div> Let’s talk about another important data structure. You must have a fair idea of stacks.</div> <div> Some examples of stacks in real life are stack of books, stack of plates etc. We can</div> <div> add new items at the top of the stack or remove them from the top. We can only</div> <div> access the elements of the stack at the top. Following is the definition of stacks.</div> <div> “Stack is a collection of elements arranged in a linear order”</div> <div> Let’s see an example to understand this. Suppose we have some video cassettes. We</div> <div> took one cassette and put it on the table. We get another cassette and put it on the top</div> <div> of first cassette. Now there are two cassettes on the table- one at the top of other. Now</div> <div> we take the third cassette and stack it on the two. Take the fourth cassette and stack it</div> <div> on the three cassettes.</div> <div> Now if we want to take the cassette, we can get the fourth cassette which is at the top</div> <div> and remove it from the stack. Now we can remove the third cassette from the stack</div> <div> CS301 – Data Structures Lecture No. 05</div> <div> ___________________________________________________________________</div> <div> Page 50 of 505</div> <div> and so on. Suppose that we have fifty cassettes stacked on each other and want to</div> <div> access the first cassette that is at the bottom of the stack. What will happen? All the</div> <div> cassettes will fell down. It will not happen exactly the same in the computer. There</div> <div> may be some problem. It does not mean that our data structure is incorrect. As we see</div> <div> in the above example that the top most cassette will be removed first and the new</div> <div> cassette will be stacked at the top. The same example can be repeated with the books.</div> <div> In the daily life, we deal with the stacked goods very carefully.</div> <div> Now we will discuss how to create a stack data structure or a factory, going to create</div> <div> stack object for us. What will be the attributes of this object? During the discussion on</div> <div> the list, we came to know that a programmer adds values in the list, removes values</div> <div> from the list and moves forward and backward. In case of a stack too, we want to add</div> <div> things and remove things. We will not move forward or backward in the stack. New</div> <div> items can be added or removed at the top only. We can not suggest the removal of the</div> <div> middle element of the stack.</div> <div> Let’s talk about the interface methods of the stacks. Some important methods are:</div> <div> Method Name Description</div> <div> push(x) Insert x as the top element of the stack</div> <div> pop() Remove the top element of the stack and return it.</div> <div> top() Return the top element without removing it from the stack.</div> <div> The push(x) method will take an element and insert it at the top of the stack. This</div> <div> element will become top element. The pop() method will remove the top element of</div> <div> the stock and return it to the calling program. The top() method returns the top-most</div> <div> stack element but does not remove it from the stack. The interface method names that</div> <div> we choose has special objective. In case of list, we have used add, remove, get, set as</div> <div> the suitable names. However, for stack, we are using push, pop and top. We can</div> <div> depict the activity from the method name like push means that we are placing an</div> <div> element on the top of the stack and pushing the other elements down.</div> <div> The example of a hotel’s kitchen may help understand the concept of stacks in a</div> <div> comprehensive manner. In the kitchen, the plates are stacked in a cylinder having a</div> <div> spring on the bottom. When a waiter picks a plate, the spring moves up the other</div> <div> plates. This is a stack of plates. You will feel that you are pushing the plates in the</div> <div> cylinder and when you take a plate from the cylinder it pops the other plates. The top</div> <div> method is used to get the top- most element without removing it.</div> <div> When you create classes, interfaces and methods, choose such names which depicts</div> <div> what these method are doing. These names should be suitable for that class or factory.</div> <div> Let’s discuss the working of stack with the help of a diagram.</div> <div> CS301 – Data Structures Lecture No. 05</div> <div> ___________________________________________________________________</div> <div> Page 51 of 505</div> <div> At the start, the stack is empty. First of all, we push the value 2 in the stack. As a</div> <div> result, the number 2 is placed in the stack. We have a top pointer that points at the top</div> <div> element. Then we said push(5). Now see how 2 and 5 are stacked. The number 5 is</div> <div> placed at the top of number 2 and the pointer top moves one step upward. Then we</div> <div> pushed the number 7 which is placed on the top and the number 2 and 5 are below.</div> <div> Similarly, we push number 1. The last figure in the first row shows the stacked values</div> <div> of the numbers- 1, 7, 5 and 2.</div> <div> Let’s pop the elements from the stack. The first figure of second row shows the pop</div> <div> operation. As a result, the number 1 is popped. Than again we push the number 21 on</div> <div> the stack. The number 7, 5, and 2 are already in the stack and number 21 is pushed at</div> <div> the top. If we pop now, the number 21 is popped. Now number 7 is at the top. If we</div> <div> pop again, the number 7 is popped. Pop again and the number 5 is popped and number</div> <div> 2 remains in the stack. Here with the help of this diagram, we are proving that the</div> <div> values are added at the top and removed at the top in a stack.</div> <div> The last element to go into the stack is the first to come out. That is why, a stack is</div> <div> known as LIFO (Last In First Out) structure. We know that the last element pushed in</div> <div> the stack is at the top which is removed when we call pop. Let’s see some other</div> <div> scenarios. What happens if we call pop() while there is no element? One possible</div> <div> way-out is that we have isEmpty() function that returns true if stack is empty and false</div> <div> otherwise. This is a boolean function that returns false if there is no element in the</div> <div> stack. Otherwise, it will return true. The second option is this that when we call pop</div> <div> on an empty stack, it throws an exception. This is a concept of advanced C++.</div> <div> Exception is also a way to convey that some unusual condition has arisen or</div> <div> something has gone wrong. Suppose, if we have a division method and try to divide</div> <div> some number with zero. This method will throw ‘division by zero’ exception.</div> <div> push(2)</div> <div> top 2</div> <div> push(5)</div> <div> top</div> <div> 2</div> <div> 5</div> <div> push(7)</div> <div> top</div> <div> 2</div> <div> 5</div> <div> 7</div> <div> push(1)</div> <div> top</div> <div> 2</div> <div> 5</div> <div> 7</div> <div> 1</div> <div> 1 pop()</div> <div> top</div> <div> 2</div> <div> 5</div> <div> 7</div> <div> push(21)</div> <div> top</div> <div> 2</div> <div> 5</div> <div> 7</div> <div> 21</div> <div> 21 pop()</div> <div> top</div> <div> 2</div> <div> 5</div> <div> 7</div> <div> 7 pop()</div> <div> 2</div> <div> top 5</div> <div> top 2</div> <div> 5 pop()</div> <div> CS301 – Data Structures Lecture No. 05</div> <div> ___________________________________________________________________</div> <div> Page 52 of 505</div> <div> Currently we will not throw an exception but use the isEmpty() method. The user who</div> <div> is employing the stack is responsible to call the isEmpty() method before calling the</div> <div> pop. Call the pop method if isEmpty() returns false . Otherwise, there will be a</div> <div> problem.</div> <div> Stack Implementation using array</div> <div> Let’s discuss the implementation of the stack. Suppose we implement the stack using</div> <div> the arrays. The stack shown in the above diagram may be considered as an array. Here</div> <div> the array is shown vertically. We can implement the stack using array. The interface</div> <div> will remain as push and pop methods. The user of the stack does not need to know</div> <div> that the stack is internally implemented with the help of array. The worst case for</div> <div> insertion and deletion from an array may happen when we insert and delete from the</div> <div> beginning of the array. We have to shift elements to the right for insertion and left for</div> <div> removal of an element. We face the same problem while implementing the list with</div> <div> the use of the array. If we push and pop the elements from the start of the array for</div> <div> stack implementation, this problem will arise. In case of push, we have to shift the</div> <div> stack elements to the right. However, in case of pop, after removing the element, we</div> <div> have to shift the elements of stack that are in the array to the left. If we push the</div> <div> element at the end of the array, there is no need to shift any element. Similarly as the</div> <div> pop method removes the last element of the stack which is at the end of the array, no</div> <div> element is shifted. To insert and remove elements at the end of the array we need not</div> <div> to shift its elements. Best case for insert and delete is at the end of the array where</div> <div> there is no need to shift any element. We should implement push() and pop() by</div> <div> inserting and deleting at the end of an array.</div> <div> In the above diagram, on the left side we have a stack. There are four elements in the</div> <div> stack i.e. 1, 7, 5 and 2. The element 1 is the extreme-most that means that it is inserted</div> <div> in the end whereas 7, 5, and 2 have been added before. As this is a LIFO structure so</div> <div> the element 1 should be popped first. On the right side we have an array with</div> <div> positions 0, 1, 2, 3 and so on. We have inserted the numbers 2, 5, 7 and 1. We have</div> <div> decided that the elements should be inserted at the end of the array. Therefore the</div> <div> most recent element i.e. 1 is at position 3. The top is the index representing the</div> <div> position of the most recent element. Now we will discuss the stack implementation in</div> <div> detail using array.</div> <div> We have to choose a maximum size for the array. It is possible that the array may</div> <div> ‘fill-up’ if we push enough elements. Now more elements cannot be pushed. Now</div> <div> what should the user of the stack do? Internally, we have implemented the stack</div> <div> using array which can be full. To avoid this, we write isFull() method that will return</div> <div> top</div> <div> 2</div> <div> 5</div> <div> 7</div> <div> 1</div> <div> 2 5 7 1</div> <div> 0 1 2 3 4</div> <div> top = 3</div> <div> CS301 – Data Structures Lecture No. 05</div> <div> ___________________________________________________________________</div> <div> Page 53 of 505</div> <div> a boolean value. If this method returns true, it means that the stack (array) is full and</div> <div> no more elements can be inserted. Therefore before calling the push(x), the user</div> <div> should call isFull() method. If isFull() returns false, it will depict that stack is not full</div> <div> and an element can be inserted. This method has become the part of the stack</div> <div> interface. So we have two more methods in our interface i.e. isEmpty() and isFull().</div> <div> Now we will discuss the actual C++ code of these operations. These methods are part</div> <div> of stack class or stack factory. We have an array named A while current is its index.</div> <div> The code of pop() method is as:</div> <div> int pop()</div> <div> {</div> <div> return A[current--];</div> <div> }</div> <div> In this method, the recent element is returned to the caller, reducing the size of the</div> <div> array by 1.</div> <div> The code of push method is:</div> <div> void push(int x)</div> <div> {</div> <div> A[++current] = x;</div> <div> }</div> <div> We know that ++current means that add one to the current and then use it. That also</div> <div> shows that element x should be inserted at current plus one position. Here we are not</div> <div> testing that this current index has increased from the array size or not. As discussed</div> <div> earlier that before using the push method, the user must call isFull() method.</div> <div> Similarly it is the responsibility of the user to call the isEmpty() method before calling</div> <div> the pop method. Therefore there is no if statement in the push and pop method.</div> <div> The code of the top() method is:</div> <div> int top()</div> <div> {</div> <div> return A[current];</div> <div> }</div> <div> This method returns the element at the current position. We are not changing the</div> <div> value of current here. We simply want to return the top element.</div> <div> int isEmpty()</div> <div> {</div> <div> return ( current == -1 );</div> <div> }</div> <div> This method also tests the value of the current whether it is equal to -1 or not. Initially</div> <div> when the stack is created, the value of current will be -1. If the user calls the</div> <div> isEmpty() method before pushing any element, it will return true.</div> <div> CS301 – Data Structures Lecture No. 05</div> <div> ___________________________________________________________________</div> <div> Page 54 of 505</div> <div> int isFull()</div> <div> {</div> <div> return ( current == size-1);</div> <div> }</div> <div> This method checks that the stack is full or not. The variable size shows the size of the</div> <div> array. If the current is equal to the size minus one, it means that the stack is full and</div> <div> we cannot insert any element in it.</div> <div> We have determined the cost and benefit of all the data structures. Now we will see</div> <div> how much time these methods take. A quick examination shows that all the five</div> <div> operations take constant time. In case of list, the find method takes too much time as it</div> <div> has to traverse the list. Whereas the add and remove methods are relatively quick. The</div> <div> methods of stack are very simple. There is no complexity involved. We insert element</div> <div> at one side and also remove from that side not in the middle or some other place.</div> <div> Therefore we need not to carry out a lot of work. During the usage of the array, the</div> <div> stack methods push, pop, top, isFull and isEmpty all are constant time operations.</div> <div> There is not much difference of time between them.</div> <div> The complete code of the program is:</div> <div> /* Stack implementation using array */</div> <div> #include <iostream.h></div> <div> /* The Stack class */</div> <div> class Stack</div> <div> {</div> <div> public:</div> <div> Stack() { size = 10; current = -1;} //constructor</div> <div> int pop(){ return A[current--];} // The pop function</div> <div> void push(int x){A[++current] = x;} // The push function</div> <div> int top(){ return A[current];} // The top function</div> <div> int isEmpty(){return ( current == -1 );} // Will return true when stack is empty</div> <div> int isFull(){ return ( current == size-1);} // Will return true when stack is full</div> <div> private:</div> <div> int object; // The data element</div> <div> int current; // Index of the array</div> <div> int size; // max size of the array</div> <div> int A[10]; // Array of 10 elements</div> <div> };</div> <div> // The main method</div> <div> int main()</div> <div> {</div> <div> Stack stack; // creating a stack object</div> <div> // pushing the 10 elements to the stack</div> <div> for(int i = 0; i < 12; i++)</div> <div> CS301 – Data Structures Lecture No. 05</div> <div> ___________________________________________________________________</div> <div> Page 55 of 505</div> <div> <br /></div> <div> <b><a href="http://www.genrica.com/vustuff/CS301/CS301_handouts_1_45.pdf" target="_blank"><br /></a></b></div> <div> <b><a href="http://www.genrica.com/vustuff/CS301/CS301_handouts_1_45.pdf" target="_blank">Download Book</a></b></div> <div> <b><a href="http://www.genrica.com/vustuff/CS301/CS301_handouts_1_45.pdf" target="_blank">Data Structures CS301 book HANDOUTS in pdf</a></b></div> </div> </span></div>

Data Structures CS301 book HANDOUTS in pdf

Data Structures CS301 book HANDOUTS in pdf Data Structures (CS301) Handouts | Lectures | Contents | Books Data Structures Lectur...

Read more »