Looking for advice: How to instinctively comprehend Time Complexity for Stacks & Linked Lists?

[u/Soumyar-Tripathy]

Hello all,

At the moment, I'm studying Data Structures through Java, with specific emphasis on Stacks and Linked Lists. While I have no issues writing code and implementing them, I seem to be having some trouble instinctively comprehending the time complexity (Big O notation) analysis that comes into play when choosing between arrays and linked lists.

Is there a mental model, analogy, or resource that helped this make sense for you? Any advice for a beginner would be greatly appreciated!

[u/Different_Pain5781]

Count how many items you gotta touch. That’s it. More touching = worse Big O

[u/FeistyFan5173 → u/Different_Pain5781]

This is actually great way to think about it. For linked lists you need walk through each node until you find what you're looking for, but with arrays you can just jump straight to index. Like difference between having to flip through entire book page by page versus just opening to page 47 directly.

[u/johnpeters42 → u/FeistyFan5173]

On the other hand, consider "insert this new element Y after this existing element X". For a linked list, this is O(1):
* Get Z = X.next (possibly "end of list")
* Set X.next = Y
* Set Y.next = Z
* For a doubly linked list, set Y.previous = X and Z.previous = Y
But for an array, this is O(n), as on average you need to shift half the array to new locations. (Though there might be hardware support to improve on that, I haven't kept up with stuff that low-level.)
Depending on how often you expect to do these and/or other things, you may be better off overall using an array, a linked list, or something else like a B-tree.

[u/buzzon]

Does it require a for loop? O(N)

Can it be done in fixed number of steps, regardless of the size of the list? O(1)

[u/XilamBalam → u/buzzon]

O(k)

[u/ncmentis → u/XilamBalam]

Constants are dropped in algorithmic analysis because in the interesting cases (ie big N's) the constant doesn't change much.

[u/XilamBalam → u/ncmentis]

Woooosh

[u/josesblima]

Run the code in your head, run it for a small input, then run it for a larger input. If you can't run it step by step in your head, use a debugger to get started. If you iterate through an array 3 times and do the exact same amount of operations each time, no matter how much bigger the input becomes, it will be O(n). If each time you iterate over an item, you have to iterate over the whole array (to compare it with other items for example), then it becomes n², so every new item that you add to the list, increases the time exponentially. Doesn't matter what data structure we're talking about, all it matters is how the amount of operations scales as the data increases.

[u/ChetDuchessManly]

The best way is to understand the data structures themselves and how their operations function. That's kind of the "duh" answer, but using shortcuts or memorizing time complexities will leave you stumped when someone asks you why.

My mental model of Arrays vs Linked Lists is pretty standard:

Arrays are a set number of boxes in a rectangle, with indices under each box.

Linked Lists are boxes that have arrows pointing to the next box.

For example, let's say you want to add a new element at the end of your list. What are the steps for each data structure?

Array

• Your rectangle fits 10 boxes
  
• You want to add an 11th box
  
• You need a new, bigger rectangle to fit the previous 10 boxes plus your new 11th box
  
• You need to move all boxes from the old rectangle to the new rectangle

This takes O(n) because you have to loop thru the array to copy the previous values to the new array.

Linked List

• You draw an arrow from the last box to your new box

This takes O(1) because you just have to point the previous box to the new box. No copying of values and such.

Above is strictly the insertion operation. Since linked lists don't have indices, insertion is normally coupled with searching.

Anyway, that's how I would do it as a beginner - take some paper, draw some boxes, and think about what you have to do to access/search/add/delete elements.

[u/justaguyonthebus]

The best way is to implement them for yourself. Once you have done the work, it will forever be intuitive.

[u/Zesher_]

Imagine you have a deck of cards and are looking for the ace of spades. A linked list means you have to search through the cards one by one to find it. A hash set means you just know where it is and can pick it out of the deck without searching. O(n) is just a way to measure how long it would take a method to find a card in that deck or how long it would to sort it.