Lab 7: Linked List Iterator
- Pick a partner.
- Help each other with the code as needed. Do not type for your partner
and avoid dictation, but
make sure your partner is able to finish the assignment.
- Make sure that your partner understands the mergesort enough to
take a test over it.
- Put your partner's name with yours in the header of the
- If your partner is unable to complete the lab, your maximum grade is a 90%.
Linked List Class
- The list class has a dummy head and tail: that is, the first node and last node
do not hold meaningful data. Instead, they hold the address of the first and last actual nodes.
- The list class has an embedded node class. The node class has simply a public next, prev,
- The list class has an embedded iterator class.
- The iterator class has a pointer to the list it is working on.
- The iterator class has a pointer to the current node.
- Because iterator is embedded, it can access any private data in the linked list class.
- The iterator can be forward and start after the dummy head or reverse and start before
the dummy tail.
const iterator &operator++ (int); The int parameter is simply
to specify that this is the post increment function. If the direction of the iterator
is forward, you should go to next. Otherwise go to prev. Don't allow incrementing past the head
const iterator &operator-- (int); If the direction of the iterator
is forward, you should go to prev. Otherwise go to next. Don't allow decrementing past the head
- Don't remove the head or the tail.
- Move the current past the element we will be deleting. ("past" may be backward or forward)
- Be sure to free memory and update pointers.
void insert_element(const T &val);
- Inserts before the current element.
- If insert is called on the dummy head, no insertion is performed.
- Create the new node.
- Insert before current. Make sure to fix all links.
const T& back(); This method is one line.
iterator begin(); This method is easy.
const iterator &erase(iterator &loc); Relies on
remove_current in the iterator class.
const T& front(); This method is one line.
const iterator &insert(iterator &loc, const T &val);
Relies on insert_element in the iterator class.
iterator rbegin(); This method is easy. (rbegin is a reverse iterator,
so it starts right before the dummy tail.)
- Copy everything from
/users/smatzko/212/public/ to your folder.
- Use the make file to pull it all together.
Turn in all of the code, and the Makefile.
sendlab.212.302 7 *.cpp *.h Makefile