Linked Lists
The time complexity of inserting a node at the end of a singly linked list.
O(n)
We need to store a collection of items where insertions and deletions can happen from both the front and the back in constant time.
Deque (Dynamic Array)
This type of linked list allows traversal in both directions.
Doubly linked list
A hospital has a check-in system that asks the patient to rate their pain. If their pain is really high they will have priority over those with lower pain. What data structure would be useful for quickly finding the next patient that is in the most pain?
Sorted Priority Queue
What are the names of the empty nodes at the front and end of a doubly linked list?
Sentinels
A music playlist is designed so that when the last song finishes, it loops back to the first song and continues playing in an infinite cycle.
Circular linked list
add_first(7), add_first(5), add_first(12), add_first(10), add_last(9), add_last(6), delete(10), delete(7)
How could we find the 3rd element? What is it without using eyeball algorithm.
Count iterations, 9
You are designing a way for planes to be added in line for landing based on how much fuel they have. Since there are so many planes, adding them to the line is more important than taking them out. Which data structure should be used?
Unsorted priority queue
Below is the code of a generator function for a singly linked list with an error. Identify the error and fix it.
def __iter__(self):
current = self.head
while current != None:
return current._element
current = current._next
yield current._element
A train ticket booking system needs a data structure that expands automatically when more bookings are made, allowing fast access to any reservation.
Dynamic array