Close
Close Window

Masters of Engineering Bridge Course

Chapter 8 Linked Lists, Bags, Stacks, and Efficiency

Show Source |    | About   «  7.9. Unit 7 Lab 3 Placeholder   ::   Contents   ::   8.2. Linked Bags  »

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

   «  7.9. Unit 7 Lab 3 Placeholder   ::   Contents   ::   8.2. Linked Bags  »

Close Window