Unit 1.4 · about 5 h
91 / 324Arrays, strings, locality and linked structures
Arrays and linked nodes are the two physical layouts everything else composes. Index discipline and pointer discipline learned here prevent the off-by-one and aliasing bugs of every later unit.
- explain
- implement
You can now
- Implement in-place array routines (compaction, back-merge, rotation) with exact index bounds.
- Implement singly linked insert, delete and traversal with a sentinel, and state the pointer invariant.
- Explain list over-allocation and string-builder costs from CPython behavior and your own measurements, and separate Python locality from C++ cache numbers.
Covers
- Arrays, strings, contiguous layout and locality
- Singly and doubly linked structures and pointer invariants
Study, in this order
6 steps
- Arrays: static, dynamic, multi-dimensionalDSA Handbook - Foundations and linear patterns
What an array actually is; The cost model you can quote in an interview; Three problems, three techniques (LC 88 back-merge, LC 27 two-pointer compaction, LC 189 three-reverse rotation)
- Strings: encoding, immutability, buildersDSA Handbook - Foundations and linear patterns
The \(O(n^2)\) concatenation trap with the refcount-1 in-place note; the parts-plus-join builder idiom
Depth · The chapter's 2.2x figure is a CPython 3.11 micro-benchmark. Rerun the comparison on 3.13 yourself (see Reproduce) instead of quoting it.
- Linked list fundamentalsDSA Handbook - Foundations and linear patterns
The four pointer primitives; The sentinel; Designing the list: LC 707 (
get,addAtHead,addAtTail,addAtIndex,deleteAtIndex); When the design changes (doubly-linked insert) - CPython list over-allocationCPython source - list and dict objects
list_resize: the(newsize + (newsize >> 3) + 6) & ~3formula with the growth-pattern comment (0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...)Depth · Read the function and its comment only; the rest of the file is later.
- Cache LinesAlgorithmica - memory and data layout
64-byte cache lines and the strided-loop demonstration (stride 1 against stride 16)
Depth · These are C++ measurements on contiguous arrays. Do not quote them for Python lists; your Reproduce shows why.
- External Memory ModelAlgorithmica - memory and data layout
Cache-Aware Model and Array Scan: why a scan is the cheapest access pattern
Depth · Read for the model only; the numbers are C++ measurements.
Focus on
- In-place means bounded extra space with exact bounds: merge from the back, compact with a write pointer, rotate with three reverses.
- The sentinel (dummy head) removes the empty-head special case; every rewiring snapshots
nextbefore clobbering. - CPython lists over-allocate geometrically (about 1.125x) but store pointers: consecutive elements are separate heap objects, so stride effects differ from C arrays.
- Unaliased local string accumulation grows in place on CPython 3.13 and runs near
joinspeed; one extra reference to the running string restores the quadratic copying.
Reproduce closed-book
parts = [str(i) for i in range(30000)] and time three functions on Python 3.13.14 (12th Gen Intel Core i9-12900K): s = s + p in a loop where s is the only reference (about 0.5 ms), the same loop with t = s taken before each concatenation (about 0.09 s, quadratic copying), and ''.join(parts) (about 0.1 ms). The aliased loop is over 100x slower. Then, without notes, implement remove-element compaction plus sentinel-based insert-after and delete-after.Traps
- Iterating to capacity instead of length, and front insertion or
pop(0)in a loop: growth amortizes the tail only, so \(n\) front inserts cost \(\Theta(n^2)\). - Quoting the handbook's 2.2x concat figure or Algorithmica's stride numbers as your Python behavior. Both were measured elsewhere; rerun on 3.13.
- Rewiring
curr.nextbefore saving it: the rest of the list is gone.
Practice
Implement the read/write two-pointer compaction in place with \(O(1)\) extra memory. State the write-pointer invariant in a comment.
After submitting, compare against the handbook arrays section LC 27: Remove Element, the two-pointer compaction.
LeetCode 707: Design Linked List
Implement get, addAtHead, addAtTail, addAtIndex and deleteAtIndex with a sentinel node. Test empty-list, head and tail-index cases.
After submitting, compare against the handbook linked-list-fundamentals sections The sentinel and Designing the list: LC 707.
Self-test
-
Why does Merge Sorted Array merge from the back?
The tail of the destination is free buffer. Writing forwards would overwrite unmerged elements; writing backwards only touches buffer cells or already-placed cells. -
Argue the three-reverse rotation correct.
Reversing everything puts each element at its rotated mirror position; reversing the first \(k\) and the rest then fixes each segment's internal order. -
getsizeofsteps land at lengths 1, 5, 9 and 17. What capacities are those?With a 56-byte header and 8 bytes per slot, 88, 120, 184 and 248 bytes mean 4, 8, 16 and 24 slots, matching the 0, 4, 8, 16, 24 pattern. -
Consecutive list elements sit 32 bytes apart by
id(). Why does the stride-16 demo not apply?The list stores pointers; elements are separate heap objects. Striding the list still chases pointers, unlike striding a C array of inline values.
Completion criterion
Stop when
Both solutions are accepted, your concat rerun reproduces the 100x gap, and you can draw the pointer state before and after each rewiring.
Mark passed, then open 1.5 Only mark this when you can do it without notes.Leads to
- 1.5 Hash tables: collisions, load factor, resizing and tombstones Hash tables layer probing and chaining over the array layout.
- 1.6 Stacks, queues, deques and monotone structures Stacks and queues pick their backing layout from this unit.
Comes after
- 1.1 Cost models, asymptotic notation and casesArrays are the first structure whose operations you cost with this vocabulary.
Resources for this unit
- DSA Handbook - Foundations and linear patterns Study Part 0, Part 1, Part 3 and Part 4 in order, plus the Part 5 Linked-list fundamentals chapter. Use the routing-rule pages for arrays versus lists, map choice, stack versus queue, two pointers, sliding windows and prefix methods before seeing solved code.
- Algorithmica - memory and data layout Read the memory hierarchy, cache and complexity-model chapters, then measure one contiguous-versus-linked and one hash-versus-ordered workload crossover.
- CPython source - list and dict objects Read
list_resizeinObjects/listobject.cfor the growth formula and pattern comment, and theUSABLE_FRACTIONdefinition, perturbation-probing comment and dummy-entry handling inObjects/dictobject.c. Read the cited functions and comments only.
Also in this section
- AlgoMaster DSA - linear structures slice Attempt Design HashMap, Longest Substring Without Repeating Characters and Sliding Window Maximum cold. Hide tags, state the invariant first, and add randomized operation histories to Design HashMap.
- MIT 6.042J - asymptotics and invariants Use the asymptotics, state-machine invariants and proof-method readings when a cost or correctness argument is weak. Solve only the matching problems.
- Algorithms lecture notes - amortized analysis and hashing Use note 9 Amortized Analysis for the summation, taxation, charging and potential-function proofs, and note 5 Hashing for chaining, universal hashing and open-addressing analysis, when the handbook treatment is too brief for a proof.
- NeetCode - unseen linear problems Use only for two tag-hidden transfer problems after the AlgoMaster slice. Do not start another full roadmap or watch a solution before the attempt is complete.
- Hypothesis documentation - Quickstart and stateful testing Follow Quickstart for
@givenstrategies and the pytest combination, Configuring test settings formax_examplesandderandomize, then Rule-based state machines (rule,precondition,invariant,run_state_machine_as_test) for randomized operation histories againstdictanddequeoracles.