Skip to Main Content

Data Structures

Computer Science Department

Doubly Linked Webpage - 10 Course Points

The purpose of this assignment is to learn how to traverse and use Doubly Linked Lists.

The assignment has one component: Coding (10 points) submitted through Autolab.

Overview

In a web browser, you can go back and forward to pages and skip others. For instance, after navigating to a few CS112 pages, then going to Canvas and viewing our modules, here’s what you’ll see when you right click the Back button.

But you don’t have to go back or forward linearly – you can access previously visited pages or pages you skipped at that point in time. We can represent this as a doubly linked list and refer to whichever is our current page. 

The DoublyLinkedWebPage class is meant to implement a doubly linked list, where each list node is doubly-linked and contains a String.

Fill in the code for the numberSites() and addRecent() methods, to finish the doubly linked list and enable the Driver website visualization.

Reminder, a singly linked list (SLL) is comprised of individual nodes. Each node has a “next” variable, which corresponds to another node. This allows nodes to be chained together, although those links can only be traversed in one direction.

A doubly linked node instead has TWO connections to other nodes, often known as “next” and “prev” (previous). This allows the linked list of nodes to be traversed in two directions, both forwards and backwards.

Similarly to an SLL, we store a Doubly Linked List (DLL) using a reference to one of the nodes in the list. Since the list is doubly linked, this reference can point to ANY node, rather than just the front of the list.

 

Directions

  • DO NOT add new import statements.
  • DO NOT add any new class attributes
  • DO NOT change any of the method’s signatures.
  • DO NOT modify the given constructor.

To complete this Lab, implement the numberSites() and addRecent() methods for the doubly linked list of strings. Each node in this doubly linked list is represented as a WebPage, with a String name, a next field and a prev field. The next and prev field both point to another WebPage node.

The method signatures are already given, do not modify these or add any new ones.

There is one class attribute provided for you in DoublyLinkedWebPage.java:

  • “current” which is a reference to a single node in the doubly linked list
    • This is not a reference to specifically the front or end of the list. Since the list is doubly linked, the driver and tests move this pointer back and forth along the list. This differs from past examples you’ve done in class.
    • current is the currently viewed page in the driver.

numberSites()

This method is a counter method, which returns the total number of nodes that are currently in the list. Use a WebPage pointer variable to traverse the list, and use an integer counter to count the number of nodes.

REMEMBER, the list is Doubly linked and the “current” attribute may point to any node in the list. SO, to count the total number of nodes, you need to start at “current” and count in BOTH directions (both next and prev, aka forwards and backwards).

  • OR you can find to the front of the list and start counting from there.

Note: Make sure to use a pointer variable to do this traversal, do not change the “current” attribute. Meaning that “current” does not move, so you need an auxiliary pointer variable (just like we did in class).

There are NO getter/setter methods provided in the WebPage class. To traverse, directly access the “next” and “prev” attribute with “ptr.next” and “ptr.prev” (where “ptr” is a variable that holds a WebPage node).

Once you’ve traversed the whole list, return the number of WebPages.

addRecent(String toAdd)

This method adds a new WebPage node with the given string immediately after “current” (aka current.next). It does not keep the nodes that were originally after current, so it effectively deletes them.

  • This is done to mimic the behavior of the forward/back buttons on a web browser. When visiting multiple sites in succession, they all get added to a list that you can traverse with the forward/back buttons. But if you move back, then click a new link, you no longer can move forward as you have added a new recent site.

To complete this method:

-When the list is empty (current == null), then set current equal to a new WebPage node, and set its website to the given String.

– If the list is not empty, create a new WebPage node, and set its website. Then, set its “prev” attribute equal to current. Then, set current.next to that new node. Finally, current equal to current.next.

Hint: You do NOT need to use any loops to complete this method.

Driver

Once you implement your code, you can run the DoublyLinkedWebPage.java file and interact with the driver. It will show a visualization of a fake web browser. You can use the “Visit new site” button to open a new random link and view the page. There are also forward and back buttons which can view your site history. This mimic the webpage behavior described in the overview. It also shows the number of sites currently in the history list.

You can use this Driver to test your code, but it is still useful to write JUnit test cases, in case the driver does not catch all cases.

Testing Your Code

We can test this linked list code using a test class, since the WebPage nodes can contain any String.

In the main project folder, there exists a “test” folder next to the “src” folder. This contains JUnit tests, which can run and test pieces of your code. To compile and run these tests, you must install the JUnit package. See the Assignment FAQ for more info on VScode extensions.

You are provided with a premade JUnit test class for DoublyLinkedWebPage.java. Within this test class there is a COMPLETED test for addRecent() and an INCOMPLETE test stub for numberSites().

You should implement the latter using JUnit tests (assertTrue(), assertFalse(), assertEquals()) in order to test your code as you write it. You do NOT need to submit this test file.

See the JUnit Testing Guide to learn more about JUnit tests. See the Debugging Guide to learn more about debugging.

Tests not running? 

First, make sure you’re in the right folder and the tests are implemented. Next, if you have the “Code Runner for Java” or Oracle “Java” extension, make sure you uninstall those extensions. (You’ll know if you have the Oracle Java extension if you see a “Run Configuration” option on the bottom-left corner of your VS Code window. Remember that you must fill in the test for numberSites().

VSCode Extensions

You can install VSCode extension packs for Java. Take a look at this tutorial. We suggest:

Importing VSCode Project

  1. Download DoublyLinkedWebPage.zip from Autolab Attachments.
  2. Unzip the file by double-clicking.
  3. Open VSCode
    • Import the folder to a workspace through File > Open Folder

Executing and Debugging

  • You can run your program through VSCode or you can use the Terminal to compile and execute. We suggest running through VSCode because it will give you the option to debug.
  • How to debug your code
  • If you choose the Terminal:
    • first navigate to DoublyLinkedWebPage directory/folder
      • to compile: javac -d bin src/doubly/DoublyLinkedWebPage.java
      • to execute: java -cp bin doubly.DoublyLinkedWebPage
      • NOTE: if you have DoublyLinkedWebPage (2) -> DoublyLinkedWebPage or CS112 -> DoublyLinkedWebPage in VS Code, open the INNERMOST DoublyLinkedWebPage through File -> Open Folder.

Before submission

COMMENT all printing statements you have written from DoublyLinkedWebPage.java 

Collaboration policy. Read our collaboration policy here.

Submitting the assignment. Submit DoublyLinkedWebPage.java separately via the web submission system called Autolab. To do this, click the Labs and Assignments link from the course website; click the Submit link for that assignment.

Getting help

If anything is unclear, don’t hesitate to drop by office hours or post a question on Piazza.

  • Find instructors office hours here
  • Find tutors office hours on Canvas -> Tutoring
  • Find head TAs office hours here
  • In addition to office hours we have the Coding and Social Lounge (CSL) , a community space staffed with ilab assistants which are undergraduate students further along the CS major to answer questions.

By Colin Sullivan