Linked Lists

Big O: Analysis of Algorithm Efficiency

Big O describes the complexity at which a code solves a certain problem in terms of its consumption of time and space, consider these 4 keys:

1. Input size (n):
   • Usually proportional to time and space consumption
2. Units of measurement:
   • ms, number of operations and basic operations for time consumption and input, output, code, and running operations size for space consumption
3. Order of growth (as input size changes):
   • Constant
   • Logarithmic
   • Linearithmic
   • Linear
   • Quadratic
   • Cubic
   • Exponential
   • Factorial
4. All cases: worst, best, and average cases

Linked Lists

a linked list is a set of related nodes where each node references another node, either singly when each node reference the next node only, or doubly when each node references both next and previous nodes.

Some common terminology needed are:

• Current: for the current node
• Next: to move to next node
• Head: the first node

When dealing with linked lists it is more convenient to use while loops to iterate through, reaching null means the linked list has finished.

Some pseudo code for checking if a linked list contains a certain value and for adding to a linked list will help clear the idea

Additional resources: link 1,link 2