CODEWITHSUNDEEP
javaalgorithmlinked-listtime-complexity
Sean Hill
Sean Hill

Reputation: 1327

Why do we say linked list inserts are constant time?

I understand that linked list insertions are constant time due to simple rearrangement of pointers but doesn't this require knowing the element from which you're doing the insert?

And getting access to that element requires a linear search. So why don't we say that inserts are still bound by a linear search bottleneck first?

Edit: I am not talking about head or tail appends, but rather insertions anywhere in between.

Upvotes: 1

Views: 2532

Answers (3)

Arun
Arun

Reputation: 20383

The following two operations are different:

  • Operation A: Insert anywhere in the linked list

  • Operation B: Insert at a specific position in the linked list

Operation A can be achieved in O(1). The new element can inserted at head (or tail if maintained and desired).

Operation B involves finding followed by inserting. The finding part is O(n). The inserting is as above, i.e. O(1). If, however, the result of the finding is provided as input, for example if there are APIs like

Node * Find(Node * head, int find_property);
Node * InsertAfter(Node * head, Node * existing_node, Node * new_node);

then the insert part of the operation is O(1).

Upvotes: 1

Andreas
Andreas

Reputation: 159096

Why do we say linked list inserts are constant time?

Because the insert operation is constant time.

Note that locating the position of the insert is not considered part of the insert operation itself. That would be a different operation, which may or may not be constant time, e.g. if including search time, you get:

  • Insert at head: Constant
  • Insert at tail: Constant
  • Insert before current element while iterating1: Constant
  • Insert at index position: Linear

1) Assuming you're iterating anyway.

By contrast, ArrayList insert operation is linear time. If including search time, you get:

  • Insert at head: Linear
  • Insert at tail: Constant (amortized)
  • Insert before current element while iterating1: Linear
  • Insert at index position: Linear

Upvotes: 4

user555045
user555045

Reputation: 64904

Yes, it requires already having a node where you're going to insert next to.

So why don't we say that inserts are still bound by a linear search bottleneck first?

Because that isn't necessarily the case, if you can arrange things such that you actually do know the insertion point (not just the index, but the node).

Obviously you can "insert" at the front or end, that seems like a bit of cheat perhaps, it stretches the meaning of the word "insert" a bit. But consider an other case: while you're appending to the list, at some point you remember a node. Just any node of your choosing, using any criterium to select it that you want. Then you could easily insert after or before that node later.

That sounds like a very "constructed" situation, because it is. For a more practical case that is a lot like this (but not exactly), you could look at the Dancing Links algorithm.

Upvotes: 5

Related Questions