Data Struct operations Flashcards
1
Q
Avg. Access Array
A
O(1)
2
Q
Avg. Search Array
A
0(n)
3
Q
Avg. Insertion Array
A
O(n)
4
Q
Avg. Deletion Array
A
O(n)
5
Q
Avg. Access Singly Linked List
A
O(n) - have to loop to n
6
Q
Avg. Search Singly Linked List
A
O(n) - have to loop to n
7
Q
Avg. Insertion Singly Linked List (insert @ end)
A
O(1) - add a new node/ append to end
8
Q
Avg. Insertion Singly Linked List (insert @ index)
A
O(n) - have to loop to index, then insert value
9
Q
Avg. Delete Singly Linked List (delete @ end)
A
O(1) - delete the end node
10
Q
Avg. Delete Singly Linked List (delete @ index)
A
O(n) - have to loop to index, then delete value
11
Q
Hash Table Access
A
O(1)
12
Q
Hash Table Search
A
O(1)
13
Q
Hash Tabe Insert
A
O(1)
14
Q
Hash Table Delete
A
O(1)
15
Q
Adavantages of Linked List
A
- have a constant insert and delete (only at ends)
- good if you don’t know how many items are in list
- if you don’t need random access
- you need to insert in the middle of a list.
