Win a copy of Functional Reactive Programming this week in the Other Languages forum!

Alex Ba
Ranch Hand
Posts: 35
For my current project, I have to write a method that checks to see if one linked list is equal to another. They must be the same length, but the nodes don't have to be in the same spot. AKA

1
3
8

is equal to

1
8
3

But the problem is I can't think up a way to check the values of 2 different lists from the class and not the main? Looking for logic help, not code.

Hunter McMillen
Ranch Hand
Posts: 492
Well from my point of view, It'd be a lot easier to focus on what makes them not equal, anything left over after the not equal list would have to be equal. So the first thing I would do is check their sizes. Then take one list and check to see if any of the values in the second list dont match the values from the first list.

so something like:
List 1 = {1,2,3}; //these cant be equal
List 2 = {1,2};

List 1 = {1,2,3}; //these also can't be equal
List 2 = {2,3,4};

-Hunter

Alex Ba
Ranch Hand
Posts: 35
But how would I do that in a method from a class? In my head it works out like so:

First, check both lists' lengths, and if they are unequal equals returns false
Then, run a while loop that traverses list a, and a nested while loop that traverses list b. AKA,

List a = {1,2,3}
List b = (3,1,2}

1 against 3 = false, increment b, 1 against 1 true;
2 against 3 = false, increment b, 2 against 1 false, increment b, 2 against 2 = true;
3 against 3 = true;

Make sense?

The problem I'm having is I can't seem to get my mind around using 2 lists. I'm so used to things like:
current = head (setting the node to be checked as the first item in a list)

But wouldn't I then need like, currenta and currentb? And how would I write that? currenta = .... (since I have 2 lists)

Paul Clapham
Sheriff
Posts: 21416
33
Alex Ba wrote:But how would I do that in a method from a class?

This question doesn't really make sense because (a) where else would you do that except in a method, and (b) methods are always in a class. So it really just boils down to "How would I do that", doesn't it?

Hunter McMillen
Ranch Hand
Posts: 492
I think you idea of nested while loops would work fine. Maybe try something like this:

-Hunter

Janeice DelVecchio
Saloon Keeper
Posts: 1809
12
Paul -

If you read the last line of Alex's first post, it makes me believe he's not used to doing things from outside the main method (procedurally). I THINK he wants to know how to execute the comparison loops from within a different class and method than the main method.

Alex Ba
Ranch Hand
Posts: 35
To clarify, I'm used to using classes and methods and whatnot. I'm not used to traversing 2 different lists from from a class (as opposed to a main.)

Like, in a main:

Or in my insert method, you're working with one list and not two. I'm confused about how to traverse two DIFFERENT lists outside the main.

Mike Simmons
Ranch Hand
Posts: 3090
14
I'm not sure we understand by the distinction of "in a class" vs. "in a main". Have you noticed that your main methods must be declared inside a class, or they won't compile? You're always "in a class", in some sense, in Java. That's the way the language was designed.

(Whether or not this was a good idea is another discussion. Nothing to see here, move along.)

It's possible this question is actually about the difference between static methods and non-static methods. Also known as class methods and instance methods. Have these terms come up recently in your course?

Alternately, have you ever written any method declarations other than a main method? Any non-static methods? Have you ever written a method that began "public boolean equals(Object ___)"?

Sorry if some of these questions seem basic, but I think it might be good to get a better idea of where your understanding is now.

Hunter McMillen
Ranch Hand
Posts: 492
if you made a traverse method it would look something like:

you could pass two different linkedlists into this method.

-Hunter

Rahul P Kumar
Ranch Hand
Posts: 188
Alex, what containsAll() yields?

shivendra tripathi
Ranch Hand
Posts: 263
Add content of one list to Set, store the size of set. Add content of another List, check if Set size gets increased. If so two lists are not equal.

Patricia Samuel
Ranch Hand
Posts: 300
It seems a better solution - Using set to check the equality.

Great Tripathi

Rahul P Kumar
Ranch Hand
Posts: 188
Patricia Samuel wrote:It seems a better solution - Using set to check the equality.

Great Tripathi

hehehe what makes you think that is better solution, was it cleverness of solution.
Ok, Our problem stated is like this:

For my current project, I have to write a method that checks to see if one linked list is equal to another. They must be the same length, but the nodes don't have to be in the same spot.

