Well... kind of a mix of announcements, review, and our agenda for today.

My notes from last week have been updated! In particular, please see the new section on copying LinkedLists located here.

Review

What is the purpose of defining a destructor?

To ensure that any dynamically allocated resources have their memory freed when the object containing them is freed.

What is the purpose of defining a copy-constructor and overloading the assignment operator for a class?

To ensure that each copied / assigned object's resources (i.e., its data members) are its own, that modifying one object will not modify another object that improperly shares resources (as by a compiler-provided copy-constructor, e.g.), and that shared resources are not multiply deleted by multiple destructors (like two LinkedLists sharing the same list of Nodes).

Today's Agenda

Things will be a bit light today, since you had your midterm this week!

• Stacks

• Queues

• Doubly-Linked Lists

• Project 3

• Debugging

Heretofore (can you believe that's a word?), we've only seen some abstract uses for LinkedLists and their comparisons to Arrays...

Let's talk about a real-world data structure that works well with LinkedLists: the stack.

A stack is a data structure used to store elements in a way that the most recently stored items are the first to be retrieved.

It is said that stacks have last-in, first-out (LIFO) behavior, because the most recently retrieved item will be the most recently added, or in other words, the least recently added item will be the last to be retrieved.

Trust me, it's cool! By analogy, think of a pile of dishes:

• You stack dishes one on top of the other

• Once you've stacked dish Z on top of all the other dishes, you can only access dish Z (and cannot access any other dish beneath it) until you pop Z off the top again

Stacks are very useful; in fact, there's a reason why local variables are stored in the stack, because every function's variables get stacked on the top when they're called, and popped off again when you leave the function!

So, let's try to use a LinkedList to represent this data structure:

OK, Andrew, why would we want to make a data structure that's a LinkedList... but more restricted than one?

This goes back to our public vs. private interface discussion: we want to give users of our classes certain guaranteed behaviors that allow for predictable code execution. If an algorithm requires that only the most recently pushed Node can be accessed at any time, we need to make sure our users don't tamper with that guaranteed behavior.

Implementing a Stack

Here's my new interface:

  #ifndef STACK_H
  #define STACK_H
  #include <string>
  
  class Stack {
  private:
      struct Node {
          std::string data;
          Node* next;
          Node (std::string s) {
              data = s;
              next = nullptr;
          }
      };

      Node* head;
      int size;
  
  public:
      Stack();
      ~Stack();
      void push(std::string s);
      std::string pop();
      void print();
  };
  
  #endif

And, of course, a shell for the implementation.

  #include "Stack.h"
  #include <iostream>
  using namespace std;
  
  // Default Stack constructor
  Stack::Stack() {
      head = nullptr;
      size = 0;
  }
  
  // Destructor
  Stack::~Stack() {
      // TODO
  }
  
  // Pushes a new Node with data string s
  // to the top of the stack!
  void Stack::push(string s) {
      // TODO
  }
  
  // Pops the top Node on the stack off,
  // returning its data member and removing
  // itself from the top (making the one beneath
  // it the new top)
  string Stack::pop() {
      // TODO
      return "";
  }
  
  void Stack::print() {
      for (Node* n = head; n != nullptr; n = n->next) {
          cout << n->data << endl;
      }
  }

Let's fill out the push and pop functions to see it in action:

  ...
  // Pushes a new Node with data string s
  // to the top of the stack!
  void Stack::push (std::string s) {
      // 1) Dynamically allocate a new Node
      Node* toAdd = new Node(s);
  
      // 2) The new node now points to the
      // current head
      // [!] Fill in here!
  
      // 3) Whether it's first or not, have the head point
      // to the new node
      // [!] Fill in here!
  
      // 4) Bump the size
      size++;
  }
  ...

  ...
  void Stack::push(std::string s) {
      Node* toAdd = new Node(s);
      toAdd->next = head;
      head = toAdd;
      size++;
  }
  ...

If we test our push with the following main function, what gets printed out?

  int main () {
      Stack onStacksOnStacks;
      onStacksOnStacks.push("Bill");
      onStacksOnStacks.push("Dolla");
      onStacksOnStacks.push("Dolla");
      onStacksOnStacks.print();
  }

Now that we can push Nodes onto a Stack, let's consider how to pop them off!

  ...
  // Pops the top Node on the stack off,
  // returning its data member and removing
  // itself from the top (making the one beneath
  // it the new top)
  string Stack::pop () {
      // 1) Return the empty string if empty
      if (head == nullptr) {
          return "";
      }
  
      // 2) Set a pointer to the top node
      // [!] Fill in here!
  
      // 3) Save the top Node's data
      string result; // [!] Fill in here!
  
      // 4) Adjust head accordingly
      // [!] Fill in here!
  
      // 5) ...take care of the top Node... quietly...
      // [!] Fill in here!
      
      // 6) Reduce size
      size--;
  
      return result;
  }
  ...

  ...
  string Stack::pop() {
      if (head == nullptr) {
          return "";
      }
    
      Node* top = head;
      string result = top->data;
      head = head->next;
      delete top;
      size--;
    
      return result;
  }
  ...

If we test our pop with the following main function, what gets printed out?

  int main () {
      Stack onStacksOnStacks;
      onStacksOnStacks.pop();
      onStacksOnStacks.push("TA");
      onStacksOnStacks.push("great");
      onStacksOnStacks.pop();
      onStacksOnStacks.push("is a");
      onStacksOnStacks.push("Andrew");
      onStacksOnStacks.push("Great...");
      onStacksOnStacks.print();
  }

-_-

Practice: try implementing the destructor yourself!

Wake up your neighbors folks, let's talk Doubly Linked Lists.

A doubly linked list is just like a regular linked list, except each Node has a pointer to the previous Node in the sequence along with a pointer to the next Node.

What's this look like you ask?

"I like the new arrows, Andrew... what good do they do?"

What is the purpose of having prev pointers in every Node? In what scenarios might they be useful?

Whereas previously, in the Singly Linked List, we had only forward arrows, if we ever wanted information about a Node behind us in the sequence, we had to start all over at the beginning... now we don't! Doubly-linked lists are useful when we have operations that need to operate on Nodes before and after the one under current inspection.

I'm sure the 1 or 2 cases in which these new arrows save us headaches will more than make up for their upkeep...

Implementing a Doubly-Linked-List

Alright... so we've been dealing with Nodes this whole time, but you know what?

I'm bored with Nodes... let's use a more pop-culture-friendly class and implementation.

  #ifndef HC_H
  #define HC_H
  #include <string>
  #include <iostream>
  
  class HumanCentipede {
      private:
          struct Person {
              std::string m_data;
              Person* m_front;
              Person* m_behind;
              Person (std::string s) {
                  m_data = s;
                  m_front = nullptr;
                  m_behind = nullptr;
              }
          };
  
          Person* head;
          Person* tail;
          int size;
  
      public:
          HumanCentipede();
          ~HumanCentipede();
          void insert(std::string);
          bool erase(std::string);
          void print();
  };
  
  #endif

  #include "HumanCentipede.h"
  #include<iostream>
  using namespace std;
  
  HumanCentipede::HumanCentipede() {
      head = nullptr;
      size = 0;
  }
  
  HumanCentipede::~HumanCentipede() {
      // TODO
  }
  
  void HumanCentipede::prepend(string toAdd) {
      // TODO
  }
  
  bool HumanCentipede::remove(string toRemove) {
      // TODO
      return false;
  }
  
  void HumanCentipede::print() {
      for (Person* p = head; p != nullptr; p = p->next) {
          cout << p->data << " ";
      }
      cout << endl;
  }

...and if you haven't seen the movie, or didn't catch the reference, please don't look it up (read: please don't sue me if you do)

