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
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.
