Linked Lists

Overview

For this project you will implement a basic linked and a sorted linked list. Notice that no public tests are part of this project as all tests are either release or secret.

Objectives

This project will allow you practice linked lists and testing.

Grading

(20%) Release Tests
(70%) Secret Tests
(10%) Style

Clarifications

Any clarifications or corrections associated with this project will be available at Project Clarifications.

Code Distribution

The project's code distribution is available by checking out the project named LinkedListsProject. The code distribution provides you with the following:

listClasses package → Where classes implementing linked lists will appear.
tests package → Where you should place your student tests.

Specifications

You are expected to implement two classes: BasicLinkedList and SortedLinkedList.The javadoc describing what you need to implement can be found at Project Javadoc.

Requirements

You may not use recursion in this project.
For this project you are not required to write student tests, but you are strongly encourage to do so. If you have a problem with your code and need assistance during office hours, you need to have a student test(s) that illustrates the problem you are experiencing. See Student Tests for information regarding the implementation of student tests.
The iterator you define may NOT be used to implement other list operations (e.g., add). The iterator is for users that want to iterate over the list.
You need to implement a singly-linked list that relies on a head and tail reference.
See Style Guidelines for information regarding style.

Additional Requirements for Students in CMSC 132H (Honors)

You need to implement the iterator's remove method.
Define a class called WithSecondaryOrderLinkedList class. This class keeps elements sorted based on two criteria: the main sorting order (as in SortedLinkedList) and a secondary one. For example, if we have a list of students, we could have the list sorted by name (primary sorting order) and id (secondary sorting order) simultaneously WITHOUT having to duplicate nodes. In order to have the secondary order, we need to add an additional field to the Node class, and an additional head and tail. Based on the above description, implement the class so the add method adds an element to the list preserving both the primary and secondary orders. Add a method call printSecondaryOrder that displays the elements associated with this order. Feel free to add any variables/methods you understand are necessary. Make sure you provide a main method in this class that illustrates how your class generates both orders using a Student class example.

Sample Driver

The following driver and associated output provide an idea of the classes you need to implement.



import listClasses.BasicLinkedList;
import listClasses.SortedLinkedList;

public class SampleDriver {

	public static void main(String[] args) {
		BasicLinkedList<String> basicList = new BasicLinkedList<String>();

		basicList.addToEnd("Red").addToFront("Yellow").addToFront("Blue");
		System.out.println("First: " + basicList.getFirst());
		System.out.println("Last: " + basicList.getLast());
		System.out.println("Size: " + basicList.getSize());
		System.out.println("Retrieve First: " + basicList.retrieveFirstElement());
		System.out.println("Retrieve Last: " + basicList.retrieveLastElement());
		System.out.println("Removing Red");
		basicList.remove("Red", String.CASE_INSENSITIVE_ORDER);
		System.out.print("Iteration: ");
		for (String entry : basicList) {
			System.out.print(entry + " ");
		}
		
		SortedLinkedList<String> sortedList = new SortedLinkedList<String>(String.CASE_INSENSITIVE_ORDER);
		sortedList.add("Yellow").add("Red");
		System.out.print("\n\nIteration (for sorted list): ");
		for (String entry : sortedList) {
			System.out.print(entry + " ");
		}
		sortedList.remove("Red");
		System.out.print("\nAfter remove in sorted list first is: ");
		System.out.println(sortedList.getFirst());
	}
}

Output

First: Blue
Last: Red
Size: 3
Retrieve First: Blue
Retrieve Last: Red
Removing Red
Iteration: Yellow 

Iteration (for sorted list): Red Yellow 
After remove in sorted list first is: Yellow