Delete nodes in linkedlist whose next node is greater

Question

Given a singly linked list, remove all the nodes which have a greater value on right side.

Examples:

a) The list 12->15->10->11->5->6->2->3->NULL should be changed to 15->11->6->3->NULL. Note that 12, 10, 5 and 2 have been deleted because there is a greater value on the right side.

When we examine 12, we see that after 12 there is one node with value greater than 12 (i.e. 15), so we delete 12. When we examine 15, we find no node after 15 that has value greater than 15 so we keep this node. When we go like this, we get 15->6->3

b) The list 10->20->30->40->50->60->NULL should be changed to 60->NULL. Note that 10, 20, 30, 40 and 50 have been deleted because they all have a greater value on the right side.

c) The list 60->50->40->30->20->10->NULL should not be changed.

This question is attributed to GeeksForGeeks.

Looking for code-review, optimizations and best practices

public class DeleteGreaterValueOnLeft {
 private Node first;
 private Node last;
 private int size;
 public DeleteGreaterValueOnLeft(List<Integer> items) {
 for (Integer item : items) {
 add (item);
 }
 }
 private void add (Integer item) {
 Node node = new Node(item);
 if (first == null) {
 first = last = node;
 } else {
 last.next = node;
 last = node;
 }
 size++;
 }
 public static class Node {
 private Node next;
 private int item;
 Node (int item) {
 this.item = item;
 }
 }
 public void deleteCurrentIfNextGreater() {
 reverse();
 delete();
 reverse();
 }
 private void reverse() {
 Node prev = null;
 Node ptr = first;
 Node ptrNext = null;
 while (ptr != null) {
 ptrNext = ptr.next;
 ptr.next = prev;
 prev = ptr;
 ptr = ptrNext;
 }
 first = prev;
 }
 private void delete () {
 Node ptr = first;
 while (ptr.next != null ) {
 if (ptr.item > ptr.next.item) {
 ptr.next = ptr.next.next;
 } else {
 ptr = ptr.next;
 }
 }
 }
 // size of new linkedlist is unknown to us, in such a case simply return the list rather than an array.
 public List<Integer> toList() {
 List<Integer> list = new ArrayList<>();
 if (first == null) return list;
 for (Node x = first; x != null; x = x.next) {
 list.add(x.item);
 }
 return list;
 }
 @Override
 public int hashCode() {
 int hashCode = 1;
 for (Node x = first; x != null; x = x.next)
 hashCode = 31*hashCode + (x == null ? 0 : 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;
 DeleteGreaterValueOnLeft other = (DeleteGreaterValueOnLeft) obj;
 Node currentListNode = first; 
 Node 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 DeleteGreaterValueOnLeftTest {
 @Test
 public void test1() {
 DeleteGreaterValueOnLeft dgvol1 = new DeleteGreaterValueOnLeft(Arrays.asList(1, 2, 3, 4, 5));
 dgvol1.deleteCurrentIfNextGreater();
 assertEquals(new DeleteGreaterValueOnLeft(Arrays.asList(5)), dgvol1);
 }
 @Test
 public void test2() {
 DeleteGreaterValueOnLeft dgvol2 = new DeleteGreaterValueOnLeft(Arrays.asList(5, 4, 3, 2, 1));
 dgvol2.deleteCurrentIfNextGreater();
 assertEquals(new DeleteGreaterValueOnLeft(Arrays.asList(5, 4, 3, 2, 1)), dgvol2);
 }
}

• Vogel612: Question: Is the behaviour for a linked list: "12->15->10->16->5->2->3->NULL" defined? "on the right side" is a little unclear IMO. It could be either: "15->16->5->3->NULL" or "16->5->3->NULL", please clarify ;)

Answer 1

Nice code. I'm assuming that you read Vogel612 comment and it is doing what you want it to do.

Naming

• ptrNext, ptr, but then only prev? I would make this uniform. Probably: next, current, and previous (or nextNode, currentNode, and previousNode to avoid having next for two different things). I would also make sure that I follow the same pattern I choose here in the other methods.
• I would probably call the class SingleLinkedList or something like that.

Errors

• In reverse: you do not change the last field
• In delete: here, you are not only not changing the last field, but also the first field, as well as the size field

Optimizations

Traversing two times through the list to reverse it should be unneccessary. Just go forwards in the list, check if the next item is bigger, and - if so - set the previous nodes next field to the currents nodes next value (and handle it for first and last outside the loop).

Other

• Your List implements hashCode and uses the hashCode method of the node class, but this class does not implement the method.
• You have the private add method but never use it. Unused private methods should probably be deleted.

Tests

• Your test should definitely check all the examples from the question (although the two you have probably cover all cases).
• They should also check corner cases. Are first and last (and size) set correctly?

Comments

You don't have to overdo it with comments, but just one seems a bit few. Some comments that might be useful:

• Are the first, last and size field affected by the method? (should definitely be commented on in case the methods handle this differently, like in your case add and delete for example)
• reverse: a comment for what this does probably would not hurt