Now, create a set of first list, time complexity is (n^2 + n)/2 worst case scenario (i.e. order of two), now when you add second list of same size say n then extra time of order two.

Think about containsAll(). that is off the shelf method. Given list is same size, but order of elements may be different, so time complexity of this will be n^2.

Mike Simmons
Ranch Hand
Posts: 3090
14
shivendra tripathi wrote:Add content of one list to Set, store the size of set. Add content of another List, check if Set size gets increased. If so two lists are not equal.

Well, that's a good start (assuming the original poster is allowed to use standard library classes for this). However, what happens if the second list contains some but not all of the elements from the first list? What happens if the second list is completely empty?

Mike Simmons
Ranch Hand
Posts: 3090
14
Rahul.p Kumar wrote:Now, create a set of first list, time complexity is (n^2 + n)/2 worst case scenario (i.e. order of two), now when you add second list of same size say n then extra time of order two.

No, it isn't. Not unless the equals() and hashCode() methods are really, really bad.

Patricia Samuel
Ranch Hand
Posts: 300
Mike,

Should not we check the size of list first before adding to the Set??

Rahul - Please be nice on the forum. We are just discussing the topic.

Mike Simmons
Ranch Hand
Posts: 3090
14
Well, that might help, but I don't think it's enough.

What if list 1 is { 1, 2, 3, 4, 5 }, and list 2 is { 1, 1, 1, 1, 1 }?

Patricia Samuel
Ranch Hand
Posts: 300
Agree. This test case fails the logic.

Patricia Samuel
Ranch Hand
Posts: 300
But does containsAll() solve the purpose -

Vivek Singh
Ranch Hand
Posts: 92
Yes the containsALL will be better solution for same length. AS here we want to check only if They Are Equal irrespective of node position.

But length of list should be campared.

Vivek Singh
Ranch Hand
Posts: 92

WORK for all conditions.. as per the requirement of task.

Raghavan Muthu
Ranch Hand
Posts: 3381
Alex,

I guess whatever the logic you have explained with nested loops should be fine. I am not very sure of the order of complexity. Being a beginner, I think you can take that for granted.

But just beware of the 'containsAll()' methods. The behavior of containsAll() method is to convey the fact the the list which is being compared [list2 in list1.containsAll(list2)] is a part of list1 are not. That's all.

Rahul P Kumar
Ranch Hand
Posts: 188
ok, Vivek, I see flaw in containsAll(), as {1, 2, 3, 4} is not equal to {1, 2, 3, 2}, then probably we should check both way l1.containsAll(l2) and if(true) then check l2.containsAll(l1) further. But now it sounds somewhat less simple and off the shelf

Rahul P Kumar
Ranch Hand
Posts: 188
Mike Simmons wrote:
Rahul.p Kumar wrote:Now, create a set of first list, time complexity is (n^2 + n)/2 worst case scenario (i.e. order of two), now when you add second list of same size say n then extra time of order two.

No, it isn't. Not unless the equals() and hashCode() methods are really, really bad.

even with well overridden equal() and hashcode(), if you will put first element in set it checks for 0 element, for second element, check is one times, whether it wsi present or not for third element, two times and so on. I am talking about worst case scenario. Then ceratinly for nth element it will be (n-1) times, it means when you are putting first list in set, time complexity will be (0+1+2+....+n-1). now put second list in same set, will not check again each and every element for equality again. so totally it will be (n^2 + n), not even divided by 2. What is wrong with this Mike.

shivendra tripathi
Ranch Hand
Posts: 263
Rahul.p Kumar wrote: ok, Vivek, I see flaw in containsAll(), as {1, 2, 3, 4} is not equal to {1, 2, 3, 2}, then probably we should check both way l1.containsAll(l2) and if(true) then check l2.containsAll(l1) further. But now it sounds somewhat less simple and off the shelf

even this will not work think abt L1 = {1,2,2,3} L2 = {1,3,3,2}

Raghavan Muthu
Ranch Hand
Posts: 3381
Just to clear the fuzz being discussed about containsAll() .

If you look at the Javadoc of the containsAll(Collection<?> c) method, it says,

Returns true if this list contains all of the elements of the specified collection

Assume you have

