• 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
  • Ron McLeod
  • Rob Spoor
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Henry Wong
  • Liutauras Vilda
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Tim Holloway
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Mikalai Zaikin
  • Piet Souris

LinkedListNode in java

 
Ranch Hand
Posts: 106
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Can anyone explain how line no 22 and 23 works:
beforeEnd.next = node;
beforeEnd = node;
This part seems to me a bit confusing.
source
 
Saloon Keeper
Posts: 1290
40
Eclipse IDE Postgres Database C++ Java
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


Sure.  The first line adds the node after the current end of the "before" list.
The second line updates the pointer to the "end of the before list".

If you didn't have the first line, you wouldn't be inserting the node into the before list.
If you didn't have the second line, you would keep overwriting the same one element in your "before" list (the 2nd element).

They do a similar thing when adding nodes to the "after" list.

Drawing yourself a picture may help?
 
Marshal
Posts: 16591
277
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Just as in the other thread you started related to the same class, this is very procedural-style code, not object-oriented at all. Just keep that in mind as you study this code and how the algorithm is implemented. This is more like how you'd do it in C, not Java.
 
Md Zuanyeed Kamal
Ranch Hand
Posts: 106
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Junilu Lacar wrote:Just as in the other thread you started related to the same class, this is very procedural-style code, not object-oriented at all. Just keep that in mind as you study this code and how the algorithm is implemented. This is more like how you'd do it in C, not Java.



The way author solved problem made me very confused. I am not familiar with C/C++ that much.

I agree with you. There is no point of solving problems in back-dated procedural way in java.


I will come up with my own solution rather than following author solutions.

 
Marshal
Posts: 74020
332
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Md Zuanyeed Kamal wrote:. . . The way author solved problem made me very confused. . . .

We have already seen that the other code posted was poor quality.

It would appear whoever it is is trying to demonstrate a sorting algorithm, possibly quicksort. If you look here, you will find that it isn't a good idea to sort a linked list in situ.
 
Junilu Lacar
Marshal
Posts: 16591
277
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Md Zuanyeed Kamal wrote:I will come up with my own solution rather than following author solutions.


One way you could do this in a more OO way is to define a separate class to represent a partition result so you could do something like this:

In other languages that support destructuring assignments, this would be even easier:
 
Bartender
Posts: 4633
182
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You have now an O(N) solution. If you don't mind an O(Nlog(N)) one, an elegant way is to take all the values of your LinkedListNodes, sort them using Comparator<Integer> comp = Comparator.comparing(i -> i >= x) (x is the split value) and recreate your Nodes from this sorted list. Should be 3 or 4 lines, depending on how easy it is to create all the Nodes.
 
Campbell Ritchie
Marshal
Posts: 74020
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Can you get that Comparator to work, Piet? Surely your λ will have a boolean return type and a Comparator wants an int? Will that code actually compile?
 
Saloon Keeper
Posts: 13268
292
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Comparator wants an int, but the comparing() method doesn't. It just wants a function that maps an element to another element that is then sorted according to its natural order. Piet is basically mapping each element to a boolean and then sorting the list according to the natural order of booleans.

It will work, but it's really just a roundabout way of using Collectors.partitioningBy:

This avoids the O(n log n) complexity of Piet's solution and is at least as elegant. You only need to convert the linked list node to a stream, which is pretty trivial.
 
Piet Souris
Bartender
Posts: 4633
182
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yew, partitioning is very nice here. But I didn't know how to turn those Nodes into a Stream. I will give it a shot and see if it is indeed a triviality!
 
Piet Souris
Bartender
Posts: 4633
182
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Can you get that Comparator to work, Piet? Surely your λ will have a boolean return type and a Comparator wants an int? Will that code actually compile?


Stephan explained it. Perhaps the two-parameter version of comparing is a little more clear:

Here, the keyExtractor is i -> i >= x, so a Boolean
and the keyComparator is the natural order of a Boolean (false - true)
So, in full
 
Stephan van Hulst
Saloon Keeper
Posts: 13268
292
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Piet Souris wrote:I will give it a shot and see if it is indeed a triviality!


Note that the solution I had in mind was simply dumping all the nodes in a list and then calling stream() on the list. This is trivial. The problem with this approach is that it takes O(n) space complexity.

Creating a custom spliterator from scratch is not trivial, but it's also not necessary if you don't intend to use a parallel stream.

