Programmers are comfortable building data structures using languages that feature pointers, but ask "How do I build data structures without pointers in Java?" The truth is that you cannot build data structures in any real sense without some way to have data elements refer to each other. In Java, all object identifiers (variables) are references to objects, which end up being pointers to objects in their implementation. So there is no mystery surrounding Java and data structures. Furthermore, Java provides a wonderful mechanism for separating the abstract notion of a collection of data from a data structure implementation. This article presents general suggestions for building data structures in Java, for using them most effectively, and for organizing your collections library using packages.

Article Summary and Navigation Aid:

Single Collection--Multiple Implementations
A single collection can have many implementations that can be used to optimize time or space consumption in your application. Code that refers to collections rather than their implementation does not need to be changed or recompiled when the collection implementation changes.

Single Implementation--Multiple Perspectives
A single object can implement many collection interfaces, which provides for multiple perspectives on the same data structure.

Multiple Perspectives as a Constraint Mechanism
Other team members can be restricted from illegal or dangerous access to your data structure by giving them restricted perspectives on your data.

Homogeneous Collections
Collections can be restricted to accept only objects of a certain type. Most solutions catch errors at run-time rather than compile-time because the compile-time solutions require significant programming overhead.

Enumerations of Collection Elements
Java provides a standard interface called Enumeration for walking your data structures.

Implementation Details

Data Structure Cells
Data structures are generally a set of wrappers or cells that contain references to the actual objects stored in a collection and references to other collection cells.

Suggested Package Structure
A simple package structure to prevent symbol collisions, promote data hiding, and organize your collections library.

Source code
Source code for List, Stack, LList, LLCell using the package structure suggested in this article.

Common Article Trails:

Summary trail for programmers interested in the central concepts behind collections and their implementation in Java:

Collections versus Data Structures

Enumerations of Collection Elements

Single Collection--Multiple Implementations

Single Implementation--Multiple Perspectives

Suggested Package Structure

Data Structure Cells

Complete trail for programmers who prefer to begin the learning process with concepts and organization: use the order given in the navigation aid.

Complete trail for programmers who prefer to begin the learning process with source code:

Collections versus Data Structures

Data Structure Cells

Source Code

Enumerations of Collection Elements

Single Collection--Multiple Implementations

Single Implementation--Multiple Perspectives

Multiple Perspectives as a Constraint Mechanism

Homogeneous Collections

Suggested Package Structure

Collections versus Data Structures

During the design process, think of collections of data in the abstract, such as List, Set, and Queue. It is only at the programming stage that actual data structure implementations should be chosen for each collection. Naturally, appropriate data structures are chosen according to memory constraints, and how the collections will be accessed (for example, how fast can data be stored, retrieved, and sorted.) In Java, you can separate the abstract notion of a collection of data from its data structure implementation using interfaces. For example, consider a List interface versus a linked list implementation. A simple List might have the following behavior:

interface List {
  public void add(Object o);
  public boolean includes(Object o);
  public Object elementAt(int index);
	public int length();
}

class LList implements List {
  public void add(Object o) {...}
  public boolean includes(Object o) {...}
  public Object elementAt(int index) {...}
  public int length() {...}
}

LList list = new LList();
  list.add("Frank");
  list.add("Zappa");
  list.add(new Integer(4));
  if (list.includes("Frank")) 
    System.out.println("contains Frank");

Single Collection--Multiple Implementations

Also consider how other parts of your program could reference your list. Should another team member care what implementation you used to make that list? No. Therefore, they would refer to your linked list using the List interface. For example, you could pass a linked list off to a method that referred to it by its role--a List:

LList list = new LList();
list.add(...);
paySalaries(list);

public void paySalaries(List employees) {
  for (int i=0; i&ltemployees.length(); i++) {
    Employee empl = employees.elementAt(i);
    empl.pay();
  }
}

DynamicArray anotherList = new DynamicArray();
anotherList.add(...);
paySalaries(anotherList);

class DynamicArray implements List {
  public void add(Object o) {...}
  public boolean includes(Object o) {...}
  public Object elementAt(int index) {...}
  public int length() {...}

}

// BAD: implementation specific!
public void paySalaries(LList employees) {...} 

