COMP 139 - Lab 4 - Linked Lists

Learning Outcomes and Introduction

In this lab assignment you will be creating a Linked List data structure. In the process you'll practice:

• using generics
• throwing exceptions
• implementing interfaces
• creating container classes that manage other objects
• writing "library" classes without a pre-determined use case

The Java standard library includes several flexible list implementations (including a doubly-linked list), but creating your own is a useful experience that will give you a better understanding of how linked data structures work and the trade-offs compared to fixed structures such as arrays. Note that the List interface provided here differs substantially from the one defined in the standard library in order to simplify your work for the assignment. We will look closer at the standard library classes later on in the course.

Do not use any classes from the Java Collections Framework in your solutions for this assignment, except for java.util.NoSuchElementException.

Make sure you test your code as you progress through the tasks. There is no "main program" in this assignment, so good unit tests will be essential to ensure that your code is correct. Use a single main-method class to test your code from all tasks, and submit it along with the rest of your work.

Task 1: implement List

Create an implementation of the List interface using a linked data structure. You will likely need to create two classes: one for the overall list itself, and one for the "nodes" that it chains together to hold the list content.

Task 2: implement Stack

Implement the Stack interface using your linked data structure from Task 1.

You may create an entirely new class for this task, or you may choose to extend your solution from Task 1. Eg:

			public class MyLinkedList<T> implements examples.List<T>, examples.Stack<T> { }
		

Note: the interface below is identical to the one from lab 3.

Submission

Completing all tasks in this lab should result in 2 or more separate Java files (a linked-list implementation, plus a main-method testing class) within a single package named like LastnameFirstname_lab4. Do not include the List or Stack interfaces in your submission. Compress the package directory into a ZIP archive and upload it to the D2L assignment.

The marks for this lab are heavily weighted towards good coding practice and style. Pay attention to your code formatting, make sure you have documented all public members using JavaDoc, and make sure you are using constants, arrays, loops, and methods effectively.

NOTE: This assignment is to be done individually. You can help one another with problems and questions, but in the end everyone must do their own work.