For this recitation, we will be working on implementing the code that underlies linked lists to get a better understanding of them. Linked lists have many of the same methods as an ArrayList, but the way in which they are implemented is very different. Before we get to linked lists though, let's go over the other classes.
Book.java is nothing out of the ordinary - it's just a book that keeps track of the book's title and its author, as well as the number of pages. It has a few getter and setter methods, but overall this class is pretty straight forward.
BookNode.java gets a little more interesting. A BookNode is an object that you can think of as a container. You can see that its instance variables include a book which is contained by the BookNode and another BookNode called next. This is so this particular node can always keep track of the node that comes next in the sequence. If the node is the last one in the sequence, its next will be set to null. Note: what we are implementing today is a singly linked list so it only keeps track of the one in front of it, not the one behind it. There are also methods for setting the next node and getting the next node, as well as a method for returning the book that the node contains.
Now let's look at the LinkedBookList class. You'll see that the instance variables for this are very simple. Only a BookNode called head and an int to keep track of the size of the linked list. Surprising, since the linked list is a data struture, that it doesn't keep track of all of the nodes. That's the neat thing, though, is that the linked list only needs to keep track of the first node in the list.
Let's look at some scenarios. Let's say that we are adding a new BookNode to an empty linked list. What can we do? That part isn't that difficult, it's just a simple assignment. What if we want add a BookNode at the end? For this, one way to go about it is using a for loop. Rather than writing a for loop the normal way with a roaming integer, now we can write a for loop with BookNodes. Think about where we want to start. What do we do in the initialization? What will be our conditional to indicate where we are stopping? What do we want to do in the afterthought?
Let's say we want to remove a BookNode. We could traverse the linked list until our traversing BookNode equals the Booknode that we want to remove. What then? We can't go back to set the pointer correctly, so we know that we've gone too far. What do we want to compare to the BookNode that we want to remove?
Many of what we are trying to implement here can be reasoned through by drawing pictures. Try busting out some paper and trying this yourself to reason through how far to go, when to set which pointers, and when to delete pointers. Good luck and as always, let us know if you have questions.