Nodes & LinkedLists

This past week we covered our first real data structure of the course: the LinkedList. For those of you still slightly confused about the function of LinkedLists and how they interact with Nodes, here’s my crash course explanation…

The Node class makes up the foundation of the LinkedList class. Think of a LinkedList as a list made up of many, separate items. Each item will be represented by a Node. The Nodes are like the lego blocks making up our LinkedList. Each Node only has to be aware of two things: (1) It’s data value and (2) It’s next neighbor. In other words, each Node knows what number it represents and who it’s connected to.

Since all of our Nodes are connected (via node.next variable), our LinkedList object only needs to know about the FIRST Node in the list. As such, the LinkedList’s only member variable is the Node variable first. One way to picture this is like holding a ribbon of carnival tickets. Since all of the tickets are connected, you only need to hold on to one end of the ticket ribbon. Even though you hold on to only one ticket you can still get to every other ticket; there’s no need to hold all of the individual tickets in your hands! Since each ticket is connect to it’s neighbor ticket and each ticket has a value, I think this is a good real world analogy for a LinkedList.

tickets

Leave a Reply

Your email address will not be published. Required fields are marked *