Linked Lists

Single linked lists:
   - Each element point to next
   - Start pointer is available
   - To get pointer to last element u need to traverse the whole list. ( circular linked list improve this )
   - If you have a pointer to an elememt and you wamt to get the previous element, you have to traverse the whole list ( double linked list improves this )

Circular linked list
    - last element points to first element.
    - last element pointer is available. And first element can be got from it.

Double linked list
    - Each element points to previous and next elements
    - More storage is needed than single linked list
    - More operations to insert and delete
    - No need to traverse whole array to get previous element
    - Traversing a list is possible in both directions

Algorithms Asymptotic Analysis

In order to compare algorithms, we have several aspects:
   - Execution time
   - Memory consumption
   - Disk storage
   - ... etc

The most important and common aspect usually is Execution time.

To compard algorithms execution times we have two methods:
   - Real measurements
   - Analysis

Commonly we use analysis. Here are the steps:

    1 - get the execution time as function of number of inputs ( ex: n + 5 )
    2 - Get the order, by considering the significant terms when n is very big, and ignoring insignificant terms when n is very big( ex: order n )
    3 - Compare knowing that the orders from fastest to slowest are:

- 1
- log n ( logarithmic )
- n (linear)
- nlog n ( linear logarithmic )
- n to power 2 ( quadratic )
- n to power 3
-  ....
- 2 to power n ( exponential )
- 3 to power n
- .... n!  ( factorial )

Notes:
   - In this analysis we consider the worst case. Example, a for loop which traverses a list to find an element, breaks when find it. It can find it the first element or last. We consider worst case while calculating the order.
    - We does not care about absolute time, we care about how the time increase with number of inputs increase.