Object Graphs and References

In Java every variable of a class type holds a reference to an object, and a garbage collector frees objects that no live reference can reach. Building an object graph takes no special effort: objects hold references to any others, cycles included. The design questions are different from memory management: who may change a shared object, which references are part of an entity and which only point at another entity, and what stops a list of listeners from keeping every listener alive forever. This article gives a ladder of representations from simplest to most flexible: immutable trees, mutable trees with parent links, IDs, and weak references. The rule is to start at the top and go down only when a requirement forces it.

Which arrows are real

A UML association arrow has no meaning for lifetime or for who may change what. Classify each arrow (see class diagrams and relationships for the notation):

Relationship	Meaning	Java representation
Composition (whole owns part)	Part exists only as part of the whole	A `private final` field holding the part or a list of parts, copied on the way in and out
Association by identity	A refers to B, B lives elsewhere	An ID (`BookId`, `UserId`) looked up in a map
Temporary use	A uses B for one call	A method parameter
Shared reference	Several objects use one object	A plain reference; the shared object is immutable or thread-safe
Back-reference that must not keep the target alive	Child points to parent, listener points to subject	A reference inside one lifetime, or a `WeakReference`, or an ID

The Java language has no rule about which object controls the lifetime of another. The classification is a design decision that the code has to enforce by convention and by encapsulation.

Example 1: references, identity and equality

A reference is a handle to an object. Two references can point at the same object (aliasing). The operator == compares references (identity). The method equals compares contents when the class defines it. A record defines equals over its components.

Java

import java.util.ArrayList;
import java.util.List;

record Point(int x, int y) {}

public class Main {
    public static void main(String[] args) {
        var a = new ArrayList<>(List.of(1, 2));
        var alias = a;                    // the same object under a second name
        var copy = new ArrayList<>(a);    // a new object with equal contents

        alias.add(3);
        System.out.println("a = " + a);
        System.out.println("copy = " + copy);
        System.out.println("a == alias: " + (a == alias));
        System.out.println("a == copy: " + (a == copy));
        System.out.println("a.equals(copy): " + a.equals(copy));

        copy.add(3);
        System.out.println("after copy.add(3), a.equals(copy): " + a.equals(copy));

        var p = new Point(1, 2);
        var q = new Point(1, 2);
        System.out.println("p == q: " + (p == q));
        System.out.println("p.equals(q): " + p.equals(q));
    }
}

Output

a = [1, 2, 3]
copy = [1, 2]
a == alias: true
a == copy: false
a.equals(copy): false
after copy.add(3), a.equals(copy): true
p == q: false
p.equals(q): true

Changing the list through alias changed what a sees, because both names refer to one object. copy stayed unchanged until it was changed itself. Two distinct but equal objects are equals and not ==. Design code compares entities with equals (or by ID) and uses == only for identity questions.

Example 2: a leaked reference breaks an invariant

A class that returns its internal list gives every caller a reference to its private state. The class can no longer protect its invariants (see encapsulation and invariants). Returning a copy or an unmodifiable view closes the gap.

Java

import java.util.ArrayList;
import java.util.List;

final class LeakyCart {
    private final List<String> items = new ArrayList<>();

    void add(String item) {
        items.add(item);
    }

    List<String> items() {
        return items; // the caller receives the internal list
    }
}

final class SafeCart {
    private final List<String> items = new ArrayList<>();

    void add(String item) {
        items.add(item);
    }

    List<String> items() {
        return List.copyOf(items); // an immutable snapshot
    }

    int size() {
        return items.size();
    }
}

public class Main {
    public static void main(String[] args) {
        var leaky = new LeakyCart();
        leaky.add("pen");
        leaky.items().clear();
        System.out.println("leaky cart size: " + leaky.items().size());

        var safe = new SafeCart();
        safe.add("pen");
        try {
            safe.items().clear();
        } catch (UnsupportedOperationException e) {
            System.out.println("snapshot is read-only");
        }
        System.out.println("safe cart size: " + safe.size());
    }
}

Output

leaky cart size: 0
snapshot is read-only
safe cart size: 1

