CSC 1061: LinkList Data Structure and Templates

CSC 1061: LinkList Data Structure, Rule of 3, Templates, and Recursion

• Objectives: Design, implement, and test collection classes using linked lists to store elements. Ensure value semantics by implementing the Rule of 3 for dynamic classes. Convert Node and LinkList to generic template classes.
• Agenda (Week 11): Template classes, Node and LinkList, Rule of 3 (Assignment operator, Copy Constructor, Destructor), and Recursion.
• Review and Pre-Challenge: Review implementing an unordered LinkList, work through CodeLens examples, and complete multiple-choice questions. Note: The LinkList keeps track of both head and tail.
• Templates Overview: The idea is to use the same code for various data types (generic code). Templates are expanded at compile time, and the compiler checks types before expansion. Source code contains only function/class definitions, but compiled code may have multiple instances for different data types. Function templates are generic for different data types. Class templates define independent components (data structures or containers) that don't depend on the data type.
• Disadvantages of Templates: All code is exposed, some compilers support templates poorly, and error messages when problems arise in template code can be unhelpful and confusing.
• Function Templates: Useful for overloaded functions with the same definitions. Templates allow passing not only the parameter value but also its data type. Templates use operators to determine the specific function called based on the argument type.
• Example Std Class Templates: Class templates are useful for data structures allowing different data types (e.g., std::array, std::vector). Template parameter "T" is used for the element type (e.g., std::array<T>, std::vector<T>). Class templates leverage operators to maintain genericity.
• Example Class Template: A template class Item is shown with data members and methods such as getData(), setData(), and an overloaded ostream operator.
• Class Templates Review: Class templates are helpful for data structures (collection classes). They allow handling different data types in the container, making the template generic for various types. Template parameter 'T' is frequently used as a placeholder for the data structure elements' type. Class templates rely on operators to maintain genericity.
• Node & LinkList Template Steps: When using templates, class names change to class<T> everywhere. Copy constructors and assignment operator arguments must use class<T>. Scope resolution operator must use class<T>::functionName(). The Node class will also be a template if it's used in a template LinkList. Allocation needs to specify the type parameter (e.g., Node<T>*).
• Template Node: Show example code for a templated Node class, including a friend declaration for the LinkList class.
• Template LinkList: Show example code for a templated LinkList class including member functions (constructors, destructor, append, potentially others). Example codes provided.
• Rule of 3: LinkList is a dynamically allocated and deallocated data structure, so copying requires reallocating and linking. All memory allocated on the heap must be destroyed/deallocated when the object goes out of scope. The copy constructor (e.g., LinkList(const LinkList<T>& source)), the assignment operator (e.g., LinkList<T>& operator=(const LinkList<T>& source)), and the destructor (e.g., ~LinkList()) are critical for managing dynamic memory to prevent memory leaks or other errors.
• Shallow Copy vs Deep Copy: Shallow copies just copy pointers, leading to issues when deallocating, whereas deep copies allocate memory for new data and copy the contents. This was illustrated visually in diagrams.
• Copy Constructor (Example): A copy constructor example, showing how to traverse the source list and append data into the new list, illustrated with an example of the copy constructor implementation using a loop.
• Assignment Operator Example: Example of the assignment operator showing how to handle self-assignment, deallocate existing memory, and copy data from the source list to the destination list, illustrated with an example of the assignment operator implementation with a loop.
• Recursive Function: Recursion is a function that calls itself. It must have a stopping case to prevent infinite recursion, and all function calls are placed on the call stack. Recursive functions are useful for operations that inherently involve repetitive subtasks.
• Printing Backwards Recursion (Example): Example of how to print a LinkList in reverse with a recursive function, with code-example given of recursive printBackwards() implementation. Stopping case (base case) for recursive calls is clearly identified.