Classwork 4 - Enlisted to Finish IntList

Today, you’ll be finishing the IntLinkedList class we started in… well… class! Once it’s done, you’ll use it to stand up an IntQueue.

PostCommit + Skeleton

Definition

Start with the solution skeleton in-hand! The following will also serve as your submission mechanism (see submission instructions below).

Assignment

Sign in to PostCommit and accept Classwork 4 from your dashboard to get your repository.

Your repository contains:

• src/main/intlist/IntLinkedList.java — the linked list from class, with the work below left for you
• src/main/intlist/IntQueue.java — a queue backed by an IntLinkedList, fully stubbed out
• src/test/intlist/IntLinkedListTests.java and src/test/intlist/IntQueueTests.java — the grading tests

Specifications

Definition

Complete the work below. You may add private helper methods and the one new field described in Part 1, but do not change any of the existing public method signatures.

Part 1: Give the list a tail

Right now IntLinkedList tracks only its head. That’s why append() has to walk the entire list every single time just to find the end — look at it and you’ll see the loop.

Your first job is to fix that:

1. Add a tail field alongside head, and initialize it in the constructor.
2. Then make sure every method that changes the shape of the list keeps tail pointing at the right node. Three methods need your attention, and each is marked with a // TODO comment: append(), prepend(), and removeAt().

Think carefully about the boundary cases, because the tests absolutely check them:

• Appending or prepending to an empty list — the new node is both the head and the tail.
• Removing the last remaining node — head and tail both need to end up back at null.
• Removing the node that is the tail — something has to become the new tail.

Tip

Once tail is maintained correctly, go back and simplify append(). It no longer needs that loop — it can reach the end of the list in one step. That’s the whole reason we’re doing this.

Part 2: Report the ends

public Node getHead ();

Returns the Node at the front of the list.

If the list is empty, throw new IllegalStateException();

Warning

Parts 1 and 2 are graded together, so do them together. Nearly every test in IntLinkedListTests checks its result by reading getHead().data or getTail().data — which means a correct tail with no getTail() fails, and a getTail() with a sloppy tail fails too. If the whole suite is red at once, it’s almost always one of these two rather than twelve separate bugs.

// Example:
@Test
public void testAppend_t1() {
    listy.append(1);
    listy.append(2);
    listy.append(3);
    listy.append(4);
 
    assertEquals(1, listy.getHead().data);
    assertEquals(4, listy.getTail().data);
}

---

public Node getTail ();

Returns the Node at the end of the list.

If the list is empty, throw new IllegalStateException();

// Example:
@Test
public void testPrepend_t1() {
    listy.prepend(1);
    listy.prepend(2);
    listy.prepend(3);
    listy.prepend(4);
 
    assertEquals(4, listy.getHead().data);
    assertEquals(1, listy.getTail().data);
}

---

public IntLinkedList copy ();

Returns a new IntLinkedList containing the same ints as this one, in the same order.

The copy must stand on its own: it gets its own Node objects, so the two lists never share nodes. Copying an empty list gives back an empty list.

// Example:
@Test
public void testClone_t2() {
    listy.append(1);
    listy.append(2);
    listy.append(3);
    listy.append(4);
    listy.prepend(0);
 
    IntLinkedList listy2 = listy.copy();
 
    assertFalse(listy.getHead() == listy2.getHead());
    assertFalse(listy.getTail() == listy2.getTail());
}

Part 3: IntQueue

A queue is first-in, first-out: ints come out in the order they went in. Yours stores its contents in an IntLinkedList — so every method below should be a one- or two-liner that hands the work off to the list it already has.

public void push (int toPush);

Adds the given int to the back of the queue.

---

public int poll ();

Removes and returns the int at the front of the queue.

If the queue is empty, throw new IllegalStateException();

---

public int peek ();

Returns the int at the front of the queue without removing it.

If the queue is empty, throw new IllegalStateException();

---

public int size ();

Returns the number of ints currently in the queue.

---

public boolean empty ();

Returns whether the queue has no ints in it.

// Example:
@Test
public void testPoll_t0() {
    q.push(0);
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
 
    assertEquals(0, q.poll());
    assertEquals(1, q.poll());
    assertEquals(2, q.poll());
    assertEquals(3, q.poll());
    assertEquals(4, q.poll());
    assertThrows(IllegalStateException.class, () -> q.poll());
}

Notes

Success

Because we’re just getting our feet wet with designing data structures, I’ve given you all of the grading tests you’ll need to pass for this assignment!

You are, of course, always free to add tests that help you diagnose where things might be going wrong in your code, but to receive full credit here, simply pass all of the given tests!

Not sure where to start? Look at how the other methods are implemented from what we did in class as inspiration!

Note also that you’re allowed to call other methods we designed in class as part of your implementation if it makes sense to do so — keep that code DRY!

Tip

copy() is easiest if you walk the original list and append() each int onto a fresh IntLinkedList. That hands you brand-new nodes for free — and it only works once Part 1 is right, which makes it a decent check on your own work.

---

Submission

Definition

You will be submitting your assignments through PostCommit!

What

Complete all classes that accomplishes the specification above, in the project structure given in the skeleton above.

How

To clone this assignment (if you need a refresher), consult the guide here:

Assignment

PostCommit Tutorial

To submit this assignment:

• Simply push your final, submission copy to the PostCommit repository associated with you or your group.
• If you worked in a group (3 individuals maximum), ensure that your PostCommit group includes all members, and place all group members’ names at the top of all submitted files (in appropriate JavaDoc commenting fashion) AND in the accompanying readme file.

---