Data Structures Review
Studied by 0 people
Learn
Practice Test
Spaced Repetition
Match
Flashcards1/20
Earn XP
Description and Tags
Flashcards for reviewing key concepts in data structures, including time complexity and properties of linked lists, trees, and arrays.
Name | Mastery | Learn | Test | Matching | Spaced |
|---|
No study sessions yet.
21 Terms
The worst-case running time to search in a singularly linked list with n items.
O(n)
Deleting the first node in a circular linked list with n items.
O(1) time
Deleting the first node in a singularly linked list with n items takes O(n) time
false
Insertion into a balanced BST with n items.
O(log n) time
The worst-case running time to search for a value in a 2D n x n array.
O(n²) time
Stacks can be used to reverse a list of objects
True
Maximum height of a 2-3 tree with n items.
log₂n
Union find can be used to determine if two items are connected
True
A singly linked list that only stores the reference to the front node can be transformed into a circular linked list in…
O(n) time because there needs to be a pointer sent to the end of the LL that can point to the head
A singly linked list that only stores the reference to the front node of the list can be reversed in…
O(n)
Binary Search can run on a Doubly Linked List in…
O(n) time since theres no random access, you have to traverse linearly through the LL to get to the middle point
The worst case time complexity to delete an arbitrary item on a Doubly Linked list is…
O(n)
If all elements are connected to each other
Given a parent[] array where parent[i] represents i's immediate parent, we can use union-find to determine…
Concatenating two doubly linked lists can be done in…
O(1)
Search time in an unsorted array
O(n)
Search time in an unsorted linked list
O(n)
Search time in a sorted array
O(log n)
Search time in a sorted linked list
O(n)
Search time in a regular BST
O(n)
Search time in a 2-3 Tree
O(log n)
Search time in a red-black BST
O(log n)