Welcome to Lesson 4!

Learning Objectives

By the end of today's lesson, you should know:
  • How do you implement the List manipulations procedures?
  • How do you overload operators?
    • How do you overload the == operator for the List class?
  • What is a circular linked list?
  • What are applications of circular linked lists?
  • What is a multilist?
  • Give an example of a multilist.

Announcements

  • Quiz 1 after break.
  • Lab 2 due Monday
    • Who has started on Lab 2?
    • If you haven't started yet, start today!
    • Make sure you get lots of help if needed! (Email, office hours, ATC drop in homework help, free tutoring with Mega, Gel or Dixon)
    • When you email me for help, please attach ALL your files to the email!
  • You can find Eclipse on the Lab computers under "Eclipse Neon jcc"
  • Reminder: Women in Computer Science Club Meeting today at 12:30pm in ATC 202!
  • Please see me at break if you are on waitlist


Review Activity

With a partner, answer the following questions:

  • What is the precondition for getStart?
  • Write the getStart function, handling the precondition in the manner described last class
  • What is the precondition for getIterator?
  • Write the getIterator function, handling the precondition in the manner described last class
  • Write the removeStart function


Writing the List Manipulation Procedures

  • Manipulation procedures allow the user to alter the current state of the data structure.
  • In our List, the manipulation procedures are used to add data to the list, remove data from the list and alter the position of the iterator.
  • You already wrote insertStart, insertStop, removeStart, and removeStop as part of Lab 1.
  • You will need to update these functions for Lab2 for a doubly-linked List.
  • To write the list manipulation procedures for the iterator, it will help to visualize the linked list in this way:
Image representing iterator and next nodes


Manipulation Procedure: insertIterator

  • The insertIterator function adds a node following the one currently being pointed to by the iterator.
  • It can be used to insert nodes at any position in the list.
  • You can visualize the insertIterator operation with the following diagram:
Image depicting insertIterator

  • When the user calls the insertIterator function, a new node is added after the iterator.
  • We must update the new node's next field to point to the iterator->next.
  • Then, we must update the pointer of the iterator's next field to point to the new node.
  • There are a couple of edge cases in this function:
    1. The iterator is currently pointing to the stop<-- Why is this an edge case?
    2. There is also a precondition that the iterator is not off the end of the list.
      • We can call our offEnd function here to test for this precondition!
  • Here is the pseudocode for this function:
  1. If the iterator is offEnd <-- this is a precondition
    1. Call assert
  2. If the iterator is pointing to the end node
    1. call insertLast
  3. Otherwise
    1. Declare a new Node variable
    2. Update the new node's next pointer to equal the iteratator's next
    3. Set the iterator's next to point to the new node
    4. Increment the size of the List

Another depiction of insertIterator:


Singly linked list insert after.png

Image source.


Group Activity: Drawing removeIterator

  • Let's take a moment to draw the removeIterator operation.
  • This is probably the most challenging function you will need to write for the list data structure.
  • I strongly recommend only implementing this function with your doubly-linked list, as it will be much easier!
  • Drawing this operation will help you when it comes time for you to write the code for removeIterator in your lab.


Overloading Operators

Introducing Operator Overloading

  • When we are writing our own classes in C++, and we would like to be able perform operations such as arithmetic, making comparisons, etc, we have two options:
    •  We can write our own functions to handle these operations
    • We can overload the C++ operators
  • However, for many software engineers, overloading the C++ operators provides more elegance and readability.
  • For example, which do you find easier to read and understand?
