As you might have already seen in class, one of the interesting aspects of programming is that different problem solutions (although eliciting the same correct behavior), may go about finding the solution in wildly different ways.

The next thing you'll notice is that not all solutions are of the same quality!

What I mean by this is that what one solution takes 2 minutes to solve, another takes 2 days...

Just because they arrive at the same answer, doesn't mean that one of them wasn't incredibly stupid in doing it.

Resource management involves the ability to effectively, efficiently, and economically use data structures to accomplish your program's goals.

That sounded more like a business slogan than a definition, but the idea is that you want to use the right tool for the right job, and then effectively clean up after yourself.

So, let's examine how to engineer the right tools so we won't be sad.

Last class, we learned about the list Abstract Data Type (ADT), where elements are ordered relative to one another.

We then investigated one implementation using arrays, but hark! Today we have another list implementation.

Linked List Overview

A linked list is an implementation of the list ADT, except that instead of indexes indicating the position of each list element, the relative order of data is stored through references in each data node.

A linked list node is used to enclose the data being stored, as well as references to the next node in the chain (in the case of a singly linked list), or references to both the next and previous node in the chain (in the case of doubly linked lists).

Depending on your needs, you may implement either a singly or doubly linked list, but we'll examine the simpler today: the singly linked list.

Let's start out by seeing what a linked list looks like pictorially:

Note: just like the contents of any sequential list index, the data field of any node can contain data of any type (even another linked list!).

Inside Linked Lists

Let's examine the contents of a linked list, starting with each Node:

As mentioned, the data field contains the "meat" of the linked list, and can hold data of any type.

This is already an advantage of linked lists over array implementations, since the data can be of different types between nodes.

Whenever we have a collection of mixed-type data, we call it heterogeneous, compared to a collection with contents of the same type, which we call homogeneous.

Though it is not always necessary, or necessarily a good idea, to have heterogeneous collections, linked lists can fascilitate them more naturally that arrays.

Name some of the pros and cons of using Linked Lists over traditional arrays.

The next field in each Node simply contains a pointer to another Node, or is set to nullptr to indicate that it is the last element in the list.

Note: There are also implementations of linked lists where nullptr is never used; for instance, circular linked lists simply connect the last Node to the first, and can check if any Node is the final by seeing if its next is the same as the first!

Which brings us to the next component...

We also record-keep a reference to the first node in the list, often called the head.

In some implementations, we may also record-keep a pointer to the last node, often called the tail, though there are valid arguments for and against doing so.

In a non-circular LL implementation, the head is set to nullptr when the list is empty.

Now that we've seen the internals of linked lists and their Nodes, let's look at a few of the operations that we've seen lists support:

Linked List Operations

Just like the operations in sequential lists, linked lists host a variety of operations for adding, removing, and manipulating their contained data.

However, because our data organization is different for linked lists, the implementations of these operations will vary.

Insertion

Inserting into linked lists is quite simple *when we know where we want to insert the new Node*

Here is a simple example: inserting a Node at the front of the list.

1. Set the new node's next to point to the currently first.

2. Update the head to reference the newly added node.

Done! Later, we'll see how simple this insertion is.

However, what if we want to insert an element at the end of the list?

