The primary disadvantage of quasi-functional lists is that sharing list tails between two list objects can produce unexpected results when list objects are mutated. Mutating a shared list tail changes all of the list objects that share that tail! In the programming literature, the sharing of mutable data objects is often called ``aliasing''.
Finger Exercise Define a test class for the class
QuasiList that creates several lists that share a tail.
Try modifying the shared tail and print the values of all of
the list that share it.
Our formulation of quasi-functional lists also has a significant performance limitation. There is no efficient way to insert and remove elements from the rear of a list. As the preceding example shows, inserting an element at the rear of the list involves constructing a new copy of entire list starting with a singleton QuasiList value containing the new list element.
The absence of the constant-time operations for inserting and removing elements at the rear of list means that we cannot use a QuasiList as an efficient queue, also called a FIFO list (FIFO abbreviates ``first in first out''). A queue is a list of where elements are inserted at the rear and removed from the front.
In principle, we could develop a richer version of the MutSeq interface that included primitive operations for inserting and removing elements from the rear of the list. In addition, we could produce an efficient implementation of this interface by adding extra pointer fields that provide shortcuts to the end of a list, but the resulting maze of pointers would compromise the conceptual simplicity of the QuasiList class. The close kinship between the structure of quasi-functional and functional lists would be lost.
What we will do instead is develop object-oriented formulations of singly-linked and doubly-linked lists, which are both widely used in procedural programming. The interfaces for singly-linked and doubly-linked lists are not remotely functional and do not support sharing list tails.