Lab 7: Linked List Iterator

Lab Structure

  1. Pick a partner.
  2. 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.
  3. Make sure that your partner understands the mergesort enough to take a test over it.
  4. Put your partner's name with yours in the header of the sort.c file.
  5. 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, and element.
  • 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.

Assignment

iterator class

  1. Write 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 or tail.
  2. Write 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 or tail.
  3. Write void remove_current();
    1. Don't remove the head or the tail.
    2. Move the current past the element we will be deleting. ("past" may be backward or forward)
    3. Be sure to free memory and update pointers.
  4. Write void insert_element(const T &val);
    1. Inserts before the current element.
    2. If insert is called on the dummy head, no insertion is performed.
    3. Create the new node.
    4. Insert before current. Make sure to fix all links.

list class

  1. Write const T& back(); This method is one line.
  2. Write iterator begin(); This method is easy.
  3. Write const iterator &erase(iterator &loc); Relies on remove_current in the iterator class.
  4. Write const T& front(); This method is one line.
  5. Write const iterator &insert(iterator &loc, const T &val); Relies on insert_element in the iterator class.
  6. Write iterator rbegin(); This method is easy. (rbegin is a reverse iterator, so it starts right before the dummy tail.)

Testing

  1. Copy everything from /users/smatzko/212/public/ to your folder.
  2. Use the make file to pull it all together.

Turn in

Turn in all of the code, and the Makefile.
Use sendlab.212.302 7 *.cpp *.h Makefile