Java 11 Reverse LinkedList Iteratively

Question

I have been attempting to reverse in place a LinkedList in Java 11 using a custom Node class and iteration.

The logic used was to swap the previous and next references of each element in the list in a loop and then subsequently swap the head and tail elements. However the list remains unchanged.

Also it would be hepful to have a toString() method for the Node class but I haven't been able to achieve this.

If anybody can assist with this it will be much appreciated.

My code follows:

import java.util.LinkedList;

public class TEST {

  public static void main(String[] args) {
    LinkedList<String> strList = new LinkedList<>();

    strList.add("one");
    strList.add("two");
    strList.add("five");
    strList.add("four");
    strList.add("three");

    System.out.println("String list before reversal");
    System.out.println(strList);

    reverseStringLinkedList(strList);
    System.out.println("String list after reversal");
    System.out.println(strList);
  }

  //method to reverse the string linked list
  public static void reverseStringLinkedList(LinkedList strList) {
    Node head = new Node((String) strList.getFirst());
    Node tail = new Node((String) strList.getLast());
    Node curr = head;
    Node temp;

    //swap prev and next references
    while (curr != null) {
      temp = curr.next;
      curr.next = curr.prev;
      curr.prev = temp;
      curr = curr.prev;
    }

    //swap head and tail
    temp = head;
    //DEBUG
    System.out.println("temp: " + temp.string);
    System.out.println("head: " + head.string);
    System.out.println("tail: " + tail.string);
    //END DEBUG
    head = tail;
    tail = temp;
    //DEBUG#
    System.out.println("AFTER SWAPPING");
    System.out.println("head: " + head.string);
    System.out.println("tail: " + tail.string);
    //END DEBUG
  }
}

class Node {

  //fields
  String string;
  Node prev;
  Node next;

  //constructor
  public Node(String string) {
    this.string = string;
  }
}

Warning: you are using raw types (LinkedList). Don't do this, always specify the necessary type arguments (i.e. LinkedList<…>). — MC Emperor
– MC Emperor, Commented Oct 6, 2022 at 10:41

talex · Accepted Answer · 2022-10-06 10:22:17Z

2

You use java.util.LinkedList. You need to create your own implementation.

Code of reverseStringLinkedList doesn't affect strList just read it's first and last values.

answered Oct 6, 2022 at 10:22

talex

20.8k3 gold badges34 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

mmartinez04 · Accepted Answer · 2022-10-06 11:33:57Z

As @talex mentioned, if you want to use a custom Node, you need to implement your own custom version of LinkedList as well.

Otherwise, you can reverse a LinkedList pretty easily. The built-in LinkedList has addFirst() and remove() functions that make it relatively simply:

public static void reverseList(LinkedList list){
    
    // First, store the size of our list
    int length = list.size();
    
    //Iterate across the list
    for (int i = 0; i < length; i++){
        
        //Add the current element to the front
        list.addFirst(list.get(i));
        
        //Remove the duplicate element we just added
        //Index = i+1 since we just added an extra element
        list.remove(i+1);

    }
    
    //Now, we should have the reverse order of the original list
}

Example:

public static void main(String[] args) {
    LinkedList<Integer> myList = new LinkedList<Integer>();
    
    System.out.print("Original List: ");
    
    for (int i = 1; i <= 5; i++){
        myList.add(i);
        System.out.print(myList.get(i-1) + " ");
    }
    
    reverseList(myList);
    
    System.out.print("\nReverse List: ");
    
    for (int i = 0; i < myList.size(); i++){
        System.out.print(myList.get(i) + " ");
    }
}

Output:

Original List: 1 2 3 4 5 
Reverse List: 5 4 3 2 1

Not A Number · Accepted Answer · 2022-10-06 13:38:35Z

1

You can use java.util classes:

LinkedList<String> given = new LinkedList<>(List.of("one", "two", "three", "four", "five"));
Collections.reverse(given);                             //  1. Reverses your list
System.out.println(Arrays.toString(given.toArray()));   //  2. Prints all elements

answered Oct 6, 2022 at 13:38

Not A Number

1964 bronze badges

Collectives™ on Stack Overflow

Java 11 Reverse LinkedList Iteratively

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related