Return to Answer

• 1

• 112.9k
• 15
• 154
• 396

On top of @tim's excellent answer, a couple of things to add.

Unnecessary validation

The input validation in this method seems really unnecessary:

public void deleteAlternate ( ) {
 if (first == null) {
 throw new IllegalStateException("The first node is null.");
 }
 Node<T> node = first;
 // node == null, if even nodes are present in LL
 // node.next == null, if odd nodes are present in LL
 while (node != null && node.next != null) {
 node.next = node.next.next;
 node = node.next;
 }
}

Why is it bad if the linked list is empty? What if it has only one item? The outcome is the same, nothing will be deleted. You can simply drop this validation.

Also, the while loop would be more natural as a for loop. I would rewrite the method like this:

public void deleteAlternate() {
 for (Node<T> node = first; node != null && node.next != null; ) {
 node = node.next = node.next.next;
 }
}

Implementing equals

Instead of this:

if (obj == null)
 return false;
if (getClass() != obj.getClass())
 return false;

Do it this way:

if (obj instanceof LinkedList) {
 // ...
}

This is simpler than using the getClass methods, and it automatically includes the null-check as well.

Personally I would omit this check:

if (this == obj)
 return true;

If I wanted to know that two objects are identical, I would use == instead of .equals, and I rarely see code where identical objects are being compared.

Consider adding a toString method

To make unit testing easier, it's good to add a toString method, so that when two linked lists are not equal, you would get a more informative message than this:

java.lang.AssertionError: 
Expected :LinkedList@71f5d4c7
Actual :LinkedList@32a1bedf

Something like this, for example:

@Override
public String toString() {
 StringBuilder builder = new StringBuilder();
 for (Node<T> node = first; node != null; node = node.next) {
 builder.append(node.item).append(" -> ");
 }
 return builder.toString();
}

Changing a failed exception to this:

java.lang.AssertionError: 
Expected :1 -> 2 -> 
Actual :1 ->

Unit testing

Violating the DRY principle in unit tests is not a huge problem in general. But your tests are a bit too repetitive, and cry for some helper methods:

private void assertEqualsAfterDeleteAlternate(List<Integer> expected, List<Integer> orig) {
 LinkedList<Integer> linkedList = new LinkedList<>(orig);
 linkedList.deleteAlternate();
 assertEquals(new LinkedList<>(expected), linkedList);
}
private void assertNotEqualsAfterDeleteAlternate(List<Integer> expected, List<Integer> orig) {
 LinkedList<Integer> linkedList = new LinkedList<>(orig);
 linkedList.deleteAlternate();
 assertNotEquals(new LinkedList<>(expected), linkedList);
}

Using these will simplify your tests:

@Test
public void testWithSingleItem() {
 assertEqualsAfterDeleteAlternate(Arrays.asList(1), Arrays.asList(1));
 assertNotEqualsAfterDeleteAlternate(Arrays.asList(1, 2), Arrays.asList(1));
}
@Test
public void testWith2Items() {
 assertEqualsAfterDeleteAlternate(Arrays.asList(1), Arrays.asList(1, 2));
 assertNotEqualsAfterDeleteAlternate(Arrays.asList(1, 2), Arrays.asList(1, 2));
 assertNotEqualsAfterDeleteAlternate(Arrays.asList(1, 2, 3), Arrays.asList(1, 2));
}
@Test
public void testWith8Items() {
 assertEqualsAfterDeleteAlternate(Arrays.asList(1, 3, 5, 7), Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8));
}

Notice some other improvements here:

• Your original tests were all assertEquals and I added some assertNotEquals in the bunch. It's a good idea to add tests of the inverse logic like this, especially when your classes override equals. As I was refactoring your code differently, at some point all the original tests passed even when I broke the equals method: any LinkedList was equal to any other, which I wouldn't see with only assertEquals tests.

• Test cases should have descriptive names.

Naming

The class is really a linked list, so you should call it that way. If you want to emphasize in this exercise that the main feature you want to work on and test is deleting alternate (actually, every second) item, then you could call it LinkedListWithDeleteAlternate.