Understanding Java Arrays and Lists — The Theory Behind Representation, Information Hiding, and the Big-O Contract Java’s Type System Won’t Enforce

Arbiter Guide Theory • Day 7 | Exploring the raw array as pre-abstraction storage, the Iterator pattern as information hiding applied to traversal, and why ArrayList and LinkedList can satisfy an identical interface while diverging completely in cost

This infographic illustrates the underlying representations and performance characteristics of common data structures. On the left, a jagged array diagram and a class-box diagram visualize how different structures hide data behind abstract interfaces. In the center, an iterator is shown traversing both an array and a linked list, highlighting a unified access pattern over distinct implementations. On the right, two tables detail the Big O time complexity for standard operations in ArrayLists and LinkedLists, using color-coded labels for O(1) (green) and O(n) (red).

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class java_7ArraysLists {
    public static void main(String[] args) {
        int[][] grid = new int[][] {
            {1,  2,  3,  4,  5 }, 
            {6,  7,  8,  9,  10},
            {11, 12, 13, 14, 15},
            {16, 17, 18, 19, 20},
            {21, 22, 23, 24, 25},
        };

        int n = grid.length;
        int ringCount = 0;

        if (n % 2 == 0) {
            ringCount = n / 2;
        } else {
            ringCount = (n + 1) / 2;
        }

        int total = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                total += grid[i][j];
            }
        }

        int idx = 0;
        int grandTotal = 0;
        while(idx < ringCount) {
            int sum = 0;
            System.out.println("Ring: " + idx);

            for (int i = idx; i < grid.length - idx; i++) {
                for (int j = idx; j < grid[i].length - idx; j++) {
                    if ((i == idx) || (i == grid.length - (idx + 1))) {
                        System.out.println("Element: " + grid[i][j]);
                        sum += grid[i][j];
                    } else if ((j == idx) || (j == grid[i].length - (idx + 1))) {
                        System.out.println("Element: " + grid[i][j]);
                        sum += grid[i][j];
                    }
                }
            }
            System.out.println("Ring " + idx + " total: " + sum + "\n");
            idx++;
            grandTotal += sum;
        }

        System.out.println("Total by travelsal: " + total);
        System.out.println("Grand Total by rings: " + grandTotal);
        System.out.println();

        ArrayList<Integer> arrayList = new ArrayList<>(List.of(
            -25, -23, -15, -8,
            -2, 1, 1, 7,
            15, 27, 27, 39,
            41, 42, 47, 50, 
            22, 14, 14, 49
        ));

        Iterator<Integer> it = arrayList.iterator();
        while(it.hasNext()) {
            Integer element = it.next();

            if (element < 0 || element % 7 == 0) {
                it.remove();
            }
        }

        System.out.print("(Part A) Elements of arraylist: ");
        for (Integer i : arrayList) {
            System.out.print(i + " ");
        }
        System.out.println();

        LinkedList<Integer> linkedList = new LinkedList<>();
        Iterator<Integer> it2 = arrayList.iterator();
        while(it2.hasNext()) {
            Integer element = it2.next();

            if (element % 2 == 0) {
                linkedList.addFirst(element);
            } else {
                linkedList.addLast(element);
            }
        }

        System.out.print("(Part B) Elements of linkedlist: ");
        for (Integer i : linkedList) {
            System.out.print(i + " ");
        }
        System.out.println();

        System.out.println("(Part C) First Element: " + linkedList.getFirst() + ", Last Element: " + linkedList.getLast());
    }
}

A programming language could get away with giving you exactly one way to store a sequence of values. Java gives you at least three — a raw array, an ArrayList, a LinkedList — and lets you walk all three with the exact same for-each syntax.

That’s not redundancy. It’s evidence that “a sequence of things” and “how that sequence is actually laid out in memory” were deliberately pulled apart at some point, and the split is old enough, and consequential enough, to have its own theory.

What Does It Mean to Choose a Representation for a Sequence?

Today’s constructs — the array, the Iterator, and the ArrayList/LinkedList pair — all sit on either side of one question: once a program has decided it needs "a sequence of things," how much of how that sequence is stored should the rest of the program be allowed to see? In this seventh theoretical article of the Arbiter Learning Journey, we'll trace that question from the raw array — the one place Java still lets representation leak straight through — to the Iterator pattern that hides it everywhere else, and finish with the actual algorithmic cost each representation choice locks in, a cost Java's type system stays conspicuously silent about.

This article accompanies the practical guide for Day 7 and focuses on the reasoning behind the language, not on writing code.

Arrays as Pre-Abstraction: What Simula Was Built to Move Past

