Art of Computer Programming, The: Volume 1: Fundamental Algorithms, 3rd Edition

Chapter Two. Information Structures

I think that I shall never see

A poem lovely as a tree.

— JOYCE KILMER (1913)

Yea, from the table of my memory

I’ll wipe away all trivial fond records.

— HAMLET (Act I, Scene 5, Line 98)

2.1. Introduction

COMPUTER PROGRAMS usually operate on tables of information. In most cases these tables are not simply amorphous masses of numerical values; they involve important structural relationships between the data elements.

In its simplest form, a table might be a linear list of elements, when its relevant structural properties might include the answers to such questions as: Which element is first in the list? Which is last? Which elements precede and follow a given one? How many elements are in the list? A lot can ...