Concerning the survey from last class #
The differences between an array and a linked list:
- Access: arrays can access an spot instantly, linked lists need to iterate from the head until they reach the target.
- Size: arrays are fixed in size, linked lists can become bigger or smaller
Stacks can be implemented using a linked list or an array. FILO
Queues can be implemented using a linked list or a circular array. FIFO
Recursion #
Recursive functions must have a base case, otherwise you will get an infinite loop!
- f1 has no base case
- f2 doesn’t reduce the problem to the base case (no n - 1)
- f3 needs to check the base case first
- f4 recursive call is infinite when n > 0
Algorithm analysis #
