You are here

List Design and the Composite Design Pattern

26 July, 2019 - 09:51
Available under Creative Commons-ShareAlike 4.0 International License. Download for free at

The UML diagram below captures the recursive data definition of the list data structure.

Figure 3.1 UML diagram of a list
A list can be represented using the composite design pattern

The definition translates into Java code as follows.

/** * Represents the abstract list structure. */ public interface IList { }
* Represents empty lists.
public class MTList implements IList { }

* Represents non-empty lists.
public class NEList implements IList {
private Object _first;
private IList _rest;

The above is an example of what is called the composite design pattern. The composite pattern is a structural pattern that prescribes how to build a container object that is composed of other objects whose structures are isomorphic to that of the container itself. In this pattern, the container is called a composite. In the above, IList is called the abstract component, MTList is called the basic component and NEList is called the composite. The composite design pattern embodies the concept of recursion, one of the most powerful thinking tool in computing. (There is a subject in theoretical computer science and mathematics called "recursive function theory," which studies the meaning of what computing means and in effect defines in the most abstract form what a computer is and what it can and cannot do.)