8.1. Linked Chains (Pointers)¶
8.1.1. Objectives¶
Upon completion of this module, students will be able to:
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
8.1.1.1. Acknowledgement¶
Some prose and images on this page originally came from a document written by Nick Parlante of Stanford University, and used by permission of the author: “Pointers and Memory” by Nick Parlante, Copyright 1998-2000, Stanford CS Education Library.
8.1.2. Interactive: Intro to Linked Chains of Nodes [10:51]¶
Follow Along and Engage
Follow along with the video, refering to the LinkedChain class
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
}
8.1.3. Checkpoint 1¶
8.1.4. Interactive: Demo in Visualizer [11:31]¶
Follow Along and Engage
Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!
Video Slides 8.1.3-LinkedChainCode.pdf
8.1.5. Checkpoint 2¶
8.1.6. Contains() method Animation [5:14]¶
Follow Along and Engage
Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!
Video Slides 8.1.4-LinkedChainContains.pdf