.. _Lists:

.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "Lists";ODSA.SETTINGS.MODULE_LONG_NAME = "Lists";ODSA.SETTINGS.MODULE_CHAPTER = "Slides"; ODSA.SETTINGS.BUILD_DATE = "2019-04-01 22:21:50"; ODSA.SETTINGS.BUILD_CMAP = true;JSAV_OPTIONS['lang']='en';JSAV_EXERCISE_OPTIONS['code']='java';</script>


.. |--| unicode:: U+2013   .. en dash
.. |---| unicode:: U+2014  .. em dash, trimming surrounding whitespace
   :trim:



.. odsalink:: AV/List/alistCON.css

.. odsalink:: AV/List/llistCON.css

.. odsalink:: DataStructures/DoubleLinkList.css

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

.. avmetadata::
   :author: Cliff Shaffer


=====
Lists
=====

Lists
-----

Lists
~~~~~
   A list is a finite, ordered **sequence** of data items.

   Important concept: List elements have a **position**.

   Notation: :math:`<a_0, a_1, …, a_{n-1}>`

   What operations should we implement?


List Implementation Concepts
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   Our list implementation will support the concept of a
   **current position**.

   Operations will act relative to the current position.

   :math:`<20, 23\ |\ 12, 15>`

List ADT (1)
~~~~~~~~~~~~
   .. codeinclude:: Lists/List
      :tag: ListADT1


List ADT (2)
~~~~~~~~~~~~
   .. codeinclude:: Lists/List
      :tag: ListADT2


List ADT (3)
~~~~~~~~~~~~
   .. codeinclude:: Lists/List
      :tag: ListADT3


List ADT Examples
~~~~~~~~~~~~~~~~~
   List: :math:`<12\ |\ 32, 15>`

   L.insert(99);

   Result: :math:`<12\ |\ 99, 32, 15>`

   Iterate through the whole list:

   .. codeinclude:: Lists/ListTest
      :tag: listiter


List Find Function
~~~~~~~~~~~~~~~~~~
   .. codeinclude:: Lists/ListTest
      :tag: listfind


Array-Based List Class (1)
~~~~~~~~~~~~~~~~~~~~~~~~~~
   .. codeinclude:: Lists/AList
      :tag: AListVars

   .. codeinclude:: Lists/AList
      :tag: Constructors


Array-Based List Insert
~~~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: alistInsertCON ss
      :long_name: Array-based List Insertion Slideshow
      :output: show


Link Class
~~~~~~~~~~
   Dynamic allocation of new list elements.

   .. codeinclude:: Lists/Link
      :tag: Link


Linked List Position (1)
~~~~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: llistBadCON ss
      :long_name: Linked List Slideshow 1
      :output: show


Linked List Position (2)
~~~~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: llistBadDelCON ss
      :long_name: Linked List Slideshow 2
      :output: show


Linked List Position (3)
~~~~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: llistInitCON dgm
      :align: center

   |

   .. inlineav:: llistHeaderCON dgm
      :align: center


Linked List Class (1)
~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: llistVarsCON ss
      :long_name: Linked List Variables Slideshow
      :output: show


Linked List Class (2)
~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: llistConsCON ss
      :long_name: Linked List Constructors Slideshow
      :output: show


Insertion
~~~~~~~~~
   .. inlineav:: llistInsertCON ss
      :long_name: Linked List Insert Slideshow
      :output: show


Removal
~~~~~~~
   .. inlineav:: llistRemoveCON ss
      :long_name: Linked List Remove Slideshow
      :output: show


Prev
~~~~
   .. inlineav:: llistOtherCON ss
      :long_name: Linked List Position Slideshow
      :output: show

Overhead
~~~~~~~~
   * Container classes store elements. Those take space.

   * Container classes also store additional space to organize the
     elements.

      * This is called **overhead**

   * The **overhead fraction** is: overhead/total space


Comparison of Implementations
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   * Array-Based Lists:
      * Insertion and deletion are :math:`\Theta(n)`.
      * Prev and direct access are :math:`\Theta(1)`.
      * Array must be allocated in advance.
      * No overhead if all array positions are full.

   * Linked Lists:
      * Insertion and deletion are :math:`\Theta(1)`.
      * Prev and direct access are :math:`\Theta(n)`.
      * Space grows with number of elements.
      * Every element requires overhead.


Space Comparison
~~~~~~~~~~~~~~~~
   "Break-even" point:

   :math:`DE = n(P + E)`

   :math:`n = \frac{DE}{P + E}`

   E: Space for data value.

   P: Space for pointer.

   D: Number of elements in array.


Space Example
~~~~~~~~~~~~~
   * Array-based list: Overhead is one pointer (8 bytes) per position in
     array – whether used or not.

   * Linked list: Overhead is two pointers per link node
     one to the element, one to the next link

   * Data is the same for both.

   * When is the space the same?

     * When the array is half full


Freelist
~~~~~~~~
   .. odsalink:: AV/List/listFreeCON.css

   System new and garbage collection are slow.

   * Add freelist support to the Link class.

   .. inlineav:: listFreeCON ss
      :long_name: Freelist Slideshow 1
      :output: show


Doubly Linked Lists
~~~~~~~~~~~~~~~~~~~
   .. inlineav:: dlistDiagramCON dgm
      :output: show


Doubly Linked Node (1)
~~~~~~~~~~~~~~~~~~~~~~
   .. codeinclude:: Lists/DLink
      :tag: DLink


Doubly Linked Insert
~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: dlistInsertCON ss
      :long_name: Doubly Linked List Insert
      :output: show   


Doubly Linked Remove
~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: dlistRemoveCON ss
      :long_name: Doubly Linked List Remove
      :output: show

.. odsascript:: AV/List/alistInsertCON.js
.. odsascript:: AV/List/llist.js
.. odsascript:: AV/List/llistBadCON.js
.. odsascript:: AV/List/llistBadDelCON.js
.. odsascript:: AV/List/llistInitCON.js
.. odsascript:: AV/List/llistHeaderCON.js
.. odsascript:: AV/List/llistVarsCON.js
.. odsascript:: AV/List/llistConsCON.js
.. odsascript:: AV/List/llistInsertCON.js
.. odsascript:: AV/List/llistRemoveCON.js
.. odsascript:: AV/List/llistOtherCON.js
.. odsascript:: AV/List/listFreeCON.js
.. odsascript:: DataStructures/DoubleLinkList.js
.. odsascript:: AV/List/dlist.js
.. odsascript:: AV/List/dlistDiagramCON.js
.. odsascript:: AV/List/dlistInsertCON.js
.. odsascript:: AV/List/dlistRemoveCON.js