8 – Linked Data Structures

This chapter examines a number of data structures and shows how the VAX instruction set manages them. It shows how the instruction and addressing techniques have evolved to efficiently support the needs of compilers and operating systems, focusing on linked structures, lists, queues, and trees. Arrays, lists, queues, and trees are typical multi-element data structures commonly used in both high-level and assembly language programming. These data structures are homogeneous collections of data elements. The chapter describes the VAX INSQUE and REMQUE instructions and the doubly linked structures manipulated by them. These instructions operate on queue elements that contain a two-longword field for storing the forward and backward links. Such queues are known as absolute queues because the forward and backward link fields are stored as 32-bit absolute addresses.