Data structures

Arrays, records and tuples, then the abstract data types: stacks, queues, linked lists, hash tables and dictionaries, vectors, and how records are organised in files. The robot undoes its moves, queues its commands and tracks itself with vectors.

Module A3A level9 lessons

Start in the simulator
  1. A3.1 Arrays, records and tuples Arrays in one, two and three dimensions, records and fields, tuples and lists, and static structures.
  2. A3.2 Abstract data types and stacks ADTs, static and dynamic structures, and a stack with a top pointer: an undo stack for the robot's moves.
  3. A3.3 Queues: linear, circular and priority Front and rear pointers, wrapping round with MOD, and priority queues: a command queue for the robot.
  4. A3.4 Linked lists Nodes and pointers, the free list, and traversing, inserting and deleting: a route of waypoints.
  5. A3.5 Hash tables Hashing functions, collisions, rehashing by probing, chaining and load factor: finding markers fast.
  6. A3.6 Dictionaries Keys and values, dictionaries built on hash tables, and information retrieval: commands looked up by name.
  7. A3.7 Vectors Vectors as lists, functions and arrows; addition, scaling, dot product and convex combination, on the robot's position.
  8. A3.8 Fields, records and file organisation Text and binary files, fixed-length records, and serial, sequential, indexed sequential and direct access files.
  9. A3.9 Project: mission control A mission read from a file into a circular queue, moves looked up in a dictionary, position tracked as a vector, and…