Yige

Yige

Build
HomeArchives作品集

ArrayList and LinkedList

#Java基础38
AI Translation
This post is translated from Chinese into English through AI.View Original
AI-generated summary
The document discusses the differences between `ArrayList` and `LinkedList` in Java. ### ArrayList - **Overview**: Inherits from `AbstractList` and implements the `List` interface. It functions as a dynamic array with methods for adding, removing, modifying, and traversing elements. It supports serialization. - **Time Complexity**: Provides constant time complexity for operations like `size`, `isEmpty`, `get`, and `set`. Adding or removing elements has a time complexity of O(N). - **Capacity**: Each `ArrayList` has a capacity that starts at 10 and can grow automatically. The `ensureCapacity()` method can be used to pre-allocate space. - **Thread Safety**: Not thread-safe; alternatives include `Vector`, `CopyOnWriteArrayList`, or wrapping with `Collections.synchronizedList`. ### LinkedList - **Overview**: Implemented as a doubly linked list, maintaining head and tail pointers. - **Comparison with ArrayList**: `LinkedList` is more efficient for insertions and deletions, while `ArrayList` is faster for accessing elements by index. `LinkedList` uses more memory due to its pointers. ### Key Considerations 1. Insertions and deletions in `ArrayList` can be fast if done at the end. 2. `ArrayList` is generally faster for traversal due to memory locality. 3. `ArrayList` expands its capacity by 1.5 times when needed. 4. The maximum size of an `ArrayList` is `Integer.MAX_VALUE - 8` due to metadata storage. 5. `ArrayList` is not thread-safe; use alternatives for concurrent access. 6. Using arrays as queues can be inefficient due to data movement, but fixed-size arrays work well in certain implementations. 7. Differences between arrays and `ArrayList`: arrays can hold primitive types and have fixed sizes, while `ArrayList` is dynamic and

ArrayList && LinkedList#

ArrayList#

1. Overview:#

  • Inherits from AbstractList and implements the List interface; it is an array queue that provides related functions for adding, deleting, modifying, and traversing.
  • Besides the list interface, this class provides a method to manipulate the size of the array to store the size of the array in the list.
  • Implements the Serializable interface, which means ArrayList supports serialization and can be transmitted through serialization.

1. Time Complexity:#

  • ArrayList implements the RandomAccess interface, providing random access functionality.
  • The calls to methods size, isEmpty, get, set, iterator, and listIterator are constant time.
  • The time complexity for adding and deleting is O(N). All other operations also have linear time complexity.

2. Capacity:#

  • Each ArrayList has a capacity, which is at least the length of the List elements, initialized to 10 by default, and the capacity can grow automatically.
  • If you know in advance that there will be many array elements, you can increase the capacity in advance by calling the ensureCapacity() method to reduce the overhead of automatic capacity growth later.
  • You can also initialize this capacity using a constructor with an initial capacity.

3. Thread Safety:#

  • ArrayList is not thread-safe; in multi-threaded scenarios, you can choose Vector or CopyOnWriteArrayList, or use Collections.synchronizedList to wrap a regular ArrayList into a thread-safe version of an array container.

2. LinkedList#

Internally implemented using a doubly linked list, retaining two pointers for the head and tail, along with other operations of LinkedList.

Differences between ArrayList and LinkedList#

  • LinkedList implements the List and Deque interfaces, generally referred to as a doubly linked list; ArrayList implements the List interface, which is a dynamic array.
  • LinkedList is more efficient for inserting and deleting data, while ArrayList is more efficient for retrieving data at a specific index.
  • LinkedList requires more memory than ArrayList because it needs to maintain two pointers for the previous and next nodes.

3. Thoughts#

1. Is inserting and deleting in ArrayList always slow?#

Not necessarily; it depends on how far the insertion or deletion position is from the end of the array. For example, if you insert at the end, the time complexity is O(1).

2. How does the performance of traversing ArrayList compare to LinkedList?#

In terms of traversal, ArrayList is much faster than LinkedList. The biggest advantage of ArrayList in traversal is memory continuity, as the CPU's internal cache structure can cache contiguous memory segments, significantly reducing the performance overhead of reading memory.

3. How does ArrayList expand its capacity?#

Taking adding elements as an example, the calculateCapacity() method first calculates the required capacity, and the ensureExplicitCapacity method internally calls the grow method for expansion. The specific implementation of the grow method is:

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // Expand to 1.5 times the original capacity
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // Check if the new capacity is sufficient; if not, use minCapacity as the capacity size
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // If the preset value exceeds the default maximum value, check for overflow
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // Point the array to the new contiguous memory space of newCapacity and copy data
    elementData = Arrays.copyOf(elementData, newCapacity);
}

4. Why is the default maximum array size of ArrayList Integer.MAX_VALUE - 8?#

Array objects have an additional metadata overhead to represent the size of the array, which requires an extra 8 bytes to store this metadata.

5. Is ArrayList thread-safe?#

ArrayList is not thread-safe; in multi-threaded scenarios, you can choose Vector or use Collections.synchronizedList to wrap a regular ArrayList into a thread-safe version of an array container. The principle is similar, both directly use synchronized for locking. CopyOnWriteArrayList is thread-safe and implements a read-write separation mechanism, suitable for scenarios with many reads and few writes. For more details, refer to: CopyOnWriteArrayList Implementation Principle and Source Code Analysis.

6. Is an array suitable for use as a queue?#

Queues are generally FIFO. If you use ArrayList as a queue, you would need to append data at the end of the array and remove data from the front, and vice versa. However, in any case, at least one operation will involve moving data within the array, which is performance-intensive.
However, a fixed-length array is quite suitable, such as ArrayBlockingQueue, which is internally implemented as a circular queue using a fixed-length array. Additionally, the well-known Disruptor open-source library also implements a high-performance queue using a circular array.

7. What are the differences between Array and ArrayList? When should I use Array instead of ArrayList?#

  • An Array can contain both primitive types and object types, while ArrayList can only contain object types.
  • The size of an Array is fixed, while the size of an ArrayList is dynamic.
  • ArrayList provides more methods and features, such as: addAll(), removeAll(), iterator(), etc.

4. Reference Links#

Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.