wood burning stoves 2.0*
The moose likes Java in General and the fly likes Linked List equals method Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Linked List equals method" Watch "Linked List equals method" New topic
Author

Linked List equals method

Alex Ba
Ranch Hand

Joined: Oct 14, 2009
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

Joined: Mar 13, 2009
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


"If the facts don't fit the theory, get new facts" --Albert Einstein
Alex Ba
Ranch Hand

Joined: Oct 14, 2009
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
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

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

Joined: Mar 13, 2009
Posts: 492

I think you idea of nested while loops would work fine. Maybe try something like this:


-Hunter
Janeice DelVecchio
Saloon Keeper

Joined: Sep 14, 2009
Posts: 1659
    
  11

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.


When you do things right, people won't be sure you've done anything at all.
Alex Ba
Ranch Hand

Joined: Oct 14, 2009
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

Joined: Mar 05, 2008
Posts: 2994
    
    9
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

Joined: Mar 13, 2009
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

Joined: Sep 26, 2009
Posts: 188
Alex, what containsAll() yields?
shivendra tripathi
Ranch Hand

Joined: Aug 26, 2008
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.


SCJP 1.5(97%) My Blog
Patricia Samuel
Ranch Hand

Joined: Sep 12, 2007
Posts: 300
It seems a better solution - Using set to check the equality.

Great Tripathi
Rahul P Kumar
Ranch Hand

Joined: Sep 26, 2009
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

Joined: Mar 05, 2008
Posts: 2994
    
    9
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

Joined: Mar 05, 2008
Posts: 2994
    
    9
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

Joined: Sep 12, 2007
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

Joined: Mar 05, 2008
Posts: 2994
    
    9
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

Joined: Sep 12, 2007
Posts: 300
Agree. This test case fails the logic.
Patricia Samuel
Ranch Hand

Joined: Sep 12, 2007
Posts: 300
But does containsAll() solve the purpose -
Vivek Singh
Ranch Hand

Joined: Oct 27, 2009
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

Joined: Oct 27, 2009
Posts: 92


WORK for all conditions.. as per the requirement of task.
Raghavan Muthu
Ranch Hand

Joined: Apr 20, 2006
Posts: 3344

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.


Everything has got its own deadline including one's EGO!
[CodeBarn] [Java Concepts-easily] [Corey's articles] [SCJP-SUN] [Servlet Examples] [Java Beginners FAQ] [Sun-Java Tutorials] [Java Coding Guidelines]
Rahul P Kumar
Ranch Hand

Joined: Sep 26, 2009
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

Joined: Sep 26, 2009
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

Joined: Aug 26, 2008
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

Joined: Apr 20, 2006
Posts: 3344

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



Your test on



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

Joined: Sep 26, 2009
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

Joined: Sep 26, 2009
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

Joined: Mar 05, 2008
Posts: 2994
    
    9
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

Joined: Oct 27, 2009
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

Joined: Mar 05, 2008
Posts: 2994
    
    9
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

Joined: Oct 13, 2005
Posts: 38016
    
  22
No longer a "beginning" question. Moving thread.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2994
    
    9
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

Joined: Oct 27, 2009
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

Joined: Aug 26, 2008
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

Joined: Aug 26, 2008
Posts: 263


Try this guys. Looking forward for some test cases where this logic fails
Rahul P Kumar
Ranch Hand

Joined: Sep 26, 2009
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

Joined: Sep 26, 2009
Posts: 188
If two linkedList is converted to arraylist and then equals() is invoked, will it not pass the test?
shivendra tripathi
Ranch Hand

Joined: Aug 26, 2008
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

Joined: Sep 26, 2009
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]
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Linked List equals method
 
Similar Threads
hashcodes
why we override hashcode and equal methods
Bit Pattern
regarding scjp 1.5
Understanding HashMap