Skip to main content
Engineering LibreTexts

9.3: Implementations of Collections

  • Page ID
    36380
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    Table \(\PageIndex{1}\): Some collection classes categorized by implementation technique.
    Arrayed Implementation Ordered Implementation Hashed Implementation Linked Implementation Interval Implementation

    Array

    String

    Symbol

    OrderedCollection

    SortedCollection

    Text

    Heap

    Set

    IdentitySet

    PluggableSet

    Bag

    IdentityBag

    Dictionary

    IdentityDictionary

    PluggableDictionary

    LinkedList

    SkipList

    Interval

    These categorizations by functionality are not our only concern; we must also consider how the collection classes are implemented. As shown in Table \(\PageIndex{1}\), five main implementation techniques are employed.

    1. Arrays store their elements in the (indexable) instance variables of the collection object itself; as a consequence, arrays must be of a fixed size, but can be created with a single memory allocation.

    2. OrderedCollections and SortedCollections store their elements in an array that is referenced by one of the instance variables of the collection. Consequently, the internal array can be replaced with a larger one if the collection grows beyond its storage capacity.

    3. The various kinds of set and dictionary also reference a subsidiary array for storage, but use the array as a hash table. Bags use a subsidiary Dictionary, with the elements of the bag as keys and the number of occurrences as values.

    4. LinkedLists use a standard singly-linked representation.

    5. Intervals are represented by three integers that record the two end-points and the step size.

    In addition to these classes, there are also “weak” variants of Array, Set and of the various kinds of dictionary. These collections hold onto their elements weakly, i.e., in a way that does not prevent the elements from being garbage collected. The Squeak virtual machine is aware of these classes and handles them specially.

    Readers interested in learning more about the Smalltalk collections are referred to LaLonde and Pugh’s excellent book1.


    1. Wilf LaLonde and John Pugh, Inside Smalltalk: Volume 1. Prentice Hall, 1990, ISBN 0–13– 468414–1.


    This page titled 9.3: Implementations of Collections is shared under a CC BY-SA 3.0 license and was authored, remixed, and/or curated by Andrew P. Black, Stéphane Ducasse, Oscar Nierstrasz, Damien Pollet via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.