1 of 59

This is CS50

2 of 59

Think.

Pair.

Share.

3 of 59

  • What are the key trade-offs between data structures we should consider in decisions about which to use?
  • What are some of the primary operations we should know how to do on a linked list?
  • How can we build our very own hash table?

4 of 59

Scenario

5 of 59

Imagine you work for a company that has created a digital assistant running on a mobile device.

6 of 59

Customer reports indicate people have trouble activating the assistant with its "wake word".

7 of 59

Your team has been asked to ensure the voice assistant can be awoken with a greater variety of words.

8 of 59

What data structure would you propose the team build to store these words?

9 of 59

"Hi!"

NULL

"Hey!"

list

Linked List

10 of 59

…

H

I

J

K

L

…

"Hey!"

"Hello!"

"Lo there!"

Hash Table

11 of 59

H

E

L

L

O

Y

Trie

P

12 of 59

Nodes

13 of 59

typedef struct node

{

string phrase;

struct node *next;

}

node;

14 of 59

typedef struct node

{

string phrase;

struct node *next;

}

node;

node

15 of 59

typedef struct node

{

string phrase;

struct node *next;

}

node;

phrase

node

16 of 59

typedef struct node

{

string phrase;

struct node *next;

}

node;

phrase

"Hi!"

node

17 of 59

typedef struct node

{

string phrase;

struct node *next;

}

node;

phrase

"Bye!"

node

18 of 59

typedef struct node

{

string phrase;

struct node *next;

}

node;

phrase

next

node

19 of 59

typedef struct node

{

string phrase;

struct node *next;

}

node;

phrase

0x123

next

node

20 of 59

typedef struct node

{

string phrase;

struct node *next;

}

node;

phrase

0x456

next

node

21 of 59

typedef struct node

{

string phrase;

struct node *next;

}

node;

phrase

next

node

22 of 59

Creating a Linked List

23 of 59

node *list = NULL;

list

24 of 59

node *n = malloc(sizeof(node));

list

25 of 59

node *n = malloc(sizeof(node));

list

26 of 59

node *n = malloc(sizeof(node));

n

list

27 of 59

node *n = malloc(sizeof(node));

n->phrase = "Hi!";

"Hi!"

n

list

28 of 59

node *n = malloc(sizeof(node));

n->phrase = "Hi!";

n->next = NULL;

"Hi!"

NULL

n

list

29 of 59

list = n;

"Hi!"

NULL

n

list

30 of 59

list = n;

"Hi!"

NULL

n

list

31 of 59

Inserting Nodes

32 of 59

n = malloc(sizeof(node));

"Hi!"

NULL

list

33 of 59

n = malloc(sizeof(node));

"Hi!"

NULL

list

n

34 of 59

n = malloc(sizeof(node));

n->phrase = "Hey!";

"Hi!"

NULL

list

"Hey!"

n

35 of 59

n = malloc(sizeof(node));

n->phrase = "Hey!";

n->next = list;

"Hi!"

NULL

list

"Hey!"

n

36 of 59

list = n;

"Hi!"

NULL

"Hey!"

list

n

37 of 59

list = n;

"Hi!"

NULL

"Hey!"

list

38 of 59

Inserting into a Linked List

Download and open list.c.

Find the first TODO.

Starting below that TODO, implement code to add a node to the linked list. Ensure that list always points to the head of the linked list. Also ensure your new node contains a phrase.

39 of 59

Unloading Nodes

40 of 59

"Hi!"

NULL

"Hey!"

list

41 of 59

free(list);

"Hi!"

NULL

"Hey!"

list

42 of 59

free(list);

"Hi!"

NULL

"Hey!"

list

43 of 59

"Hi!"

NULL

"Hey!"

list

44 of 59

node *ptr = list->next;

"Hi!"

NULL

"Hey!"

list

ptr

45 of 59

free(list);

"Hi!"

NULL

"Hey!"

ptr

list

46 of 59

list = ptr;

"Hi!"

NULL

"Hey!"

ptr

list

47 of 59

list = ptr;

"Hi!"

NULL

ptr

list

48 of 59

ptr = list->next;

"Hi!"

NULL

ptr

list

49 of 59

ptr = list->next;

"Hi!"

NULL

list

50 of 59

free(list);

"Hi!"

NULL

list

51 of 59

list = ptr;

list

52 of 59

Unloading a Linked List

Open the same list.c file.

Find the unload function below main.

Implement unload such that all nodes in the linked list are free'd when the function is called. Return true when successful.

53 of 59

"Hey!"

"Hello!"

"Lo there!"

54 of 59

…

H

I

J

K

L

…

"Hey!"

"Hello!"

"Lo there!"

55 of 59

…

…

7

H

8

I

9

J

10

K

11

L

…

…

"Hey!"

"Hello!"

"Lo there!"

56 of 59

Hash Function

"Hey!"

7

57 of 59

Hashing

Download and open table.c.

Complete hash to return a number, 0–25, depending on the first character in the word.

58 of 59

A good hash function…

Always gives you the same value for the same input

Produces an even distribution across buckets

Uses all buckets

​

59 of 59

This was CS50