Linked List

Question 1

Accessing the head?

Answer 1

O(1)

Question 2

Accessing the tail? (2)

Answer 2

1. O(N) without a reference to the tail.

2. O(1) with a reference to the tail.

Question 3

Accessing a middle node?

Answer 3

O(N)

Question 4

Inserting or Removing the head?

Answer 4

O(1)

Question 5

Inserting or Removing the tail? (2)

Answer 5

1. O(N) to access + O(1) to insert/remove. Without a stored tail reference.
2. O(1) to insert/remove. With a stored tail reference.

Question 6

Inserting or Removing a middle node?

Answer 6

1. O(N). O(N) to access + O(1) to insert/remove.

Question 7

Searching for a value?

Answer 7

O(N)