**************************
Linked-List Data Structure
**************************
A linked-list is a sequential data structure implemented as linked nodes. Each
node typically contains one or more values and one or more links to neighboring
nodes. The term **link** means pointers pointing from one node to another.

.. graphviz::
  :caption: a minimal linked-list

  digraph ll {
      rankdir=LR;
      node [shape=record];
      head [label="head"];
      a [label="{ <data> 12 | <ref>  }", width=1.2];
      b [label="{ <data> 99 | <ref>  }"];
      c [label="{ <data> 37 | <ref>  }"];
      head:e -> a:data    [arrowhead=vee, arrowtail=none, dir=both, tailclip=false];
      a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
      b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
  }

Characteristics
===============
+ A data structure based on linked nodes
+ Nodes are linked together by links
+ Logically contiguous, physically non-contiguous
+ Advantages

  * Dynamic size
  * Ease of insertion/deletion
  * Not requiring contiguous memory
  * Sequential access

+ Limitations

  * Inefficient random access
  * Extra memory space

Implementation Variations
=========================
+ Minimal implementation: a head pointer; singly-linked
+ Ideal implementation: a head pointer, a tail pointer; a size/count instance
  variable; doubly-linked
+ Reference pointers

  * head pointer
  * tail pointer

+ Number of links per node

  * singly-linked - a pointer to next node
  * doubly-linked - pointers to previous and next nodes

+ Terminal node handling (FYI)

  * cyclic - link(s) connecting the first and last nodes; not useful
  * acyclic

+ Dummy node before the first node (FYI)

  * simplifies empty list and first node handling
  * complicates other operations
  * not useful

Behaviors
=========
+ Insertion

  * at the beginning
  * at the end
  * at a specified position (by value, by index)

+ Removal

  * at the beginning
  * at the end
  * at a specified position (by value, by index)

C++ Implementation Details
==========================
+ Classes

  * linked-list class

    - head pointer
    - tail pointer
    - size/count instance variable

  * node class/struct

    - Option 1: top-level class, not nested (preferred most of the time)
    - Option 2: nested class/struct (better information hiding)

+ Use class templates for generalization

  * type of data stored in nodes can be parameterized
  * make a header only module

+ Insert before a given node

  * cannot handle insertion after the last node

+ Append
+ Remove

Time Complexity
===============
+ Based on the **Ideal Implementation** (head pointer, tail pointer, size/count
  instance variable; doubly-linked)
+ Search by value :math:`\Theta(n)`
+ Indexing (access kth element) :math:`\Theta(n)`
+ Insert :math:`\Theta(1)` (:math:`\Theta(n)` if locate the insertion point
  first)
+ Remove :math:`\Theta(1)` (:math:`\Theta(n)` if locate the removal point
  first)

Pitfalls
========
+ Linked-List is not an ADT. It is a data structure to be used to implement some
  ADTs.
+ Not handling empty list
+ Not handling the first/last element

Linked-list Glossary
====================
.. glossary::

  Linked-List
    A sequential data structure based on linked nodes

  Link
    A pointer pointing to node

  Node (linked-list)
    The base unit linked together to form a linked-list

  Dummy Node (linked-list)
    The empty node added in front of the first node to simplify certain
    linked-list algorithms