A Different Kind of List

Let’s imagine Java did not have built-in arrays. How would we implement a list, a collection of items that we can add to, remove from, and access by index?

An array gives us one block of memory with all the elements stored in it, side by side. Without arrays we do not have that block. We have objects and references. So the question is whether we can build a sequence out of separate objects that refer to each other. Let’s look at an example where that already happens.

Suppose we are building an application for the HR department of a company. We need an Employee class to represent the employees of the company:

public class Employee {
  private String name;
  private int id;

  // constructor, getters, setters, etc.
}

Now, we want each employee to know their manager. We can add a manager field to the Employee class:

public class Employee {
  private String name;
  private int id;
  private Employee manager;

  // constructor, getters, setters, etc.
}

The manager field is of type Employee. One employee has a reference to another employee. (I assume you know the difference between primitive types and reference types in Java. If you need a refresher, take a look at my blog post on it.) This allows us to create a chain of employees, where each employee can have a manager, and that manager can have their own manager, and so on. You can imagine a junior employee who reports to a mid-level manager, who reports to a senior manager, who reports to the CEO. Each of those employees can be represented as an Employee object, and the manager field can point to the next employee in the chain. (For the CEO, who has no manager, we set the manager field to null.)

Why not a separate Manager class?

You might ask why the manager field is not of some new Manager type. We could write a Manager class, but it would make things more complicated. Each manager is also an employee, so we would duplicate code between the Employee and Manager classes. And each manager has a manager, so Manager would end up with a reference to another Manager and we would have the same problem again. (We could use inheritance and make Manager extend Employee, but we will not go into that here.)

The Employee class has some fields that store data, name and id. It also has a field that references another Employee. When a class has a field that refers to another instance of the same class, that gives us a chain of objects. A chain has an order to it: there is a first object, and from each object there is at most one next object.

That order is what a list needs. A list is a sequence of items, and a sequence has an order. The order does not require the items to be stored next to each other in memory. The items can be separate objects anywhere in memory, as long as each one holds a reference to the object that comes after it.