4.2.1. Objectives¶

Upon completion of this module, students will be able to:

• Review the concept of reference variables

• Understand the characteristics and use of a Linked Chain of Nodes

• Implement a Linked Chain and associated methods

• Iterate though a Linked Chain

• Trace the execution of Linked Chain methods

• Compare Array-based and Linked Chain implementation

• Practice linked chain manipulation

4.2.2. Reference Variables¶

Java uses a restricted version of the pointer concept, which is called a reference. While they mean roughly the same thing, the term “pointer” tends to be used in discussions that are not specific to any particular language or implementation. The word “pointers” connotes the common C/C++ implementation of pointers as addresses or locations in memory. A reference only “points to” an object. This means that programmers are given more limited access with a reference. While this limits what they can do, the Java philosophy is that this is more than made up for by a greater chance of the code working correctly. Java programmers may only assign to a reference and compare two references for equality. Other uses of a reference are done implicitly with no control from the programmer. These restrictions reduce the chance for bugs.

Two references which both refer to a single object are said to be “sharing”. Sometimes we say that each is an alias for the other, because we can refer to the referenced object through either name. That two or more references can cooperatively share a single memory structure is a key advantage of references. Either can modify the object’s value.

4.2.3. Interactive: Intro to Linked Chains of Nodes¶

Follow Along and Engage

Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!

IntroToNodes.pptx

4.2.6. Interactive: Demo in Visualizer¶

LinkedChain Class Example

This code can be pasted into the visualizer from the link in the course slides:

package linkedchain;

public class LinkedChain {

   private Node head; // Reference to first node
   private int numberOfEntries;

   public static void main(String[] args) {

      LinkedChain chain = new LinkedChain();
      chain.add(10);
      chain.add(-2);
      chain.add(57);
   }

   public LinkedChain() {
      head = null;
      numberOfEntries = 0;
   } // end default constructor

   public void add(int newEntry) {
      // Add to beginning of chain:
      Node newNode = new Node(newEntry);
      newNode.next = head; // Make new node reference rest of chain
      head = newNode; // New node is at beginning of chain
      numberOfEntries++;
   } // end add

   private class Node {
      private int data;
      private Node next; // Link to next node

      private Node(int dataPortion) {
         this(dataPortion, null);
      } // end constructor

      private Node(int dataPortion, Node nextNode) {
         data = dataPortion;
         next = nextNode;
      } // end constructor
   } // end Node
}

Follow Along and Engage

Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!

LinkedChainCode.pdf

4.2.9. Contains() method Animation¶

Follow Along and Engage

Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!

LinkedChainContains.pdf