Different implementations of the List interface allow you to tune your application for speed or space efficiency without having to change code that refers to List objects. Note that linked lists are not time-efficient to get the nth element whereas dynamic arrays are very fast at arbitrary element access. However, linked lists are more flexible and sometimes more space efficient than dynamic arrays because they do not have to allocate portions of the list in large chunks (for example, a dynamic array might initially allocate 100 cells even though you only want to store 3 elements). If application constraints force you to care about element access speed, you would create a DynamicArray. On the other hand, if you cared about memory efficiency, you would create a LList. The key idea is that any code referring to a List could use either implementation without modification, or even recompilation! This is the essence of polymorphism and dynamic binding. 

Single Implementation--Multiple Perspectives

We have seen how a collection such as a List can be implemented in many different ways, trading off time and space. Conversely, a single implementation such as a linked list may be accessed in multiple ways; that is, a linked list can implement many collection interfaces such as a List, Queue, and Stack. For example,

class LList implements List, Stack, Queue {

  // Satisfy List Interface
  public void add(Object o) {...}
  public boolean includes(Object o) {...}
  public Object elementAt(int index) {...}
  public int length() {...}


  // Satisfy Stack Interface
  public void push(Object o) {...}
  public Object pop() {...}
  public int height() {...}

	
	// Satisfy Queue Interface
  public void getInLine(Object o) {...}
}

interface Stack {
  public void push(Object o);
  public Object pop();
  public int height();
}

The alternative to satisfying multiple interfaces is to subclass LList to create LLStack, for example, that implements Stack:

class LLStack extends LList implements Stack {
  public void push(Object o) {...}
  public Object pop() {...}
  public int height() {...}
}

List list;
Stack stack;
LList llist = new LList();
list = llist; // no problem
stack = llist;// no problem

List list;
Stack stack;
LList llist = new LList();
list = llist; // no problem
stack = llist;// ERROR: must create LLStack

Multiple Perspectives as a Constraint Mechanism

Multiple perspectives on the same object also provide an important constraint mechanism. Imagine that you have a linked list of operands in a "reverse polish" calculator and that you want to prevent other team members from accessing anything but the top of stack. You could pass them a Stack perspective of your linked list to restrict the operations allowed on that collection.

class RPNCalculator {
  // for flexibility, use LList
  LList operands = new LList();
  // assume LList implements Stack
  Stack getOperandStack() { 
	return operands; 
  }
  void optimizeOperandStack() {
	  /* examine operands as List not 
	  * Stack to do constant folding etc... 
	  */
  }
}

void add() {
  Stack o = calculator.getOperandStack();
  Integer a = (Integer)o.pop();
  Integer b = (Integer)o.pop();
  Integer n = 
    new Integer(a.intValue() + b.intValue());
  o.push( n );
}

// this method should only access 
// the linked list as a stack.
void add() {
  LList o = calculator.operands;
  Integer a = (Integer)o.pop();
  Integer b = (Integer)o.pop();
  Integer n = 
    new Integer(a.intValue() + b.intValue());
  o.push( n );
}

interface ReadOnlyList {
  public boolean includes(Object o);
  public Object elementAt(int index);
  public int length();
}

void foo(ReadOnlyList list) {
  // ERROR: compiler indicates list has no add()
  list.add("Jim"); 
}

interface List extends ReadOnlyList {
	public void add(Object o);
}

The collections described so far are considered heterogeneous collections as they can hold any type of element. In order to restrict the type of the elements in a particular collection, you can easily subclass a given collection implementation. Consider making a linked list of Employee objects. You only have to restrict the add method:

class EmployeeLList extends LList {
  public void add(Object o) 
	  { /* throw exception */ }
  public void add(Employee e) 
	{ super.add(o); }
}

EmployeeLList elist = new EmployeeLList();
foo(elist);
...
void foo(List list) {

  list.add(new Employee("Jim"));
  // add(Object) called and error 
  // caught at run-time
  list.add("ack"); 
}

interface EmployeeList {
  public void add(Employee o);
  public boolean includes(Employee o);
  public Employee elementAt(int index);
  public int length();
}

