a question with linked list

[rian bron]

Hello guys, i have a question about linked list i got for homework and i need your help:

i got these 2 classes:

ublic class IntNodeTwo
{
    private int _num;
    private IntNodeTwo _next,_prev;

    public IntNodeTwo(int n)
    {
        _num=n;
        _next=null;
        _prev=null;
    }

    public IntNodeTwo(int num,IntNodeTwo n,IntNodeTwo p)
    {
        _num=num;
        _next=n;
        _prev=p;
    }

    public int getNum()
    {
        return _num;
    }

    public IntNodeTwo getNext()
    {
        return _next;
    }
    
    
    public IntNodeTwo getPrev() 
    {
        return _prev;
    }

    public void setNum(int n)
    {
        _num=n;
    }

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

    public void setPrev (IntNodeTwo node)
    {
        _prev=node;
    }
}

public class IntListTwo
{
    private IntNodeTwo _head,_tail;
    public IntListTwo()
    {
        _head=null;
        _tail=null;
    }

    public IntListTwo(IntNodeTwo h,IntNodeTwo t)
    {
        _head=h;
        _tail=t;
    }
}

now, i need to write a method in the IntListTwo class that gets an average int from the user, and returns true if there is a sub-list that it's average is equals to the given average. and false if not.
the method should look like this :

public boolean average(int average)
{...}

so i thought about the algorithm:
1. i will calculate the sum of all the list + count the number of numbers in the list.
2. i will calculate the average of the list ( sum/count)
3. if the average is bigger than the given average, i will subtract the last element from the sum and subtract 1 from the counting and take the last element of the list one step back.
3. if the average is smaller than the given average, i will subtract the first element from the sum and subtract 1 from the counting and take the first element of the list one step forward.

By the way- the list is sorted!
Now, when i have the algorithm im still struggling to write it,
would you help me ?
Thank you !

[Piet Souris]

hi Rian,

are you sure that this is a Beginners item?

I like your algorithm, but my first thought is that you need to sort your list first. If it is unsorted, removing your last element might increase the calculated average. Alternatively, you could start with element 0, and maintain a running average, to which you can apply your algo. Might be a tad easier to implement. But these are my first two thoughts, Does this sublist need to contain only consecutive elements?


Edit: your edit about the list being sorted came just before my reply!

[Piet Souris]

I would start by writing a method 'int removeLastNode()' and 'int removeFirstNode()' in  your IntListTwo class. The return value is the value of the removed node.

[Paul Clapham]

I would suggest starting with a method which takes an IntListTwo object and returns its average. Then you could use a method which takes an IntListTwo object and returns another IntListTwo object which is the input object with the tail node removed. And another method which does the same for head node.

[rian bron]

Piet Souris wrote:I would start by writing a method 'int removeLastNode()' and 'int removeFirstNode()' in  your IntListTwo class. The return value is the value of the removed node.

yes, i know this one , but i am struggling to write those 2 methods and basically those 2 methods are the answer plus some things around it but basically this is that answer.
can you show me how to write on of them and i will try to write the other one?

thank you

[Paul Clapham]

The removeLastNode method which Piet suggests will have to be a method of the IntListTwo class, of course. Now ask yourself "What information in the IntListTwo class would I have to change to remove its last node?" And then "How would I do that?" The latter question might involve drawing pictures which contain nodes linked together with arrows.

[Piet Souris]

hi Rian,

first of all: we must be careful not to make your homework for you. That could bring about all sorts of misery.

Second: I would first make a copy of your IntListTwo object. That is easy, you just need a new IntListTwo, with _head and _tail of your original. Then you can freely remove heads and tails, but alternatively you can do what Paul suggests and return a new List with altered heads or tails.

Suppose you want to remove _head. It means that the new _head will be the node referred to by _head.next (if present, it could be null if the list only contains a head and a tail). So, make a note of the heads value (that you can use as your return value). Now, all that is left to do is making _head.next your new _head. How would you do that? And analoguus for removing the _tail.

Edit: almost forgot: remember that _head.next has a previous field that refers to its predecessor. Now, what to do if this predecessor gets removed? Follow Pauls suggestion and draw some nodes with arrows in between them, so that it becomes clear what will happen to the arrows if a node gets eliminated.

[Piet Souris]

Ajakkes.

It is more complicated than I thought. The problem is that when replacing _head by _head.next, you must, as I wrote, edit the 'previous' field of _head.next. But that means that you also change the original _head.next, since it is the same object. And that means that your original IntListTwo will be in an inconsistent state.

So, you can't change your _head.next directly. What about making a constructor in your IntNodeTwo class that takes an IntNodeTwo object as parameter (a copy constructor, as it were)?

[Piet Souris]

It's midnight here in Holland, time for me to go to bed. But my last remark before making a complete mess of this topic:

forget about all that removing of heads an tails and copying nodes and editing fields: way too complicated. Just maintain two nodes: currentHead and currentTail, that you initiate by making them equal to _head and _tail. Now, iff you want to 'remove' the _head, just do: currentHead = currentHead.next. No editing, no complicated things, and likewise for the 'removal' of _tail.

[Paul Clapham]

Piet Souris wrote:It is more complicated than I thought.

Rule 2 of Life, the Universe, and Everything: "It's actually more complicated than that."

[Piet Souris]

 

Or to quote Hofstadters Law: it is always more difficult than you think, even if you take Hofstadters Law into account.

[Piet Souris]

hi Rian,

when I went to bed last night, I was thinking about a problem. If your list has n elements, then there are n(n+1)/2 subsets that have only consecutive elements, so possible candidates. Your procedure however, considers only n of them. So, is that procedure so clever that it can eliminate most of the possible solutions? If we define (a, b) as the subset that starts with element at index a and ends with element at index b, and suppose your list has 10 elements, your procedure might be:

(0, 9) -> av. too small (compared to the user input) ->
(1, 9) -> av. still too small ->
(2, 9) -> av. too high  ->

***
now there are two possibilities to decrease the average: either reduce the 2 (making it 1) or reduce the 9 (making it 8). However, reducing the 2 brings us back to (1, 9) that we already investigated. So, we consider (2, 8). That is what your procedure does anyway
***

(2, 8) -> av. too high  ->

***
Now your procedure continues with (2, 7), but it does not consider (1, 8). Conclusion is that not all candidates will be investigated.
***

A classic way is to use a Queue, with a breadth-first-search for instance, but that is certainly not simple to implement. What, for instance, should the objects be that you put in the Queue?

I don't know your knowledge and experience, but is there anything that you were taught that sounds like it could be of use here?

[Piet Souris]

Hmm, when coding some BFS search with a queue, I realised I made a big blunder in my reasoning. I said that the algo did not inspect (1, 8), and that that was wrong, but it is absolutely correct! Before, I said that the average of (1, 9) was too small, well, then that is certainy true for (1, 8). So I have faith in the correctness of the algo, although I have not proven it completely, yet.

I just finished the code with what I suggested, using the variables currentHead, currentTail, currentSum and currentNrOfElements, and it works great. I used this algo:

1) set currentHread = head, currentTail = tail, sum = sum of all elements, N = number of elements.
2) if calculated average is too low, then sum = sum - currentHead.value, N = N - 1, currentHead = currentHead.next (i.e. making the step from (0, 9) to (1, 9))
3) et cetera.

You could start by checking that the user supplied average is at least equal to the first element, and that it is not higher than the last element.

Sorry for all the confusion I caused. How are you doing?