.. _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 = "Week 3"; ODSA.SETTINGS.BUILD_DATE = "2017-01-30 16:09:20"; ODSA.SETTINGS.BUILD_CMAP = false;JSAV_OPTIONS['lang']='en';JSAV_EXERCISE_OPTIONS['code']='java';</script>


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


.. 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, Stacks, Queues
~~~~~~~~~~~~~~~~~~~~~
   .. odsalink:: AV/List/alistCON.css
   .. odsalink:: AV/List/llistCON.css

   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
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/List/alistInsertCON.js


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
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/List/llist.js
   .. odsascript:: AV/List/llistBadCON.js

Linked List Position (2)
~~~~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: llistBadDelCON ss
      :long_name: Linked List Slideshow 2
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/List/llistBadDelCON.js


Linked List Position (3)
~~~~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: llistInitCON dgm
      :output: show

   |

   .. inlineav:: llistHeaderCON dgm
      :output: show

   .. odsascript:: AV/List/llistInitCON.js
   .. odsascript:: AV/List/llistHeaderCON.js


Linked List Class (1)
~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: llistVarsCON ss
      :long_name: Linked List Variables Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/List/llistVarsCON.js


Linked List Class (2)
~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: llistConsCON ss
      :long_name: Linked List Constructors Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/List/llistConsCON.js


Insertion
~~~~~~~~~
   .. inlineav:: llistInsertCON ss
      :long_name: Linked List Insert Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/List/llistInsertCON.js

Removal
~~~~~~~
   .. inlineav:: llistRemoveCON ss
      :long_name: Linked List Remove Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/List/llistRemoveCON.js

Prev
~~~~
   .. inlineav:: llistOtherCON ss
      :long_name: Linked List Position Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/List/llistOtherCON.js

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
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/List/listFreeCON.js

Doubly Linked Lists
~~~~~~~~~~~~~~~~~~~
   .. odsalink:: DataStructures/DoubleLinkList.css
   .. odsalink:: AV/List/dlistCON.css

   .. inlineav:: dlistDiagramCON dgm
      :output: show

   .. odsascript:: DataStructures/DoubleLinkList.js
   .. odsascript:: AV/List/dlist.js
   .. odsascript:: AV/List/dlistDiagramCON.js


Container Class Design Issues
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   * Storing a record vs. Storing a reference to a record
   * Homogeneity: Allow different record types? Check and block?
   * Deletion: What happens to the record?


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


Doubly Linked Insert
~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: dlistInsertCON ss
      :long_name: Doubly Linked List Insert
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/List/dlistInsertCON.js



Doubly Linked Remove
~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: dlistRemoveCON ss
      :long_name: Doubly Linked List Remove
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/List/dlistRemoveCON.js


Stacks
~~~~~~
   LIFO: Last In, First Out.

   Restricted form of list: Insert and remove only at front of list.

   Notation:

   * Insert: PUSH
   * Remove: POP
   * The accessible element is called TOP.


Stack ADT
~~~~~~~~~
   .. codeinclude:: Lists/Stack
      :tag: Stack



Array-Based Stack (1)
~~~~~~~~~~~~~~~~~~~~~
   Issues:

   * Which end is the top?
   * Where does “top” point to?
   * What are the costs of the operations?


Array-Based Stack (2)
~~~~~~~~~~~~~~~~~~~~~
   .. codeinclude:: Lists/AStack
      :tag: AStack1


Linked Stack
~~~~~~~~~~~~
   .. codeinclude:: Lists/LStack
      :tag: LStack1

   What are the costs of the operations?


   How do space requirements compare to the array-based stack
   implementation?


Queues
~~~~~~
   FIFO: First in, First Out

   Restricted form of list: Insert at one end, remove from the other.

   Notation:

   * Insert: Enqueue
   * Delete: Dequeue
   * First element: Front
   * Last element: Rear


Queue Implementation (1)
~~~~~~~~~~~~~~~~~~~~~~~~
   .. odsalink:: AV/List/aqueueCON.css

   .. inlineav:: aqueueFirstCON ss
      :long_name: Array-based Queue Positions Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: DataStructures/CircularQueue.js
   .. odsascript:: AV/List/aqueueFirstCON.js

Queue Implementation (2)
~~~~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: aqueueDriftCON ss
      :long_name: Array-based Queue Drift Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/List/aqueueDriftCON.js


Queue Implementation (3)
~~~~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: aqueueBadCON ss
      :long_name: Array-based Queue Bad Representation Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/List/aqueueBadCON.js


Circular Queue (1)
~~~~~~~~~~~~~~~~~~
   .. inlineav:: aqueueCircularCON ss
      :long_name: Circular Array-based Queue Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show


   .. odsascript:: AV/List/aqueueCircularCON.js

Circular Queue (2)
~~~~~~~~~~~~~~~~~~
   .. inlineav:: aqueueEmptyCON ss
      :long_name: Empty Circular Array-based Queue Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/List/aqueueEmptyCON.js