Delete alternate nodes of a linked list

Question

If the linked list is 1->2->3->4 then the output should be 1->3. If the linked list is 1->2->3->4->5, then the output should be 1->3->5.

The question is attributed to GeeksForGeeks. I'm looking for code-review, best practices and optimizations.

public class DeleteAlternate<T> {
 private Node<T> first;
 private Node<T> last;
 private int size;
 public DeleteAlternate(List<T> items) { 
 for (T item : items) {
 create(item);
 }
 } 
 private void create (T item) {
 Node<T> n = new Node<>(item);
 if (first == null) {
 first = last = n;
 } else {
 last.next = n;
 last = n;
 }
 size++;
 }
 private final class Node<T> {
 private Node<T> next;
 private T item;
 Node (T item) {
 this.item = item;
 }
 }
 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;
 }
 }
 // size of new linkedlist is unknown to us, in such a case simply return the list rather than an array.
 public List<T> toList() {
 final List<T> list = new ArrayList<>();
 if (first == null) return list;
 for (Node<T> x = first; x != null; x = x.next) {
 list.add(x.item);
 }
 return list;
 }
 @Override
 public int hashCode() {
 int hashCode = 1;
 for (Node<T> x = first; x != null; x = x.next)
 hashCode = 31*hashCode + x.hashCode();
 return hashCode;
 }
 @Override
 public boolean equals(Object obj) {
 if (this == obj)
 return true;
 if (obj == null)
 return false;
 if (getClass() != obj.getClass())
 return false;
 DeleteAlternate<T> other = (DeleteAlternate<T>) obj;
 Node<T> currentListNode = first; 
 Node<T> otherListNode = other.first;
 while (currentListNode != null && otherListNode != null) {
 if (currentListNode.item != otherListNode.item) return false;
 currentListNode = currentListNode.next;
 otherListNode = otherListNode.next;
 }
 return currentListNode == null && otherListNode == null;
 }
}
public class DeleteAlternateTest {
 @Test
 public void test1() {
 DeleteAlternate<Integer> dAlternate1 = new DeleteAlternate<>(Arrays.asList(1));
 dAlternate1.deleteAlternate();
 assertEquals(new DeleteAlternate<>(Arrays.asList(1)), dAlternate1);
 }
 @Test
 public void test2() {
 DeleteAlternate<Integer> dAlternate2 = new DeleteAlternate<>(Arrays.asList(1, 2));
 dAlternate2.deleteAlternate();
 assertEquals(new DeleteAlternate<>(Arrays.asList(1)), dAlternate2);
 }
 @Test
 public void test3() {
 DeleteAlternate<Integer> dAlternate3 = new DeleteAlternate<>(Arrays.asList(1, 2, 3));
 dAlternate3.deleteAlternate();
 assertEquals(new DeleteAlternate<>(Arrays.asList(1, 3)), dAlternate3);
 }
 @Test
 public void test4() {
 DeleteAlternate<Integer> dAlternate4 = new DeleteAlternate<>(Arrays.asList(1, 2, 3, 4));
 dAlternate4.deleteAlternate();
 assertEquals(new DeleteAlternate<>(Arrays.asList(1, 3)), dAlternate4);
 }
 @Test
 public void test5() {
 DeleteAlternate<Integer> dAlternate5 = new DeleteAlternate<>(Arrays.asList(1, 2, 3, 4, 5));
 dAlternate5.deleteAlternate();
 assertEquals(new DeleteAlternate<>(Arrays.asList(1, 3, 5)), dAlternate5);
 }
}

• David Harkness: Does 1->2->3->4->5 really become 1->2->5? I assume that 2 is a typo and should be 3.

Answer 1

Unused Variables / wrong variable values

You are not actually using last for the algorithm, and you are also not keeping it up-to-date, so I would just get rid of it. Alternatively, keep it, but then it should always have a correct value. The same goes for size.

You should do this because the assumption will always be that these values are correct, and as they are not, this could easily lead to bugs in the future.

Naming

• create should probably be called add
• n would be better as node or newNode (it is a small scope, so it's not that bad)
• your test cases should have proper names, so it is obvious what went wrong from looking at the name.

hashCode and equals

I said this already, but the list implements hashCode and uses the hashCode method of your Node class, but that class does not implement hashCode.

In equals: Do not just use !=, but use the equals method of your node, which in turn should use the equals method of the item. If you use non-primitive types, your current approach will lead to bugs.

Tests

As this is a generic list, I would not only test primitive types, but also custom classes.

• JavaDeveloper: Great feedback - but would you please explain "I said this already, but the list implements hashCode and uses the hashCode method of your Node class, but that class does not implement hashCode." in different words ? I seem to not get hang of it.
• tim: @JavaDeveloper sorry, I'll try to be a bit clearer. your DeleteAlternate class overrides the hashCode method, but your Node class does not. If you actually use hashCode, this can cause bugs. See also this question on how to implement hashCode and equals.

Answer 2

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.

Answer 3

This answer is an addendum to other answers and will handle only one aspect of your implementation : extensibility.

Your class should really be final for the following reasons :

• equals() and hashCode() are overridden. Since they are not final, any subclass could in turn override them again, which would mean a violation of the Liskov Substitution principle (for more information you may want to read Effective Java 2nd ed. Item 8.) You could just make equals() and hashCode() final to deal with this.
• The two overridable methods with actual behavior : deleteAlternate() and toList() in a subclass, do not have access to the private fields needed to implement them. In other words there is no meaningful way in which your class can be extended.