Should we start at the start? Let's try simply inserting elements to the front of our DLL via a prepend operation.

  ...
  void HumanCentipede::prepend(string toAdd) {
      Person* newPerson = new Person(toAdd);
      // TODO: set newPerson to point to old head
      
      if (head != nullptr) {
          // TODO: if head != nullptr, what
          // do we have to update?
      }
      
      // TODO: update head appropriately
      
      // TODO: update any other data members...
  }
  ...

  ...
  void HumanCentipede::prepend(string toAdd) {
      Person* newPerson = new Person(toAdd);
      newPerson->next = head;
      if (head != nullptr) {
        head->prev = newPerson;
      }
      head = newPerson;
      size++;
  }
  ...

It should work with this main function:

  int main () {
      HumanCentipede cent;
      // Yes, I looked up the character names
      cent.prepend("Katsuro");
      cent.prepend("Lindsay");
      cent.prepend("Jenny");
      cent.print();
  }

Alright, that one was basically a freebie... no more freebies for HumanCentipede... instead, let's just walk through the erase function.

Here are some behaviors for erasing a node at certain positions in a Doubly Linked... sorry... HumanCentipede:

K, how about this one?

There are, in general, 3 cases for updates required to our DLL for any arbitrary deletion. E.g., 1) is that if we delete the head, we must update the head pointer. What are the other 2?

2) If we delete a Person p with p->next != nullptr, then we must update p->next's prev. 3) If we delete a Person p with p->prev != nullptr, then we must update p->prev's next.

With these 3 cases in mind, let's try implementing the remove function.

