0

Linked lists: build and traverse

Structuresused in ~95% of apps

The first structure you have to build yourself, and the first one where drawing a picture is not optional. Three variables and four lines of code, but the order of those lines is the whole thing.

Core idea. A list made of separate objects, each holding a value and a reference to the next one. There is no index and no length. All you ever have is a pointer to the front, and the only way to reach anything is to walk.
Playground, this isn't a screenshot
reversing 1 → 2 → 3, one node at a time
prevnullcur1rest2→3
prev1cur2rest3
prev2→1cur3restnull
prev3→2→1curnull. Donerestnull

Each row moves one node from rest to the front of prev. Save rest before flipping the arrow, or the rest of the list is lost.

↑ play a little first, then dig in