深入解析ArrayList与LinkedList在堆和栈内存中的存储结构

Great question—let’s break this down step by step to clear up all the confusion around how these two collections handle memory! First, let’s recap the core memory rules we need to start with:

• Stack memory: Stores primitive values and references to objects (not the objects themselves). Think of these references as little pointers pointing to the actual object’s location in the heap.
• Heap memory: Stores all objects—including ArrayList, LinkedList instances, and every element they hold (even primitives get wrapped into wrapper classes like Integer for int and stored as objects here).

How ArrayList Stores Elements #

An ArrayList is built on top of a fixed-size array that resizes dynamically when it runs out of space. Here’s the play-by-play:

• The ArrayList object itself lives in the heap. It contains a few key things: a reference to its underlying array (which is also an object in the heap), plus variables tracking the current size and capacity of the list.
• The underlying array holds references to each element in the list. If you’re storing primitives (like int), they get wrapped into their corresponding wrapper objects (e.g., Integer) first—so the array is always holding references to heap objects.
• When you create an ArrayList as a local variable:
  1. The reference to the ArrayList is stored in the stack.
  2. The actual ArrayList object (and its underlying array) lives in the heap.
  3. Every element you add is an object in the heap, and the array holds a reference to each one.
• That "fixed size" you mentioned refers to the array’s initial capacity. When you add more elements than the array can hold, ArrayList creates a new, larger array in the heap, copies all the old references over, and the old array gets garbage collected eventually.

How LinkedList Stores Elements #

A LinkedList is a chain of nodes, where each node acts as a container for your element plus pointers to adjacent nodes (Java’s LinkedList is a doubly-linked list, so each node has a next and prev pointer). Here’s how it works:

• The LinkedList object itself lives in the heap. It only holds references to the first (head) and last (tail) nodes in the chain.
• Each node is a separate object in the heap. Every node contains: a reference to your element (again, primitives are wrapped), plus references to the next and previous nodes in the list.
• Just like ArrayList, the reference to the LinkedList (if it’s a local variable) lives in the stack, pointing to the main LinkedList object in the heap.

Answering Your Specific Questions #

1. Do all elements have a stack reference, or just one reference to the collection? #

Only the collection’s own reference lives in the stack (assuming it’s a local variable). Individual elements, along with the collection’s internal structures (like ArrayList’s array or LinkedList’s nodes), are all in the heap. The stack doesn’t track references to each element—those are managed entirely within the heap via the collection’s internal setup.

2. Does LinkedList use more memory than ArrayList? #

Absolutely. Here’s why:

• Each LinkedList node has extra overhead beyond just the element reference. It needs to store two additional pointers (next and prev), each taking up memory (usually 4 or 8 bytes depending on your JVM and system architecture).
• ArrayList only has the overhead of its underlying array (a contiguous block of references) plus a small amount of metadata in the main ArrayList object. There’s no per-element overhead beyond the element reference itself.
• For example, storing 1000 String objects: ArrayList uses an array of 1000 references, while LinkedList uses 1000 nodes each holding 3 references (element, next, prev)—that’s way more memory for the same number of elements.

Quick Cheat Sheet #

• Both ArrayList and LinkedList instances live in the heap; their references live in the stack (if they’re local variables).
• ArrayList uses a heap-based array to track element references; LinkedList uses heap-based nodes with element + pointer references.
• Only the collection’s reference is in the stack—individual elements are referenced via the collection’s internal heap structures.
• LinkedList has higher memory overhead per element due to the node pointers.

内容的提问来源于stack exchange，提问作者Alex Vulchev