Linked Lists Flashcards
What is the algorithm for searching a linked list? And time complexity?
![](https://s3.amazonaws.com/brainscape-prod/system/cm/344/477/312/a_image_thumb.png?1619794902)
What is the algorithm for inserting a node after a node? What is the time complexity?
![](https://s3.amazonaws.com/brainscape-prod/system/cm/344/477/775/a_image_thumb.png?1620220957)
Deleting after node in linked list and time complexity
![](https://s3.amazonaws.com/brainscape-prod/system/cm/344/477/822/a_image_thumb.png?1619795154)
Time complexity of delete (unordered singly linked list)
O(n)
Time complexity of find (unordered singly linked list)
O(n)
Time complexity of delete (ordered singly linked list)
O(n)
Time complexity of find (unordered singly linked list)
O(n)
Time complexity of add (unordered singly linked list)
O(1)
Time complexity of delete (unordered singly linked list)
O(n)
Time complexity of find (ordered singly linked list)
O(n)
Time complexity of add (ordered singly linked list)
O(n) unless I have a pointer to the tail, then O(1)
Time complexity of delete (ordered singly linked list)
O(n), unless I want to delete after a node then O(1)
Are linked lists cache friendly?
Unlike arrays where items are always located next to each other in computer memory, linked list nodes can be scatterd all over.
How do you use fast and slow runners to find linked list cycles?
- Every time slow runner moves 1 node, fast runner moves 2 nodes
- When slow runner is the same node as fast runner we’ve found a cycle
- Otherwise fast will hit the end of the linked list