Skip to content

CMSC 14300: Practice Set 6 - Linked Lists and Hash Tables

Practice for the material in Week 5: self-referential nodes and the linked-list traversal/pointer surgery from Lecture 9, and the hash tables from Lecture 10 - a hash function, bucket indices, and separate chaining. None of these repeats a lecture or homework exercise; together they drill the new moves - rewiring next pointers, keeping a list ordered, turning a key into a bucket, and storing keyed data in an array of chains. This is good preparation for the next quiz.

Work in a fresh directory and compile everything with warnings on. Some problems need <stdlib.h> (for malloc/free) and <string.h> (for strlen/strcpy/strcmp):

mkdir -p ~/cmsc14300/pset06 && cd ~/cmsc14300/pset06
clang -Wall -Wextra -std=c17 problem1.c -o problem1

Keep last week's rules in view: a self-referential struct keeps its tag, you save next before you free a node, and every malloc still has exactly one free. Problems 1 and 2 use the linked-list node; problems 3 to 5 use hashing.

struct node { int data; struct node *next; };
typedef struct node node_t;

Problem 1 - Reverse a linked list

Write a function that reverses a linked list in place and returns the new head. Nothing is copied and no new nodes are allocated - you only rewire the existing next pointers.

node_t *reverse(node_t *head);

before: 1 -> 2 -> 3 -> NULL
after:  3 -> 2 -> 1 -> NULL
  • Walk the list with three pointers: prev (starts NULL), cur (starts head), and a saved next. Each step: save next = cur->next, flip cur->next = prev, then advance prev = cur and cur = next. When cur is NULL, prev is the new head - return it.
  • Build a small list with push_front (from Lecture 9), print it, reverse it, print again, then free it.
  • Check your understanding: why must you save cur->next into a local before writing cur->next = prev? What would break if you did not?

Problem 2 - Keep a list sorted (ordered insert)

Write insert_sorted, which inserts a value into a list that is already in ascending order so that the list stays ascending. It returns the (possibly new) head. Building a list entirely with insert_sorted produces a sorted list.

node_t *insert_sorted(node_t *head, int value);

insert 3, 1, 4, 1, 5 -> 1 -> 1 -> 3 -> 4 -> 5 -> NULL
  • Make the new node first. If the list is empty or the new value belongs before the head (value <= head->data), it becomes the new head - point its next at the old head and return it.
  • Otherwise walk with a prev/cur pair until cur is NULL or cur->data >= value, then splice the new node between prev and cur (new->next = cur; prev->next = new;).
  • Read integers in a loop and insert_sorted each one; print the list at the end and confirm it is sorted. Free it when done.
  • Check your understanding: which two cases does the prev == NULL (insert at the head) branch cover that the splice branch does not?

Problem 3 - How evenly does the hash spread? (bucket histogram)

A hash table is only fast when keys spread across the buckets. Write a function that hashes a set of usernames into nbuckets and prints how many land in each bucket - the shape of the load. You do not need a full table for this, just the hash and a count per bucket.

unsigned long hash_string(const char *key);          /* djb2, as in Lecture 10 */
void bucket_histogram(const char *names[], int n, int nbuckets);

nbuckets = 4
bucket 0: 2
bucket 1: 1
bucket 2: 3
bucket 3: 0
  • Make an int counts[nbuckets] (a dynamic array, or a fixed one for a known size), zero it, then for each name do counts[hash_string(name) % nbuckets]++. Print each bucket's count.
  • Try the same names with nbuckets = 1 and with a larger nbuckets. With one bucket every name collides (a single count of n); with more buckets the counts spread out.
  • Check your understanding: if one bucket's count is much larger than the others, what does that do to lookup time for the keys in that bucket, and why?

Problem 4 - A small price lookup (string keys, int values)

Build a hash table that maps item names to prices in cents, then answer a series of lookup queries, printing not found for a missing item. Reuse your Lecture 10 ht_create, ht_put, ht_get, and ht_free (types repeated below for convenience).

struct entry { char *key; int value; struct entry *next; };
typedef struct entry entry_t;

struct hash_table { entry_t **buckets; int nbuckets; };
typedef struct hash_table hash_table_t;

apple  -> 40
banana -> 25
cherry -> not found
  • In main, ht_put a handful of items (for example "apple" 40, "banana" 25, "date" 90), then run several ht_get queries and print each result, using the found/not-found flag to print not found for a miss.
  • Put one item twice with a new price and confirm the lookup returns the updated price - the table maps each key to exactly one value.
  • Free the whole table at the end and confirm it is valgrind-clean.
  • Check your understanding: why does ht_get return a found/not-found flag through the return value and hand the price back through an out-parameter, instead of just returning the price?

Problem 5 - Have I seen this before? (a hash set)

Detect duplicate IDs in a stream. A hash set stores keys with no values: all you ask is "is this key already here?" Use a hash table whose entries hold only a key, and report each ID the first time it repeats.

int  set_contains(hash_table_t *set, const char *key);   /* 1 if present, else 0 */
void set_add(hash_table_t *set, const char *key);        /* add if not already present */

ids: a7 b2 a7 c9 b2 a7
duplicate: a7
duplicate: b2
duplicate: a7
  • set_contains hashes to the bucket and walks the chain with strcmp, returning 1 on a match. set_add does nothing if the key is already present; otherwise it push_fronts a new entry that owns a copy of the key (there is no value to store).
  • For each incoming ID: if set_contains says it is already there, print it as a duplicate; otherwise set_add it. Free the set at the end.
  • Check your understanding: a hash set and the price table from Problem 4 use the same chaining machinery. What is the one field an entry no longer needs when the structure is a set rather than a map?

Self-check

You're ready for the upcoming quiz material if you can, without looking it up:

  • Draw a linked list as boxes and arrows, and write the walk-to-NULL traversal loop from memory. Say why a self-referential node must keep its struct tag.
  • Rewire next pointers to insert at the head, insert in sorted order, and reverse a list - and say why each still returns the (possibly new) head.
  • Free a chain of nodes without a use-after-free, explaining why you save next before you free.
  • Turn a string key into a bucket index with a hash function and % nbuckets, and say why the hash must be unsigned.
  • Explain what a collision is, why it is unavoidable, and how separate chaining (an array of linked lists) resolves it.
  • Look up, insert-or-update, and free a string-keyed hash table: compare keys with strcmp (never ==), give each entry an owned copy of its key, and free every key and entry plus the bucket array. Say what the load factor is and when a hash table degrades to O(n).