<aside> 💡 A linked list is a linear data structure in which elements are stored in nodes, each consisting of a value and a reference to the next node.
</aside>
struct llnode {
int item;
struct llnode *next;
};
struct llist {
struct llnode *front;
};
// list_create() creates a new, empty list
// effects: allocates memory: call list_destroy
struct llist *list_create(void) {
struct llist *lst = malloc(sizeof(struct llist));
lst->front = NULL;
return lst;
}
// add_front(i, lst) adds i to the front of lst
// effects: modifies lst
void add_front(int i, struct llist *lst) {
struct llnode *newnode = malloc(sizeof(struct llnode));
newnode->item = i;
newnode->next = lst->front;
lst->front = newnode;
}
// insert(i, slst) inserts i into sorted list slst
// requires: slst is sorted [not asserted]
// effects: modifies slst
// time: O(n), where n is the length of slst
void insert(int i, struct llist *slst) {
if (slst->front == NULL || i < slst->front->item) {
add_front(i, slst);
} else {
// find the node that will be "before" our insert
struct llnode *before = slst->front;
while (before->next && i > before->next->item) {
before = before->next;
}
// now do the insert
struct llnode *newnode = malloc(sizeof(struct llnode));
newnode->item = i;
newnode->next = before->next;
before->next = newnode;
}
}
void free_nodes(struct llnode *node) {
if (node) {
free_nodes(node->next);
free(node);
}
}
void list_destroy(struct llist *lst) {
free_nodes(lst->front);
free(lst);
}
(There’s a lot more functionalities you might want to review…)
Stack → LIFO Queue → FIFO
struct llnode {
int item;
struct llnode *next;
};
struct queue {
struct llnode *front;
struct llnode *back; // <--- NEW
};
At the implementation level, trees are very similar to linked lists. However, each node can link to more than one node
struct bstnode {
int item;
struct bstnode *left;
struct bstnode *right;
int count; // *****NEW
};
<aside> 💡 The dictionary ADT (also called a map, associative array, key-value store or symbol table), is a collection of pairs of keys and values.
</aside>
struct bstnode {
int item; // key
char *value; // additional value (augmentation)
struct bstnode *left;
struct bstnode *right;
};
struct dictionary {
struct bstnode *root;
};
(I don’t think we’ll be working with graphs in this course.. )
https://online.cs.uwaterloo.ca/assets/courseware/v1/64fda2c92298b032bc18287d467d161c/asset-v1:UW+CS136+2023_01+type@asset+block/10-linked-data-show.pdf