In this java program we will implement a singly linked list class to get a better understanding of this reference-based data structure. The interface you will implement is very similar to that provided by ArrayLists, but the way in which they are implemented is very different.

Phase 1 - Build the project

Create an P13 project and download the following files into that project.

Book.java

http://www.cs.colostate.edu/~cs164/.Fall17/recitations/R20/src/Book.java

LinkedBookList.java

http://www.cs.colostate.edu/~cs164/.Fall17/recitations/R20/src/LinkedBookList.javaDescription

public class LinkedBookList { private BookNode head; private int size; public LinkedBookList(){ head = null; size = 0; } //returns size of the list public int size(){ return size; } //IMPLEMENT -- adds a book to the end of the linked list public void add(Book b){ return; } //IMPLEMENT -- adds a book at the specific index, // or at the end if index is greater than size public void add(Book b, int index){ return; } //IMPLEMENT -- removes a book and returns it, or // returns null if book is not present public Book remove(Book b){ return null; } //IMPLEMENT -- removes a book at a specific index and returns it, // or returns null if index is not present public Book remove(int index){ return null; } //IMPLEMENT -- returns the total number of pages in the linked list public int totalPages(){ return 0; } public String toString() { String res = ""; for (BookNode pos = head; pos != null; pos = pos.getNext()) { if (pos.getBook() == null) { res += "null"; } else { res += pos.getBook(); } if (pos.getNext() != null) res += " "; } return res; } }

BookNode.java

http://www.cs.colostate.edu/~cs164/.Fall17/recitations/R20/src/BookNode.java

R20.java

http://www.cs.colostate.edu/~cs164/.Fall17/recitations/R20/src/R20.java

import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; public class R20 { public static void main(String[] args) throws FileNotFoundException{ LinkedBookList lbl = new LinkedBookList(); Scanner scan = new Scanner(new File("top10.txt")); int bookCount = (Integer.parseInt(scan.nextLine())); //reads in all of the books, and adds them to the linked list for(int i = 0; i < bookCount; i++){ String line = scan.nextLine(); String[] parts = line.split("\t"); String name = parts[0]; String title = parts[1]; int numPages = Integer.parseInt(parts[2]); Book b = new Book(name, title, numPages); lbl.add(b); } System.out.println("Testing add"); System.out.println(lbl); scan.close(); } } 

You will also need to download a text file containing books that appeared on the New York Times list of top 10 Fiction Hardback Books. This file contains the books name, author, and number of pages.

top10.txt

http://www.cs.colostate.edu/~cs164/.Fall17/recitations/R20/src/top10.txt

Phase 2 - File Descriptions

Book.java

Book.java is nothing out of the ordinary - it's just 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 very straight forward.

BookNode.java

BookNode.java is a little more interesting. A BookNode is an object that stores a Book in its book instance variable, and has a reference to the next BookNode in its next instance variable. If the node is the last one in the sequence, its next variable will be set to null. 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.

LinkedBookList.java

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, which refers to the first item, and an int to keep track of the size of the linked list. This is all we need, since each element contains a reference to the next one.

R20.java

R20.java is your test program to run and show the output to the TAs.

Phase 3 - Implementation

Your task is to implement the first add method, which adds a book at the end of the list (not the beginning).

This method will require you to iterate through the list. You can do this either with a while loop or a for loop. If using a for loop, think what are the three components that make up the loop:

(initialization; are we done?; operation to reach the next item) 

Many of the operations that we are trying to implement here, can be reasoned through by drawing pictures. Use that to reason how far to go, when to set which pointers, and when to delete pointers.