Java основы

30 карточек

1 / 30✓ 0✗ 0

mid

What is the difference in the internal implementation of ArrayList and LinkedList, and how does it affect performance?

нажми, чтобы перевернуть

midjava-basics

ArrayList uses a dynamic array with amortized O(1) insertion and O(1) index access. LinkedList is a doubly-linked list with O(1) insertion/deletion at the ends, but O(n) access and high memory overhead per node.

Memory Structure

ArrayList stores elements in a contiguous memory block (Object[]), providing excellent CPU cache locality. When the array fills up, it copies elements to a new array 50% larger (growth factor of 1.5x).

LinkedList consists of separate node objects (Node<E>), each storing references to the previous and next elements. This results in an overhead of ~24-32 bytes per element and memory fragmentation.

CPU caching prefers contiguous blocks. For most tasks, ArrayList is faster even with frequent middle insertions, as long as the collection size doesn't exceed a few thousand elements.

Состояния:

▸empty

▸growing

▸full

Когда да

Index-based reading, frequent iterations, predictable size, or data buffering.

Когда нет

Frequent insertions/deletions at the beginning/middle without using an iterator, or working under strict memory constraints.

Альт:VectorCopyOnWriteArrayListArrayDeque

Свайп вправо — знаю, влево — не знаю

ArchCase

ArchCase

Java основы

ArrayList uses a dynamic array with amortized O(1) insertion and O(1) index access. LinkedList is a doubly-linked list with O(1) insertion/deletion at the ends, but O(n) access and high memory overhead per node.

Memory Structure