ArrayList vs. LinkedList

Cheatsheet Content

1. Overview of Collections Both ArrayList and LinkedList implement the List interface in Java. They provide ordered collections of elements, allowing duplicates. The primary difference lies in their underlying data structures and performance characteristics for various operations. 2. ArrayList 2.1 Underlying Data Structure Implemented using a dynamic array. Elements are stored in contiguous memory locations. When the array is full, a new, larger array is created, and elements are copied. 2.2 Performance Characteristics Access ( get(index) ): $O(1)$ - direct access by index due to contiguous memory. Add to End ( add(E e) ): Amortized $O(1)$ - usually constant, but $O(N)$ when resizing occurs. Add to Middle ( add(index, E e) ): $O(N)$ - elements after the insertion point must be shifted. Remove from End ( remove(size-1) ): $O(1)$. Remove from Middle ( remove(index) ): $O(N)$ - elements after the removal point must be shifted. Iteration: Fast, $O(N)$ using an iterator or for-each loop. Memory Usage: Can be less memory efficient if capacity is much larger than actual size, or more efficient due to less overhead per element compared to LinkedList . 2.3 Use Cases When frequent random access (getting elements by index) is required. When adding/removing elements mostly occurs at the end of the list. Good choice for most general-purpose list implementations. 3. LinkedList 3.1 Underlying Data Structure Implemented using a doubly linked list. Each element (node) stores the data and references (pointers) to the next and previous nodes. Elements are not stored in contiguous memory. 3.2 Performance Characteristics Access ( get(index) ): $O(N)$ - requires traversing the list from the beginning or end to reach the $N$-th element. Add to End ( add(E e) ): $O(1)$ - direct access to the tail node. Add to Middle ( add(index, E e) ): $O(N)$ - requires traversing to the insertion point, then $O(1)$ for insertion. Remove from End ( remove(size-1) ): $O(1)$ - direct access to the tail node. Remove from Middle ( remove(index) ): $O(N)$ - requires traversing to the removal point, then $O(1)$ for removal. Add/Remove to Front ( addFirst() , removeFirst() ): $O(1)$ - direct access to the head node. Iteration: $O(N)$ using an iterator or for-each loop. Memory Usage: Higher memory overhead per element due to storing next/previous references. 3.3 Use Cases When frequent insertions or deletions are required in the middle of the list. When frequent additions or removals occur at the beginning or end of the list (can act as a queue or stack). When random access is rare. 4. Comparison Table Feature ArrayList LinkedList Data Structure Dynamic Array Doubly Linked List Random Access ($get(index)$) $O(1)$ $O(N)$ Add/Remove at End Amortized $O(1)$ / $O(1)$ $O(1)$ Add/Remove at Middle $O(N)$ $O(N)$ (traversal) + $O(1)$ (insertion) Memory Less overhead per element, but potential wasted space. More overhead per element (pointers). Contiguous Memory Yes No Implements List , RandomAccess List , Deque 5. When to Choose Which Choose ArrayList if: You need fast random access to elements. You mostly add/remove elements at the end. Memory is a concern and you want to minimize overhead per element. Choose LinkedList if: You frequently add or remove elements from the beginning or middle of the list. You intend to use it as a queue (FIFO) or stack (LIFO). Random access is not a primary requirement.