List.copyOf copies the elements once per call. An alternative is Collections.unmodifiableList(items), which is a read-only view of the live list and reflects later changes. Choose a copy when the caller needs a stable snapshot, and a view when copying is too costly and live updates are acceptable.

Example 3: an immutable tree

If the data is a tree, let each parent hold its children and let nothing change after construction. A file system directory is the standard example (see design file system for the full problem). A sealed interface lists the two kinds of node, and records hold the data. The compact constructor of Dir copies the child list so that the caller's list cannot alter the node later.

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Optional;

sealed interface Node {
    record File(String name, long size) implements Node {}

    record Dir(String name, List<Node> children) implements Node {
        public Dir {
            children = List.copyOf(children);
        }
    }
}

public class Main {
    static long totalSize(Node node) {
        return switch (node) {
            case Node.File(var name, var size) -> size;
            case Node.Dir(var name, var children) -> children.stream().mapToLong(Main::totalSize).sum();
        };
    }

    static void print(Node node, int depth) {
        String indent = "  ".repeat(depth);
        switch (node) {
            case Node.File(var name, var size) -> System.out.println(indent + name + " (" + size + ")");
            case Node.Dir(var name, var children) -> {
                System.out.println(indent + name + "/");
                for (Node child : children) {
                    print(child, depth + 1);
                }
            }
        }
    }

    // Navigation upward is a search from the root, because nodes have no parent link.
    static Optional<List<String>> pathTo(Node node, String target) {
        return switch (node) {
            case Node.File(var name, var size) ->
                name.equals(target) ? Optional.of(List.of(name)) : Optional.empty();
            case Node.Dir(var name, var children) -> {
                if (name.equals(target)) {
                    yield Optional.of(List.of(name));
                }
                for (Node child : children) {
                    var found = pathTo(child, target);
                    if (found.isPresent()) {
                        var path = new ArrayList<String>();
                        path.add(name);
                        path.addAll(found.get());
                        yield Optional.of(List.copyOf(path));
                    }
                }
                yield Optional.empty();
            }
        };
    }

    public static void main(String[] args) {
        var root = new Node.Dir("root", List.of(
            new Node.File("a.txt", 10),
            new Node.Dir("docs", List.of(new Node.File("b.md", 32)))));
        print(root, 0);
        System.out.println("total " + totalSize(root));
        System.out.println(pathTo(root, "b.md"));
        System.out.println(pathTo(root, "missing"));
    }
}

Output

root/
  a.txt (10)
  docs/
    b.md (32)
total 42
Optional[[root, docs, b.md]]
Optional.empty

This is the simplest design and needs no synchronization, because nothing changes. Its limit is that navigation only goes down. A child is created before its parent, so an immutable child cannot hold a reference to a parent that does not exist yet. Upward navigation becomes a search from the root, as pathTo shows. A requirement that needs fast upward navigation moves the design to the next level.

Example 4: a mutable tree with parent references

Mutable nodes remove the creation-order problem: create the parent first, then create each child with a reference to its parent. Parent and child now refer to each other, which is a cycle. Java allows this and the garbage collector reclaims the whole structure once nothing outside it refers to it.

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

final class TreeNode {
    private final String name;
    private final TreeNode parent;                         // null for the root
    private final List<TreeNode> children = new ArrayList<>();

    private TreeNode(String name, TreeNode parent) {
        this.name = name;
        this.parent = parent;
    }

    static TreeNode root(String name) {
        return new TreeNode(name, null);
    }

    TreeNode addChild(String name) {
        var child = new TreeNode(name, this);
        children.add(child);
        return child;
    }

    List<TreeNode> children() {
        return Collections.unmodifiableList(children);
    }

    String path() {
        return parent == null ? name : parent.path() + "/" + name;
    }

    void depthFirst(List<String> out) {
        out.add(name);
        for (TreeNode child : children) {
            child.depthFirst(out);
        }
    }

    @Override
    public String toString() {
        return name; // prints the name only, so a cycle never recurses
    }
}

public class Main {
    public static void main(String[] args) {
        var root = TreeNode.root("root");
        var usr = root.addChild("usr");
        var bin = usr.addChild("bin");
        root.addChild("etc");

        System.out.println(bin.path());
        var order = new ArrayList<String>();
        root.depthFirst(order);
        System.out.println(order);
        System.out.println(root.children());
    }
}

