Welcome to Lesson 4!

Learning Objectives

By the end of today's lesson, you should know:

  • What is the difference between a deep and shallow copy?
  • How do you write a copy constructor?
  • How do you override the equals method 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


1. List Copy Constructor

  • Copy constructors are used to create a copy of an existing object.
  • Note that they are most often preferred over overriding the more error-prone clone method for Object (source: Joshua Bloch, Effective Java).
  • Thus, while your textbook overrides clone for several classes, we will not follow this example.
  • In our linked list class, the copy constructor's job will be to create a new list that is an identical -- but distinct -- copy of the original list.
  • We would call the copy constructor for a linked list by passing in the original list as a parameter:
List copy = new List(original_list); //calling the copy constructor
  • After making the above method call, copy should contain the same data, in the same order, as original_list.
  • However, the two Lists will be different Lists (stored separately in memory).
  • In other words, the copy constructor should make a deep copy of the List, not a shallow copy.


1.1. Deep vs Shallow Copies

  • A shallow copy simply sets all fields in the new object equal to the fields in the original object:
copy_list.head = original_list.head;
copy_list.tail = original_list.tail;
    copy_list.length = original_list.length;

enter image description here

  • The important concept to understand here is that we need to make a deep copy rather than a shallow copy.
  • A deep copy will allocate new memory. This memory will contain a copy of the data in the original list.
  • A shallow copy will simply create two names for the same List. Anything that I do to one List, will affect the other List and vice versa.
  • Instead, the goal is two separate lists containing the same data in the same order.




With a deep copy, we allocate new memory and then copy the contents of the original object into these new memory locations. Image Source


1.2. How to Write a Copy Constructor

  • In Java the copy constructor follows this standard format:
public classname (classname obj) {
   // body of constructor
} 
  • Therefore, our List copy constructor needs to have the following signature:
public List(List original)
{
    //body of constructor
}

  • Above, the variable original is the List you are trying to make a copy of.


1.3. How to Write the List Copy Constructor

  • Here is the pseudocode for the List copy constructor:
public List(List original)
if(original list is empty) //i.e. all fields are default
set fields of this list to be default
else
    set a temp reference to first node of original
while (temp is not NULL)
copy the contents of temp node into this
set iterator of this list to be null

  • Here is the code for the copy constructor. Make sure you understand it.
    /**
     * Instantiates a new List by copying another List
     * @param original the List to make a copy of
     * @postcondition a new List object, which is an identical
     * but separate copy of the List original
     */
    public List(List original) {
        if (original.length == 0) {
            length = 0;
            first = null;
            last = null;
            iterator = null;
        } else {
            Node temp = original.first;
            while (temp != null) {
                addLast(temp.data); //inserts into this
                temp = temp.next;
            }
            iterator = null;
        }
      
    }

  • Why do I need to create the temp variable above?

1.4. Example Copy Constructor Steps in Images

STEP 1:
Data from first node of original copied into this

STEP 2:

Second value inserted of original now inserted into this

STEP 3:
data from last node of original copied into this

STEP 4:

temp advanced off end of the original list, and iterator of this set to null


1.5. Calling the List Copy Constructor
  • Below is an example of calling the List copy constructor:
           List L = new List(); //calling default constructor
    for (int i = 0; i < 10; i++) {
        L.addLast(i);
    }
        
    List Lcopy = new List(L); //calling copy constructor
    //verify Lcopy contains same values as L
    System.out.println("Printing Lcopy: " + Lcopy);


1.6. Further Reading


2. Overriding the Equals Method

2.1. Why Override the Equals Method?

  • The equals() method is defined in java.lang.Object
  • Recall that all Java classes inherit from the Object class
  • Object contains a method called equals, which compares two objects for equality:
public boolean equals(Object obj) {
    return (this == obj);
}
  • Notice that this default implementation only compares two objects to see if they are stored in the same location in memory (i.e. they are the same, identical object!)
  • This implementation is not useful to us, as our goal with the List class is to compare two distinct Lists to determine whether they are equal, meaning:
    • The two Lists contain the same data
    • That data is stored in the same order
  • Thus we will want to override the equals method to redefine it for the List class.

