BIT 143 - Assignment 2

DUE DATE: < Listed In Course Schedule >

Linked Lists and the 'Browser History' Application

You are not allowed to work in groups this assignment.  For this assignment, you should start, finish, and do all the work on your own.  If you have questions, please contact the instructor.

Learning Objectives:
(This is a list of the major topics that you, as students, will learn in this assignment:)

• Linked Lists
  In this assignment, you will need to implement a simple linked list class (either a pure linked list class that is used by other classes, or else you will merge an implementation of a linked list class into another class).  Specifically, you will need to be able to add nodes to / remove nodes from the ends of the linked list.
   
• Abstract Data Type(s)
  In this assignment, you will need to select and implement an appropriate Abstract Data Type (although perhaps not a 'pure' implementation of said ADT).

Part 1: Writing the program

            Imagine that you're writing an application to manage a browser's history.  Because we want to keep things (relatively) simple for this homework assignment  we're only going to track the name of each page (specifically, we're not going to track the URL, or the contents of the page, etc).  Essentially, the way the program works is that you visit a page and then the program adds that page to the 'history' that it's tracking.  As you add more pages it'll keep adding these new pages to your history.  You can then 'back up' in the history, much like you can push the 'Back button' in a real web browser.  When you back up in the history the program moves the most recently visited page from your history into a list of 'future' pages, so that if you choose to then go forwards in your history you can revisit those pages.  Here's an example transcript of one run of the program;

            As you examine the above transcript you should notice that if you 'back up' in the history and then visit a new page the program will remove all the pages your 'future'.   Also note that backing up past the first entry is not possible, nor is it possible to move forwards when there's no items in the 'future'.

            You should base your program's design off one of the Abstract Data Types that we've examined.  The ADT should be implemented using a linked list, so that you get experience implementing linked lists.  You need to write this code yourself, from scratch - it is NOT ok to use any LinkedList class made by anyone else (including the one built into .Net/C#).  Also, do NOT use a doubly-linked list for this assignment. (If you stick with what we covered in class you will do fine, regardless of whether you know what a ‘doubly linked list’ is or not).

Starter Project: You will be provided with a starter project that will provide you with a console-based user interface that will use the code that will use the BrowserHistory class that you implement in order to provide the functionality described in the previous paragraph.

The interface to the BrowserHistory class is defined below, so that you're clear on how the BrowserHistory class needs to behave.  You are free to create other classes ('helper classes', or auxiliary classes) that you use to implement the BrowserHistory class.

Other restrictions:

1.  In the weekly exercises we looked at using some of the basic data structures that are built into the standard C# library.  You do not need to use any of these classes to solve this project, nor are you allowed to.  To be clear: You need to write all the code for this yourself, using just 'basic' C#.

Group Work, Commenting:

            You are not allowed to work in groups for this assignment.  You should start, finish, and do all the work on your own.  If you have questions, please contact the instructor.

            Additionally, you should aggressively comment your code, paying particular attention to areas that are difficult to understand.  If you found something to be tricky when you wrote it, make sure to comment it so that the next person (the instructor, who's grading you) understands what your code is doing.  It is not necessary to comment every single line.

The purpose of new requirement is to both help you understand, and have you demonstrate, a thorough understanding of exactly how your program works.

Every file that you turn in should have:

•  At the top of each file that you normally edit, you should put your name (first and last), the name of this class (“BIT 143”), and the year and quarter, and the assignment number, including the revision number, which starts at 0 (“A2.0”).  If you’re handing this in again for a regrade, make sure to increase the minor version number by one (from “A2.0”, to “A2.1").
  You normally edit the C# source code files (.CS files), and any Word documents that you're handing in (if any).
  You do not normally edit the .SLN or .CSPROJ files, and so you should not try to put this identifying information in those files.

In general, you should make sure to do the following before handing in your project:

• All variables used should have meaningful names.

• The code should be formatted consistently, and in an easy to read format.   

What to turn in:

o   The C# source code for the entire program. 
Please include all the .CS files, whether you've changed them or not, just on the off chance you forgot that you changed them.

How to electronically submit your homework:

This was covered in a separate document in this website..