---

  Lab 03 - Linked List (10/01/2022)

---

A class template is an example of instantiation-style polymorphism. A class template MyClass<T> isn't really a class but rather a recipe for creating a class for a data type T at compile time. MyPair<T> is an example of a class template that stores two elements of any valid type:

template <typename T>
class MyPair
{
private:
   T first;
   T second;
public:
   MyPair(T arg1, T arg2) : first(arg1), second(arg2) {}
   T getMax(void) { return first > second ? first : second; }
};

The intention of C++ class templates is to avoid having to write nearly identical classes differing only in data types. The class template MyPair<T> can be used to instantiate an integer template class (MyPair_int) or a float template class (MyPair_float) that contains two values and a getMax() member function that returns the greater of the two values:

int main(void)
{
   MyPair<int> MyPair_int(100, 75);
   cout << endl << MyPair_int.getMax();
   MyPair<double> MyPair_double(2.72, 3.14);
   cout << endl << MyPair_double.getMax();
   return 0;
}

So a class template is literally a template and not a class. It is a recipe for creating a concrete template class corresponding to the specified template parameter (T). A class template cannot be compiled into code, only the resulting instantiated template class can be compiled.

Finally, because template classes are only created/compiled when required, the implementation (definition) of a template class or function must be in the same file as its declaration and not a separate file.

For further reading...

C++ has no built-in concept of an interface. However, an inherited abstract class which contains only pure virtual functions behaves as an interface class. An abstract class is a class with at least one pure virtual function. With inheritance, a C++ pure abstract class can be inherited by another class which then must implement the pure virtual functions in order to be instantiated.

For example, MyClass inherits Interface class and MUST implement the virtual myMethod function:

class Interface
{
public:
    Interface(){}
    virtual ~Interface(){}
    virtual void myMethod() = 0;  // pure virtual method
};

class MyClass : public Interface
{
private:
   int myMember;
public:
   MyClass(){}
   ~MyClass(){}
   virtual void myMethod()
   {
      // myMethod implementation
   };
};

int main(void)
{
    Interface* myClass = new MyClass();
    myClass->myMethod();
    delete myClass;
    return 0;
}

A linked list is a sequential container that has constant time insertion and deletion operations anywhere within the sequence. The ordering is kept internally by the association between elements via links (pointers) to the next element in the sequence. Doubly linked lists have links to the previous as well as next elements, while singly linked lists only have a forward links to the next element. Singly linked lists can only be iterated forwards and are somewhat smaller and more efficient than doubly linked lists.

Compared to other standard sequential containers (arrays, vectors, stacks, and deques), lists perform generally better when inserting, extracting and moving elements in any position within the container for which an iterator has already been obtained. Many algorithms use iterators exclusively, like sorting algorithms.

The main drawback of lists compared to other sequential containers is that they lack direct access to the elements by their position. For example, to access the sixth element in a list, one has to iterate from a known position (like the beginning or the end) to the sixth position, which takes linear time in the distance between these positions. Lists also consume extra memory to keep the linking information associated with each element (which may be an important factor for large lists of small-sized elements).

Linked List vs Array

Arrays can be used to store linear data of similar types, but arrays have following limitations.

1. The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.
2. Inserting a new element in an array of elements is expensive because room has to be created for the new elements and to create room existing elements have to shifted.
3. Deletion is also expensive with arrays unless some special techniques are used.

Advantages of linked lists over arrays:

1. Dynamic size.
2. Ease of insertion/deletion.

Disadvantage of linked lists:

1. Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.
2. Extra memory space for a pointer is required with each element of the list.

Representing Linked Lists in C++.

A singly linked list is represented by a pointer to the first node of the linked list. The first node is called head. If the linked list is empty, then value of head is NULL.

Each node in a list consists of at least two parts:

// A linked list node
struct Node
{
   int data;
   struct Node *next;
};

A node can be either a struct or a class (usually a struct). A template class LinkedList contains a pointers to the first Node in the list and methods to access Node elements..

Linked List Traversal.

Inserting a new node in a singly linked list.

1. At the front of the linked list.

   

2. After a given node.

   

3. At the end of the linked list.

   

Deleting a node from a singly linked list.

Reversing nodes in a singly linked list.

Video.

A short video has been created for this lab which you may find very helpful. You can watch it here.

Doubly linked List

A doubly linked list is a linked data structure that consists of a set of sequentially linked records with two link fields that are reference the previous as well as the next node in the sequence of nodes.

The Gang of Three rule states that if a class defines one (or more) of the following, it should probably explicitly define all three:

1. Copy constructor – create new object members from corresponding member constructors.
2. Copy assignment operator – assign corresponding members from existing members.
3. Destructor – call the destructors of all the object's class-type members.

Default constructors, destructors, and assignment operators do shallow copies. You need to explicitly create user constructors, destructor, and assignment operators when a deep copy is needed (class contains pointers to dynamically allocated resources).

• The copy constructor is called when a new object is created from an existing object, as a copy of the existing object. Such is the case when passing an object as an argument to a function (by value) or returning an object (by value) from a function:

  MyClass t1, t2;       // default constructor
  MyClass t3 = t1;      // copy constructor (t3 is new)

• The assignment operator is called when an already initialized object is assigned a new value from another existing object.

  t2 = t1;              // assignment operator (t2 exists)
  t2.operator=(t1);     // assignment operator (equivalent)

• A deep destructor is needed if a class contains pointers to dynamically allocated resources. Otherwise a memory leak occurs.

Note: You will need a deep copy constructor, destructor, and assignment operator to use your List implementation in an ordered Set implementation.

Copy Constructor

We want a copy of an object to be an independent copy, which means we should be able to modify one of the objects without affecting the other. Copying of primitive types is straightforward—the values are duplicated and placed in the target locations. Without a deep copy constructor, destructing an object that was shallow copied would run the destructor twice on the same object (once for the original and once for the copy) - a source for trouble!

For class types, copying is done by a class's copy constructor:

MyClass(const MyClass& other);

The copy constructor is invoked automatically:

• when an object is passed to a function by value.
• when an object is returned from a function.
• when an object is initialized with another object of the same class.
• when the compiler generates a temporary object.

Be sure to add a deep copy constructor to your List class.

Copy Assignment Operator

The assignment operator (operator=) is called when an already initialized object is assigned a new value from another existing object. For class types, the assignment operator signature looks like:

MyClass& operator=(const MyClass& other);

Every class has a default assignment operator which makes a copy of each source data field and places it into the corresponding data field of the target. The default assignment operator makes a shallow copy of an object, so we must override it if we want truly independent copies.

Be sure to add a deep assignment operator to your List class.

Destructor

Destructors contain code that is run whenever an object is destroyed. Each class has a default destructor, which effectively invokes the destructor for each data field. If the object references a dynamically allocated object, the memory allocated to that object must be freed.

Be sure to add a deep destructor to your List class to avoid memory leaks.

An alternate way to indicate an error, especially if there are several possible errors, is through the use of exceptions. Exceptions are used to signal that an error has occurred during the execution of a program. You can insert code in your program that throws an exception when a particular kind of error occurs. When an exception is thrown, the normal flow of execution is interrupted and control transfers to another part of the program. An exception handler allows the user to catch or handle the exception.

The exception object can be of any type.

• The standard library includes standard exception classes.
• User defined exceptions can be of any data type.

If an exception is thrown and not caught, then the program aborts and an error message is displayed. To avoid uncaught exceptions, enclose the code segment within a try block followed by catch block(s) that catch and handle thrown exceptions. Code within a try block is referred to as protected code. More than one catch block can follow a try block.

• Each catch block handles a different kind of exception.
• They are checked in the order in which they appear.
• Check specific exception before more general exceptions.

Example:

#include <iostream>
#include <string>
#include <stdexcept>
using namespace std;

int divide(int a, int b)
{
	if (a == 1) throw exception("We don't like a equal to 1!");
	if (b == 0) throw string("Why are you dividing by zero?");
	int result = a / b;
	return result;
}

int main(int argc, char* argv[])
{
	for (int i = 0; i < 10; ++i)
	{
		try
		{
			int a = rand() % 10;
			int b = rand() % 10;
			cout << endl << a << " / " << b << " = ";
			int c = divide(a, b);
			cout << c;
		}
		catch (const string& s) { cerr << s; }
		catch (const exception& myString) { cerr << myString.what(); }
		catch (...) { cerr << "????"; }
	}
	return 0;
}

1. You are required to implement a template class for your linked list.
   1. Publicly inherit the lab interface class (LinkedListInterface.h).
   2. Implement the pure virtual abstract member functions:
      • virtual void push_front(const T& value) = 0;
      • virtual void pop_front(void) = 0;
      • virtual T& front(void) = 0;
      • virtual bool empty(void) const = 0;
      • virtual void remove(const T& value) = 0;
      • virtual void clear(void) = 0;
      • virtual void reverse(void) = 0;
      • virtual size_t size(void) const = 0;
      • virtual string toString(void) const = 0;
   3. While the lab only requires string types, the template argument should be able to accept both int and string types.
2. Program a main function that:
   1. uses argv[1] and argv[2] for input/output files names, respectively.
   2. Instantiates a LinkedList<string> class.
   3. Processes the following input commands:

   COMMAND	DESCRIPTION	EXAMPLE INPUT / OUTPUT
   Clear	Delete all items in the linked list Output "OK" if successful. (void clear(void);)	Clear OK Size 0
   Empty	Output true if linked list empty, else false. (bool empty(void) const;)	Empty false Clear OK Empty true
   Delete	Delete the first item in the linked list. Output "OK" if successful. (Call void pop_front(void);) Throw an error "Empty!" if linked list is empty.	PrintList The quick brown fox jumped over the lazy dog. Delete OK PrintList quick brown fox jumped over the lazy dog. Clear OK Delete Empty!
   First	Output the first item in the linked list. (Call T& front(void);) Throw an error "Empty!" if linked list is empty.	PrintList The quick brown fox jumped over the lazy dog. First The Clear OK First Empty!
   Insert <item> { <item>}	Insert item or items at the head of the linked list. (Call void push_front(const T& value);)	Insert men. good all for Insert time the is Now PrintList Now is the time for all good men.
   PrintList	Output the contents of the linked list, space separated. Output "Empty!" if list is empty. (Use insertion operator "<<" to call string toString(void) const;)	PrintList Now is the time for all good men. Clear OK PrintList Empty!
   Remove <item>	Remove all like items from the linked list. (Call void remove(const T& value);)	PrintList The very quick brown fox jumped over the very lazy dog. Remove very PrintList The quick brown fox jumped over the lazy dog.
   Reverse	Reverse the items in the linked list. Output "OK" if successful. (Call void reverse(void);) Throw an error "Empty!" if linked list is empty.	PrintList dog. lazy very the over jumped fox brown quick very The Reverse OK PrintList The very quick brown fox jumped over the very lazy dog. Clear OK Reverse Empty!
   Size	Output the number of items in the linked list. (Call size_t size(void) const;)	Size 11
   Copy	Make a deep copy of the current List.	Copy OK
   PrintCopy	Output the contents of the linked list copy (created by the Copy command), space separated. Output "Empty!" if list is empty. (Use insertion operator "<<" to call string toString(void) const;)	PrintCopy Now is the time for all good men. Copy OK Clear OK PrintList Empty! PrintCopy Now is the time for all good men.
   BONUS COMMANDS FOR DOUBLY LINKED LIST ONLY!!! ***The following commands must use a tail pointer. Accessing list items using the head pointer is cheating and would result in a 0 for the lab.***
   Last	Output the last list item in the doubly linked list. (Call T& back(void);) Throw an error "Empty!" if linked list is empty.	PrintList The quick brown fox jumped over the lazy dog. Last dog. Clear OK First Empty!
   Append <item> { <item>}	Insert item or items at the end of the doubly linked list. (Call void push_back(const T& value);)	Append Now is the time for all good men. PrintList Now is the time for all good men.
   Drop	Delete the last item in the doubly linked list. Output "OK" if successful. (Call void pop_back(void);) Throw an error "Empty!" if linked list is empty.	PrintList The quick brown fox jumped over the lazy dog. Drop OK PrintList The quick brown fox jumped over the lazy Clear OK Delete Empty!

3. Due to the nature of template classes (which are templates and not objects), you must implement the entire class in your '.h' file. (Any class method with more than 10 lines of code is also included in method declaration of the '.h' file and not a separate '.cpp' file.
4. Although the copy constructor and assignment operator are not specified in the linked list interface, they must be implemented in your linked list class.
5. Implement your linked list as a singly linked list with a pointers from each node to the next node in the list. You should have a head pointer, but no tail pointer is needed.
6. For bonus points, implement your linked list as a doubly linked list with a pointers from each node to the previous and next nodes in the list. You should have a tail pointer as well as a head pointer.
7. YOU MAY NOT USE any C++ Standard Template Library (STL) containers. (Be careful NOT to #include any of them as the auto-grader will then reject your submission.)
8. Be sure to recover all "new" memory to prevent memory leaks.

• Step 1 - Begin with a main function.
  1. Open for input argv[1] and for output argv[2].
  2. Add code to read and output input file.
  3. Parse input commands and output corresponding messages.

• Step 2 - Design and implement the singly linked LinkedList template class.
  1. Create a LinkedList template class that inherits from LinkedListInterface class. Since LinkedListInterface is an abstract class, stub out all virtual functions so that there are no compiler errors. Include both .h files in your main file.
  2. Implement one function at a time and then test it before moving on to the next one. Begin implementing the more basic functions like toString and insert.
  3. Create small test files to test each command. Incrementally add these files to a regression file to test that new additions to your implementation didn't break previous work.
  4. Create your own test case files to aid in your incremental testing.
  5. When all the commands have been implemented, enclose the parsing code in a try-catch block to handle error conditions.

• Step 3 - If desired, implement the bonus doubly linked list functions and commands. Remember, the bonus commands MUST use the tail pointer and not the head.
   
• Step 4 - When you've completed the incremental testing, test your program with all the provided test cases.

Use extraction operator (">>") to read from the input stream. For example:

// process input strings
for (string line; getline(in, line);)
{
   string item1, item2;
   if (line.size() == 0) continue;
   out << endl << line;
   istringstream iss(line);
   iss >> item1;
   if (item1 == "Insert")
   {
      while (iss >> item2)
      {
         out << endl << item2;
         linked_list.push_front(item2);
      }
   }
}

**Note: if you are not using an istringstream extraction operator >> to find commands, make sure you check for exact command string match (ie. if (line.substr(0, 5) == "First") {}).

Understanding VS_MEM_CHECK Output.

You can find helpful hints and explanations of the VS_MEM_CHECK macro here.

Understanding Valgrind Output.

You can find helpful hints and explanations of Valgrind output here.

Total Score = 0