How to count duplicates in a list using a circular linked list

user_17230029 0
Viewed 294

I am working on expanding my circular linked list and I implemented a few methods that will add and delete nodes from a list. I want to create a method that will count the duplicates in a list, the method should return the number of objects that occur more than once in the list. for example a list has [30, 30, 50, 50, 80, 90, 10, 10] the method should return: the number of duplicates is 3

I have tried implementing the following method but this method only counts the total nodes in the list, what should I add to make it count the duplicates in the list.

public int countNode() {
    int count = 0;

    if (!isEmpty()) {
        Node<E> temp = current;
        Node<E> prev = current;

        do {
            if (prev.element == temp.element)
                count++;
                temp = temp.next;
                prev = prev.next;
        } while (temp != current);
    }

    return count;
}
circular-list do-while java
3 Answers

You are initializing prev and temp with the same node. So the comparison always returns true and the two nodes are continuing together

user_133851860

The simple solution is to use Java's HashSet data structure which only allows unique values. You will need to add each node's value to the set as you iterate. In the end, the difference between the size of the set and the size of the list will be your answer.

Here I've simplified an example code by representing circular linked list as an array of integers:

// Your linkedlist, shown as an array
int[] arr = new int[] {30, 30, 50, 50, 80, 90, 10, 10};

// Allows only unique values
HashSet<Integer> set = new HashSet<Integer>();

// Fill your set
for(int n : arr) {
    set.add(n);
}

// answer = list's length - set's length
System.out.println(arr.length - set.size());
user_135951200

To define a unique object Node(as opposed to primitives) define its hasCode and equals as demonstrate in the following mre:

import java.util.*;

public class Main   {

    public static void main(String[] args) {
        int[] values = new int[] {30, 30, 50, 50, 80, 90, 10, 10};

        Node root = null, node = null;
        for(int i : values){
            if(root == null) {
                root= new Node(i);
            }else if(node == null){
                node = new Node(i);
                root.setNext(node);
            }else{
                Node temp = new Node(i);
                node.setNext(temp);
                node = temp;
            }
        }

        System.out.println("Number of distinct Nodes: "+countUniqueNodes1(root));
        System.out.println("Number of distinct Nodes: "+countUniqueNodes2(root));
    }

    //not null safe
    public static int countUniqueNodes1(Node root){
        Node next = root.getNext();
        Set<Node> nodesSet = new HashSet<>();
        nodesSet.add(root);

        while (next != null){
            nodesSet.add(next); 
            next = next.getNext();
        }
        return nodesSet.size();
    }

    //not null safe
    public static int countUniqueNodes2(Node root){
        Node next = root.getNext();
        List<Node> nodes = new ArrayList<>();
        nodes.add(root);

        while (next != null){
            nodes.add(next);
            next = next.getNext();
        }
        return (int) nodes.stream().distinct().count();
    }
}

class Node{

    final int value;
    private Node next;

    public Node(int value) {
        this(value, null);
    }

    public Node(int value, Node next) {
        this.value = value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    @Override
    public int hashCode() {
        return String.valueOf(value).hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof Node)) return false;
        return value == ((Node)obj).value;
    }
}
user_39929390
Related