Linked Lists
Big O: Analysis of Algorithm Efficiency
Big O notation is used to describe the efficiency of an algorithm or function. There are two evaluations:
- Running Time: The amount of time a function needs to complete
- Memory Space: The amount of memory resources a function uses to store data and instructions
Units of Measurement
Quantifying Running Time
- The time in milliseconds from the start of a function execution until it ends
- The number of operations that are executed
- The number of basic operations that are executed
Quantifying Memory Space
- The amount of space needed to hold the code for the algorithm
- The amount of space needed to hold the input data
- The amount of space needed for the output data
- The amount of space needed to hold working space during the calculation
Big Omega (Best Case)
This notation describes the Best Case for a given algorithm. The Order of Growth used represents the lower bounds of Time and Space.
The efficiency for the best possible input of size n.
This case runs the quickest for all possible inputs of n. In the case of sorting, this assumes that values are sorted, and so searched-for values are easy to find.
Linked Lists
A linked list is a data structure that contains nodes that links to the next node in the list.
Singly - It means that there is only one reference in the list
Doubly - It means that there is only one reference in the list
Node - There are the individual links in the list
Linear Data Structures
Linear data structures are linked lists that follow a sequential order when going through the data points. Non-linear data structures are non sequential and allow you to connect one data point to multiple.
What’s a Linked List Anyway
There are three types of linked lists:
- Singly linked lists
- Doubly linked lists
- Circularly linked lists