ArrayLists and LinkedLists in Java
Introduction to Lists in Java
Lists are ordered collections that allow duplicates. Java provides several implementations, including
ArrayList and LinkedList.
Both are part of the [Link] package and implement the List interface.
ArrayList
Definition: A resizable array implementation of the List interface.
Underlying Structure: Uses a dynamically resizing array to store elements.
Performance Characteristics:
- Access (get/set): O(1), as elements can be accessed directly by index.
- Insertion at end: O(1), except when resizing is needed (then it's O(n)).
- Insertion/Removal at specific index: O(n), due to shifting elements.
Usage Scenarios:
- Good when frequent access by index is needed.
- Less efficient for frequent insertions or deletions, especially at the beginning or middle.
Example:
List<String> arrayList = new ArrayList<>();
[Link]("Apple");
[Link]("Banana");
[Link](1); // Returns "Banana"
LinkedList
Definition: A doubly-linked list implementation of the List and Deque interfaces.
Underlying Structure: Consists of nodes where each node holds a reference to the previous and
next node.
Performance Characteristics:
- Access: O(n), as traversal from the start or end is required.
- Insertion/Deletion at beginning or end: O(1), due to the Deque nature.
- Insertion/Removal at specific index: O(n), as it requires traversal.
Usage Scenarios:
- Preferred when frequent insertions or deletions at the beginning or middle are required.
- Less efficient for random access by index.
Example:
List<String> linkedList = new LinkedList<>();
[Link]("Apple");
[Link]("Banana");
[Link](0); // Removes "Apple"
Key Differences Between ArrayList and LinkedList
- Underlying Data Structure: Array vs. Linked Nodes.
- Access Time: ArrayList provides constant-time access; LinkedList requires traversal.
- Insertion and Deletion: LinkedList is generally faster for insertions and deletions, especially at
the beginning or middle.
- Memory Overhead: LinkedList requires more memory per element (due to storing node
references).
Choosing Between ArrayList and LinkedList
Use ArrayList if:
- You need fast random access by index.
- Insertion and deletion are primarily at the end.
Use LinkedList if:
- You need frequent insertions or deletions at the start or middle.
- Accessing elements by index is less frequent.
Example Comparisons
Adding Elements:
- Adding 1,000,000 elements to the end of ArrayList vs. LinkedList.
Removing Elements:
- Removing from the start of ArrayList vs. LinkedList.
Code Example Comparing ArrayList and LinkedList
List<String> arrayList = new ArrayList<>();
List<String> linkedList = new LinkedList<>();
// Measure time to add 1,000,000 elements
long start = [Link]();
for (int i = 0; i < 1000000; i++) {
[Link]("Element " + i);
long arrayListTime = [Link]() - start;
start = [Link]();
for (int i = 0; i < 1000000; i++) {
[Link]("Element " + i);
long linkedListTime = [Link]() - start;
[Link]("ArrayList add time: " + arrayListTime);
[Link]("LinkedList add time: " + linkedListTime);
Conclusion
Both ArrayList and LinkedList are powerful data structures but have different strengths.
Understanding the performance implications helps in choosing the right list for specific use cases.