Why a Java 2D array is really an array of arrays, and why that’s not a bug so much as a fossil.

grid[i].length, re-read on every single row of the ring-traversal loop rather than cached once as a shared n, looks like a small defensive habit. It's actually an acknowledgment of what a Java 2D array really is: not one contiguous rectangular block, but an array of arrays, where each row is its own, independently allocated object with its own length. Nothing forces those rows to match — Java simply doesn't stop a program from allocating a genuinely jagged array — and the traversal that re-reads grid[i].length is the one that's actually honest about that.

This is worth placing historically. Ole-Johan Dahl and Kristen Nygaard’s Simula 67 introduced the class specifically to bundle a piece of data together with the operations allowed to touch it, so that code depending on the class would never need to know, or be able to assume, anything about its internal layout. An array never joined that abstraction. It predates it, in spirit if not always in literal chronology — a block of memory with an exposed length and exposed indices, offering no interface between the caller and the layout at all. grid[i].length isn't a computed property behind a boundary; it's a direct, public fact about one specific row's allocation, visible to absolutely anything holding a reference to that row. The array is, in a real sense, the one corner of Java that Dahl and Nygaard's abstraction never fully reached.

The ring-extraction algorithm itself is worth a second look through a different, older lens. Corrado Böhm and Giuseppe Jacopini proved in 1966 that exactly three control constructs — sequence, selection, and iteration — are jointly sufficient to express any computable flowchart, with no goto required. The ring algorithm looks spatially intricate: nested loops walking a shrinking sub-square, boundary checks deciding which cells count. Underneath, it's nothing but those three primitives, composed: iteration (the nested for loops), selection (the if/else if boundary tests), and sequence (accumulating sum, then grandTotal, in order). Böhm and Jacopini's theorem is exactly why that composition was guaranteed to be enough before a single line of it was written.

The Iterator: Information Hiding Applied to Traversal

Why the exact same for-each loop works identically over an array-backed list and a node-linked one — and why that’s Parnas’s principle at work, not a coincidence.

David Parnas’s 1972 paper, On the Criteria to Be Used in Decomposing Systems into Modules, formalized a principle that now sounds close to obvious: a module’s internal design decisions — especially how it represents its data — should be hidden behind an interface, so that changing the decision later never ripples out to every piece of code that uses the module. Iterator<T> is that principle applied directly to the act of traversal. Its two methods, hasNext() and next(), say nothing about where the iterator currently is. For an ArrayList, "where" is an integer index into a backing array. For a LinkedList, "where" is a reference to the current node in a chain. Code holding only the Iterator reference cannot tell which is true, and critically, doesn't need to.

That pattern was later formalized on its own terms — independent of any one language — by Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides in Design Patterns (1994), where the Iterator pattern is described as providing sequential access to the elements of an aggregate without exposing its underlying representation. Parnas supplies the why; the Gang of Four supply the reusable shape of the answer, which is exactly the shape java.util.Iterator takes.

Information hiding also explains why it.remove() exists as a separate, deliberate operation rather than simply calling list.remove(element) mid-loop. Joshua Bloch — who, beyond writing Effective Java, was the principal architect of the Java Collections Framework itself — built the framework's iterators to be fail-fast: each list tracks a modCount, and any structural change made outside the iterator invalidates it, throwing ConcurrentModificationException on the next next() call rather than allowing the iterator's hidden position to silently drift out of sync with a structure it no longer accurately describes. it.remove() is the one channel exempted from that check, precisely because it's the one channel that updates the iterator's own hidden bookkeeping and the list's structure together, atomically, as a single coordinated operation. It's information hiding enforced, not just offered: the representation is hidden so thoroughly that Java refuses to let anything but the iterator itself touch it safely mid-traversal.

Big-O: The Part of the Contract Java’s Type System Doesn’t Enforce

Why List<Integer> guarantees nothing about how fast add() runs — and why that's a real gap in Bertrand Meyer's Design by Contract, not an oversight.

ArrayList and LinkedList both satisfy the identical List<E> interface. Code written against List<E> cannot, from the type system alone, tell which concrete implementation it's holding — and today's lesson used exactly that interchangeability, assigning a LinkedList<Integer> and building it with addFirst()/addLast(), methods that don't even exist on the plain List interface, precisely because reaching for LinkedList by name was the point.

