Java algorithm in linked lists

Question

I have the next classes: (Singly linked list)

public class class CharNode {
    private char _value;
    private CharNode _next;

    public CharNode(char val, CharNode n) {
        _value = val;
        _next = n;
    }

    public CharNode(char val) {
        _value = val;
        _next = null;
    }

    public int getValue() {
        return _value;
    }

    public CharNode getNext() {
        return _next;
    }

    public void setValue(char v) {
        _value = v;
    }

    public void setNext(CharNode node) {
        _next = node;
    }
}

and this class:

public class CharList {
private CharNode _head;

public CharList()
{
    _head = null;
}
 //methods
}

I need to write a method (called "what") that gets two char and returns the amount of possible lists that starts and ends with those char. for example if the linked list is "abbcd" the method what(a,b) will return 2 and the method what(a,c) will return 1. I saw the next solution:

public int what(char start, char end) 
{
    int count = 0, countStart = 0;
    CharNode temp = _head;

    while(temp != null)
    {
        if(temp.getValue() == start){
            countStart++;
            temp = temp.getNext();
            if(temp.getValue() == start && start == end)
                countStart++;
        }

        if(temp.getValue() == end && countStart>0){
            count += countStart;
        } 

        temp = temp.getNext();
    }

    return count;
}

but the problem is that I can't understand how they get the algorithm. In other words, how does it work "mathematical"?

Try to write your own. That way, you'll need to think on how this can be done. — RealSkeptic
– RealSkeptic, Commented Jul 3, 2017 at 15:28
The gist is: go through all elements, if you find one which matches the start, go through every subsequent element and count the elements which match the end. In my opinion it's written in a needlessly complex and confusing way. I wouldn't write it like that. — Michael
– Michael, Commented Jul 3, 2017 at 15:35

zThulj · Accepted Answer · 2017-07-03 15:59:37Z

1

The answer algorithm that you've posted :

Each time you find the start character, you increase the counter of "how many start" you've found.

And then, each time you find the 'end' character, you know that you have to add the current counter number of word, corresponding to the number of 'start' character found before this 'end' character.

Example :

For this string : 'ababab'

The first 'b' will give us 1 word because he has only 1 'a' before
The second 'b' will give us 2 words because he has 2 'a' before
The third 'b' will give us 3 words because he has 3 'a' before

edited Jul 3, 2017 at 15:59

answered Jul 3, 2017 at 15:39

zThulj

1497 bronze badges

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

2 Comments

Aaron Over a year ago

If I'm not mistaken, a 'weight' is generally understood as a reduction toward a number in the context of decision algorithm (i.e. you get multiple complex objects, you reduce them to numbers so that you can chose the lesser 'cost', which you'll obtain by adding some of these weights). I think both the algorithm and example you provide are great, but maybe you should focus on them and leave the 'weight' algorithm parallel aside : although the reduction toward number is there, we're not in the context of a decision algorithm

zThulj Over a year ago

Yeah, I wanted to explain the 'what algo' provided in the topic with easy words, it's certainly a translation misunderstanding. My bad. For me the weight was just a way to explain the current number of word. I'll change that in my answer.

D M · Accepted Answer · 2017-07-03 15:57:04Z

Well, let's look at the various sections of code.

int count = 0, countStart = 0;
CharNode temp = _head;

The above code just does simple initializations.

while(temp != null)
{
 // ....
    temp = temp.getNext();
}

The above code loops through your list.

    if(temp.getValue() == start){
        countStart++;

The above code keeps track of how many possible starting places there are so far.

    if(temp.getValue() == end && countStart>0){
        count += countStart;
    }

The above code says that when there's an end character, the count is increased by the number of starting characters so far. (Checking whether countStart>0 is actually not necessary, since if it was 0 you'd just add 0, but it doesn't hurt anything.) This makes sense - if you have aaa, then a b at that point would add 3 possibilities.

        temp = temp.getNext();
        if(temp.getValue() == start && start == end)
            countStart++;

The above code appears to be an attempt to account for the special case of the start and end characters being the same. I am NOT convinced that this section of code is correct - frankly, I think it introduces bugs in the case where start and end are different, by using getNext() out of turn.

Michael · Accepted Answer · 2017-07-03 16:13:28Z

As I stated in the comments, their implementation is a bit strange to me. Hopefully mine makes more sense.

The idea is to simply iterate through until you find a valid start character, then count all the valid end points from then on. Do the same until you reach the end of the list.

public int what(char start, char end) 
{
    int count = 0;
    CharNode currentNode = _head;

    while(currentNode != null)
    {
        if(currentNode.getValue() == start)
        {
            CharNode potentialEnd = currentNode.getNext();

            while (potentialEnd != null)
            {
                if(potentialEnd.getValue() == end) count++;

                potentialEnd = potentialEnd.getNext();
            }
        }
        currentNode = currentNode.getNext();
    }

    return count;
}

Here's a runnable example.

Yahya · Accepted Answer · 2017-07-03 18:19:16Z

This method searches for a given followed two chars in the List by passing the start and the end chars.

public int what(char start, char end)

The count variable is to calculate the total number of occurrence and repetition of the pair of chars (the start & the end chars). So, if we are looking for ab in abcabc the count will be incremented twice because it found the pair ab two times.

int count = 0,

And to count the one occurrence in case it could pass the two tests which are the start & the end chars are found followed by each other, we use:

countStart = 0;

The program starts from the head of the list and continues searching until there is no next node! That means temp.getNext() will return null!

CharNode temp = _head;
while(temp != null)
   .....................
   CharNode temp = _head;

Now for every current value, if it's the start char, proceed and start counting. Otherwise and in all cases - as long as there is next node - get the next node temp = temp.getNext();

Check then for the next node, and assign it to temp, if it's current value (next node's current value) equals start char AND start char is similar to end char complying to the user's request =, example: search for aa in abcaad, also increment the startCounter to announce finding it and to include it in the final result.

if(temp.getValue() == start && start == end)
    countStart++;
}

Now, we're still in the next node, so it's value should equals the end char whether the start and end chars similar or not. but to include the occurrence of the start char to be mandatory exact before the end char, we need to check if countStart bigger than zero, that means the previous start char has already been found. If so, add the one occurrence to the total and increment total count.

if(temp.getValue() == end && countStart>0){
        count += countStart;
}

At the end return total count

return count;

akiva · Accepted Answer · 2021-06-15 22:41:33Z

0

Here's a version that does the same in a linear time, it may help you to understand your version: (I did not test it, so I hope it works)

public int what (char start, char end) {
    int count = 0, res = 0;
    for (CharNode p = _head; p != null; p = p.getNext())
        if (p.getValue() == start)
            count++;
        else if (p.getValue() == end)
            res += count;
    return res;
}

answered Jun 15, 2021 at 22:41

akiva

3691 silver badge9 bronze badges

Collectives™ on Stack Overflow

Java algorithm in linked lists

5 Answers 5

2 Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

2 Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related