Data Structures

What this covers

• Separating an abstract data type (list, map, set, priority queue) from its implementations, and comparing the operation costs of each backing structure
• Pointer and reference manipulation in singly, doubly, and circular linked lists: insertion at a node, deletion with a predecessor, dummy heads, and the off-by-one errors that break them
• Hash tables: hash function properties, load factor, separate chaining versus open addressing with linear or quadratic probing, and why deletion needs tombstones
• Binary search trees: insert, search, delete with two children, in-order traversal, degeneration to a linked list, and how AVL or red-black rotations restore height balance
• Binary heaps as arrays: sift-up, sift-down, index arithmetic for parent and child, heapify, and priority queue operations
• Amortised analysis of dynamic array growth, plus adjacency list versus adjacency matrix trade-offs for sparse and dense graphs

Where learners get stuck

Assuming a linked list is faster than an array because insertion is O(1)

The O(1) figure assumes you already hold a reference to the node. Students quote the insertion cost without noticing that reaching the position took an O(n) traversal, so many list operations are no better than an array's.

Treating a binary search tree's O(log n) as guaranteed

Textbook diagrams show tidy balanced trees, so the average case gets memorised as the only case. Inserting sorted data produces a height-n chain, which is why balanced variants exist at all — a point that only lands once you trace the degenerate insert yourself.

Mutating nodes through an aliased reference and expecting the original to be unchanged

In Java and Python, an assignment like node = node.next rebinds a local variable, while node.next = x edits the shared object. The two lines look symmetrical, so students write list-reversal and deletion code that either loses the tail or corrupts the chain.

What a session looks like

Sessions are one-on-one voice conversations with an AI tutor. A typical session starts with you describing the structure or assignment you are stuck on, then Evelyn walks you through tracing an operation node by node or index by index, stopping to ask what the pointers look like after each step. You can talk through your own code line by line, work out the cost of a proposed design before writing it, or be given small structures to analyse aloud. Because it is voice-led, the emphasis is on stating invariants and reasoning out loud rather than reading code silently.

Helpful to know first

• One semester of programming in Java, Python, C, or C++, including loops, functions, and arrays
• Classes and objects, or structs and pointers, depending on your course language
• Comfort with recursion, including writing a recursive function and reading its call stack
• Basic big-O notation: recognising O(1), O(log n), O(n), and O(n log n)

Questions

How is a data structures course different from an algorithms course?

Data structures centres on how collections are represented and what each operation costs — building a hash table, balancing a tree, wiring up linked nodes. An algorithms course takes those structures as given and studies problem-solving techniques such as sorting, greedy methods, dynamic programming, and graph traversal, with formal proofs of correctness and running time. There is overlap in big-O analysis; the sibling Algorithms topic covers that side.

Does the tutoring use Java, Python, or C++?

Whichever your course uses. Say so at the start of the session and the discussion of references, memory, and generics will follow that language's conventions — for instance, manual node allocation in C++ versus garbage-collected references in Java.

Can it help me debug my linked list or BST assignment?

Yes, by talking through it. You can read out or describe your code and the failing case, and the session works toward finding which pointer assignment or base case is wrong. It is guided debugging rather than being handed a corrected file, so bring the assignment you are working on.

I can code the structures but I freeze when asked which one to use. Can that be practised?

That is a common gap and it responds to drilling. Sessions can pose scenarios — a workload with frequent lookups by key, or one needing the smallest element repeatedly — and ask you to justify a structure from the operation costs, which is the same reasoning exams and interviews test.