EmployeeLList elist = new EmployeeLList();
foo(elist);
...
void foo(EmployeeList list) {
  list.add(new Employee("Jim"));
  // ERROR: compiler warns add(String) not found. 
  list.add("ack"); 
}

A reasonable solution for enforcing homogeneity, albeit at runtime, revolves around Java's run-time type system. The programmer is not required to create any subclasses or additional interfaces--the type of the collection elements is passed to the collection constructor in a similar manner to a template (parameterized type). For example, a linked list that knows the type of its elements would have the following use:

TypedLList tlist = 
  new TypedLList(Class.forName("Employee"));
tlist.add(new Employee("Jim"));
tlist.add("this String causes a run-time exception");

public class TypedLList extends LList {
  Class elementType;
  public TypedLList(Class c) { elementType=c; }
  public void add(Object o) {
    if ( o.getClass() == elementType ) {
	     super.add(o);
    }
    else {
      // tried to add invalid type to TypedLList.
      throw new InvalidTypeCollectionType();
    }
  }
}

// unfortunately, also causes run-time exception
tlist.add(new Manager("Mike")); 

A more sophisticated version of TypedLList would accept interface objects instead of class objects and would then check to see if the object to be added implemented the required interface. Because, when discussing collections, the concern is mostly with the behavior of an object, rather than its exact type. Checking interfaces may prove more satisfactory for you.

Enumerations of Collection Elements

The java.util package includes an interface called Enumeration that allows enumerations of your data structure. A class that implements this interface is essentially an ordered walk of your data where there may be many walks of the same data (for example, depth-first or breadth-first tree walks). An enumeration is not usually a copy of the data, but rather a control mechanism for walking. For example, an enumerator could walk a list as follows:

Enumeration e = list.elements();

for (; e.hasMoreElements();) {
	System.out.println(e.nextElement());
}

class LList implements List {
  public void add(Object o) {...}
  public boolean includes(Object o) {...}
  public Object elementAt(int index) {...}
  public int length() {...}
  public Enumeration elements() { 
	  return new LLEnumeration(this);
  }
}

final class LLEnumeration implements Enumeration {
  public LLEnumeration(LList l) {...}
  public boolean hasMoreElements() {...}
  public Object nextElement() {...}
}

Implementation Details

Data Structure Cells

Java can only allocate objects on the heap, therefore, objects cannot contain other objects--objects can only refer to other objects. Consequently, most data structures need small "wrapper" objects or "cells" to encapsulate references to the data objects and to the other cells. For example, a linked list will need a cell like:

class LLCell {
  Object data;
  LLCell next;
  public LLCell(Object o) { data = o; }
}

/* C/C++ code */
struct EmployeeLLCell {
  Employee cell;  // space for employee 
                  // struct made here 
  EmployeeLLCell *next;
};

A LList object would probably hold a head and tail reference to the first and last cell in the list. To add an object to a LList, a cell is created to hold a reference to that object and a reference to the next cell managed by the LList:

public class LList {
  LLCell head=null, tail=null;
  public void add(Object o) {
    LLCell n = new LLCell(o);
    if ( tail==null ) head=tail=n; 
	  // if the list is empty
    else {
      tail.setNext(n);
      tail=n;
    }
  }
  ...
}

Suggested Package Structure

Collections and their implementations should be placed in packages not just for organizational reasons, but to prevent access to private classes and to allow you to create names without concern that they will collide with other libraries (for example, "List" is a fairly common symbol). See the following sample structure:

collections.* has the interfaces; e.g.,
    collections.List
    collections.Stack
    collections.Tree
    collections.Dictionary

collections.impl.* has the implementations; e.g.,
    collections.impl.LinkedList
    collections.impl.DynArray
    collections.impl.BinaryTree
    collections.impl.HashTable

package collections;
public interface List {...}

package collections.impl;
public class LList implements List, Queue {...}

Source Code

	List.java The LList interface definition
	Stack.java The Stack interface definition.
	LList.java A linked list data structure that implements List and Stack. In other words, the same data structure implementation can be manipulated as a List or a Stack.
	LLCell.java A wrapper used by LList to contain references to list elements and the next LLCell in line.
	LListTest.java A test for the LList class using the List perspective.
	LLStackTest.java A test for the LList class using the Stack perspective.