Java doubly linked list -- equality of two adjacent nodes

Question

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.

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
– azurefrog, Commented Dec 8, 2014 at 4:36
You code can't compile like this. The compiler should complain about missing return value. — nhahtdh
– nhahtdh, Commented Dec 8, 2014 at 4:37
@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
– Freestyle076, Commented Dec 8, 2014 at 5:04
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
– paxdiablo, Commented Dec 8, 2014 at 5:07

Freestyle076 · Accepted Answer · 2014-12-08 05:05:35Z

2

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!

edited Dec 8, 2014 at 5:05

answered Dec 8, 2014 at 4:47

Freestyle076

1,5762 gold badges19 silver badges39 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

KimCheeFatChoyProgrammer Over a year ago

Awesome, so basically hasNext() is a check to see if the currentNode has a next node? Is there a difference from using: while(currentNode.next != null) { ??

paxdiablo Over a year ago

Careful, this will crash on an empty list, and I find the use of if (x) action1 else if (!x) action2; to be , ..., tortured (sorry, trying to be tactful). There are much cleaner ways to express what you're trying to do.

Freestyle076 Over a year ago

Well, list iterators do not have a variable member next, but they do have a next() function. It returns the next node (NULL if there isnt one) AND ADVANCES THE ITERATOR. This means you would need to eliminate the node advancement in the first branch.

paxdiablo · Accepted Answer · 2014-12-12 03:19:08Z

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

Collectives™ on Stack Overflow

Java doubly linked list -- equality of two adjacent nodes

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related