2.2. The Equals Contract
  • Per the Oracle documentation for the equals method for Object, when you override equals, you must ensure that your method adheres to what is known as the "equals contract:"
    • It is reflexive: for any non-null reference value x, x.equals(x) should return true.
    • It is symmetric: for any non-null reference values x and y, x.equals(y) should return true if and only if y.equals(x) returns true.
    • It is transitive: for any non-null reference values x, y, and z, if x.equals(y) returns true and y.equals(z) returns true, then x.equals(z) should return true.
    • It is consistent: for any non-null reference values x and y, multiple invocations of x.equals(y) consistently return true or consistently return false, provided no information used in equals comparisons on the objects is modified.
    • For any non-null reference value x, x.equals(null) should return false.
  • Therefore, we must write equals with care to ensure that we do not violate the above aspects of the contract.
  • According to Joshua Bloch in Effective Java, all equals methods should do the following:
    • Use the == operator to check if the argument is a reference to this object
    • Use the instanceOf operator to check if the argument has the correct type.
    • Cast the argument to the correct type.
    • For each significant field in the class, check if that field of the argument matches the corresponding field of this object.

2.3. Overriding Equals for the List Class
  • Recall that our goal for this method is to determine if two Lists contain the same data, in the same order.
  • Thus, our method will need to traverse the Nodes in the List - one-by-one - to compare the data stored in their Nodes.
  • Algorithm for testing for equality of two lists:

  1. Check if the lengths of the two Lists are equal and, if not, return false

  2. Set two temporary iterators to point to the start of each List

  3. While the temp iterators are not null, do:

    1. Test whether the data in both Nodes is equal

    2. If not, return false

    3. Advance the temp iterators up by one Node in each List

  4. Return true (you haven't return false yet, so the Lists must be equal)

  • In this method, we will be comparing this List with a List that we pass in as a parameter.
  • Thus, when we call the method, we would call it something like this:
List L1 = new List();
L1.addFirst(3);
List L2 = new List();
L2.addFirst(1);
L2.addFirst(2);

//call below to equals method
System.out.println("The two Lists are equal (should print false): " + L1.equals(L2));
  • We, therefore, write the method this way:
    /**
     * Determines whether two Lists have the same data
     * in the same order
     * @param L the List to compare to this List
     * @return whether the two Lists are equal
     */
    @Override public boolean equals(Object o) {
        if(o == this) {
            return true;
        } else if (!(o instanceof List)) {
            return false;
        } else {
            List L = (List) o;
            if (this.length != L.length) {
                return false;
            } else {
                Node temp1 = this.first;
                Node temp2 = L.first;
                while (temp1 != null) { //Lists are same length
                    if (temp1.data != temp2.data) {
                        return false;
                    }
                    temp1 = temp1.next;
                    temp2 = temp2.next;
                }
                return true;
            }
        }
    }

2.4. Reflection: Is the equals method an accessor, mutator, constructor, or additional operation?


3. Advanced Linked Lists

3.1. Introducing Circular Lists

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

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

3.2. 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 game
    • representing the game board in games like Life or Monopoly.
  • In general, circularly linked lists are useful when implementing algorithms for round-robin style scheduling.


3.3. 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.


3.4. Group Activity: Visualizing insertFirst on a Circular Linked List

  • With a partner, draw a circular linked list on a sheet of paper.
  • Add the values 1, 2, 7 to your List.
  • 1 is the first value and 7 is the last
  • We wish to add the node containing the value 11 to the front of the list
  • Alter the arrows in the diagram so that the Node containing 11 is the new first Node.
  • When you are finished, hold onto your paper for the next exercise.


3.5. Case Study: Insertion in 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 refrence of our last node as well.
  • 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?

public void addFirst(int data)
{
    Node N = new Node(data);
    if (length == 0) //edge case
    {
        first = last = N;

        last.next = N; //making the List circular   

    }
    else
    {
        N.next = first;
        last.next = N; //making the List circular

        first = N;
    }

    length++;

}



3.6. Multi-Linked Lists
  • A multi-linked List is a List where each Node may contain references to more than one Node in the 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, id# 1234
    Sven, id# 5678
    Larry, id# 9101
    Nina: id# 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.


3.7. 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 references.
    2. The references are exact inverses of each other.
  • We will not spend much class time working on multi-linked lists other than doubly-linked lists.
  • In Lab 2, you are writing a doubly-linked, a.k.a. muti, List


Wrap Up
  • Answer the review questions on Canvas for today's lesson


Upcoming Assignments

  • Lab 2 due Monday at midnight
  • Complete your weekly quiz


~Have a Great Weekend!~