Scribd
Upload
110 views2 pages

Data Structures Cheat Sheet

This document is a cheat sheet that summarizes common data structures like arrays, lists, stacks, queues, and dictionaries. It provides big O time complexities for common operations like adding/removing elements, accessing elements randomly or sequentially, and searching. The cheat sheet notes that arrays are most memory efficient when data size is fixed, while lists generally have the best performance. Linked lists allow fast insertion/removal but have slower random access than arrays. Stacks and queues are useful for their algorithmic properties rather than performance. Dictionaries have fast lookups but slower in-order access than other structures.

Uploaded by

Joy Rahman
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
110 views2 pages

Data Structures Cheat Sheet

This document is a cheat sheet that summarizes common data structures like arrays, lists, stacks, queues, and dictionaries. It provides big O time complexities for common operations like adding/removing elements, accessing elements randomly or sequentially, and searching. The cheat sheet notes that arrays are most memory efficient when data size is fixed, while lists generally have the best performance. Linked lists allow fast insertion/removal but have slower random access than arrays. Stacks and queues are useful for their algorithmic properties rather than performance. Dictionaries have fast lookups but slower in-order access than other structures.

Uploaded by

Joy Rahman
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Data Structures Cheat Sheet

1 of 2

https://www.clear.rice.edu/comp160/data_cheat.html

Data Structures Cheat Sheet


[Data Structures I] [Data Structures II] [Data Structures III] [Data Structures IV] [Data Structures Cheat Sheet]

add to
end

Array

O(n)

List<T>

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

Collection<T>

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

LinkedList<T>

O(1)

Stack<T>

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

Queue<T>

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

Dictionary<K,T>

best
case
O(1);
worst
case

remove
from
end

O(n)

O(1)

O(1)

O(1)

O(1)

insert at
middle

O(n)

O(n)

O(n)

O(1)

N/A

O(1)

N/A

O(1)

best
case
O(1);
worst
case

remove
from
middle

O(n)

O(n)

O(n)

O(1)

N/A

N/A

O(1)

Random
Access

O(1)

O(1)

O(1)

O(n)

N/A

N/A

O(1)*

In-order
Access

O(1)

O(1)

O(1)

O(1)

N/A

N/A

O(1)*

Search
for
specific
element

Notes

O(n)

Most efficient
use of
memory; use
in cases where
data size is
fixed.

O(n)

Implementation
is optimized for
speed. In
many cases,
List will be the
best choice.

O(n)

List is a better
choice, unless
publicly
exposed as
API.

O(n)

Many
operations are
fast, but watch
out for cache
coherency.

N/A

Shouldn't be
selected for
performance
reasons, but
algorithmic
ones.

N/A

Shouldn't be
selected for
performance
reasons, but
algorithmic
ones.

O(1)

Although
in-order
access time is
constant time,
it is usually
slower than
other
structures due

1/18/2017 3:40 PM

Data Structures Cheat Sheet

2 of 2

https://www.clear.rice.edu/comp160/data_cheat.html

O(n)

O(n)

to the
over-head of
looking up the
key.

1/18/2017 3:40 PM

You might also like