Singly Linked List

Queues

Data
Structures
CHEAT SHEET

Time Complexity

Arrays
 Arrays
Time Complexity
Description
"n" represents the number of elements in the array.
An array is a collection of elements identified by index or
key values. The elements are stored contiguously in memory.
Operation Time Complexity
Access O(1)
Visualization Search O(n)
arr[0] arr[1] arr[2] arr[3] arr[4] arr[5] arr[6] Insertion O(n)
8 10 12 7 19 4 8 Deletion O(n)
Array Indices 0 1 2 3 4 5 6

Space Complexity Notable Usages

O(n) Efficient random access.
Contiguous memory allocation.

Singly Linked List

Description
A singly linked list contains nodes which have a data part and an address part, i.e., next, which points to the next node in the order of
sequence of nodes.

Visualization

20 0x7FFD9518 34 0x8EFD9218 8 0x0FAD9518 12 0x7AAD8528

Head
Node's Data
Single Node
Next Node Address 98 NULL

Time Complexity Space Complexity

"n" represents the number of nodes in the Singly Linked List. O(n)

Operation Time Complexity

Access O(n)
Search O(n)
Notable Usages
Insertion O(1) Dynamic memory allocation.
Deletion O(1) Efficient insertion and deletion at the beginning.

01 Data Structure Cheatsheet

 Doubly Linked List
Description
In a doubly linked list, each node contains data and two links, the first link points to the previous node and the next link points to the
next node in the sequence.

Visualization

Notice these two values are same!! Notice these two values are same!!

NULL 20 0x7FFD9518 0x8EFD9218 56 0x0FAD9518

Head
Nodeʼs Data

Previous Node Next Node

Address Address

0x7FFD9518 17 0x7AAD8528 0x0FAD9518 6 NULL

Single Node

Time Complexity Space Complexity

"n" represents the number of nodes in the Doubly Linked List. O(n)

Operation Time Complexity

Access O(n)
Notable Usages
Search O(n)
Insertion O(1) Bi-directional traversal.
Deletion O(1) Efficient deletion of a node.

02 Data Structure Cheatsheet

 Stacks

Description Visualization
A stack is a linear data structure that follows the LIFO
Push Pop
(Last In First Out) principle. It has two main operations: D D
push and pop.

Top D D
Time Complexity
C Top C
"n" represents the number of elements in the Stack.
B B

Operation Time Complexity A A

Access O(n)
Search O(n)
Insertion O(1)
Deletion O(1) Notable Usages
Function call management.
Undo/Redo operations.
Space Complexity
O(n)

Queues

Description Visualization
A queue is a linear data structure that follows the FIFO
(First In First Out) principle. It mainly has two operations:
enqueue and dequeue.
Dequeue
Enqueue E D C B A

Time Complexity
Back Front
"n" represents the number of elements in the Queue. E A

Operation Time Complexity

Access O(n)
Search O(n)
Insertion O(1)
Deletion O(1) Notable Usages

Job scheduling.
Breadth-first search.
Space Complexity
O(n)

03 Data Structure Cheatsheet

 Binary Tree

Description Visualization
A binary tree is a tree-type non-linear data structure with a
maximum of two children for each parent. 20

8 22

Time Complexity
4 12
"n" represents the number of nodes in the binary tree.

Two children nodes

Operation Time Complexity 10 14
of node 20
Access O(n)
Search O(n)
Insertion O(n)
Deletion O(n) Notable Usages
Hierarchical data representation.
Quick searching and sorting.
Space Complexity
O(n)

Binary Search Tree

Description Visualization
A binary search tree, also known as an ordered or sorted binary
tree, is a rooted binary tree whose internal nodes each store a key
8 8 is greater than all the nodes in its left
greater than all the keys in the node's left subtree and less than
subtree. 8 is less than all the nodes in its
those in its right subtree.
right subtree
4 10

Worst Case Time Complexity

2 6 9
"n" represents the number of nodes in the binary search tree.

All nodes in a binary search tree

Operation Worst Case Time Complexity 5
adhere to this property.
Access O(n)
Search O(n)
Insertion O(n)
Deletion O(n)

Space Complexity
O(n)

04 Data Structure Cheatsheet

 Demonstration of Search operation
Find 5
8 pointer 8 8
As 8 > 5, go left.

4 10 pointer 4 10 4 10
As 4 < 5, go right.

2 6 9 2 6 9 2 6 9

pointer
5 5 5 As 6 > 5, go left.

4 10

2 6 9

5 Got it!

Notable Usages
Efficient searching.
In-order traversal.

05 Data Structure Cheatsheet

 AVL Tree
Description
An AVL tree is a self-balancing binary search tree. For every node, the difference between the heights of the left and right subtrees is
at most one.

Visualization
Concept of Left Rotation
2 2
4 4
Go up
(Left rotation) 1
1 1 6
6 6
0 0
0 0 4 8
8 8

Unbalanced tree Left Rotation Balanced Tree

due to node 4

Concept of Right Rotation

2 2
4 Go up 4
(Right rotation)
1 1 1
2 2 2

