Reversing a singly linked list

jonas

Well-Known Member
Code:
rec_reverse(last_of_rev,to_rev) = if to_rev != nil:
  next_rev = to_rev.next;
  to_rev.next = last_of_rev;
  rec_reverse(to_rev,next_rev)

reverse(to_rev) = rec_reverse(nil, to_rev)
Code:
reversed list    list to be reversed
(|<-()<-...<-()  ,  []->()->...->()->|)
after one recurisve step becomes:
(|<-()<-...<-()<-[]  ,  ()->...->()->|)
at the end of recursion becomes:
(|<-()<-...<-()<-[]<-()<-...<-()  ,  |)
 
Last edited:

Accname

2D-Graphics enthusiast
How about this?
Code:
    public void reverse() {
       Node prev = null;
       Node current = first;
       while (current != null) {
         Node next = current.next;
         current.next = prev;
         prev = current;
         current = next;
       }
       first = prev;
     }
This is using a simple while-loop.
Here a full example with test case:
Code:
  public static void main(final String[] args) {
     LList l = new LList();
     l.first = new Node("A");
     l.first.next = new Node("B");
     l.first.next.next = new Node("C");
     l.first.next.next.next = new Node("D");
     l.first.next.next.next.next = new Node("E");
     l.first.next.next.next.next.next = new Node("F");
    
     System.out.println(l);
     System.out.println();
     l.reverse();
     System.out.println(l);
     System.out.println();
   }
  
   public static class LList {
     Node first;
    
     public void reverse() {
       Node prev = null;
       Node current = first;
       while (current != null) {
         Node next = current.next;
         current.next = prev;
         prev = current;
         current = next;
       }
       first = prev;
     }
    
     @Override
     public String toString() {
       StringBuilder sb = new StringBuilder();
       Node current = first;
       while (current != null) {
         sb.append(current.value);
         sb.append(" ");
         current = current.next;
       }
       return sb.toString();
     }
   }
  
   static class Node {
     Object value;
     Node next;
    
     public Node(Object value) {
       this.value = value;
     }
    
   }
Output:
A B C D E F

F E D C B A
 

Accname

2D-Graphics enthusiast
Its not quite the same depending on the execution enviroment and language you are using. A loop is much better in java than recursion. Sure, at some point the JIT will jump in and might improve the recursive method, but until then the loop will outperform the recursion every time.
 

jonas

Well-Known Member
Its not quite the same depending on the execution enviroment and language you are using. A loop is much better in java than recursion. Sure, at some point the JIT will jump in and might improve the recursive method, but until then the loop will outperform the recursion every time.
Note that I was not giving a java program... At the conceptual level the two are identical, and that was the level in which I was giving the algorithm. Yes, in a given actual implementation the performance between the two may differ significantly, and one of them may run out of memory while the other may not (this is actually the bigger issue). From my point of view, you have simply given the idiomatic Java implementation of the conceptual algorithm above. Maybe we can find common ground here?
 

Accname

2D-Graphics enthusiast
You have to go to a veeeeerrrryyy high conceptual level to call these two implementations equal. Sure, in the end they do the same thing because thats what they are supposed to do. But both use different syntactic and semantic constructs some of which may or may not be available in a given language / runtime enviroment.
 

jonas

Well-Known Member
You have to go to a veeeeerrrryyy high conceptual level to call these two implementations equal. Sure, in the end they do the same thing because thats what they are supposed to do. But both use different syntactic and semantic constructs some of which may or may not be available in a given language / runtime enviroment.
The first one is not an implementation, it's a description of the algorithm. There might not even be a compiler or interpreter for that language.
I wouldn't just say that they do the same thing, I'd go as far to say they do it the *same way*, namely by going through the pointers and flipping them one by one. Recursion and iteration just say "repeatedly do this", or "repeatedly do this until".
 

Accname

2D-Graphics enthusiast
Thats a little to vague for my taste. A loop is an actual syntactical structure defined by a language. Recursion is a method of software-developement that can be used in most languages but there is no syntactical component to it in any language I know of. There are many different languages, some of which do not have loops. Some of them do not have the concept of methods either but they have loops. Some have methods but do not allow for recursion, etc.
I can not say with a straight face that these two things are "the same". They might be very similar, they might be exchangeable in most enviroments, but they are not "the same".
 

jonas

Well-Known Member
Well, I understand that you live in the practical world of building real software, where there are very clearly specific definitions and precise differences for these definitions. If I would develop a Java program, I would use a while loop, not a recursive method call, just like you have.

I on the other hand live in the theoretical world of building language models and proving that can be compiled correctly to run on real machines, so I'm looking more at the conceptual level of what languages can do (in general) and how it would be compiled and run, and so in my world they use the same mechanisms and I don't distinguish between them. Whether a language implements "doing the same thing over and over" by function recursion or loop recursion or a recursion operator (like system T) is completely irrelevant to me; if it has a way of "doing the same thing over and over", it needs to do a) b) and c) to compile correctly for x86.
 
General chit-chat
Help Users
  • No one is chatting at the moment.
  • tom_mai78101 tom_mai78101:
    Would like to get some annual forum statistics report.
  • The Helper The Helper:
    there are stats in the xenforo forum admin section and we have matomo stats we started collecting beginning of the year so we will not have annual on that until next year
  • The Helper The Helper:
    I thought you had keys to the bathroom Tom? Ghan does Tom have access to the stats thread in the bathroom
  • The Helper The Helper:
    since I started jacking with the bots on the site we doubled our page views on the site in a week lol
  • The Helper The Helper:
    I have been having lots of fun
  • The Helper The Helper:
    we have had like 6000 views of the American Airlines economy class thread in the last week
  • The Helper The Helper:
    I ought to stick a travel affiliate link or something on that page to try and monetize that they are just going there and leaving it might even be bots I am not sure
  • The Helper The Helper:
    I just got into it with the Atari VCS Facebook Moderator I started trolling him and almost got banned
  • The Helper The Helper:
    They deleted one of my posts one time so I was trolling him on a help post I put up because I am evil I guess and bored and the guy handled it well I loved his attitude Atari has a good social media presence even if they do not have many games.
  • The Helper The Helper:
    The French Atari they call them even though they are like totally based in America they just have French Money coming in. Gotta love it
  • Ghan Ghan:
    Microsoft buying Activision Blizzard holy crap!
  • The Helper The Helper:
    I know right holy cow
  • Accname Accname:
    Thats not going to save it.
  • The Helper The Helper:
    It might
  • The Helper The Helper:
    They are going to use alot of that IP in the Metaverse
  • The Helper The Helper:
    I found a new section of the stats that is freaking interesting!
  • The Helper The Helper:
    oh yeah this is what I was looking for good job matomo! These are some sweet stats I am learning the interface on it too!
  • The Helper The Helper:
    If anyone ever asks later how I found out about it was watching the site bots but not watching what they were doing but asking myself why they were here?
  • The Helper The Helper:
    there must be a reason and ok that is it
  • The Helper The Helper:
    the past and the future all come together into one
  • The Helper The Helper:
    the search engines are what built thehelper.net the search engines will make it big again maybe
  • The Helper The Helper:
    the real question is are 5 million links better than 60 real good links?
  • The Helper The Helper:
    the answer is 60 lol
  • The Helper The Helper:
    unless you put 100k links on it lol then you get something

    Staff online

    Members online

    Affiliates

    Hive Workshop NUON Dome
    Top