The first midterm exam will cover the introductory material on C++ from lecture notes 1-6, chapter 3, and chapter 4.
The main preparation for the exam is to complete the first three programming assignments. Those assignments will force you to grapple with most of the key concepts we have covered. You should also make sure that you read the relevant sections in the text. Those sections are
Chapter 3: 3.1, 3.2, and 3.7
Chapter 4: 4.1, 4.2, 4.4, and 4.5.
1. The picture below illustrates a variant on the singly linked list, called the circular linked list.
In this structure the list is composed of nodes, as usual, but now the nodes are always linked together in a circle, with the last node pointing back to the first. The list class itself maintains a single pointer to the node at the tail of the list.
Write a class declaration for the node class for this data structure, and then write the code for these two methods in a CircularList<T> class
void addToTail(const T& item); void removeFromFront();
Be sure to handle special cases, such as adding an item to an empty list.
2. Below you will find a pair of class declarations for a stack class and a node class to go with the stack. In this version of the stack class the stack is implemented as a list of nodes, where each node points to the node below it on the stack. The stack class itself then just consists of a pointer to the node at the top of the stack.
template <typename T> class stackNode { public: stackNode(const T& el); T data; stackNode<T>* ptr; }; template <typename T> class stack { public: stack(); ~stack(); void push(const T& el); // Push a new data item on the stack bool isEmpty(); // Return true if the stack is empty T top(); // Return a copy of the data item on the top void pop(); // Remove the top of the stack private: stackNode<T> *topPtr; // Pointer to the top of the stack };
Write the code for the push()
and pop()
methods.
3. A singly linked list class is implemented using nodes of type
template <typename T> class node { public: T data; node<T> *next; node() : next(nullptr) {} node(const T& item, node<T> *ptr = nullptr) : data(item), next(ptr) {} };
The list class itself contains pointers head
and tail
that point to the two ends of the linked list. Write the code for a method
void remove(const T& el);
in the list class that will remove all of the nodes from a list whose data member is el
.
4. Using the same classes as in problem 3, write the code for a method
void push_back(const T& el);
in the list class that adds a new node to the back of the linked list.
5. Using the same classes as in problem 3, write the code for a method
list<T>& operator=(const list<T>& other);
in the list class that is used to assign another list to a list.