“Big O” (Order) of a function is the magnitude of its efficiency (based on the worst efficiency possible as written), consisting of two parts:
Time Complexity: the time taken for the function to run.
Space Complexity: the memory required for a function to run.
Input Size: Represented by n, accounts for the parameters that are taken in by the function.
Units of Measurement for Efficiency:
Time: Milliseconds elapsed during function; operation count during a function; and the most significant or “basic operation” executed within the function.
Memory usage: Algorithm code storage; input data storage; output data storage; and working space required for execution.
Orders of growth: magnitude of efficiency based on size of input n.
Constant: Represented by 1, indicates that efficiency is independent of the value of inputs.
Logarithmic: represented by lgn, indicates decreasing rate in loss of efficiency as n increases.
Linear: represented by n, represents direct proportionality of efficiency to value of n
Linked lists are linear data structures. Data is sequential, however memory is not contiguous (unlike with arrays). Because of this, the number of nodes may be adjusted as needed by [re]assigning their references. A Current variable begins at the head and tracks traversal per Next value (like with a while loop checking reference values).
Anatomy of a node in a linked list:
Data held
Reference to next node in list
Types of linked lists:
Singly linked: unilateral– begins with the head until the last node, which references null
Doubly linked: bilateral– contains references to next and to previous nodes (by using more memory).
Circular: mostly unilateral, but all nodes reference one and are referenced by one in continuous loop with the exception of the tail, which refers to another node already referenced rather than to a null value.
Disadvantages:
slow traversal (O(n))
no for or for-each loops