Lab 2 - Doubly-Linked List (100 pts)

Due Monday, January 20 at 11:59pm on Canvas


Pair Programming Required (Or No Lab Credit!)

  • Both partners fill in, sign and date the pair programming contract and BOTH partners submit this file.
  • Only one partner submits the lab assignment on Canvas. Please make sure both your names are on ALL the files.
  • Both partners follow the rules for pair programming.

Part 1: Creating a Doubly-Linked List Class

  • To begin this assignment, open List.java from Lab 1 and update this class to be a doubly-linked list.
  • The principle difference between the singly-linked list that you wrote in Lab 1 and a doubly-linked List is that each node contains a reference to both to the next node and to the previous node in the List.
  • You can visualize a doubly-linked list like so:

Image source.

  • Therefore, your inner Node class will be updated to look like the following:

private class Node {
private T data;
private Node next;
private Node prev;

public Node(T data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
  • Additionally, bear in mind that the first Node of the list now has a prev Node reference to null while the last Node has a next Node reference to null.
  • The advantage of the prev reference is the ease with which we can traverse the list in both directions, and also perform some more challenging operations such as removeLast().
  • To account for the presence of this additional reference variable in the Node class, you will need to make updates to your code for many of the List methods.
  • Most of these updates are as simple as adding one line of code to the method.
  • For example, let's look at the insertFirst() method:
      /**
     * Creates a new first element
     * @param data the data to insert at the
     * front of the list
     * @postcondition a new first element
     */
    public void addFirst(T data) {
        if (first == null) {
            first = last = new Node(data);
        } else {
            Node N = new Node(data);
            N.next = first;
            first.prev = N;
            first = N;
        }
        length++;
    }
  • Important! Each time you update one of your methods, run your tests again to make sure your List is still working properly.
  • If you want more information on doubly-linked lists, you can watch this short video (8 min).


Part 2: Adding New Functionality to your List Class

  • Your doubly-linked list needs to be able to perform all of the same operations as your singly-linked list.
    • However, as you may have noted when writing Lab 1, the Lab 1 List class was very limited.
    • You could only add and remove data at the two ends of the List
    • What about the middle of the List?
  • How can we access data or insert and remove data from the middle of the List?
  • To increase the functionality of our class, we will be adding some new methods and a new field to the List.
  • First, add a new private field to the class to store the iterator - a node reference that we will use to move around the List container.
  • Unlike the first and last Nodes, which must always remain in the same location, the iterator will need to change positions in the List.
private int length;
private Node first;
private Node last;
private Node iterator;

  • All of the required methods for this lab are described below:


Constructors:

constructor: constructs a new linked list object.
copy constructor
: makes a copy of this list object

Mutators:

removeFirst: removes the element at the beginning of the list   
removeLast:
removes the element at the end of the list
<--Important: Rewrite for this Lab! Remove while loop
addFirst:
inserts an element at the beginning of the linked list

addLast:
inserts an element at the end of the list
placeIterator: moves the iterator to the start of the list
removeIterator: removes the element currently pointed to by the iterator. Postcondition: Iterator then points to NULL.
addIterator: inserts an element after the node currently pointed to by the iterator
advanceIterator: moves the iterator up by one node
reverseIterator: moves the iterator down by one node

Accessors:

getFirst: returns the first element
getLast:
returns the last element

isEmpty: tests whether the linked list is empty
getLength: returns the current length of the list
getIterator: returns the element currently pointed at by the iterator
offEnd: returns whether the iterator is off the end of the list, i.e. is NULL
equals: overrides the equals method for object to compares this list to another list to see if they contain the same data in the same order.

Additional Operations:

toString: overrides the toString method for object to make a String with each element in the List separated by a new line

  • Note that, as you write each method, you must also write its Javadoc comment, including using the @precondition tag, @postcondition tag and @throws tag where necessary.
  • Hint: You can use the above descriptions as a starting point for your Javadoc comments.


Part 3: Testing Your List Class

  • You should test all of your methods inside of ListTest.java (write 2-4 tests per method).
    • Note that you should test all cases for a method. For example, you should write at least 4 calls to removeIterator() in ListTest.java.
      • One method call to test that the method is handling the precondition correctly
      • One method call for each edge case (2 edge cases)
      • One method call for the general case
      • Total: 4 method calls
  • Additionally, you should create unit tests (or update the unit tests where necessary) for the following methods:
(update these unit tests for your new generic, doubly-linked list class)
    • addFirst
    • addLast
    • getFirst
    • getLast
    • removeFirst
    • removeLast
    • isEmpty
    • getLength
(write unit test for new methods)
    • addIterator
    • advanceIterator
    • equals
    • getIterator
    • offEnd
    • placeIterator
    • removeIterator
    • reverseIterator
    • copy constructor

Part 4: CardApp.java
Overview
  • Create a class called Card.java and a second class named CardApp.java (containing a main method).
  • Optionally, you may create a test file (not to be submitted) name CardTest.java, and any additional test files (not to be submitted).
  • The purpose of the program is to read in a series of abbreviations representing a complete deck of playing cards from a text file.
  • The program should both shuffle the playing cards according to a given algorithm and also sort them based on their rank and suit.
  • After the program has shuffled the cards, the shuffled abbreviations should be written to a file named shuffled.txt and once the program has sorted the cards, the sorted abbreviations should be written to a file named sorted.txt.

Card.java Starter Code:
  • Copy and paste the below starter code into a Java file named Card.java
  • Note that the below methods are only "stubs"
  • Fill in the missing method bodies for each method according to the Javadoc comments below.
  • Note that you are not allowed to add any additional methods or member variables other than those that are given in the starter code below or you will not receive credit for this part of the lab assignment.

/**
 * Card.java
 * @author
 * @author
 * CIS 22C, Lab 2
 */

public class Card implements Comparable<Card>{
    private String rank;
    private String suit;
   
    /**
     * Constructor for the Card class
     * @param rank the rank of card from 2 to A
     * @param suit the suit of card C, D, H, or S
     */
    public Card(String rank, String suit) {
       
    }
   
    /**
     * Returns the card's rank
     * @return rank a rank from 2 (low) to A (high)
     */
    public String getRank() {
        return null;
    }
   
    /**
     * Returns the card's suit
     * @return C, D, H, or S
     */
    public String getSuit() {
        return null;
    }
   
    /**
     * Updates the card's rank
     * @param rank a new rank
     */
    public void setRank(String rank) {
        return;
    }
   
    /**
     * Updates the card's suit
     * @param suit the new suit
     */
    public void setSuit(String suit) {
        return;
    }
   
    /**
     * Concatenates rank and suit
     */
    @Override public String toString() {
        return "";
    }
   
    /**
     * Overrides the equals method for Card
     * Compares rank and suit and
     * follows the equals formula given in
     * Lesson 4 and also in Joshua Block's text
     */
    @Override public boolean equals(Object o) {
        return false;
    }
   
    /**
     * Orders two cards first by suit (alphabetically)
     * Next by rank. "A" is considered the high card
     * Order goes 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A
     * @return a negative number if this comes before c
     * and a positive number if c comes before this
     * and 0 if this and c are equal according to the above
     * equals method
     */
    @Override public int compareTo(Card c) {
        return 0;
    }
}



CardTest.java Code:
  • Use the below test file to ensure that your compareTo method for the Card class is working properly.
  • Note: Update the values of c1 and c2 to test other card combinations.

/**
 * CardTest.java
 * @author
 * @author
 * PLS DO NOT SUBMIT THIS FILE
 */

public class CardTest {
    public static void main(String[] args) {
        Card c1 = new Card("10", "S"); //update here
        Card c2 = new Card("2", "S"); //update here
        if (c1.equals(c2)) {
            System.out.println(c1 + " is the same as " + c2);
        } else if(c1.compareTo(c2) < 0) {
            System.out.println(c1 + " comes before " + c2);
            System.out.println(c1.compareTo(c2));
        } else {
            System.out.println(c2 + " comes before " + c1);
            System.out.println(c1.compareTo(c2));
        }
    }
}



CardApp.java Starter Code:
  • Copy and paste the below starter code into a Java file named CardApp.java
  • Note that the below methods are only "stubs"
  • Fill in the missing method bodies for each method according to the Javadoc comments below
  • You may optionally write additional methods inside of this class.
  • However, you are not allowed to add any additional import statements to this file.
  • Note that the purpose of your program is to shuffle the deck of cards (read in from a file) according to the algorithm given in the shuffle method comment.
  • Additionally, you need to be able to sort a deck of cards using the bubble sort algorithm (should have learned in a prior class). Use the below pseudocode when you write your sort method:
BubbleSort(A[])
    for i = 0 up to and including length - 2
        for j = 0 up to and including length - i - 2 //each pass make fewer comparisons
            if A[j] > A[j+1]
               A[j] <---> A[j+1] //swap
  • After you have shuffled the deck of cards, write the result into a file named shuffled.txt
  • After you have sorted the deck of cards, write the result to a file named sorted.txt
  • Note that you are required to shuffle before sorting to receive credit.
  • Note that the user should be able to enter the name of any input file containing valid card abbreviations:
    • In the case that the file is not found, the program should prompt the user to enter a valid file name (please see below sample output).
/**
 * CardApp.java
 * @author
 * @author
 * CIS 22C, Lab 2
 */

import java.util.Scanner;
import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;

public class CardApp {
   
    private List<Card> L =  new List<>();
   
    public static void main(String[] args) {
        return;
    }
   
    /**
     * Shuffles cards following this algorithm:
     * First swaps first and last card
     * Next, swaps every even card with the card 3
     * nodes away from that card. Stops when it
     * reaches the 3rd to last node
     * Then, swaps ALL cards with the card that is
     * 3 nodes away from it, stopping at the 3rd
     * to last node
     */
    public void shuffle() {
        return;
    }
   
    /**
     * Implements the bubble sort algorithm
     * to sort L into sorted order, first by suit
     * (alphabetical order)
     * then by rank from 2 to A
     */
    public void sort() {
        return;
    }

}

Simple Shuffle and Sort Example:
  • The below example is intended to help you verify that you understand how to shuffle and sort the cards:

Before shuffling: 1H 2H 3H 4H 5H 6H 7H 8H 9H 10H

First and last swapped:
10H 2H 3H 4H 5H 6H 7H 8H 9H 1H

Swapped 2H and 5H
10H 5H 3H 4H 2H 6H 7H 8H 9H 1H

Swapped 4H and 7H
10H 5H 3H 7H 2H 6H 4H 8H 9H 1H

Swapped 6H and 9H
10H 5H 3H 7H 2H 9H 4H 8H 6H 1H


***End first set of swaps***

10H 5H 3H 7H 2H 9H 4H 8H 6H 1H

Swapped 5H and 2H
10H 2H 3H 7H 5H 9H 4H 8H 6H 1H

Swapped 3H and 9H
10H 2H 9H 7H 5H 3H 4H 8H 6H 1H

Swapped 7H and 4H
10H 2H 9H 4H 5H 3H 7H 8H 6H 1H

Swapped 5H and 8H
10H 2H 9H 4H 8H 3H 7H 5H 6H 1H

Swapped 3H and 6H
10H 2H 9H 4H 8H 6H 7H 5H 3H 1H

Swapped 7H and 1H
10H 2H 9H 4H 8H 6H 1H 5H 3H 7H


***End second set of swaps***

After sorting:
1H 2H 3H 4H 5H 6H 7H 8H 9H 10H


CardApp.java Sample Output:

Welcome!

Enter the name of a file containing a deck of cards: cards2.txt
Please open shuffled.txt and sorted.txt.

Goodbye!


Alternately:

Welcome!

Enter the name of a file containing a deck of cards: mydeck.txt
Please open shuffled.txt and sorted.txt.

Goodbye!



Alternately:

Welcome!

Enter the name of a file containing a deck of cards: myd.txt
Invalid file name. Please enter a valid file name: my.txt
Invalid file name. Please enter a valid file name: m.txt
Invalid file name. Please enter a valid file name: mydeck.txt
Please open shuffled.txt and sorted.txt.

Goodbye!



Sample Input File:

  • How to Save in the Correct Location:
    • Right-click on the project folder

    • Go to New -> File

    • Name your file

    • Important: Note that the file will be placed directly under the project folder, not under src, if you followed the above steps correctly.

AS
2S
3S
4S
5S
6S
7S
8S
9S
10S
JS
QS
KS
AC
2C
3C
4C
5C
6C
7C
8C
9C
10C
JC
QC
KC
AH
2H
3H
4H
5H
6H
7H
8H
9H
10H
JH
QH
KH
AD
2D
3D
4D
5D
6D
7D
8D
9D
10D
JD
QD
KD



Corresponding shuffled.txt:

KD
2S
9S
4S
JS
6S
KS
8S
2C
10S
4C
QS
6C
AC
8C
3C
10C
5C
QC
7C
AH
9C
3H
JC
5H
KC
7H
2H
9H
4H
JH
6H
KH
8H
2D
10H
4D
QH
6D
AD
8D
3D
10D
5D
QD
7D
JD
9D
AS
5S
3S
7S



Corresponding sorted.txt:

2C
3C
4C
5C
6C
7C
8C
9C
10C
JC
QC
KC
AC
2D
3D
4D
5D
6D
7D
8D
9D
10D
JD
QD
KD
AD
2H
3H
4H
5H
6H
7H
8H
9H
10H
JH
QH
KH
AH
2S
3S
4S
5S
6S
7S
8S
9S
10S
JS
QS
KS
AS

Specifications for Submission:

  • Please submit the following files to Canvas:
    • List.java (a complete and fully commented generic, doubly-linked List class, including specified methods)
    • ListTest.java (test file with at least 2 method calls to each method written)
    • Card.java 
    • CardApp.java
    • Unit Test classes for the required methods as specified above
    • Pair programming contract (-5 if contract is missing)
  • Important: You must name your files exactly as described above
  • Also, your code must compile using Eclipse for Java.
  • Please submit each file separately (no zip files or other compressed file type -5 pts).
  • Please remove all package statements before submitting (-5 pts).
  • Please format the code in your files (Go to source->format) (-5 pts)


How You Will Be Graded:

  • No credit if your List.java file contains any additional methods other than those specified in the directions or if the inner Node class has been altered in any way from what was given in this Lab.
  • Make sure that you test your list thoroughly inside of ListTest.java and your unit tests!
  • No credit if your List doesn't compile or run using the Eclipse IDE as specified above
  • No credit if your program doesn't compile. Make sure to comment out the parts that aren't working (if any) before you submit.
  • Please include a block comment with your name on the top of EACH file like so:

/**
* @author FirstName LastName
* @author FirstName LastName
* CIS 22C, Lab 2
*/
  • 38 points of the credit will be for submitting a complete and functional generic, doubly-linked list (2 points per correct method)
  • 22 points for adequate testing (1 point per unit test class and 5 points for a complete ListTest.java class)
  • 40 for a complete and functional Card.java and CardApp.java program that works as shown in the sample output.
  • No credit do not complete this assignment with a partner, following the rules of pair programming.
  • No credit for the CardApp.java if you use an array, ArrayList or any other structure aside from your Lab 2 linked list in your solution to this assignment.