object4 = object1 + object2 * object3;
OR
object4 = plus(object1, times(object2, object3);
  • Writing our own plus and times functions can make our code harder to read.
  • The + and * operators are easier to read.
  • In C++, the following 38 operators can be overloaded:

 +

 /


 |




+= 
 -=*= 
/= 
%= 
^= 
&= 
 |=
 <<>> 
<<= 
 >>=== 
!= 
<= 
>= 
&& 
 ||++ 
-- 
 ->* ,
 ->[] 
 ()new 
new[] 
delete 
delete[] 


How to Overload Operators

  • Operators can be overloaded in one of two ways:
  1. They can be defined as simple functions, separate from any class definition.
  2. They can be defined as member functions within the body of a class definition.
  • We are going to focus primarily on the second option for this lesson.
  • The following is a general formula for overloading operators:
return_type operatoroperator_symbol(parameters)
{
    //statements to redefine operator
}
  • Once we have redefined the operator, we can use it as normal.
  • For example:
class Line
{
    public:
        bool operator<(const Line &line);

    private:
        int length;
};

...

bool Line::operator<(const Line &line)
{
    if(length < line.length)
        return true;
    return false;
}


Example Program that Overloads the < Operator

/** Line.h file */

#ifndef LINE_H
#define LINE_H

#include<iostream>
using namespace std;

class Line
{
    public:
        Line();
        Line(int new_length);
        bool operator<(const Line &line);
    private:
        int length;

};

#endif // LINE_H


/** Line.cpp file */

#include "Line.h"

Line::Line():length(0){}
Line::Line(int new_length)
{
    length = new_length;
}

bool Line::operator<(const Line &line)
{
    if(length<line.length)
        return true;
    return false;
}

int main()
{
    Line line1(3);
    Line line2(4);
    if(line1 < line2)
    {
        cout << "It works!\n";
    }

   //note that the above test is not sufficient, but is just an example

   return 0;
}

Applying Operator Overloading to Our List Class

  • When we write our own classes, it is good practice to write an equals function so that we can compare two objects from the class.
  • We can use operator overloading to accomplish this task by overloading the == operator.
  • Let's look at an example using our List class from the last two lectures.
  • Let's add some code to override the == operator to compare two lists.
  • First, we will add a signature to our additional list operations in our List.h file:

        /**Access Functions*/

        bool operator==(const List &list);
        //Tests two lists to determine whether their contents are equal
        //Postcondition: returns true if lists are equal and false otherwise

  • Algorithm for testing for equality of two lists:
  1. Check if the sizes of the two lists are equal and, if not, return false
  2. Set the iterators to point to the start of each list
  3. While not offEnd of one of the lists
    1. Test whether the data at each node is equal
    2. If not, return false
    3. Move the iterators up by one node in each list
  4. Return true (you haven't return false yet, so the lists must be equal)
  • C++ code, overloading the equality operator for a linked list:


template <class listdata>
bool List<listdata>::operator==(const List& list)
{
    if(length != list.length)
        return false;
    Node* temp1 = start;
    Node* temp2 = list.start;
    while(temp1 != NULL)
    {
        if(temp1->data != temp2->data)
            return false;
        temp1 = temp1->next;
        temp2 = temp2->next;
    }
    return true;
}

  • Then, in main, you could run tests like this one:
List L1;
List L2;

//some additional lines of code to add data to the Lists

if(L1==L2)

      cout << "Lists are equal!\n";
else
      cout << "Lists are unequal!\n";



Advanced Linked Lists

Introducing Circular Lists

  • A circular linked list is a list in which the end node points to the first node rather than to NULL.

A singly linked circular list is one in which the end node points to the first node. Image source.

  • If we implement our list as a doubly-linked list, the first node will also need to point to the end node.

Doubly Circular Linked List

A doubly linked circular list is one in which the end node points to the first node and the strat node points to the end node. Image source.


Applications of Circularly Linked Lists

  • Circularly linked lists have applications to games, for example: keeping track of whose turn it is in an online version of a multi-player board game or to represent the game board in games like Life or Monopoly.
  • In general, circularly linked lists are useful when implementing algorithms for round-robin style scheduling.


Writing the Circular List Data Structure:
  • Circular linked lists are less common that linear linked list
  • Therefore, we will not be implementing a full circular linked list in this class.
  • However it will be good practice to consider some of the differences in implementation of the circular and linear linked lists.


Case Study: Iterating Through a Circularly Linked List

  • One of the main differences when writing functions for a circular and linear linked list is the approach we take when iterating through our list.
  • Consider the print() function.
  • This function requires us to iterate through the list one node at a time until we reach the end of the list.
  • But, in the case of a circular list, there is no true end to the list.
  • Therefore, we must modify our approach when we implement this function.
  • For example, let's look at the print function for a linear singly-linked list.
  • How can we alter this function to work for a circular singly-linked list?

template <class listdata>
void List<listdata>::printList()
{
    Nodeptr iter = first;
    while (iter != NULL)
    {
        cout << iter->data << " ";
        iter = iter->next;
    }
    cout << endl;
}

  • For example, what will happen if we change the above code to the following?

template <class listdata>
void List<listdata>::printList(){
    Nodeptr iter = first;
    while (iter != first)//changed NULL to first
    {
        cout << iter->data << " ";
        iter = iter->next;
    }
    cout << endl;
}

  • There are several approaches we could take to this problem.
  • One approach is to print the first and last nodes separately.
  • For example, we can stop the loop when the iterator reaches the last node and then print the last data out separately:

template <class listdata>
void List<listdata>::printList()
{
    Nodeptr iter = first;
    while (iter != last) //changed NULL to last
    {
        cout << iter->data << " ";
        iter = iter->next;
    }
    cout << last->data << endl; //print last data separately from loop
}

  • Another approach is to use a pre-iterator that follows one step behind the iterator:
template <class listdata>
void List<listdata>::printList()
{
    Nodeptr iter = first;
    Nodeptr pre_iter = last;
    while (iter != last)
    {
        iter = iter->next;
        pre_iter = pre_iter->next;
        cout << pre_iter->data << " ";
    }
}
  • Can you think of any other options?


Group Activity: Visualizing insertLast on a Circular Linked List

  • With a partner, draw a circular linked list on a sheet of paper.
  • Add the values "Susan", "Shin", "Juan", and "Mark" to your List.
  • "Susan" is at the first and "Mark" is the last.
  • We wish to add the node containing the string "Aastha" to the back of the list
  • Alter the arrows in the diagram so that the node containing "Aastha" is the new end node.
  • When you are finished, hold onto your paper for the next exercise.


Case Study: insertion on a Circular Linked List

  • The Implementation of a circularly linked list differs from that of a linearly linked list only in the operations performed at the start and the end of the list.
  • For example, when we add or delete a node at the start of the list, we must update the next pointer of our last node as well.
  • Similarly, when we add or delete a node at the end of the list, we must update the previous pointer of the first node in the case of a doubly-linked list.
  • Operations that occur in the middle of the list will not differ.
  • Let's examine the code below to add a new node at the start of a circular singly-linked list.
  • Notice what happens when the list is empty and we need to add a new node. Why?

template <class listdata>
void List<listdata>::insertFirst(listdata data)
{
    Nodeptr newFirst = new Node(data);
    if (size == 0)
    {
        first = last = newFirst;

        last->next = first;   

    }
    else
    {
        newFirst->next = first;
        last->next = newFirst;

        first = newFirst;
    }

    size++;

}



Multi-Linked Lists
Definition:
  • A multi-linked list is a linked list where each node may contain pointers to more than one nodes of the linked list.
  • The standard use of multi-linked lists is to organize a collection of elements in two or more different ways.
  • For example, suppose my elements include student objects that store both the name of a student and his or her student id number. For example:

    Latisha: 1234, Sven: 5678, Larry: 9101, Nina: 1121

  • Let's further suppose that I might want to order the students alphabetically for certain applications, and by id number for other applications.
  • I could use a multi-linked list as it would offer me this type of flexibility.
  • Below is a representation of a multi-linked list storing our example data:
  • Despite this example, keep in mind that the nodes in multi-linked lists can point to more than just two nodes.
  • Each node could point to three or more nodes, depending on the application.
  • One such application could be ordering songs in an MP3 player according to artist, album, genre, playlist, recently-played, etc.


Doubly Linked Lists = A Special Variety of Multi-Linked Lists
  • As it turns out, doubly-linked lists are a special case of multi-linked lists. They are a special case for the following reasons:
    1. Each node has just 2 pointers.
    2. The pointers are exact inverses of each other.
  • We will not spend much class time working on multi-linked lists other than doubly-linked lists.
  • It is important only that you understand the concept.


Wrap Up

  • With a partner, answer today's learning objectives

Upcoming Assignments

  • Lab 2 due Monday


~Have a Great Weekend!~