Output

root/usr/bin
[root, usr, bin, etc]
[usr, etc]

Three design choices keep the cycle safe:

The parent field is final and set only through addChild, so a node cannot be attached to two parents.
children() returns an unmodifiable view, so callers cannot add a child without a parent link.
The class keeps identity-based equals and hashCode and a toString that prints only the name. A record with a parent component would call toString, equals and hashCode on the parent, which calls them on its children, which call them on the parent again, until a StackOverflowError.

Removing a node needs two steps (drop it from the parent's list and clear the references it holds), so a remove method belongs to the same class that owns the invariant.

Example 5: IDs instead of references

Give every entity an ID and store IDs in relationships. The data lives in one owner, typically a map inside a repository or a service. An ID is an immutable value that can be stored anywhere. This is the default for domain models such as a library (members, books, loans), and it mirrors a database. The ID is a record, so two IDs with the same number are equal and a plain int cannot be passed in its place by mistake.

Java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Optional;

record EmployeeId(int value) {}

record Employee(String name, EmployeeId manager) { // manager is null for the top of the chain
    Optional<EmployeeId> managerId() {
        return Optional.ofNullable(manager);
    }
}

final class Company {
    private final Map<EmployeeId, Employee> staff = new LinkedHashMap<>();

    void add(EmployeeId id, Employee employee) {
        if (staff.putIfAbsent(id, employee) != null) {
            throw new IllegalArgumentException("duplicate id " + id.value());
        }
    }

    Optional<Employee> find(EmployeeId id) {
        return Optional.ofNullable(staff.get(id));
    }

    List<String> chainOfCommand(EmployeeId id) {
        var names = new ArrayList<String>();
        var seen = new HashSet<EmployeeId>();
        Optional<Employee> current = find(id);
        EmployeeId currentId = id;
        while (current.isPresent()) {
            if (!seen.add(currentId)) {
                throw new IllegalStateException("management cycle at " + currentId.value());
            }
            names.add(current.get().name());
            currentId = current.get().manager();
            current = currentId == null ? Optional.empty() : find(currentId);
        }
        return names;
    }

    List<String> reportsOf(EmployeeId boss) {
        return staff.values().stream()
            .filter(e -> boss.equals(e.manager()))
            .map(Employee::name)
            .toList();
    }

    void remove(EmployeeId id) {
        if (!reportsOf(id).isEmpty()) {
            throw new IllegalStateException("employee " + id.value() + " still has reports");
        }
        staff.remove(id);
    }
}

public class Main {
    public static void main(String[] args) {
        var company = new Company();
        company.add(new EmployeeId(1), new Employee("Priya", null));
        company.add(new EmployeeId(2), new Employee("Omar", new EmployeeId(1)));
        company.add(new EmployeeId(3), new Employee("Zoe", new EmployeeId(2)));

        System.out.println(company.chainOfCommand(new EmployeeId(3)));
        System.out.println(company.reportsOf(new EmployeeId(1)));
        System.out.println(company.find(new EmployeeId(9)));
        try {
            company.remove(new EmployeeId(1));
        } catch (IllegalStateException e) {
            System.out.println(e.getMessage());
        }
        company.remove(new EmployeeId(3));
        System.out.println(company.reportsOf(new EmployeeId(2)));
    }
}

Output

[Zoe, Omar, Priya]
[Omar]
Optional.empty
employee 1 still has reports
[]

Employees point up through manager, and the downward direction is a search over the map. There is one owner, Company, so there is no question about who changes what. The costs match a database: a lookup can miss, so a dangling ID is handled (find returns an Optional), removing an entity means checking or cleaning the IDs that point at it, and bad data can contain a cycle, which chainOfCommand detects instead of looping forever. See modeling domains in Java for records as IDs.

Example 6: weak references for back-links

A subject that keeps its listeners in a list holds a strong reference to each of them. A listener that nobody else uses stays reachable through that list and is never collected, which is a memory leak in a garbage-collected language (the "lapsed listener" problem). A java.lang.ref.WeakReference refers to an object without keeping it reachable. When no strong reference remains, the collector may clear the weak reference, and get() then returns null.

Java

import java.lang.ref.Reference;
import java.lang.ref.WeakReference;
import java.util.ArrayList;
import java.util.List;

final class Listener {
    private final String name;

    Listener(String name) {
        this.name = name;
    }

    void receive(String message) {
        System.out.println(name + " got " + message);
    }
}

final class Subject {
    private final List<WeakReference<Listener>> listeners = new ArrayList<>();

    void subscribe(Listener listener) {
        listeners.add(new WeakReference<>(listener));
    }

    // Delivers to live listeners, drops cleared references, returns the delivery count.
    int publish(String message) {
        int delivered = 0;
        var it = listeners.iterator();
        while (it.hasNext()) {
            Listener listener = it.next().get();
            if (listener == null) {
                it.remove();
            } else {
                listener.receive(message);
                delivered++;
            }
        }
        return delivered;
    }
}

public class Main {
    static WeakReference<Listener> subscribeTemporary(Subject subject) {
        var temporary = new Listener("temporary");
        subject.subscribe(temporary);
        return new WeakReference<>(temporary); // the only strong reference ends with this method
    }

    public static void main(String[] args) {
        var subject = new Subject();
        var kept = new Listener("kept");
        subject.subscribe(kept);
        var probe = subscribeTemporary(subject);

        System.out.println("delivered " + subject.publish("first"));

        // System.gc() is a request. The loop repeats it until the collector clears the probe.
        for (int i = 0; i < 100 && probe.get() != null; i++) {
            System.gc();
        }
        System.out.println("delivered " + subject.publish("second"));
        Reference.reachabilityFence(kept); // keeps `kept` strongly reachable up to this line
    }
}

Output

kept got first
temporary got first
delivered 2
kept got second
delivered 1

The first publish reaches both listeners. After the temporary listener loses its last strong reference, the collector clears the weak reference, and the second publish reaches only kept. The JVM chooses when to collect, so production logic must never depend on the moment a weak reference clears. The example retries only to make the demonstration stable. Reference.reachabilityFence stops the compiler from treating kept as unreachable after its last use, which would let the collector clear it too.

Weak references suit caches and registries where losing an entry is acceptable. A listener that must always be notified needs an explicit unsubscribe instead (see event bus and observers).

Choosing the representation

Requirement	Use
Strict hierarchy, only downward traversal	Immutable tree: sealed interface, records, `List.copyOf`
Tree with parent links, changed over time	Classes with a `final` parent reference, a private child list, and an unmodifiable view
Entities related by identity, stored in a repository	ID records plus a map
Back-reference that must not keep the target alive	`WeakReference`, or an explicit unsubscribe
Shared across threads	Immutable objects, or thread-safe components (see thread-safe components)
Temporary access	A method parameter

For a graph problem in an interview, the choice between references and IDs follows from the operations. Objects with direct references are the shortest code when the graph is built once and traversed. IDs and a map suit entities that are created, deleted and looked up independently. For a linked structure inside a data structure problem, see design LRU cache, where LinkedHashMap already holds the links.

Interview points

== compares references, equals compares contents, and a record compares all its components.
Returning an internal collection leaks a reference and breaks the class's invariants. Return a copy or an unmodifiable view.
Cycles are legal in Java. The collector frees an unreachable cycle. Records with a parent component recurse in toString, equals and hashCode.
A strong reference from a long-lived list keeps an object alive. A WeakReference does not, but the moment it clears is not under program control.
IDs plus a map avoid shared mutable references and must handle missing and dangling IDs.

Summary

Each arrow in a class diagram is one of: composition, identity, temporary use, shared reference, or a back-reference; decide which before writing types.
Variables hold references. Aliasing means a change through one name is visible through all of them.
Immutable trees built from records are the simplest and need no synchronization, but they cannot hold parent links.
A mutable tree with parent links is a cycle. Keep the links final where possible, expose children read-only, and keep identity equality.
IDs plus a map handle associations, at the cost of handling missing entries and cleaning references on removal.
A WeakReference breaks a keep-alive chain such as a listener list. Its clearing time is decided by the collector.
Start at the simplest level and move down only when a stated requirement forces it.