Current Events > I know what a Linked List is

(+) Yeah! (+)

Start with a class for a node in the list, its data, and the next node it points to. Something like

Probably should have a "previous" too, unless that's some other structure.

figure out how to detect a loop in a linked list and congrats you can now pass many senior software developer interviews

Iterate, hashmap the pointer to the node (or just the referenced object, as long as it has object equality). Any collision on hashmap insert is a loop.

What's the runtime complexity? Can you do it more efficiently?

But I have no clue how the fuck I'm supposed to make one

You don't. Just use the built in one.

Or use a reference if whatever you're using doesn't have a built in list.

Tbh linked lists are rarely the best choice of data structure. Most of the time a contiguous resizable vector (already implemented in the standard libraries of most languages these days) is superior in almost every way.

Linked list is easier to insert something g into the middle of, worse for accessing values

figure out how to detect a loop in a linked list and congrats you can now pass many senior software developer interviews

Linked list is easier to insert something g into the middle of, worse for accessing values

The code from the video above gave a very simple example. Do you have a better example of what I could use a Linked List for? I watched another video that said Linked Lists are good for queues and stacks so I just assumed programmers used them for stuff like shopping carts on low stock items. Or when buying tickets for an upcoming show.

I haven't used a linked list ever since college. I just use the built in c# List<> which is an expandable vector. Best of both worlds, kinda.

Best i can think of in that scenario is double iteration wit a worst case of nsquared. Iterate forwards so you don't check for a combination you've already checked. Technically the run time would be something along the lines of nC2, but setting that up would still quirk out to about nsquared.

1. check the current item's sentinel bit, panic if it's already "true"
2. set the sentinel bit to true
3. move on to next item

Add a sentinel bit to the list item definition.
Then, iterate through the whole list:
1. check the current item's sentinel bit, panic if it's already "true"
2. set the sentinel bit to true
3. move on to next item

The "best" way to do it is to use two pointers, a fast one and a slow one. In a loop move the fast one forward two nodes and the slow one forward one node. If the fast one reaches the end of the list there is no loop. If at any time they both point to the same node there is a loop.