Walking a Linked List into an Array

Try This First

You have a linked list holding the integers 10, 20, 30 (in that order). After calling toArray(), what is arr[1]?

What You Need To Walk In With

• A singly linked list stores a head reference and a size field. There is no dummy head node; head is null when the list is empty.
• Walking the list means starting at head and following .next until cur becomes null.
• Generic array creation is not allowed in Java: new T[size] does not compile because of type erasure. Use Object[] instead.
• A fresh array must be allocated on every call so the caller cannot reach inside the list and corrupt its state.

How It Works

toArray needs to snapshot every element in order. The strategy is straightforward: allocate an Object[] of exactly size slots, walk the list with a cursor pointer, copy each node’s data into the next slot, and return the array.

public Object[] toArray() {
    Object[] arr = new Object[size];  // fresh array every call
    int i = 0;
    for (Node<T> cur = head; cur != null; cur = cur.next) {
        arr[i++] = cur.data;          // copy data, advance index
    }
    return arr;
}

For an empty list head is null, so the loop body never executes and arr has length 0. That is correct: the method returns new Object[0] in effect, not null.

Here is the pointer picture for a three-node list:

head
 |
[10] -> [20] -> [30] -> null
  ^       ^       ^
cur=0   cur=1   cur=2    (i tracks the slot)

Each step: copy cur.data into arr[i], post-increment i, then advance cur to cur.next. When cur hits null the loop exits and all data has been copied.

The returned array is isolated from the list. The caller can sort it, clear it, or pass it elsewhere without affecting any node inside the list.

Worked Example: Predict, Then Check

A MyLinkedList<String> contains the elements “A”, “B”, “C” added in that order. After the call:

Object[] result = list.toArray();
result[0] = "Z";

What is the first element still stored in the list?

A Common Mistake

A tempting shortcut is to cache an internal array field and return it directly:

// WRONG
private Object[] cache;

public Object[] toArray() {
    if (cache == null) cache = new Object[size];
    // ... fill cache ...
    return cache;  // caller now holds a reference into list internals
}

The problem: the caller can write result[0] = null and silently break the list’s own data. The lab spec requires a fresh allocation on every call precisely to prevent this aliasing. The fix is to allocate new Object[size] inside toArray each time so each returned array is an independent copy. (Source: S20.Lab5-LL_NDH spec, “fresh array required”.)

Go Deeper (optional)

The time cost of toArray is O(n): one pass through all n nodes with constant work per node. The space cost is also O(n) for the new array. If you later encounter a dummy-head variant of the linked list, toArray looks nearly identical: the only difference is that the walk starts at head.next instead of head, because the dummy node itself holds no real data. The course version starts at head directly (Liang 10e Ch 24).

Check Yourself

Close the notes and answer each one from memory, then reveal it. Pulling an idea back from memory is one of the strongest ways to make it stick.