CMIS 240 Week 9 Chapter 6 covers various elaborations on linked lists. You don't need to learn how to do them now, just be aware of their existence. A circularly linked list (Fig 6.1) has its last node point to the first node, instead of to NULL, so that from any node you can traverse to any other node. If the external pointer points to the last node (Fig 6.2), then you have quick access to both ends of the list. In a doubly linked list (Fig 6.7), each node has two pointers, one points to the next node in the list, the other points to the previous node in the list. So you can traverse the list in either direction. Also, you can delete a node if you have a pointer to it (a singly linked list must be traversed from the beginning to find the node before the node to be deleted to change its pointer). The drawback of having two pointers per node is the memory needed to store the extra pointer (not a terrible cost though) and more complicated code (not terrible either). With a circular doubly linked list (Fig 6.15) you get the benefits of both circular linked list and doubly linked list. The cost is slightly more complicated code. The Case Study uses a circular doubly linked list to implement a class of unlimited precision integers. An object of this class stores such an integer. Each digit of the number is stored in a node of a linked list. You can have integers that are much larger than the language provides natively (i.e. long ints). Arithmetic can be done with these humongous numbers. Another variation on linked lists is to have a header and/or trailer node which are dummy nodes at the beginning and end of the list. They can be used as sentinels for a sorted list. The header node is useful to simplify the Insert and Remove functions, obviating the need for the special cases when the insertion or removal is done at the beginning of the list. Very cleverly, a linked list can be implemented by an array. Fig 6.19 shows how an array of structs can act like a linked list. The "pointer" member is the index in the array of the next "node". The "linked list" that's in the array is elements 0 4 7 2 6 of the array. This is useful for various reasons: to avoid the system overhead of dynamic allocation (each use of new takes time); to easily save and restore the "linked list" to/from a file (it's useless to store pointer values to a file because as memory addresses they only have meaning for the current execution of the program); to manage the "free store"/"heap" (actually the array) yourself; and to be able to use "linked lists" in a language that doesn't have pointers and dynamic allocation (like traditional Fortran and Basic). ------------------------------------ Inheritance and polymorphism are the defining hallmarks of OOP. What we're doing in this course is sometimes referred to as "object based programming". The section on Inheritance is a preview of what's covered in an OOP course (e.g. CMIS 345). The material here is not needed or used in the rest of the book. We won't cover it (we have so much else to do, and so little time). ------------------------------------ Copy constructor and overloading the = operator are important to learn. The book's use of "copying a templated stack implemented by a linked list" as the example makes for an overly-complicated exposition. Usually, if a class uses dynamic allocation (i.e. if it has a pointer member) then the class should have a copy ctor, an overloaded assignment operator, and a destructor. ****** The destructor is needed to delete the dynamically allocated data (array or linked list nodes) that the pointer member points to when the object goes out of scope (i.e. when the object is a local variable in a function that is exiting). Without a destructor, memory leaks occur; the dynamically allocated data is inaccessible because the object, with the pointer inside it, has vanished. Dynamically allocated data is only returned to the heap when the program deletes it. ****** The copy ctor is needed to make sure that when the object is copied all the data in it, including the dynamically allocated data, gets copied. Copying occurs automatically and invisibly (i.e. "implicitly") in three places: 1. when a function is called with an object as a pass-by-value argument; 2. when an object is the return value of a function; 3. when an object is declared and initialized with another object. Let's say we have this simple class (no templates) with dynamically allocated data: class Stack { Stack(); //default ctor //copy ctor. single argument MUST be reference same class. //const for good programming practice to prevent ctor code from changing the //argument object: Stack(const Stack &); ~Stack(); //dtor deletes the dynamically allocated memory ... //implementation can be either dynamic array or linked list }; //declare an object Stack s1; //default ctor used ... //later declare another object and initialize it with an existing object. Stack s2=s1; //this is NOT assignment operation, it's special syntax //to initialize a new object by an existing one. //alternate syntax to do the same thing is: //Stack s2(s1); The copy ctor is called and will copy all the data members, including the dynamically allocated data, of the existing object (the argument object) to the new object. This is the so-called deep copy as opposed to the shallow copy which only copies the members themselves and doesn't include what the members might point to. Without a copy ctor you can still initialize a new object with an existing one but you only get shallow copy, which is fine for a class with no dynamic data, but wrong for a class with dynamic data. If a class doesn't have a copy ctor, the compiler automatically creates one so that you can initialize an object by an existing object, but the automatic copy ctor does shallow copy only. *** Let's say we have this function: void coolfunc(Stack sx) { .... } The argument is a pass-by-value Stack object. Here's a call of the function: coolfunc(s1); The copy ctor is implicitly invoked to make a copy of the actual argument s1 into the formal argument sx. If the class doesn't have a copy ctor that does deep copy, then sx does not become a complete copy of s1 (as it should since the argument is pass-by-value); sx's pointer member would point to the same dynamic data as s1, and if the function changes sx, then s1 would be changed too which you do not want to happen to a pass-by-value argument. So you need a copy ctor that does deep copy. *** Let's say we have this function: Stack coolfunc2(int i, char c) { //arguments are irrelevant to this example Stack local_s; //local object. default ctor used .... return local_s; } This function returns a Stack object. Most likely that will be a (copy of) local object. The copy ctor is implicitly called to make the copy of the local object that is returned. Again, the automatic compiler-provided copy ctor is insufficient if the class has dynamic data. A deep-copy copy ctor is needed to ensure that the dynamic data is copied as well. A temporary object is created to receive the copy. The temporary object is the return value of the function call, i.e. what the function call evaluates to. The temporary object only exists for the duration of the execution of expression containing the function call. It will be destructed when the expression has been evaluated. ****** Typically, a function that returns an object is used to assign the returned object to an object, like the following statement: s1 = coolfunc2(x,y); The value of the function call is the (deep) copy of the local object (thanks to the deep-copy copy ctor). It's then assigned to the s1 object. This leads us into overloading the = operator. If the = operator is not overloaded by the class you get an automatic compiler-provided one that does shallow copy only. In the example, the complete copy returned by the function would be only shallow copied into s1 and then s1's pointer would be pointing to the deallocated memory of the local object (it's been deallocated by the destructor function). But with an overloaded = operator that does deep copy the complete object, including the dynamic data, will be assigned to the object on the left side of the = operator. The code for an overloaded = operator is very similar to the copy ctor, since they do basically the same thing. Overloading the = operator also allows these kind of statements to work correctly: s1 = s2; ****** Putting all this together. Example: Let's say we have this function: Stack coolfunc3(Stack sx) { Stack local_s; .... return local_s; } and have a call of it: s1 = coolfunc3(s2); Copy ctor is called to make a deep copy of the actual argument s2 into the formal argument sx. Default ctor is called to make the local object local_s. Copy ctor is called to make the deep copy of the returned object into a temporary object at the function call. Destructor is called twice to delete the two local objects, local_s and sx. Overloaded = operator function is called to deep copy the returned object into s1. Destructor called to destruct the temporary object. No homework this week. Spend time reading this chapter and chapter 7 about recursion, which is perhaps the most difficult part of this course.