0 0
0 0 1 4
1 1

Unbalanced tree Right Rotation Balanced Tree

due to node 4

Concept of Left-Right Rotation

2 2 2
4 4 4
Right Rotation
1 1 1 1
2 2 3 3
Left rotation
0 0
0 0
3 0 2 4
3 2

Unbalanced tree Left Rotation Right Rotation Balanced Tree

due to node 4

Concept of Right-Left Rotation

2 2 2
4 4 4
Left Rotation
1 1 1 1
6 6 5 5
Right Rotation
0 0
0 0
5 0 4 6
5 6

Unbalanced tree Right Rotation Left Rotation Balanced Tree

due to node 4

06 Data Structure Cheatsheet

 Let's understand insertion in AVL tree: Create an AVL tree using 8, 12, 20, 10.

Insert 8
0 Insert 12 1 Insert 20 2
8 8 8

(Balanced) 0 1
12 12

(Balanced)
0
20

(Unbalanced due to Node 8)

Left Rotation

1 1
12 12
Insert 10
0 0 1 0
8 20 8 20
0
(Balanced)
10

Final AVL Tree

Time Complexity Notable Usages

"n" represents the number of nodes in the AVL tree. Self-balancing property.
Efficient searching and insertion.
Operation Time Complexity
Access O(log n)
Search O(log n)
Insertion O(log n)
Deletion O(log n)

Space Complexity
O(n)

07 Data Structure Cheatsheet

 HashTable

Description
A hash table, also known as a hash map, is a data structure that provides efficient key-value pair storage and retrieval.
It uses a hash function to compute an index, called a hash code, which maps the key to a specific location in the underlying array.

Visualization of Chained Hash Table

HashTable-Size = 5 NULL
HashTable function: h(key) = key % 5
NULL

NULL

NULL

NULL

Let's insert the following keys into the hashtable.

17
43
2
34
43
98
10

Insert 17

h(17) = 17 % 5 = 2 ---------> Insert it into index 2

NULL

NULL
0x7FFD9518 17 NULL
NULL

NULL

Insert 43

h(43) = 43 % 5 = 3 ---------> Insert it into index 3

NULL

NULL
0x7FFD9518 17 NULL
0x8EFA9528 43 NULL
NULL

08 Data Structure Cheatsheet

 Insert 2

h(2) = 2 % 5 = 2 ---------> Insert it into index 2

NULL Chaining starts..

NULL
0x7FFD9518 17 0x7AAD8528 2 NULL
0x8EFA9528 43 NULL
NULL

Insert 34

h(34) = 34 % 5 = 4 ---------> Insert it into index 4

NULL

NULL
0x7FFD9518 17 0x7AAD8528 2 NULL
0x8EFA9528 43 NULL
0x8ACA6512 34 NULL

Insert 98

h(98) = 98 % 5 = 3 ---------> Insert it into index 3

NULL

NULL
0x7FFD9518 17 0x7AAD8528 2 NULL
0x8EFA9528 43 0x7AAD8528 98 NULL
0x8ACA6512 34 NULL

Insert 10

h(10) = 10 % 5 = 0 ---------> Insert it into index 0

0x1B2C2924 10 NULL
NULL
0x7FFD9518 17 0x7AAD8528 2 NULL
0x8EFA9528 43 0x7AAD8528 98 NULL
0x8ACA6512 34 NULL

09 Data Structure Cheatsheet

 Time Complexity
"n" represents the size of hash table and "k" represents the average number of elements in each chain (linked list).

Operation Best Case Time Complexity Average Case Time Complexity Worst Case Time Complexity
Search O(1) O(1+k) O(n)
Insertion O(1) O(1+k) O(n)
Deletion O(1) O(1+k) O(n)

Space Complexity Notable Usages

O(n + m) where n is the size of Fast data retrieval.
hashtable and m is the number of Key-value storage.
elements inserted.

Trie

Description
A trie is a tree-like data structure used for efficient retrieval and storage of strings. It organizes strings by their characters in a
tree-like structure, making it ideal for tasks such as autocomplete, spell-checking, and searching for words with a common prefix.

Visualization of Trie
Let's create a trie out the following strings:

1. a
2. any
3. the
4. there
5. their
6. annoy

(root)

Insert "a"

(root)

Insert "any"

10 Data Structure Cheatsheet

 (root)

Insert "the"
(root)

a t

n h

y e

Insert "there" Insert "their" Insert "annoy"

(root) (root) (root)

a t a t a t

n h n h n h

n
y e y e y e

r r i r i

e e r e r

Note: All green nodes are leaf nodes representing the tail of a word from the root.

11 Data Structure Cheatsheet

 Time Complexity Notable Usages
"n" represents the length of the key/string under operation.
Efficient prefix searching.
Autocomplete suggestions.
Operation Time Complexity
Search O(n)
Insertion O(n)
Deletion O(n)

Space Complexity
O(n * m) where n is the maximum length
of a key and m is the number of keys
inserted.

12 Data Structure Cheatsheet