Section notes for Week 3 (Lists ADT)

Section Notes for Week 3 (List ADT)

Story thus far

  1. Conversion of Java into C++
  2. C++ I/O
  3. C++ Preprocessor
  4. Pointers, local variables, and the stack
  5. new and delete
  6. Code Review
  7. More Example Code
  8. Reference Variables and Method invocation
  9. Const keyword
  10. Constructors, copy constructors, and destructors
  11. Operator Overloading and the string class
  12. Big 3
  13. Templates and the array class

Updates

  1. Nice slow recap of String and Array class for first section

Today:

  1. Discussion of the List ADT
  2. A look at an array list implementation
  3. A look at the Linked List implementation
  4. Brief Discussion of Doubly Linked Lists

The List ADT

So as Jason mentioned in lecture, the List is an Abstract Data Type. This means that we have a basic notion of a List: a linear collection of elements that we can insert and remove from. It is different from the Array ADT (which we saw last week) in that it does not allow you to ask for the Nth item, but instead allows you to look at each item in sequence. The main things a class needs to do to be thought of as a "List" needs to do is Insert, Remove, Retrieve, Update, and Find.

This abstract idea of a list can be implemented many different ways, and have variations on how the interface can work. Jason went over the reasons for chosing the interface we have now in his lecture notes.

When we implement a List, we have to have some way to store the data of each list item.

Implementing a List using an Array

Conceptually, the easiest way to store internal List data is with an array. This is easy, but it is not optimal for speed. Why? How long does it take to Insert, Remove, and Find an element in this implementation?

So lets have a look at the code behind the implementation of this inferior list. There are a few things to notice here when examining the .h file.

  1. Notice that the List class is a template class, and uses a templated Array object to actually hold all of its internal data.
  2. Notice that the List class itself keeps track of what list element you are currently at with the current index member variable.
  3. And notice that you can change your position in the list with the ++ and -- operators, which just increment and decrement the current index.
  4. Notice that we keep track of the size of the List with the size member variable. We keep this because the array may have empty indices in it.

Moving on to the .C file, if you have a look at the constructors, you see that they use initializer lists to set up the array, and set size and current to 0. The copy constructor simply relies on operator= being defined for Array, and copies the index and size member variables. The destructor simply calls Clear(), which resets the bounds on the array, and resets the size and current variables. Notice that the operator= is simply Clear() (the code for the destructor), followed by the code for the copy constructor, with a check for self-reference. This will often be the case for operator=.

So now let's delve into the meat of the class: InsertAfter, InsertBefore, and Remove, and Find.

InsertAfter() sketch:

InsertBefore()

Remove() - 3 Cases

  1. Empty list - print error
  2. Single Element - reset current and size to 0
  3. More than 1 element:

The Linked List implementation

So this implementation is a bit trickier than the Array implementation. However, it is a true list, and exhibits the running time properties we would expect from such a data structure. (What were they, and why?)

So from a glance at the .h file for this implementation, there are a few things we should notice here right away:

  1. The methods are all basically the same as they were for the array-list class. This means a user could use either one and only have to learn one abstract interface.
  2. There is a ListNode class. C++ allows us to embed classes like this. It means that ListNode is not usable from outside the List class. ListNode is what actually implements the linked list.
  3. The private member variables are different. Notice that instead of a current index, we have a ListNode pointer. We also have a pointer for the start and end of the list (head and tail)
  4. We still have a size variable to keep track of the number of nodes in the list.

Looking at the constructors for list we see that the default one is quite simple: just set all the pointers to NULL, and the size to zero.

The destructor still calls Clear(), but Clear() is a bit more complicated. We must traverse through the list, deleting each node as we go along. Finally, the head, tail, and current are set to NULL, and size to 0.

The Copy constructor is even more frightening, so rather than scare you with code, let's walk through it's implementation. Recall that we must copy all the individual list nodes, or else two different lists will be pointing to the same nodes. So let's break this down into parts. Assuming the list isn't empty, we have 5 things to worry about:

  1. Copying the head pointer into the proper place
  2. Copying the list nodes (add the each to this->next)
  3. Copying the current pointer
  4. Copying the tail pointer
  5. Copying the size

Now operator= looks even worse, but if you look closely, it simply has a check for self-reference, and then the destructor (Clear()) followed by the same code as the copy constructor.

InsertAfter - 3 Cases

  1. If list is empty, just create a new ListNode and adjust pointers accordingly (all point to new node). Update size.
  2. List is not empty: insert and update current
  3. List is not empty, insert at tail: insert and update current, tail

InsertBefore - 3 cases

  1. If list is empty, just create a new ListNode and adjust pointers accordingly (all point to new node). Update size.
  2. List is not empty:
    If this is the case, we can't access the next pointer of the node before current.. Solution: Must make a copy of the current and insert ourselves into current's place.
  3. List is not empty, insert at tail.

Remove - 4 cases

  1. Empty List - do nothing (perhaps warn)
  2. Single Element List: delete node, reset pointers to null
  3. Deletion of the last element:
    Cycle through list to get pointer just before current, delete current, update current, set tail pointer to current.
  4. Normal Deletion:
    Works like InsertBefore: Copy the element after current into current, delete the element after current. Update the tail if needed.

Doubly Linked Lists

Notice how SLOW operator-- is (must traverse list each time). What's the answer to this problem?

Doubly linked lists have pointers in both directions. So each ListNode has not only a next pointer, but also a prev pointer. A good excercise would be to modify ListNode to do this, and actually implement it. You can use Jason's test code.