Keywords: current

Next: 2.1.7.1 Formulating Traditional Linked Up: 2.1 Sequences Previous: 2.1.6.2 Mutable Visitors

## 2.1.7 Extended Mutable Lists

Both of the preceding representations of mutable sequences--lists as containers and quasi-functional lists--are inefficient at inserting elements at the rear of a sequence. In each of these representations, the code for the operation must scan the entire sequence to reach the end. The container representation is particularly inefficient in this regard because the entire sequence must be reconstructed starting with a singleton `List` containing the new element.

Mutable sequence implementations that efficiently support adding elements at rear of the list and removing them from the front are important because this access protocol, called a queue or a FIFO (first in, first out) list, frequently arises in practice. Procedural formulations of linked lists discussed in traditional textbooks on data structures provide constant-time access to the end of the list by maintaining a ``pointer'' to the last node of the list. This strategy is conceptually simple but prone to coding errors because the empty list state requires special treatment. Moreover, the traditional procedural approach to representing lists exposes the concrete data structures (nodes and links) used in the implementation. We can exploit the same strategy in an object-oriented representation of lists that hides the concrete data structures in private object fields--provided that we deal carefully with the potentially troublesome ``boundary'' cases in the definition of list operations that involve the empty list.

Subsections

- 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

Next: 2.1.7.1 Formulating Traditional Linked Up: 2.1 Sequences Previous: 2.1.6.2 Mutable Visitors