Java doubly linked list -- equality of two adjacent nodes

0
votes

A public method twoTogether() for the class MyList returns True, if and only if the list has two adjacent elements that are equal. You can assume that no list element (data) is null. Here are some examples: the list [a,b,c,d], would return false when calling this method. But a list [a,b,b,c] or [a,b,c,d,e,f,f]. The method returns true. Write the public method twoTogether. You can use the List interface references (fields: data, prev, next)(head,tail)(size) etc. Here is the code I have written:

 public boolean twoTogether(){
      currentNode = head;
      while (currentNode.hasNext()){ 
            if (currentNode.data != currentNode.next.data){ 
                  currentNode = currentNode.next;
            }
            else if (currentNode.data == currentNode.next.data){
                 return True;
            }
      }
      return False;
  }

Would this code correctly traverse a list testing for equality between two nodes? Am I implementing hasNext() correctly also? I was having a hard time figuring out how not to terminate the loop, or return true for the nested if, then false for the else statement.

2
javalisttraversaldoubly-linked-list
You haven't shown us the implementation for hasNext(). How are we supposed to know if it is correct? Also, what type is data? Unless it's a primitive, your equality checking is going to fail. (and I assume it is not, since you mentioned a chance it could be null). – azurefrog
You code can't compile like this. The compiler should complain about missing return value. – nhahtdh
Thanks nhahtdh, ill get that fixed – KimCheeFatChoyProgrammer
@azurefrog haskell is using a linkedlist iterator. I implied that, he wasn't explicit in that fact. While i'm hear, Haskell I was correct in assuming that currentNode and head are of type LinkedList.Iterator, yes? – Freestyle076
Be careful with your (perhaps mythical) hasNext method. If this is an assignment, you would do well to take note of the limitations, specifically You can use the List interface references (fields: data, prev, next)(head,tail)(size) etc - I see nothing there about using methods to detect list end. – paxdiablo

2 Answers

2
votes

You're right, the loop termination isn't exactly right. The first two branches within the while loop doesn't belong. One of the first two branches will always fire, as != and == are complements. The return false statement belongs outside of the while loop, indicating the entire list has been traversed and no equal adjacent nodes.

public boolean twoTogether(){
    currentNode = head;
    while (currentNode.hasNext()){ 
        if (currentNode.data != currentNode.next.data){ 
            currentNode = currentNode.next;
        }
        else if (currentNode.data == currentNode.next.data){
            return True;
        }
    }
    return False;
}

the use of hasNext() is perfect! never want to over-traverse a list... hope this helps!

1
votes

The basic idea is as follows:

  • Step one, check if the list is empty. If that's the case then, by definition, there can be no duplicates, so return false and stop.

    This prevents you from trying to evaluate the following element when the current one does not exist).

    Otherwise, start with the current element being the first in the list.

  • Step two, you need to carry on as long as there is at least one more following the current element (since you want to check current against next).

    If there is no following element then you've finished the list and no duplicates were found, so immediately return false (hence stopping).

  • Step three, you now know there is both current and next, so actually check current against next.

    If their data is identical, you've found a duplicate and you can immediately return true (hence stopping).

  • Step four, there's no duplicate at this point but there may be one further on, so advance to the next element and go back to step two above for rechecking whether you've reached the end.

The pseudo-code for this would be (passing in head as the argument):

def twoTogether (node):
    if node == null:                     # empty means no dupes possible
        return false

    while node.next != null:             # loop through list
        if node.data == node.next.data:  # check current against next
            return true
        node = node.next                 # advance to next

    return false                         # no dupes before list end