would return true as the list1 (1,2,3,4) contains all the elements of the list2 (1,2,3) which is the list being compared (in other words, 'specified' as that of API's doc).

whereas, the test on

would return false, as the list2 (1,2,3) does NOT contain all the elements of list1 (1,2,3,4).

Hope this clears.

Having understood what the method does and what it does NOT, i guess you can proceed with the further steps on accomplishment of goal.

Rahul P Kumar
Ranch Hand
Posts: 188
Patricia Samuel wrote:

Rahul - Please be nice on the forum. We are just discussing the topic.

Patricia, I am sorry, If I have offended you. The thing is, the first thing came to my mind is the cleverness of the solution. Actually I liked this alternative, but I could not resist smiling the way it was solved. that is called workaround it, that we all do every now and then, when we caught up in such situations.

Rahul P Kumar
Ranch Hand
Posts: 188
shivendra tripathi wrote:
Rahul.p Kumar wrote: ok, Vivek, I see flaw in containsAll(), as {1, 2, 3, 4} is not equal to {1, 2, 3, 2}, then probably we should check both way l1.containsAll(l2) and if(true) then check l2.containsAll(l1) further. But now it sounds somewhat less simple and off the shelf

even this will not work think abt L1 = {1,2,2,3} L2 = {1,3,3,2}

You are right Tripathi.

Mike Simmons
Ranch Hand
Posts: 3090
14
Rahul.p Kumar wrote:even with well overridden equal() and hashcode(), if you will put first element in set it checks for 0 element, for second element, check is one times, whether it wsi present or not for third element, two times and so on.

It's kind of hard to follow what you are saying here. But I am assuming that when you talk about putting things in a Set, we might at least use a really well-known and very efficient implementation, a HashSet. From your description, it sounds like either you are not considering this possibility, or you don't really understand how it works. Either way, I suggest reading about the hash table algorithm to understand why basic operations like add() or contains() are O(1), not O(n).

Vivek Singh
Ranch Hand
Posts: 92
Rahul.p Kumar wrote:
shivendra tripathi wrote:
Rahul.p Kumar wrote: ok, Vivek, I see flaw in containsAll(), as {1, 2, 3, 4} is not equal to {1, 2, 3, 2}, then probably we should check both way l1.containsAll(l2) and if(true) then check l2.containsAll(l1) further. But now it sounds somewhat less simple and off the shelf

even this will not work think abt L1 = {1,2,2,3} L2 = {1,3,3,2}

You are right Tripathi.

So the SET code which i have added will work for all conditions.

Mike Simmons
Ranch Hand
Posts: 3090
14
No, it doesn't.

Consider this a challenge: find an example for which it doesn't work.

Such examples do exist, I assure you. But finding them is a skill in itself, worth developing. It won't really help you if we continue to hand out counterexamples. Try to find some of your own.

Campbell Ritchie
Sheriff
Posts: 50271
80
No longer a "beginning" question. Moving thread.

Mike Simmons
Ranch Hand
Posts: 3090
14
Actually, wait a minute - the code you've shown so far doesn't even seem to work for the last example given, {1,2,2,3} vs. {1,3,3,2}. Maybe you should restate for us: what algorithm are you currently advocating?

Vivek Singh
Ranch Hand
Posts: 92
Mike Simmons wrote:Actually, wait a minute - the code you've shown so far doesn't even seem to work for the last example given, {1,2,2,3} vs. {1,3,3,2}. Maybe you should restate for us: what algorithm are you currently advocating?

Here is the code:-
Output is false

shivendra tripathi
Ranch Hand
Posts: 263
Vivek your code won't work. It will give false even for {1,2,2,3} vs. {1,2,2,3}.

shivendra tripathi
Ranch Hand
Posts: 263

Try this guys. Looking forward for some test cases where this logic fails

Rahul P Kumar
Ranch Hand
Posts: 188
Actually this solution using set is not enough, think about {1, 2, 2, 3, 3} and {1, 2, 3, 3, 3}. size is same for two lists. but the list is not same. Making hashSet won't help here, as it will say true.

Rahul P Kumar
Ranch Hand
Posts: 188
If two linkedList is converted to arraylist and then equals() is invoked, will it not pass the test?

shivendra tripathi
Ranch Hand
Posts: 263
Rahul.p Kumar wrote:If two linkedList is converted to arraylist and then equals() is invoked, will it not pass the test?

no it will not.

Rahul P Kumar
Ranch Hand
Posts: 188
then best solution I can think of is use hashmap with key as unique element of corresponding list and value as no of repeating of that element. Compare two keysets for size first, if fail then fail all round, if true compare values of each key [sigh]