An easy but non-trivial solution that avoids O(n) space complexity (but doesn't support parallelism) is to implement a custom Iterator and then use the Spliterators utility class to convert it to a Spliterator, and then use StreamSupport to convert the spliterator to a Stream.
 
Jesse Silverman
Saloon Keeper
Posts: 1290
40
Eclipse IDE Postgres Database C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Clearly it is time to start thinking of streams as part of Beginning Java.

I'd skipped a bit ahead in my studies, almost time to go back and get more comfortable with streams beyond the absolute basics.
 
Campbell Ritchie
Marshal
Posts: 74020
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Jesse Silverman wrote:. . . time to start thinking of streams as part of Beginning Java. . . ..

I thought the time to start thinking about Streams as part of Beginning Java® was 17th March 2014 (Java8 came out on 18th March 2014)
Yes, I have long wondered why people seem so scared of teaching beginners about Streams. If you want to learn Streams, I recommend you find a copy of Modern Java in Action (older editions called Java8/9 in Action) by Urma Fusco and Mycroft (Manning 2017). Manning have a discount offer on just at the moment. I managed to persuade them to give me a 50% discount on Modern Java® in Action because I already had the old edition
 
Junilu Lacar
Marshal
Posts: 16591
277
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I don't know about beginners though... many beginners have trouble just understanding basic modularization and abstraction. Some simple examples might be helpful in illustrating how to write more declarative-style programs (vs. imperative). I'd probably lean towards introducing streams a little later, after they learn about functional decomposition and using methods to break a problem down into smaller, more manageable chunks.
 
Campbell Ritchie
Marshal
Posts: 74020
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Junilu Lacar wrote:. . . Some simple examples . . .

That goes without saying. I wouldn't show a beginner this sort of thing at all, which I think belongs in a non‑beginner's course:-Should we plague beginners by telling them that you can get an int[] 0, 1, 2, 3...8, 9 like this:-or like this?Yes, I know I would just as soon use an array initialiser, but I can easily scale the other versions to much larger arrays.
 
Jesse Silverman
Saloon Keeper
Posts: 1290
40
Eclipse IDE Postgres Database C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Interesting.  Python's Ranges and List Comprehensions are definitely considered something to be taught to absolute beginners.
In fact, they have no traditional 1974-style for loop at all, and list comprehensions are possibly the first way a beginner learns to build up alist.

Twenty years ago, some C++ people started saying "we need to stop teaching C++ by teaching C first" and now most people agree, presentations introduce (parts of) the STL rather early.

The current Java equivalent might be "We need to stop teaching modern Java by teaching Java 7 with all of the Streams stuff left as an advanced topic."

The most odious thing I have seen in an extremely popular tutorial series, is to teach Collections barely acknowledging generics at all, making use of the feature/bug to store unrelated types in them thru-out, and then teaching Generics only at the end and saying "It's better to do things like this."

If you wonder why people wander in asking about Raw Types, I think this is the reason.

That except for Applets and JNLP almost nothing from Java 1.0 is de-supported (I still see requests for material on Applets somewhat regularly!) exacerbates this problem.

Until 2014, "Modern Java" mostly meant "Show things with generics, show VarArgs, enum, auto-boxing etc." Since then it should have meant "Teach the best way to do things in Java 8 and up first", but...
I recently saw a popular tutorial channel have a whole playlist on Java 5 features made in 2018.
He states at the beginning "You wouldn't think this is needed, but I see so many people failing to use this stuff in their code!"

You might think it was just lazy dinosaurs who learned Java before 2004 and don't feel like learning anything new.
You'd be wrong.  Tons of it is coming from people who have started seriously learning Java only recently, but are using older materials (books/websites/videos) or even newer materials presented by dinosaurs who have decided they should still teach Java like is is 2003, and then show all the newer stuff in separate lessons or playlists after (if the reader/viewer actually gets that far).

This reminds me that we finally got something newer than Java 8 being provided as a choice in HackerRank very recently!!  I do not know if it was because of our mini-campaign here or not, but I will go post about that small but very important success!
 
Campbell Ritchie
Marshal
Posts: 74020
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Jesse Silverman wrote:. . . stop teaching modern Java by teaching Java 7 with all of the Streams stuff left as an advanced topic.

Agree. We still see people who don't know how to use a Scanner to read a text file, nor to use try with resources to close said Scanner.

. . . teach Collections barely acknowledging generics at all . . . teaching Generics only at the end and saying "It's better to do things like this."

I had to learn Collections without generics because I learnt on Java1.4.

. . . almost nothing from Java 1.0 is de-supported . . .

Explicit Threads, JOptionPane for keyboard input, File, AWT, remote Java®, Vector, ints in enumerated types, new Integer(123), the finalize() method, Date and Calendar?
Maybe not de‑supported, but more like forgotten about. Except maybe in nghtmares

. . . people who have started seriously learning Java only recently, but are using older materials . . .

Because they can pick up old books very cheaply, and don't actually know how out of date they are. Until the are asked at interview to read a text file and they write this sort of code:-...or even,
 
Jesse Silverman
Saloon Keeper
Posts: 1290
40
Eclipse IDE Postgres Database C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Some concepts also straddle Basic/Beginning Java and Intermediate or perhaps even Advanced.

Examples: Enum type, basic use of it is Basic, some of the advanced things you can do with it (basically using it as a self-contained non-extensible class hierarchy) pretty Advanced.

Varargs ... -- this is reasonably considered a Basic feature for such a long time (since 2004) everyone should understand it.
Knowing that @SaveVarargs annotation exists, Basic/Intermediate.
Full understanding of the implications of non-reifiable types for heap pollution, and being able to explain such without getting anything wrong or leaving anything out, I'd consider Advanced.

The first two levels of Varargs are on the 819, but not the third.

I think this idea of "Some Java features straddle Basic/Intermediate/Advanced knowledge depending on what we are talking about knowing/understanding about them" is pretty important to my studies right now.

I tend to want to know everything about everything, which takes forever.
I see other people feel "good to go" knowing only the Absolute Basic facts about a topic, feature or area, I am simultaneously jealous and scornful.

I would describe my current understanding of Generics in Java, for instance, to be Intermediate.  Enum, Intermediate to Advanced...Varargs, Intermediate.
I can use these things productively and get many questions right, but at the same time I can pose myself questions I can't answer without experiments or further study, both of which take time from learning other topic areas at even a Basic level.

The take-home I think is that we can't just say which topics or areas are now Basic or Beginner, Intermediate and Advanced, but which things about them we are including in such working descriptions.  The deepest understanding is very far away from what is needed to productively make the most basic use of Varargs, enum type, Generics, etc.  (oh, and of course, Streams, which is what got me thinking about this in the first place.)
 
This tiny ad will self destruct in five seconds.
Thread Boost feature
https://coderanch.com/t/674455/Thread-Boost-feature
reply
    Bookmark Topic Watch Topic
  • New Topic