Can we access linked list nodes by index like we do with arrays? (e.g., intArray[1] returns the element at intArray's second position.)

No! Remember, the way we maintain ordering in a linked list is through pointers, which are not inherently index-able.

This presents a small problem. If we want to insert a Node anywhere in the linked list except for the front, we have to find where to insert it first!

So, the steps are slightly different:

1. Find the position in which to insert the new node.

2. Set the next pointer in the node previous to that position to now point to the new node.

3. Update the new node's next pointer accordingly.

For an end-of-the-list insertion, this might look like the following:

Shortly, we'll look at how these different insertion formats compare to the sequential list implementation.

Removal

As with any operation in linked lists, the main difficulty is making sure that we've updated our references properly.

This is especially true with removing Nodes in a linked list.

The steps for removing a Node are as follows:

1. Find the Node you want to remove (the mechanics of which we'll cover shortly), and for this discussion, we'll refer to this Node as "RN" (Removed Node)

2. Update the Node to the left of the RN to point to the Node to the right of the RN, and vice versa if doubly linked.

3. Update any record-keeping fields, like the linked list's head reference if the RN was the first in the list (or the size field if record-kept).

Let's look at how this might be depicted:

Note above that we delete the Node with data "great" and redirect the next pointer of its predecessor to the "examples" Node.

Now the only thing left to consider is how we "find" Nodes in our linked list.

Since we can't use index access like with sequential lists, we turn to a new means of accessing and changing elements.

Access & Iterators

Earlier we saw that the "find a node" operation might be easy to implement, but costly in the number of steps it takes.

If we were to access every element in a linked list sequentially by starting at the head node each time, it would be very inefficient!

So, for arbitrary access of data in a linked list, we can turn to Iterators for help.

An iterator is an object defined on top of a data structure that allows users to efficiently access (and sometimes modify) the elements of that structure by maintaining a "sliding" pointer to each element.

That's a bit of a vague definition, but consider an iterator object defined *on* a given linked list that can be asked to move to the previous Node, next Node, or to access the data of the one it is looking at.

We'll talk more about iterators later in the course.

In this implementation tutorial, we'll cover the basics of a singly linked list with a few simple methods.

To do so, we'll be creating 2 classes:

• The IntLinkedList class itself

• The Node class to hold the data of the linked list

Often times, when we want to make "helper classes" to be used by the main class, but don't want users to be able to instantiate instances of these helpers. Typically, this is done by making private inner classes.

Inner classes are classes that are defined within the scope of another class. In C++, they have no special access to any of the private members of the containing (outer) class, but the outer class may instantiate members of the inner class.

Since we *don't* want users of our IntLinkedList class to be able to access Nodes directly, we'll make it a private inner class.

However, since *we* want to be able to access the Node's members, we'll make it a private struct (not class, in which all members are private by default).

An inner class that is private cannot be instantiated or used outside of the class, but those that are public can be.

Here's a scaffold that illustrates how we want to structure our 3 classes:

  #ifndef INTLINKEDLIST_H
  #define INTLINKEDLIST_H
  
  class IntLinkedList {
  private:
      struct Node {
        // TODO: complete Node
      };
    
      // TODO: Add data members
  
  public:
      // TODO: Add member functions
  };
  
  #endif

Designing Nodes

Let's start by designing our Nodes, which is quite simple: as we said, in a singly linked list, they contain only the data and a pointer to the next Node in the chain.

So, let's try to fill in the blanks:

  ...
  struct Node {
      // [!] Define data members (data and next)
      
      // [!] Define constructor
      Node (int d) {
          // [!] TODO
      }
  }
  ...

  ...
  struct Node {
      int   data;
      Node* next;
  
      Node(int d) {
          data = d;
          next = nullptr;
      }
  };
  ...

Designing the IntLinkedList

With our Nodes in place, we can now turn our attention to designing the IntLinkedList itself.

For this tutorial, we'll implement a few methods to be used by IntLinkedList objects themselves:

• int getSize (); returns the number of elements currently in the IntLinkedList.

• void prepend (int toAdd); adds the given int toAdd to the the head of the IntLinkedList.

• bool contains (int toFind); returns true if the IntLinkedList contains the given int toFind, false otherwise.

Let's start out easy by defining our fields, constructor, destructor, and then declaring our methods.

  ...
  class IntLinkedList {
  private:
      struct Node { ... };
      // [!] Data members here: size and head
  
  public:
      // [!] Declare member functions here
      // constructor, getSize, prepend, and contains
  };
  ...

  ...
  class IntLinkedList {
  private:
      struct Node { ... };
    
      int   size;
      Node* head;
  
  public:
      IntLinkedList();
      ~IntLinkedList();
      int getSize();
      void prepend(int toAdd);
      bool contains(int toFind);
  };
  ...

Great! Now let's head on over to our IntLinkedList.cpp and start implementing our methods!

  #include "IntLinkedList.h"
  using namespace std;
  
  IntLinkedList::IntLinkedList() {
      // TODO
  }
  
  IntLinkedList::~IntLinkedList() {
      // TODO
  }
  
  int IntLinkedList::getSize() {
      // TODO
      return 0;
  }
  
  void IntLinkedList::prepend(int toAdd) {
      // TODO
  }
  
  bool IntLinkedList::contains(int toFind) {
      // TODO
      return false;
  }

We'll start off with the constructor and move from there.

  ...
  IntLinkedList::IntLinkedList() {
      // TODO: Initialize an empty IntLinkedList
  }
  ...

  ...
  IntLinkedList::IntLinkedList() {
      size = 0;
      head = nullptr;
  }
  ...

Simple enough! Now let's get some ints inside by tackling the getSize and prepend methods.

The trick here is careful record-keeping. We have to remember that prepending to a linked list can occur in a couple of cases: (1) when it's empty, and (2) when there is at least one item already added.

If we're clever, we can structure our prepend method to handle both of these cases elegantly...

  ...
  int IntLinkedList::getSize() {
      // TODO: just return size -_-
  }
  
  void IntLinkedList::prepend(int toAdd) {
      // TODO: add a new Node containint toAdd
      // to head, remembering that current head iss:
          // nullptr (empty list) OR
          // a Node (non-empty list)
      // Hint: takes 4 lines of code!
  }
  ...

  ...
  int IntLinkedList::getSize() {
      return size;
  }
  
  void IntLinkedList::prepend(int toAdd) {
      Node* currentHead = head;
      head = new Node(toAdd);
      head->next = currentHead;
      size++;
  }
  ...

Let's implement our contains method next...

  ...
  bool IntLinkedList::contains(int toFind) {
      // TODO: iterate through the LL to see
      // if toFind is within
  }
  ...

  ...
  bool IntLinkedList::contains(int toFind) {
      for (Node* n = head; n != nullptr; n = n->next) {
          if (n->data == toFind) {
            return true;
          }
      }
      return false;
  }
  ...

Looking good, we're almost ready to test our class for basic functionality!

We have one last thing to consider...

In our prepend method, we created new Nodes using the dynamic allocation syntax; what must we do to avoid memory leaks?

Make sure their memory gets released in the destructor, of course! This will require us to call delete on EACH Node.

Let's make sure we release *all* of our dynamically allocated Nodes in the destructor:

  ...
  ~IntLinkedList() {
      // TODO: Release all allocated Nodes
  }
  ...

  ...
  ~IntLinkedList() {
      Node* n = head;
      Node* prev = nullptr;
      while (n != nullptr) {
          prev = n;
          n = n->next;
          delete prev;
      }
  }
  ...

Nice! Now let's give it a whir...

  int main() {
      IntLinkedList linky;
      linky.prepend(3);
      linky.prepend(2);
      linky.prepend(1);
      assert(linky.getSize() == 3);
      assert(linky.contains(2));
      assert(!linky.contains(5));
      cout << "[!] You did it! Yay!" << endl;
  }

Now, we're only missing one thing: being able to access the elements of our IntLinkedList in the order they appear!

At this point, we would define an Iterator for our IntLinkedList class, but that will be a topic of a future discussion...

For now, let's remember a couple of last concerns from last week's topics...

Suppose I want to have a couple of different IntLinkedLists, but (as you well know), I'm far too lazy to add values to both, so I'd like to instead copy the values from one into the other.

This would be very convenient! Still, I would like to have 2, autonomous IntLinkedLists after the copy, with each having the same stored values, but being otherwise independent.

Do we get this behavior for free? Let's find out!

What will be printed below, or will there be undefined behavior?

  int main() {
      IntLinkedList linky;
      linky.prepend(3);
      linky.prepend(2);
      linky.prepend(1);
    
      IntLinkedList linkyAlsoQuestionMark = linky;
      linkyAlsoQuestionMark.prepend(0);
    
      // [?] What will get printed here?
      cout << linky.contains(0) << endl;
      cout << linkyAlsoQuestionMark.contains(0) << endl;
  }

Hmm, that's odd -- what happened in the above, and why?

Depending on your system, you may or may not get an error from the above, but there is indeed an issue -- the compiler-provided copy-constructor for IntLinkedList copied the head pointer from linky when it made linkyAlsoQuestionMark, and so they both refer to the same Nodes in memory!

Draw a diagram that illustrates the Nodes being referred to by each of linky and linkyAlsoQuestionMark.

So, let's safely define our own copy-constructor for the IntLinkedList class.

  ...
  IntLinkedList::IntLinkedList(const IntLinkedList& other) {
      head = nullptr;     // Initialize head to nullptr
      Node* p = nullptr;  // Maintain a ptr to previous Node
    
      // Iterate through each of the other Nodes
      for (Node* n = other.head; n != nullptr; n = n->next) {
          // TODO: Create a new Node with n's data
          // TODO: Update p's next ptr
          // TODO: Update head if appropriate
          // TODO: set p appropriately
      }
    
      // TODO: Update one other data member...
  }
  ...

  ...
  IntLinkedList::IntLinkedList(const IntLinkedList& other) {
      head = nullptr;     // Initialize head to nullptr
      Node* p = nullptr;  // Maintain a ptr to previous Node
    
      // Iterate through each of the other Nodes
      for (Node* n = other.head; n != nullptr; n = n->next) {
          Node* newNode = new Node(n->data);
          if (p != nullptr) {
            p->next = newNode;
          }
          if (head == nullptr) {
            head = newNode;
          }
          p = newNode;
      }
    
      size = other.size;
  }
  ...

Now the moment of truth, let's test it once more...

  int main() {
      IntLinkedList linky;
      linky.prepend(3);
      linky.prepend(2);
      linky.prepend(1);
    
      IntLinkedList linkyAlsoQuestionMark = linky;
      linky.prepend(0);
    
      assert(linky.getSize() == 4);
      assert(linkyAlsoQuestionMark.getSize() == 3);
      assert(linky.contains(0));
      assert(!linkyAlsoQuestionMark.contains(0));
      cout << "[!] Huzzah! Crisis averted" << endl;
  }

Of course, where copy construction is allowed, so too should we make sure that the assignment operator functions as intended.

However, since assignment is so similar to copy construction, we can re-use our work with the copy-constructor by what is known as a "copy and swap."

A copy and swap operation can be used for assignment between objects (A = B), where we simply copy-construct a new version of the assigned object (B), and then swap A's and B's data members.

Let's see how that'd look:

  ...
  IntLinkedList& IntLinkedList::operator=(const IntLinkedList& other) {
      // Copy...
      IntLinkedList copy(other);
    
      // ...then swap!
      std::swap(head, copy.head);
      std::swap(size, copy.size);
      // NB, std::swap(A, B) does:
      // temp = A; A = B; B = temp;
      
      return *this;
  }
  ...

To explain the above:

• We copy-construct copy from other, which means we now want the assigned IntLinkedList (i.e., A in A = B) to be "equal to" the copy.

• To set A = B, we simply swap the data members of A with the copy.

• Any existing Nodes from A are deleted when the copy exits the scope of the assignment operator overload (because we've already designed the destructor!).

Depicting the above, let's step through each part of copy-and-swap.

Step 1 - Identifying goals: let's say we have the operation copyInto = copyFrom; We want the resources allocated in copyInto to be released, and then those in copyFrom to be deep-copied into copyInto.

Step 2 - Copy-step: the first thing we want to do is make a deep-copy of copyFrom. We'll simply use the copy-constructor we've defined for our Linked List to do this job for us, and create a new, local Linked List called copy that is a deep-copy of copyFrom.

Step 3 - Swap-step: next, we'll simply swap the data members of copyInto and copy such that copyInto now points to the Nodes that were deep-copied from copyFrom, and copy now points to copyInto's old Nodes.

Step 4 - After-assignment Cleanup: after the operator= function returns, copyInto now correctly points to the Nodes that are deep copies of those in copyFrom, and since copy was local to the operator= function, its destructor is called, which then cleans up all of copyInto's old Nodes!

And once more, just to test...

  int main() {
      IntLinkedList linky;
      linky.prepend(3);
      linky.prepend(2);
    
      IntLinkedList theRelinkening;
      theRelinkening = linky;
      theRelinkening.prepend(1);
    
      assert(linky.getSize() == 2);
      assert(theRelinkening.getSize() == 3);
      assert(linky.contains(2));
      assert(!linky.contains(1));
      assert(theRelinkening.contains(3));
      assert(theRelinkening.contains(1));
      cout << "[!] Assignment complete!" << endl;
  }

Summary

• Whenever your classes have data-members pointers, you will generally want to define a copy-constructor and assignment operation (lest the compiler's given ones not do what you want).

• Additionally, whenever your classes have dynamically allocated data members (like Nodes!), your destructors must make sure to delete them. Rule of thumb: for every time you use the new keyword, so also should you use the delete.

Let's do a couple of practice problems using our IntLinkedList class!

Add a new member function isSorted to the IntLinkedList class, which returns true if and only if the list's elements occur in ascending order from the head. Two consecutive and equivalent ints (and the empty list) are considered sorted. Signature:
bool isSorted();

  int main() {
      IntLinkedList linky;
      linky.prepend(3);
      linky.prepend(2);
      linky.prepend(1);
      assert(linky.isSorted());
      linky.prepend(5);
      assert(!linky.isSorted());
      cout << "[!] Tests passed!" << endl;
  }

[Challenge] Add a new member function remove to the IntLinkedList class, which removes the Node at the given index starting from the head (at index 0) of the IntLinkedList. Signature:
void remove(int index);

  int main() {
      IntLinkedList linky;
      linky.prepend(3);
      linky.prepend(2);
      linky.prepend(1);
      linky.remove(1); // Removes the 2
      assert(linky.contains(3));
      assert(!linky.contains(2));
      cout << "[!] Tests passed!" << endl;
  }