# The Part About Linked Lists Being O(1) That Confused Me

The subject of linked lists and their O(1) insertion time has confused many, including the author of this account. The confusion stems from a single sentence: "Insertion is O(1) because you only need to change the pointers." While this is true if you already have a reference to the node, the real confusion arises when trying to locate the node in the first place.

Imagine a simple list: A → B → C → D. If you have a direct reference to node C, inserting a new node X after it is indeed a constant time operation. You would simply adjust the pointers: C.next = X and X.next = D. This operation is O(1), meaning it takes the same amount of time regardless of the size of the list.

However, if all you know is that there's a node containing the value C, you must first traverse the list to find it. In the worst-case scenario, you'd have to visit every node, which is an O(n) operation. This is the part that initially didn't click for the author.

The key distinction here is that finding the node is a separate operation from inserting a node. Linked lists do not inherently speed up finding things; they only make rearranging the structure cheap once you already have the node or reference. Therefore, when we say linked list insertion is O(1), there's often an unstated assumption: "Given a reference to the node."

This simple phrase changes the entire picture. Many Big-O explanations may not be entirely wrong; they just fail to mention the context. It's easy to overlook the importance of having a reference to the node you want to insert. This realization highlights how a lot of Big-O explanations can be misleading if they don't specify the context in which the O(1) time complexity applies.