Reverse a Linked List in Java by Iteration

Overview

In this example we will see how to reverse a LinkedList in Java using iteration. In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.

Figure 1. Linked List

Code

In this example we will reverse the linked list using iteration. You can also use recursion to achieve the same result.

package com.zia.linkedlist;

public class ReverseLinkedListByIteration {

    private Node head;

    public static Node reverseLinkedListIteration(ReverseLinkedListByIteration.Node currentNode) {
        Node previousNode = null;
        Node nextNode;
        while (currentNode != null) {
            nextNode = currentNode.next;
            currentNode.next = previousNode;
            previousNode = currentNode;
            currentNode = nextNode;
        }
        return previousNode;
    }

    public void addToList(ReverseLinkedListByIteration.Node node) {
        if(head == null) {
            head = node;
        } else {
            ReverseLinkedListByIteration.Node temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = node;
        }
    }

    static class Node {
        private String data;
        private ReverseLinkedListByIteration.Node next;

        Node(String data) {
            this.data = data;
        }

        public String getData() {
            return data;
        }

        public Node getNext() {
            return next;
        }
    }
}

Test

Let’s write a test for the above code:

package com.zia.linkedlist;

import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class ReverseLinkedListByIterationTest {

    @Test
    public void testReverseLinkedListIteration() {

        ReverseLinkedListByIteration obj = new ReverseLinkedListByIteration();
        ReverseLinkedListByIteration.Node head = new ReverseLinkedListByIteration.Node("Head");
        obj.addToList(head);
        obj.addToList(new ReverseLinkedListByIteration.Node("First"));
        obj.addToList(new ReverseLinkedListByIteration.Node("Second"));
        obj.addToList(new ReverseLinkedListByIteration.Node("Third"));
        obj.addToList(new ReverseLinkedListByIteration.Node("Fourth"));
        obj.addToList(new ReverseLinkedListByIteration.Node("Fifth"));

        final ReverseLinkedListByIteration.Node reverseLinkedList = ReverseLinkedListByIteration.reverseLinkedListIteration(head);

        assertEquals(reverseLinkedList.getData(), "Fifth");
        assertEquals(reverseLinkedList.getNext().getData(), "Fourth");
        assertEquals(reverseLinkedList.getNext().getNext().getData(), "Third");
        assertEquals(reverseLinkedList.getNext().getNext().getNext().getData(), "Second");
        assertEquals(reverseLinkedList.getNext().getNext().getNext().getNext().getData(), "First");
        assertEquals(reverseLinkedList.getNext().getNext().getNext().getNext().getNext().getData(), "Head");
    }
}

Conclusion

In this example we saw how to reverse a linked list using iteration.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: