The Algorithm Design Manual Second Edition

66

3 .

D A T A S T R U C T U R E S

3.1

Contiguous vs. Linked Data Structures

Data structures can be neatly classified as either contiguous or linked, depending

upon whether they are based on arrays or pointers:

• Contiguously-allocated structures are composed of single slabs of memory, and

include arrays, matrices, heaps, and hash tables.

• Linked data structures are composed of distinct chunks of memory bound

together by pointers, and include lists, trees, and graph adjacency lists.

In this section, we review the relative advantages of contiguous and linked data

structures. These tradeoffs are more subtle than they appear at first glance, so I

encourage readers to stick with me here even if you may be familiar with both

types of structures.