What is the internal data structure of java.util.LinkedList, and how does it differ from ArrayList?
answer
- Doubly-linked nodes vs contiguous array
- Node = value + prev + next references
- first/last pointers + size field
- Array = index math; list = pointer chasing
- More memory per element + cache misses
basics
~20 sLinkedList stores each element in a separate node that points to the next and previous nodes (a doubly-linked list). ArrayList stores elements in a single backing array. So LinkedList chases pointers; ArrayList uses index math.
solid answer
~40 sjava.util.LinkedList is a doubly-linked list: every element lives in its own Node object holding the value plus references to the previous and next nodes. The list keeps first and last pointers and a size counter. ArrayList instead wraps a contiguous Object[] array and grows it (about 1.5x) when full. The consequence is access pattern: ArrayList gives O(1) random access by index via direct array offset, while LinkedList must walk the chain from the nearer end, costing O(n). Conversely, LinkedList can insert or remove at a known node (or either end) in O(1) without shifting, whereas ArrayList must shift elements. LinkedList also uses more memory per element because each node carries two extra references plus object overhead.
go deeper
Knows LinkedList uses nodes/pointers and ArrayList uses an array, and that get(i) is slow on a LinkedList.
Can state the Big-O for access vs insert for both, explains doubly-linked nodes with prev/next, and knows ArrayList is the usual default.
Discusses cache locality, per-node memory overhead, amortized resize cost, and why ArrayList often wins benchmarks despite same asymptotic class.
Frames the choice in terms of measured access patterns and GC/allocation pressure, and steers teams toward ArrayList/ArrayDeque, treating LinkedList as a niche tool.
## What a list is A *List* in Java is an ordered collection where each element has a position (index 0, 1, 2, ...) and duplicates are allowed. `java.util.List` is the interface; `ArrayList` and `LinkedList` are two implementations that make different internal trade-offs. ## What 'data structure' means here The *data structure* is the concrete way the elements are laid out in memory. This is the single biggest difference between the two classes. ### ArrayList: a backing array ArrayList stores its elements in one contiguous block of memory called an array (`Object[] elementData`). 'Contiguous' means the slots sit next to each other, so the address of element *i* is simply `base + i * slotSize`. Computing that address is pure arithmetic, so reading `list.get(i)` is **O(1)** — constant time, independent of list size. When the array fills up, ArrayList allocates a bigger array (roughly 1.5x) and copies everything over; that occasional copy is *amortized* away over many cheap appends. ### LinkedList: a doubly-linked list LinkedList stores each element in its own small object called a **node**. Each node holds three things: the element value, a reference (pointer) to the **next** node, and a reference to the **previous** node. 'Doubly-linked' means each node points both forward and backward, so you can walk the list in either direction. The list object itself keeps a `first` pointer, a `last` pointer, and a `size` field. Because nodes are separate objects, they can sit anywhere in memory; they are connected only by the references. There is no array and no index math. To reach the element at position *i* you must start at `first` (or `last`, whichever is nearer) and follow `next`/`prev` references *i* times. That walk is **O(n)** — proportional to how far in you go. ## Why the difference matters - **Random access (`get(i)`):** ArrayList O(1); LinkedList O(n). - **Insert/remove at a known position:** LinkedList O(1) (just relink a few pointers — no shifting); ArrayList O(n) in the middle (must shift later elements). - **Memory:** LinkedList costs more per element. Each node is a heap object with header overhead plus two references (prev/next). ArrayList stores just the element references packed in one array. - **Cache behavior:** ArrayList's contiguous memory is CPU-cache-friendly (the hardware pre-fetches neighbors). LinkedList nodes are scattered, so traversal causes more cache misses — which is why ArrayList usually wins in practice even for sequential iteration. ## Key terms - **Node:** a wrapper object holding one value plus links to neighbors. - **Pointer/reference:** in Java, a variable that refers to another object. - **O(1) / O(n):** Big-O notation; O(1) = constant time, O(n) = grows linearly with size. - **Amortized:** averaged over many operations (ArrayList's resize cost). ## Bottom line ArrayList = array under the hood, great for indexing and iteration. LinkedList = chain of nodes, only worth it when you constantly add/remove at the ends or at an iterator's current position. In modern Java, ArrayList or ArrayDeque is the default choice for almost everything; LinkedList is rarely the best tool.
- Why does ArrayList usually iterate faster than LinkedList even though both are O(n)?ArrayList's elements are contiguous in memory, so the CPU cache pre-fetches neighbors and there are no per-element object dereferences. LinkedList nodes are scattered on the heap, causing cache misses and an extra pointer chase per element, so the constant factor is much larger.
- How much extra memory does a LinkedList node add over an ArrayList slot?An ArrayList slot is essentially one reference. A LinkedList node is a separate heap object: object header plus the element reference plus prev and next references — roughly 24 bytes of overhead per element on a typical 64-bit JVM, versus about 4-8 bytes per ArrayList slot.
ArrayList is a numbered row of lockers — jump straight to locker 50. LinkedList is a treasure hunt where each clue points to the next (and previous) hiding spot — to reach the 50th clue you must follow 49 of them first.
saying these in an interview costs you the question
- Saying LinkedList is singly-linked — java.util.LinkedList is doubly-linked
- Claiming LinkedList allows O(1) random access by index
- Thinking LinkedList is generally faster than ArrayList because 'no resizing'
- Confusing get(i) cost (O(n)) with add-at-end cost (O(1))