programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Jeanne Boyarsky
• Ron McLeod
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• paul wheaton
• Rob Spoor
• Devaka Cooray
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Carey Brown
• Frits Walraven
• Tim Moores
Bartenders:
• Mikalai Zaikin

Ranch Hand
Posts: 35
• Number of slices to send:
Optional 'thank-you' note:
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.

Ranch Hand
Posts: 492
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
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)

Marshal
Posts: 28235
95
• Number of slices to send:
Optional 'thank-you' note:

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
• Number of slices to send:
Optional 'thank-you' note:
I think you idea of nested while loops would work fine. Maybe try something like this:

-Hunter

Bartender
Posts: 1849
15
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
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.

Master Rancher
Posts: 4839
74
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
if you made a traverse method it would look something like:

you could pass two different linkedlists into this method.

-Hunter

Ranch Hand
Posts: 188
• Number of slices to send:
Optional 'thank-you' note:
Alex, what containsAll() yields?

Ranch Hand
Posts: 263
• Number of slices to send:
Optional 'thank-you' note:
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.

Ranch Hand
Posts: 300
• Number of slices to send:
Optional 'thank-you' note:
It seems a better solution - Using set to check the equality.

Great Tripathi

Rahul P Kumar
Ranch Hand
Posts: 188
• Number of slices to send:
Optional 'thank-you' note:

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
Master Rancher
Posts: 4839
74
• Number of slices to send:
Optional 'thank-you' note:

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
Master Rancher
Posts: 4839
74
• Number of slices to send:
Optional 'thank-you' note:

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
• Number of slices to send:
Optional 'thank-you' note:
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
Master Rancher
Posts: 4839
74
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
Agree. This test case fails the logic.

Patricia Samuel
Ranch Hand
Posts: 300
• Number of slices to send:
Optional 'thank-you' note:
But does containsAll() solve the purpose -

Ranch Hand
Posts: 92
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:

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

Ranch Hand
Posts: 3389
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:

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
• Number of slices to send:
Optional 'thank-you' note:

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: 3389
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:

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
• Number of slices to send:
Optional 'thank-you' note:

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
Master Rancher
Posts: 4839
74
• Number of slices to send:
Optional 'thank-you' note:

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
• Number of slices to send:
Optional 'thank-you' note:

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
Master Rancher
Posts: 4839
74
• Number of slices to send:
Optional 'thank-you' note:
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.

Marshal
Posts: 79259
377
• Number of slices to send:
Optional 'thank-you' note:
No longer a "beginning" question. Moving thread.

Mike Simmons
Master Rancher
Posts: 4839
74
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:

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
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:

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

Rahul P Kumar
Ranch Hand
Posts: 188
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
If two linkedList is converted to arraylist and then equals() is invoked, will it not pass the test?

shivendra tripathi
Ranch Hand
Posts: 263
• Number of slices to send:
Optional 'thank-you' note:

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
• Number of slices to send:
Optional 'thank-you' note:
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]