Linked Lists

Question 1

What is the algorithm for searching a linked list? And time complexity?

Answer 1

Question 2

What is the algorithm for inserting a node after a node? What is the time complexity?

Answer 2

Question 3

Deleting after node in linked list and time complexity

Answer 3

Question 4

Time complexity of delete (unordered singly linked list)

Answer 4

O(n)

Question 5

Time complexity of find (unordered singly linked list)

Answer 5

O(n)

Question 6

Time complexity of delete (ordered singly linked list)

Answer 6

O(n)

Question 7

Time complexity of find (unordered singly linked list)

Answer 7

O(n)

Question 8

Time complexity of add (unordered singly linked list)

Answer 8

O(1)

Question 9

Time complexity of delete (unordered singly linked list)

Answer 9

O(n)

Question 10

Time complexity of find (ordered singly linked list)

Answer 10

O(n)

Question 11

Time complexity of add (ordered singly linked list)

Answer 11

O(n) unless I have a pointer to the tail, then O(1)

Question 12

Time complexity of delete (ordered singly linked list)

Answer 12

O(n), unless I want to delete after a node then O(1)

Question 13

Are linked lists cache friendly?

Answer 13

Unlike arrays where items are always located next to each other in computer memory, linked list nodes can be scatterd all over.

Question 14

How do you use fast and slow runners to find linked list cycles?

Answer 14

• 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