Chapter 15 Further Reading: Dynamic Data Structures

Essential References

Textbooks

  • Wirth, Niklaus. Algorithms + Data Structures = Programs (1976). The definitive treatment of data structures in Pascal, by the creator of the language. Chapters on linked lists, stacks, and queues remain clear and relevant. The title itself is Theme 5 of this textbook.

  • Wirth, Niklaus. Algorithms and Data Structures (Oberon version, 2004). Updated version of the above, freely available as a PDF from ETH Zurich. Uses Oberon (a Pascal successor) but the concepts translate directly.

  • Sedgewick, Robert. Algorithms in Pascal (1990). A practical algorithms textbook using Pascal. Excellent coverage of linked structures, sorting with linked lists, and performance analysis.

  • Dale, Nell and Walker, Henry M. Abstract Data Types: Specifications, Implementations, and Applications (1996). Rigorous treatment of stacks, queues, and lists as abstract data types. Good for understanding the separation between interface and implementation.

Classic Papers

  • Dijkstra, Edsger W. "Making a Translator for ALGOL 60" (1961). The original description of what became known as the shunting-yard algorithm for expression parsing. A masterclass in using stacks to solve parsing problems.

  • Knuth, Donald E. The Art of Computer Programming, Volume 1: Fundamental Algorithms (1968). Sections 2.2 (linear lists) and 2.5 (dynamic storage allocation) provide exhaustive, mathematically rigorous treatments of linked data structures.

Deeper Exploration

Data Structure Visualization

  • VisuAlgo (visualgo.net). Interactive visualizations of linked lists, stacks, queues, and many other data structures. Watching animations of insert, delete, and traverse operations builds intuition faster than reading code alone.

  • Data Structure Visualizations (cs.usfca.edu/~galles/visualization). University of San Francisco's collection of interactive data structure animations. Particularly good for understanding pointer manipulation step by step.

Queuing Theory

  • Gross, Donald and Harris, Carl. Fundamentals of Queueing Theory (4th ed., 2008). For readers interested in the mathematical foundations behind Case Study 2. Covers M/M/1 queues, arrival rates, service rates, and the conditions under which queues become unstable.

  • Little's Law. The formula L = lambda * W (average number in system = arrival rate * average wait time) is one of the most elegant results in operations research. Search for "Little's Law explained" for accessible introductions.

Memory Management

  • Wilson, Paul R. "Uniprocessor Garbage Collection Techniques" (1992). While Pascal uses manual memory management, understanding garbage collection (as used in Java, Python, and other languages) provides perspective on what New/Dispose is actually doing under the hood.

  • Free Pascal documentation on heap management (freepascal.org). The heaptrc unit can detect memory leaks in your programs at runtime. Enable it with {$IFDEF DEBUG}{$USES heaptrc}{$ENDIF} and it will report any un-disposed allocations when your program exits.

Practice Problems

  • LeetCode Linked List problems (leetcode.com). Problems 2 (Add Two Numbers), 19 (Remove Nth Node From End), 21 (Merge Two Sorted Lists), 141 (Linked List Cycle), and 206 (Reverse Linked List) are all solvable with the techniques from this chapter. While LeetCode uses C/Java/Python, the algorithms translate directly to Pascal.

  • Project Euler (projecteuler.net). Problems involving large number arithmetic (e.g., Problem 13, Problem 25) can be elegantly solved using linked lists to represent digits of numbers too large for native integer types.

Historical Context

The linked list was invented independently by Allen Newell, Cliff Shaw, and Herbert A. Simon at RAND Corporation in 1955–1956, for their Information Processing Language (IPL). Stacks as a concept date back to Alan Turing's 1945 proposal for the Automatic Computing Engine (ACE), though the term "stack" was not used until the 1960s. The word "queue" has been used in its computing sense since the earliest operating systems of the 1950s, borrowed directly from British English for a line of people waiting.

Pascal itself was designed by Niklaus Wirth partly to teach these exact data structures. The pointer type and New/Dispose were included in Pascal specifically so that students could implement linked lists, stacks, queues, and trees in a clean, readable language. This chapter is, in a sense, doing exactly what Wirth intended.