3.1 Contiguous vs. Linked Data Structures

Arrays

array of 1 element
+--+
|a |
+--+
double the array (2 elements)
+--++--+
|a ||b |
+--++--+
double the array (4 elements)
+--++--++--++--+
|a ||b ||c ||c |
+--++--++--++--+
double the array (8 elements)
+--++--++--++--++--++--++--++--+
|a ||b ||c ||c ||x ||x ||x ||x |
+--++--++--++--++--++--++--++--+
double the array (16 elements)
+--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+
|a ||b ||c ||c ||x ||x ||x ||x || || || || || || || || |
+--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+

Pointers and Linked Structures

Comparison

3.2 Stacks and Queues

3.3 Dictionaries

Unsorted array

3.4 Binary Search Trees

Implementing Binary Search Trees

tree *search_tree(tree *l, item_type x){
if (l == NULL) return(NULL);
if (l->item == x) return(l);
if (x < l->item)
return( search_tree(l->left, x) );
else
return( search_tree(l->right, x) );
}
tree *find_minimum(tree *t) {
tree *min; //pointer to minimum
if (t == NULL) return(NULL);
min = t;
while (min->left != NULL) //Iteratively
min = min->left;
return(min);
}
void traverse_tree(tree *l){ // in-order
if (l != NULL) {
traverse_tree(l->left);
process_item(l->item);
traverse_tree(l->right);
}
}
/* A utility function to insert a new node with given key in BST */
struct node* insert(struct node* node, int key)
{
/* If the tree is empty, return a new node */
if (node == NULL){
node* p = malloc(sizeof(tree)); /* allocate new node */
p->key = key;
p->left = p->right = NULL;
return p;
}

/* Otherwise, recur down the tree */
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);

/* return the (unchanged) node pointer */
return node;
}

How Good Are Binary Search Trees?

3.5 Priority Queues

struct item {
int item;
int priority;
}

3.6 War Story: Stripping Triangulations (Omitted)

3.7 Hashing and Strings

Collision Resolution

Efficient String Matching via Hashing

function RabinKarp(string t[1..n], string p[1..m])
hpattern := hash(p[1..m]); // length = m-1+1 = m
for i from 1 to n-m+1 //e.g. n=5, m=3, 1->n-m+1=>1->3. n-m+1-1+1 = n-m+1 times of hash computations.
hs := hash(t[i..i+m-1]) // length = i+m-1-i+1 = m
if hs = hpattern
if t[i..i+m-1] = p[1..m]
return i
return not found
# Above algorithm reduces string matching to n−m+2 hash value computations (the n−m+1 windows of t, plus one hash of p), plus what should be a very small number of O(m) time verification steps

Software Engineer in Tokyo. Aim to understand computer science very well. LinkedIn: https://www.linkedin.com/in/peng-larry-yang-9a794561/