CODEWITHSUNDEEP
javacollectionslinked-listnodes
pharaon450
pharaon450

Reputation: 523

How to count how many different nodes are in my linkedlist?

I made my own Node class and my own LinkedList class, I would like to build a function that counts how many different Node are in my LinkedList.

I have tried with this code but it does not work:

for (int i = 0; i < quantityOfNode(); i++) {
    boolean isDistinct = true;

    for (int j = 0; j < i; j++) {
        if (node.getInfo().equals(node.getNext().getInfo())) {
            isDistinct = false;
        }
    }
    if (isDistinct) {
        nbDistinct++;
    }
    if (node.getNext().getNext() != null) {
        node= node.getNext();
    }
}

exemple :

        list.add(3);
    list.add(2);
    list.add(5);
    list.add(3);
    list.add(3);
    list.add(8);

this is supose to give me 4 different node, but i get 5, because the node 3 is counted 2 times

Now i have tried to travel with a second node in my j loop and for the same input it now gives me 2 instead of 4

here is the new code i tried and still not working :

            for (int i = 0; i < quantityOfNode(); i++) {
            boolean isDistinct = true;
            for (int j = 0; j < i; j++) {
                if (node.getInfo().equals(node2.getInfo())) {
                    isDistinct = false;

                }

                if (node2.getNext() != null) {
                    node2 = node2.getNext();
                }

            }
            if (isDistinct) {
                nbDistinct++;
            }
            if (node.getNext() != null) {
                node= node.getNext();
            }
        }

Upvotes: 0

Views: 3116

Answers (5)

OldCurmudgeon
OldCurmudgeon

Reputation: 65811

Your j loop is not stepping node forward - it is always comparing the same pair of nodes and thus has no function.

You need something like:

...
Node earlierNode = rootNode;
for (int j = 0; j < i; j++) {
    if (earlierNode.getInfo().equals(node.getInfo())) {
        isDistinct = false;
    }
    earlierNode = earlierNode.getNext();
}
...

Upvotes: 1

corsiKa
corsiKa

Reputation: 82579

You can use a Set.

Set set = new HashSet();
Node cur = list.head;
while(cur != null) {
    set.add(cur.getInfo());
    cur = cur.getNext();
}
return set.size();

This doesn't use generics because I don't konw what types you have for getInfo.

Alternatively, if you cannot use a set, you should try to get rid of your 'index' variables (i and j). You really want to focus your application logic on what you actually have, not values implicitly calculated. You want to stop when your current node becomes null, not when you've advanced a certain number of times. If that's not logical let me know.

For each node, check the nodes before it to see if that node exists. I start at the head each time because I don't know if you have double links or not. It's the same complexity either way, but on a sorted list this is less optimal.

Node cur = list.head; // for each node
int nbDistinct = 0;
while(cur != null) { // go until we're out of nodes
    Node check = list.head; // check the first node
    boolean isDistinct = true; // assume distinct
    while(check != cur && isDistinct) { // stop if we found a match OR if our checker caught up to our current node
        isDistinct |= !check.getInfo().equals(cur.getInfo()); // essentially "if(check.getInfo().equals(cur.getInfo()) isDistinct = true;"
        check = check.getNext(); // advance the checker
    }
    if(isDistinct) nbDistinct++;
    cur = cur.getNext(); // advance the current node
}

Upvotes: 2

OldCurmudgeon
OldCurmudgeon

Reputation: 65811

Your first time around the i loop your j loop does nothing (because it starts at 0 and continues while j < i which it isn't) so you leave distinct set true without comparing anything with anything.

Try starting i at 1.

Upvotes: 0

Patashu
Patashu

Reputation: 21773

First problem:

If your for loop is written such that it does not go over the length of the linked list:

for (int i = 0; i < length(); i++) {

Then why do you need this?

            if (node.getNext().getNext() != null) {
                node= node.getNext();
            }

In particular, this code might mean that a node just before the end is evaluated twice, because the node beyond it is null. It is not necessarily making your algorithm wrong, but it smells bad and I don't like it.

Second problem:

            for (int j = 0; j < i; j++) {
                if (node.getInfo().equals(node.getNext().getInfo())) {
                    isDistinct = false;
                }
            }

This is a faulty way to calculate duplicates because you do not store and advance the position of the second node you are comparing against. Try something like

            Node node2 = firstNode(); //idk what method gets the first node :)
            for (int j = 0; j < i; j++) {
                if (node.getInfo().equals(node2.getInfo())) {
                    isDistinct = false;
                    break; //optimization, stop as soon as we find a duplicate
                }
                node2 = node2.GetNext();
            }

Finally, whenever faced with code that does not work, attach a debugger, step through it and notice when the code does not do what you expect it to. This will solve all logic errors quickly with just a small amount of observation. Even if you don't have access to the debugger, you can use print statements to print the value of various variables and when certain code branches execute and compare to what you expected would happen.

Upvotes: 2

BevynQ
BevynQ

Reputation: 8269

Use a Set

Set<Node> mySet = new HashSet<Node>(list);
answer = mySet.size();

this depends on you implementing hashCode and equals in your node class, alternatively you could use TreeSet and a Comparator.

Comparator<Node> myComparator = new MyCustomComparator();// you have to define your comparator.
Set<Node> mySet = new TreeSet<Node>(myComparator);
mySet.addAll(list);
answer = mySet.size();

Upvotes: 0

Related Questions