.. This file is part of the OpenDSA eTextbook project. See
.. http://opendsa.org for more details.
.. Copyright (c) 2012-2020 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata::
   :author: Molly Domino

Linked Chains (Pointers)
========================

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

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 <http://cslibrary.stanford.edu/102/PointersAndMemory.pdf>`_" by Nick Parlante, Copyright 1998-2000, Stanford CS Education Library.

.. _PointerLinkedNodes: 

Interactive: Intro to Linked Chains of Nodes [10:51]
----------------------------------------------------

.. admonition:: Follow Along and Engage 

    Follow along with the video, refering to the LinkedChain class
    
    .. code-block:: java
    
      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
      }

.. raw:: html

   <div style="position: relative; width: 100%; height: 0; padding-bottom: 38%">
     <iframe src="https://virginiatech.hosted.panopto.com/Panopto/Pages/Embed.aspx?id=0edc5f73-d8a7-4986-9eae-b40d012ea645&autoplay=false&offerviewer=true&showtitle=true&showbrand=true&captions=false&interactivity=all" style="border: 1px solid #464646; position: absolute; top: 0; left: 0; width: 960px; height: 395px; box-sizing: border-box;" allowfullscreen allow="autoplay" aria-label="Intro to Linked Chains of Nodes" aria-description="Intro to Linked Chains of Nodes"></iframe>
  </div>

Checkpoint 1
------------

.. avembed:: Exercises/MengBridgeCourse/LinkedChainCheckpoint1Summ.html ka
   :long_name: Checkpoint 1

.. _PointerVisDemo:

Interactive: Demo in Visualizer [11:31]
---------------------------------------   

   .. admonition:: Follow Along and Engage
   
       Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!
   
      .. raw:: html
      
         <a href="https://courses.cs.vt.edu/~cs2114/meng-bridge/course-notes/8.1.3-LinkedChainCode.pdf" target="_blank">
         <img src="https://courses.cs.vt.edu/~cs2114/meng-bridge/images/projector-screen.png" alt="" width="32" height="32">
         Video Slides 8.1.3-LinkedChainCode.pdf</img>
         </a>
   
.. raw:: html

   <div style="position: relative; width: 100%; height: 0; padding-bottom: 38%">
     <iframe src="https://virginiatech.hosted.panopto.com/Panopto/Pages/Embed.aspx?id=340a8bc8-4e88-49ce-9ee0-b42600b66e5c&autoplay=false&offerviewer=true&showtitle=true&showbrand=true&captions=false&interactivity=all" style="border: 1px solid #464646; position: absolute; top: 0; left: 0; width: 960px; height: 395px; box-sizing: border-box;" allowfullscreen allow="autoplay" aria-label="Demo in Visualizer" aria-description="Demo in Visualizer"></iframe>
  </div>

Checkpoint 2
------------

.. avembed:: Exercises/MengBridgeCourse/LinkedChainCheckpoint2Summ.html ka
   :long_name: Checkpoint 2

.. _PointerContains: 

Contains() method Animation [5:14]
----------------------------------
   
   .. admonition:: Follow Along and Engage
   
       Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!
   
      .. raw:: html
      
         <a href="https://courses.cs.vt.edu/~cs2114/meng-bridge/course-notes/8.1.4-LinkedChainContains.pdf" target="_blank">
            <img src="https://courses.cs.vt.edu/~cs2114/meng-bridge/images/projector-screen.png" alt="" width="32" height="32">
            Video Slides 8.1.4-LinkedChainContains.pdf</img>
            </a>
   
.. raw:: html

   <div style="position: relative; width: 100%; height: 0; padding-bottom: 35%">
     <iframe src="https://virginiatech.hosted.panopto.com/Panopto/Pages/Embed.aspx?id=5fac67c7-6fc5-4b48-89f9-b4070133fffe&autoplay=false&offerviewer=true&showtitle=true&showbrand=true&captions=false&interactivity=all" style="border: 1px solid #464646; position: absolute; top: 0; left: 0; width: 960px; height: 395px; box-sizing: border-box;" allowfullscreen allow="autoplay" aria-label="Contains method Animation" aria-description="Contains method Animation"></iframe>
  </div>