Keywords: current

Next: 2.1.1 Arrays Up: 2. Object-Oriented Data Structures Previous: 2. Object-Oriented Data Structures

# 2.1 Sequences

The first data structures that we will discuss are the common representations for sequences of elements. A sequence is an ordered collection , of data objects drawn from some base data type . Sequence representations can be classified based on the set of operations that they support. In Java, it is convenient to describe these various sets of operations as Java `interface`s.

We have already used a common representation for sequences, namely functional lists, in many of our examples of functional programming in the preceding chapter. Before we explore general representations for sequences, we need to discuss a particular formulation of sequences called arrays, which are built-in to Java as they are in nearly all other programming languages.

Subsections

- 2.1.1 Arrays
  - 2.1.1.1 Recipes for Processing Arrays
- 2.1.2 Lists
- 2.1.3 Immutable Sequences
  - 2.1.3.1 Linked Representation
  - 2.1.3.2 Contiguous Representation
- 2.1.4 Mutable Sequences
  - 2.1.4.1 Singly-linked Mutable List Representation
- 2.1.5 List Containers
- 2.1.6 Quasi-Functional Lists
  - 2.1.6.1 Nested Classes vs. Inner Classes
  - 2.1.6.2 Mutable Visitors
- 2.1.7 Extended Mutable Lists
  - 2.1.7.1 Formulating Traditional Linked Lists as Objects
  - 2.1.7.2 Spaghetti References (akin to spaghetti code)
  - 2.1.7.3 The Iterator Pattern
- 2.1.8 An Implementation
  - 2.1.8.1 BiLists and Their Iterators
- 2.1.9 Alternate Representations of Lists
  - 2.1.9.1 Arrays
- 2.1.10 Hybrid Representations of Sequences