Data structures and Algorithms

Linked Lists, or Lists

Can implement in an array, which has expensive insert and delete operations, or through pointers and structs, which need double the space.

Implementation In C - Array

required max size, wastes considerable space
constant write operation if in space
Implementation

Implementation In C - Pointers

cheaper to dynamically move, add, delete items, as link to next item changed simply.
space needed for extra pointer field for each item
Implementation

Stacks and Queues

Stacks

Data Structure that can be built using a linked list, but limited in operations.
Data is added and removed from the top of the list only. So only a head pointer needed.
Used by OS, compilers etc.
Implementation

Queues

Data Structure using a list, with items added from one end, and removed from the other.
So two pointers to the list needed, head and tail.
Used by OS schedulers etc.
Implementation

Recursion

Factorial Example

Why is 0! = 1?
Well, because it is defined so, firstly.
Secondly, a factorial can be thought of as the number of permutations (unique orderings of elements) for a set with n elements
And basically, because there is still one way to represent a set/sequence/permutation of 0!, that is an empty set. That is, can be represented in one way. So the answer is still one.
This definition also works for the combinations formula (combination is a grouping of elements of a set without regard to order.) Reference
Definition:


          n! => 

            n! * (n-1)! for n > 1 

            1 for n == 0

Towers of Hanaoi

Reference

Home Writing Games Music Dev