In the following skeleton, note that nullptr evaluates to false in if-conditionals (i.e., anywhere a bool is expected), and any pointers not nullptr evaluate to true.

  ...
  bool HumanCentipede::remove(string toRemove) {
      // 1) Search for the Person toRemove
      Person* toFind = head;
      while (toFind != nullptr) {
          // TODO: if we found it, break
          if ( ??? ) { break; }
          toFind = toFind->next;
      }
      
      // 2) Make updates based on result of search
      // Case 1: what if toRemove wasn't found?
      if ( ??? ) { ??? }
      // Case 2: what if toFind was the head?
      if (toFind == head) { ??? }
      // Case 3: what if toFind had a next Person?
      if (toFind->next) { ??? }
      // Case 4: what if toFind had a prev Person?
      if (toFind->prev) { ??? }
      
      // 3) Delete toFind and return true 
      delete toFind;
      size--;
      return true;
  }
  ...

  ...
  bool HumanCentipede::remove(string toRemove) {
      Person* toFind = head;
      while (toFind != nullptr) {
          if (toFind->data == toRemove) { break; }
          toFind = toFind->next;
      }
    
      if (toFind == nullptr) { return false; }
      if (toFind == head) { head = toFind->next; }
      if (toFind->next) { toFind->next->prev = toFind->prev; }
      if (toFind->prev) { toFind->prev->next = toFind->next; }
      delete toFind;
      size--;
      return true;
  }
  ...

If we did the above correctly, the following should work!

  int main() {
      HumanCentipede cent;
      cent.prepend("D");
      cent.prepend("C");
      cent.prepend("B");
      cent.prepend("A");
      cent.print();   // A B C D
      cent.remove("C");
      cent.print();   // A B D
      cent.remove("A");
      cent.print();   // B D
      cent.remove("D");
      cent.print();   // B
  }

Practice: try implementing the doubly-linked list's destructor! And if you're up for it, the copy-constructor!

(Queues have so many u's and e's next to each other, what a strange word!)

Queues are just like lines at a shopping market or amusement park -- they have a back where people enter and a front where they are served.

Queues are an abstract data type whereby added items are enqueued to the back and then retrieved or dequeued from the front.

Queues are said to have first-in first-out (FIFO) behavior because the first items added are the first to be retrieved.

Let's examine a Queue as an application for our doubly-linked lists.

Again, though, you should be aware that a queue is an abstract data type, and that some implementations WILL allow you to access the intermediary nodes behind the front.

That, however, is not true of the C++ STL queue, which only has access to the front and back element (We'll cover the STL later in the course).

Common Queue Operations

• push(element) (sometimes called enqueue) adds an element to the back of the queue.

• pop() (sometimes called dequeue) removes the element from the front of the queue.

• back() returns a reference to the element at the back of the queue (most recently added)

• empty() returns true if the queue has no elements, false otherwise

• size() returns a count of the number of elements in the queue

Examples

Suppose we have a Queue storing ints defined with a print() function that prints its values from front to back. What will the following print?

  Queue q;
  q.push(1);
  q.push(2);
  q.push(3);
  // [?] What gets printed here?
  q.print();

Suppose we have a Queue storing ints defined with a print() function that prints its values from front to back. What will the following print?

  Queue q;
  q.push(1);
  q.push(2);
  q.push(3);
  q.pop();
  q.pop();
  q.push(4);
  // [?] What gets printed here?
  q.print();

Project 3 requires you to implement a doubly-linked list to store People by alphabetically sorted first and last name.

People will have a first name, a last name, and some data value (of variant type) associated with them (like age or gpa).

A person's name is sorted alphabetically by 1) Last name, and if two People have the same last name, they are then sorted by 2) First name.

Let's take a look at the spec here: Click to Open Spec!

Hints

Group your doubly-linked list nodes by last name, then sort by first name within these groups -- this will make a variety of functions easier.

This means you should maintain your doubly-linked list as a sorted list -- each time you insert a new Person, find their proper, alphabetically sorted position in the list before inserting!

Private helper functions that return pointers to your Nodes / People (for various search operations) will simplify the flow of your code substantially.

For example, consider having a private function Node* findLastName(string name); that returns a pointer to the first Node with the given last name, or the first Node before where that name would go if it doesn't exist (just a suggestion, feel free to improvise).

Strings can be compared alphabetically by simple <, >, <=, >= operators!

For example, "adam" < "brett" is true because 'a' alphabetically precedes 'b'.

Note: this comparison is case-sensitive!

Confused about an operation / function? Draw out some simple cases and then translate what you drew into code!

I can't overstate the value of drawing intended behavior before implementation -- it's truly helpful!

I've had many a curious individual ask about how to use the debugger, so here's a live demo!

Suppose we made the mistake in our HumanCentipede.cpp of forgetting to update the head when the first Node is removed. [Comment that if-statement out in your file to follow along]

Now, suppose we try to run the following test, and find that it fails.

  int main() {
      HumanCentipede cent;
      cent.prepend("C");
      cent.prepend("B");
      cent.prepend("A");
      cent.print();   // A B C
      cent.remove("A");
      cent.print();   // B C
      cent.remove("C");
      cent.print();   // B
  }

Here are some general debugging steps:

1. Set breakpoints in functions that you think are to blame. In the above, the remove function seems like a good candidate.

2. Step through the breakpoints and inspect the state of the calling object. Verify that all data members are what you expect them to be with every step of the code.

3. Continue setting breakpoints in functions that are called by other functions until you find a violated assumption. The debugger helps "keep us honest" -- we often assume things as true that we overlook just by staring at the code!