Introduction to Computer Science YMT113 · Fall 2026 Assoc. Prof. Ferhat Uçar
07 Algorithms & Memory Monday, November 2, 2026

Data Structures: Linked Lists, Hash Tables and Trees

Now that you can allocate memory, you can build your own structures: linked lists that grow, hash tables that find things in constant time, binary search trees, tries, stacks and queues. And the trade-offs between them.

CS50Week 5 · Data Structures ReadK&R chapter 6.5–6.6; CS50 notes >_ Lab 6: Build a Hash Table

Before class · do this at home

Watch, read, then come

CS50x 2026 · Week 5: Data Structures by David J. Malan. Watch the lecture on YouTube (you are also enrolled on edX), read the notes, skim the slides. Our lecture builds on it instead of repeating it.

  • Watch the lecture with paper: draw every linked-list operation as boxes and arrows.
  • Midterm is next week. Start your review sheet: one page per week, weeks 2–7.

Learning objectives

By the end of this week you can:

  • 1 Explain why arrays are fast to index but slow to grow, and how a linked list trades one for the other.
  • 2 Implement a singly linked list in C: node struct, insert at head, search, free.
  • 3 Describe stacks (LIFO) and queues (FIFO) and where each is used.
  • 4 Explain hash tables: hash function, buckets, collisions, chaining, and why lookup is O(1) on average.
  • 5 Describe binary search trees and tries, and their running times.
  • 6 Choose a data structure for a problem by reasoning about its operations.

★ the wow moment

A hash table finds one word among 140 000 in the time it takes an array to check three.

CS50's speller loads a dictionary of 143 091 words. With linear search, checking one word costs up to 143 091 comparisons; with a hash table, about one. A ten-page essay is checked in milliseconds. The trick is a function that turns a word into a bucket number, and it is the same trick behind Python dictionaries, JavaScript objects, database indexes and the cache in your CPU.

Topics

  1. Abstract data types: what operations a structure supports, separate from how it is built. Stacks and queues as the simplest examples.
  2. Arrays revisited: contiguous memory, O(1) indexing, O(n) insertion, realloc.
  3. Linked lists: typedef struct node { int number; struct node *next; } node;, insert at head in O(1), search in O(n), the classic pointer-ordering bug, freeing a list.
  4. Trees: binary search trees, O(log n) when balanced, recursion again.
  5. Hash tables: array of linked lists, the hash function, collisions and load factor, why O(1) on average and O(n) in the worst case.
  6. Tries: a tree keyed by characters, O(k) lookup for a k-letter word, memory cost.
  7. Trade-offs: a table of time and space for each, and the questions to ask before choosing.

Full notes are published before the lecture. The lab, Lab 6: Build a Hash Table, builds a linked list and then a hash table for a word list, with valgrind-clean memory.

In industry

  • Everything is a hash table

    Python dicts, Java HashMaps, Redis, Memcached, DNS caches, Git's object store (keyed by SHA-1). Learning to build one is learning how most of the software world stores things.

  • Linked lists in the kernel

    The Linux scheduler, network buffers and file systems use linked lists and trees, written in exactly the C you write this week.

  • Tries power autocomplete

    Your keyboard's suggestions, search-as-you-type and IP routing tables are tries: each keystroke walks one level down.

  • Stacks and queues are architecture

    The call stack you met in week 5, undo history, browser back buttons: stacks. Print jobs, message queues like Kafka and RabbitMQ, event loops: queues.

Lab 6: Build a Hash Table

From a linked list to a hash table for a word list: insert, search, size, unload, all valgrind-clean, then measure lookup time against a plain array. C · due Fri, Nov 6 · 23:59 · 10 points · opens in week 7 Open lab instructions →

Go deeper

Tags:linked listhash tablehash functioncollisionstackqueuebinary search treetrieabstract data type