.. 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 Bags
===========

Objectives
----------

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

* Name the function and purpose of basic Java data structures
* State key characteristics of Bags in Java
* Build and populate Bags in Java

Suggested Reading:
~~~~~~~~~~~~~~~~~~

**Chapter 3: Bag Implementation That Links Data** from `Data Structures and Abstractions with Java, 4th edition  by Frank M. Carrano and Timothy Henry <https://www.amazon.com/Data-Structures-Abstractions-Java-4th/dp/0133744051/ref=sr_1_1?ie=UTF8&qid=1433699101&sr=8-1&keywords=Data+Structures+and+Abstractions+with+Java>`_


.. _LinkedBagIntro: 

Interactive: Introduction to Linked Bags
-----------------------------------------------
.. 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/SWDesignAndDataStructs/course-notes/LinkedBagIntro.pdf"  target="_blank">
      <img src="https://courses.cs.vt.edu/cs2114/opendsa/icons/projector-screen.png" alt="" width="32" height="32">
      LinkedBagIntro.pdf</img>
      </a>


.. raw:: html

   <center>
   <iframe type="text/javascript" src='https://cdnapisec.kaltura.com/p/2375811/embedPlaykitJs/uiconf_id/52883092?iframeembed=true&entry_id=1_dh0z9agx' style="width: 960px; height: 395px" allowfullscreen webkitallowfullscreen mozAllowFullScreen allow="autoplay *; fullscreen *; encrypted-media *" frameborder="0" title="Introduction to Linked Bags"></iframe> 
   </center>


.. _LinkedBagAdd: 

Interactive: LinkedBag add() and toArray()
--------------------------------------------------

.. 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/SWDesignAndDataStructs/course-notes/LinkedBagAddToArray.pdf"  target="_blank">
      <img src="https://courses.cs.vt.edu/cs2114/opendsa/icons/projector-screen.png" alt="" width="32" height="32">
      LinkedBagAddToArray.pdf</img>
      </a>


.. raw:: html

   <center>
   <iframe type="text/javascript" src='https://cdnapisec.kaltura.com/p/2375811/embedPlaykitJs/uiconf_id/52883092?iframeembed=true&entry_id=1_7kh033i4' style="width: 960px; height: 395px" allowfullscreen webkitallowfullscreen mozAllowFullScreen allow="autoplay *; fullscreen *; encrypted-media *" frameborder="0" title="LinkedBag add method and toArray method"></iframe> 
   </center>

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

.. avembed:: Exercises/SWDesignAndDataStructs/LinkedBagCheckpoint1Summ.html ka
   :long_name: Checkpoint 1

.. _LinkedBagTest: 

Interactive: ExLinkedBagJUnit Demonstration
---------------------------------------------------

.. admonition:: Follow Along, Practice and Explore

  Download to run and explore the corresponding project from the video on your own in eclipse. The project CS2-Support is required for the sample project above.  It is also used in your course projects. To download the CS2-Support you must first complete the configuration steps for your first lab. You will then be able to download it via eclipse using the blue down arrow icon or using the Project Menu and selecting "Download Assignment..."


   .. raw:: html

      <a href="https://courses.cs.vt.edu/cs2114/examples/eclipse/exLinkedBagsWithJUnit.zip"  target="_blank">
      <img src="https://courses.cs.vt.edu/cs2114/opendsa/icons/icons8-java60.png" alt=""  width="32" height="32">
      exLinkedBagsWithJUnit.zip</img>
      </a>


.. raw:: html

    <center>
    <iframe type="text/javascript" src='https://cdnapisec.kaltura.com/p/2375811/embedPlaykitJs/uiconf_id/52883092?iframeembed=true&entry_id=1_y9dkjp2z' style="width: 960px; height: 395px" allowfullscreen webkitallowfullscreen mozAllowFullScreen allow="autoplay *; fullscreen *; encrypted-media *" frameborder="0" title="ExLinkedBagJUnit Demonstration"></iframe> 
    </center>

.. _LinkedBagContains: 

Interactive: LinkedBag getFrequencyOf() and contains()
--------------------------------------------------------------

.. 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/SWDesignAndDataStructs/course-notes/LinkedFreqContains.pdf"  target="_blank">
      <img src="https://courses.cs.vt.edu/cs2114/opendsa/icons/projector-screen.png" alt="" width="32" height="32">
      LinkedFreqContains.pdf</img>
      </a>


.. raw:: html

   <center>
   <iframe type="text/javascript" src='https://cdnapisec.kaltura.com/p/2375811/embedPlaykitJs/uiconf_id/52883092?iframeembed=true&entry_id=1_jaeiozal' style="width: 960px; height: 395px" allowfullscreen webkitallowfullscreen mozAllowFullScreen allow="autoplay *; fullscreen *; encrypted-media *" frameborder="0" title="LinkedBag getFrequencyOf method and contains method"></iframe> 
   </center>


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

.. avembed:: Exercises/SWDesignAndDataStructs/LinkedBagCheckpoint2Summ.html ka
   :long_name: Checkpoint 2

.. _LinkedBagRemove: 

Interactive: LinkedBag Removing an item
-----------------------------------------------

.. 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/SWDesignAndDataStructs/course-notes/LinkedRemove.pdf"  target="_blank">
      <img src="https://courses.cs.vt.edu/cs2114/opendsa/icons/projector-screen.png" alt="" width="32" height="32">
      LinkedRemove.pdf</img>
      </a>


.. raw:: html

   <center>
   <iframe type="text/javascript" src='https://cdnapisec.kaltura.com/p/2375811/embedPlaykitJs/uiconf_id/52883092?iframeembed=true&entry_id=1_kps8b356' style="width: 960px; height: 395px" allowfullscreen webkitallowfullscreen mozAllowFullScreen allow="autoplay *; fullscreen *; encrypted-media *" frameborder="0" title="LinkedBag Removing an item"></iframe> 
   </center>


.. admonition:: Tradeoffs of using a linked chain implementation for a bag

    .. list-table:: Pros and Cons of Linked Bags
       :header-rows: 1
    
       * - Pros
         - Cons
       * - Bag can grow in size easily
         - Requires more space than a same-sized array
       * - Adding an entry to the bag is fast
         - Removing a specified entry requires time to locate the entry


Checkpoint 3
------------

.. avembed:: Exercises/SWDesignAndDataStructs/LinkedBagCheckpoint3Summ.html ka
   :long_name: Checkpoint 3


Wrapping up Bags
----------------

As you've seen, Bags are a simple but foundational data structure in Java.
We will continue with other data structures and their unique characteristics,
including opportunities to practice building them, in later modules.

Recall that the objectives for this module were to:

* Name the function and purpose of basic Java data structures
* State key characteristics of Bags in Java
* Build and populate Bags in Java


Programming Practice: LinkedBags
--------------------------------

.. extrtoolembed:: 'Programming Practice: LinkedBags'
   :workout_id: 1911