The two diverge sharply once actual cost enters the picture. LinkedList.addFirst() and addLast() are O(1): each touches exactly one node's prev/next pointers, regardless of how large the list already is. ArrayList can only match that at the back, and only in the amortized sense — its backing array periodically doubles in capacity, so most calls to add() are O(1) and the occasional resize is O(n), averaging out to O(1) over a long sequence of insertions. Inserting at the front of an ArrayList, by contrast, is unconditionally O(n): every existing element has to physically shift over by one slot to make room, every single time. Random access runs in the opposite direction — ArrayList.get(i) is O(1), a direct index calculation into contiguous memory, while LinkedList.get(i) is O(n), forced to walk node-by-node from whichever end is closer.

Bertrand Meyer’s Design by Contract, developed alongside the Eiffel language in the late 1980s, formalizes a type’s guarantees as pre-conditions, post-conditions, and invariants — precise statements about what a correct call is required to produce. Complexity sits entirely outside that vocabulary. Two methods can satisfy an identical contract — the exact same post-condition, the same resulting state — while differing by orders of magnitude in the cost of getting there, and nothing in the pre/post-condition language distinguishes them. That’s precisely the gap ArrayList and LinkedList live in: both are contractually interchangeable behind List<E>, and only a working knowledge of the representation — the very representation the interface exists to hide — tells a programmer which one actually belongs in a given piece of code.

Why These Concepts Matter

Each of today’s ideas answers a different piece of the same underlying question: once a sequence’s representation is hidden, what gets lost, and what has to be recovered some other way?

Simula’s class-based abstraction — and the raw array’s refusal to fully participate in it — is what explains why grid[i].length has to be re-read on every row. Java's array never joined the abstraction Dahl and Nygaard built everything else around, so it never earned the right to have a hidden, assumed shape.

Parnas’s information hiding, formalized as the Iterator pattern, is what explains why the exact same loop works identically over any List implementation, and why it.remove() — not list.remove() — is the only mutation path Java trusts to keep a collection's internal bookkeeping honest while something is still walking through it.

And the gap in Design by Contract is what explains why “compiles against List<E>" is not the same claim as "fast enough for this call site" — a distinction Java's type system will never make on a programmer's behalf, and Big-O reasoning is the only tool that recovers it.

The Arbiter Journey

This series is documenting a complete journey through Java before applying it to build Arbiter — a production-style microservices platform built from the ground up.

Today’s ideas become load-bearing well before Arbiter reaches its database layer. Every REST endpoint that returns a collection of test cases or execution results will hand callers a List<T> reference — and whether the service layer behind it assembled that list with an ArrayList or built it by repeatedly prepending onto a LinkedList is exactly the kind of representation decision today's Iterator pattern is designed to hide from the caller, and exactly the kind of decision today's Big-O reasoning insists still has to be made deliberately, not out of habit. And the moment Arbiter needs an actual queue — pending test executions waiting their turn, notifications waiting to be dispatched — LinkedList's O(1) guarantee at both ends stops being a theoretical footnote and becomes the concrete reason it gets chosen over ArrayList.

Follow along with the complete Arbiter playlist

https://youtube.com/playlist?list=PLZG2gr4IjsZM&si=StFLpldNdIOjc3ub

GitHub Repository

Follow the complete Arbiter Learning Journey, source code, explanations, and future lessons here: https://github.com/Someone-anon-coder/Arbiter

Follow the Complete Arbiter Series

Every Guide and Guide Theory article in this series, collected in one place:

Arbiter Guide https://computer-info-1.medium.com/list/arbiter-java-20daa21849c8

Arbiter Guide Theory https://computer-info-1.medium.com/list/arbiter-java-theory-13ecf0e21149

Explore My Other Learning Series

If you enjoy structured learning journeys, you may also find these useful:

Cybersecurity https://computer-info-1.medium.com/list/cybersecurity-cba13dd0be16

Python Guide https://computer-info-1.medium.com/list/python-guide-8e0b3bcab940

Python Guide Theory https://computer-info-1.medium.com/list/python-guide-theory-81528784ebfe

GoLang Guide https://computer-info-1.medium.com/list/golang-guide-e70e25ca8b42

GoLang Guide Theory https://computer-info-1.medium.com/list/golang-guide-theoretical-082d8e7624ab

Matplotlib https://computer-info-1.medium.com/list/my-progress-matplotlib-669052e8da38

What’s Next?

In the next Arbiter Guide Theory article, we’ll move into Maps & Sets: the algorithmic theory behind hash tables — why HashMap achieves O(1) average-case operations, why TreeMap trades that for O(log n) in exchange for a balanced tree's ordering guarantee, and how to reason about choosing a collection as a genuine Big-O trade-off rather than a default habit.

Today’s Big-O gap in the List contract is the same gap that makes that comparison meaningful — Map will hide the choice between HashMap and TreeMap exactly as thoroughly as List hides the choice made today.

Happy coding! ☕