1
\$\begingroup\$

(The next iteration.)

I have this small utility method for rotating java.util.Lists in linear time, constant space:

package net.coderodde.util;

import java.util.Arrays;
import java.util.Collections;
import static java.util.Collections.swap;
import java.util.List;
import java.util.Objects;
import java.util.Scanner;

/**
 * This class contains a static method for rotating lists in linear time and
 * constant space.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 6, 2017)
 */
public final class ListReversal {

    private ListReversal() {}

    /**
     * Performs the list rotation.
     * 
     * @param <T>           the list element type.
     * @param list          the list whose content to rotate.
     * @param rotationCount the number of steps to rotate to the right. If
     *                      negative, rotates to the left.
     */
    public static <T> void rotate(List<T> list, int rotationCount) {
        Objects.requireNonNull(list, "The input list is null.");

        if (rotationCount < 0) {
            rotateLeft(list, -rotationCount);
        } else if (rotationCount > 0) {
            rotateRight(list, rotationCount);
        }
    }

    private static <T> void rotateLeft(List<T> list, int rotationCount) {
        Collections.<T>reverse(list);
        rotationCount %= list.size();
        reverse(list, list.size() - rotationCount, list.size());
        reverse(list, 0, list.size() - rotationCount);
    }

    private static <T> void rotateRight(List<T> list, int rotationCount) {
        Collections.<T>reverse(list);
        rotationCount %= list.size();
        reverse(list, 0, rotationCount);
        reverse(list, rotationCount, list.size());
    }

    private static <T> void reverse(List<T> list, int fromIndex, int toIndex) {
        for (int i = fromIndex, j = toIndex - 1; i < j; ++i, --j) {
            swap(list, i, j);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Integer> list = Arrays.asList(1, 2, 3, 4, 5, 6);
        System.out.println(list);

        while (true) {
            int rotationCount = scanner.nextInt();
            rotate(list, rotationCount);
            System.out.println(list);
        }
    }
}

I would like to hear any comments regarding the above.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You can take a look at Collections#rotate for a more efficient implementation (your current algorithm is inefficient for RandomAccess lists, your reverse implementation is inefficient for lists without random access). You need only rotateLeft or rotateRight as a left rotate by n is equivalent to a right rotate by size()-n. \$\endgroup\$
    – Nevay
    Oct 6, 2017 at 17:12

1 Answer 1

1
\$\begingroup\$
  1. The time complexity of the rotate method is O(N^2) if the list doesn't support random access because each call to swap takes O(N) time. One can fix it by using two ListIterators (one going forward and one going backwards) to reverse a part of the list.

  2. There's no need to create separate rotateLeft and rotateRight methods. You can always take the shift modulo the size of the list (in mathematical sense, without negative results, not in a sense of the operator %) instead.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.