• Post Reply Bookmark Topic Watch Topic
  • New Topic
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

Linked List equals method

 
Ranch Hand
Posts: 35
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Firefox Browser VI Editor Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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: 28177
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Firefox Browser VI Editor Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think you idea of nested while loops would work fine. Maybe try something like this:


-Hunter
 
Bartender
Posts: 1849
15
Eclipse IDE Spring VI Editor Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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: 4796
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Firefox Browser VI Editor Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Alex, what containsAll() yields?
 
Ranch Hand
Posts: 263
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
It seems a better solution - Using set to check the equality.

Great Tripathi
 
Rahul P Kumar
Ranch Hand
Posts: 188
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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: 4796
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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: 4796
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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: 4796
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Agree. This test case fails the logic.
 
Patricia Samuel
Ranch Hand
Posts: 300
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
But does containsAll() solve the purpose -
 
Ranch Hand
Posts: 92
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


WORK for all conditions.. as per the requirement of task.
 
Ranch Hand
Posts: 3389
Mac MySQL Database Tomcat Server
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Mac MySQL Database Tomcat Server
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 188
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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: 4796
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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: 4796
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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: 79151
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
No longer a "beginning" question. Moving thread.
 
Mike Simmons
Master Rancher
Posts: 4796
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


Try this guys. Looking forward for some test cases where this logic fails
 
Rahul P Kumar
Ranch Hand
Posts: 188
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If two linkedList is converted to arraylist and then equals() is invoked, will it not pass the test?
 
shivendra tripathi
Ranch Hand
Posts: 263
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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]
 
Would anybody like some fudge? I made it an hour ago. And it goes well with a tiny ad ...
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic