Scribd
Upload
309 views2 pages

Java Data Structures Operation Speeds

This document provides a cheat sheet comparing the speed of common operations for different data structures, including arrays, lists, collections, linked lists, stacks, queues, and dictionaries. It lists the time complexity for adding and removing elements from different positions within each data structure, as well as for random access, in-order traversal, and searching. Notes are provided on the memory efficiency and typical use cases for each data structure.

Uploaded by

srini99
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
309 views2 pages

Java Data Structures Operation Speeds

This document provides a cheat sheet comparing the speed of common operations for different data structures, including arrays, lists, collections, linked lists, stacks, queues, and dictionaries. It lists the time complexity for adding and removing elements from different positions within each data structure, as well as for random access, in-order traversal, and searching. Notes are provided on the memory efficiency and typical use cases for each data structure.

Uploaded by

srini99
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
  • Cheat Sheet: Speed of Common Operations

Cheat Sheet: Speed of Common Operations

remove from end insert at middle remove from middle Random Access In-order Access Search for specific element

add to end

Notes

Array

O(n)

O(n)

O(n)

O(n)

O(1)

O(1)

O(n)

Most efficient use of memory; use in cases where data size is fixed. Implementation is optimized for speed. In many cases, List will be the best choice. List is a better choice, unless publicly exposed as API. Many operations are fast, but watch out for cache coherency. Shouldn't be selected for performance reasons, but algorithmic ones. Shouldn't be selected for performance reasons, but algorithmic ones. Although in-order access time is constant time, it is usually slower than other structures due to the

List<T>

best case O(1); worst case O(n) best case O(1); worst case O(n)

O(1)

O(n)

O(n)

O(1)

O(1)

O(n)

Collection<T >

O(1)

O(n)

O(n)

O(1)

O(1)

O(n)

LinkedList<T >

O(1)

O(1)

O(1)

O(1)

O(n)

O(1)

O(n)

Stack<T>

best case O(1); worst case O(n) best case O(1); worst case O(n) best case O(1); worst case O(n)

O(1)

N/A

N/A

N/A

N/A

N/A

Queue<T> Dictionary<K ,T>

O(1) O(1)

N/A best case O(1); worst case O(n)

N/A O(1)

N/A O(1)*

N/A O(1)*

N/A O(1)

over-head of looking up the key.

Cheat Sheet: Speed of Common Operations add to end remove from end insert at middle remove from middle Random Access In-o
over-head of looking up the key.

You might also like