Linked Lists

Linked Lists - Some thoughts

The reading used this definition:

A Linked List is a sequence of Nodes that are connected/linked to each other. The most defining feature of a Linked List is that each Node references the next Node in the link.

Linked lists are what they sound like: lists, where all the items in the list are linked to one another. The first item has a reference to the second item, the second item has a reference to the third item, etc. (in a singly linked list)

We can't loop through a linked list exactly like we can an array. And we can't access a certain item (node) in a linked list with bracket notation, because each node doesn't have an index. The only way to access the node you want in the linked list is to go through (or transverse) the list node-by-node until you find what you're looking for.

To transverse through a linked list, we have to use the "next" property of the node we're on (or the current node). So firstNode.next would equal the second node.

A few analogies come to mind. When looping through a linked list with a while loop (as described in the CF reading), I thought of this one:

Imagine a track relay races where runners pass a baton. The baton would represent the current node you're on. In our analogy, each runner would only look forward and know where the next runner is. To access the third runner on the track, you'd have to have the first runner pass the baton to the second, then the second to the third.