Java How to check if linked list has duplicate entries

Question

The method is supposed to check if the linked list has more than one of the same entry. I tried getting the method to check if the head is equal to the current node and then having the current equal to current.next, if the head never equals the current, i have the head equal to head.next and restart the current by assigning it to firstNode. When i try to test the code it gives me the following error:

Exception in thread "main" java.lang.NullPointerException at LinkedBag1.hasDuplicateEntries(LinkedBag1.java:182) java:182 is while((!head.equals(current)) || (current != null)){

Not sure what this means and what is causing my method to make this error appear.

    public boolean hasDuplicateEntries(){
    Node head = firstNode;
    Node current = head.next;
    boolean duplicate = true;

    while((!head.equals(current)) || (current != null)){
        if(head.equals(current)) {
            duplicate = true;
        }
        else{
            current = current.next;
        }
        current = firstNode;
        head = head.next;


    }


    return duplicate;
}

Is there anything I did wrong in my method? Any help will be appreciated.

If you don't want to sort the list first, you will have to use two loops, the outer one which touches every element, and the inner one which scans for duplicates. — Tim Biegeleisen, Sep 06 '16 at 01:57
@PM77-1 I think the bigger problem is the algorithm, but yeah, that too. — Tim Biegeleisen, Sep 06 '16 at 01:57

score 1 · Accepted Answer · answered Sep 06 '16 at 01:58

1

I think your problem is with head = head.next; What is head.next for the last node in your list? What happens when you set head to that value then loop back and check head.equals(current) again?

(Also, maybe you're already aware of this, but I think your algorithm will only work if the duplicate entries are right next to each other.)

answered Sep 06 '16 at 01:58

Bill the Lizard

398,270
210
566
880

I'm trying to get the head to check if it's equal with any of the entries. So when current has reached the end of the list, the head moves on to the next link. Which then checks to see if any entries are equal to it. – benoit Sep 06 '16 at 02:05
@benoit Ok, I wasn't quite following your logic. – Bill the Lizard Sep 06 '16 at 02:07

score 0 · Answer 2 · answered Sep 06 '16 at 02:30

0

Not sure about the exception, but the method will always return true, as you set "duplicate" to true when you initialize it, and only set it to true later (need "boolean duplicate = false;")

answered Sep 06 '16 at 02:30

153045

31
3

score 0 · Answer 3 · answered Sep 06 '16 at 02:47

public boolean hasDuplicateEntries() {
    int currentIndex = 0;
    for (Node current = head; current != null; current = current.next) {
        //with each node in list, compare it to all element of list
        int nodeIndex = 0;
        for (Node node = head; node != null; node = node. next) {
            if (currentIndex != nodeIndex && node.equals(current)) {
                return true;
            }
            nodeIndex++;
        }
        currentIndex++;
    }
    return false;
}

score 0 · Answer 4 · answered Sep 06 '16 at 02:57

0

Do you want to remove duplicate element ? thus, you can use some date structure that can not contain duplicate item, like Set.

answered Sep 06 '16 at 02:57

larry lai

1

Just want to return true if it does contain duplicates and false otherwise – benoit Sep 06 '16 at 03:01

Java How to check if linked list has duplicate entries

4 Answers4