Rotating Lists in Python: In-Place vs. New List Creation

Rotating a list is a common operation in programming, often encountered in algorithm challenges and data manipulation tasks.

This article explores two primary methods for list rotation in Python: rotating a list in place (modifying the original list) and creating a new, rotated list.

Let’s look at a simple example:

 Input: [1, 2, 3, 4, 5], rotate by 2
 Output (In-place): [3, 4, 5, 1, 2]
 Output (New List): [3, 4, 5, 1, 2]
 

Method 1: Rotating a List In-Place Using Slicing and Assignment

This method modifies the original list directly. It leverages Python’s slicing capabilities to move elements to their new positions within the list.

 def rotate_list_in_place(arr, k):
     """
     Rotates a list in-place by k positions.
     k can be positive (rotate right) or negative (rotate left).
     """
     n = len(arr)
     k %= n  # Normalize k to handle rotations larger than the list size
     arr[:] = arr[k:] + arr[:k]  # In-place rotation using slicing
 

 # Example usage:
 my_list = [1, 2, 3, 4, 5]
 rotate_list_in_place(my_list, 2)
 print(my_list)
 # Output: [3, 4, 5, 1, 2]

 my_list = [1, 2, 3, 4, 5] # Reset the list
 rotate_list_in_place(my_list, -1) # Rotate left by 1
 print(my_list)
 # Output: [2, 3, 4, 5, 1]
 

Explanation:

• The rotate_list_in_place function takes the list arr and the rotation amount k as input.
• k %= n normalizes k to be within the range of the list’s length. This is crucial for handling cases where k is larger than the list size, ensuring correct rotation. The modulo operator (%) returns the remainder of the division, so if k = 7 and n = 5, k becomes 2 (7 % 5 = 2).
• arr[:] = arr[k:] + arr[:k] performs the in-place rotation. It reassigns the entire list arr to a new list created by concatenating two slices: arr[k:] (elements from index k to the end) and arr[:k] (elements from the beginning to index k). The [:] ensures that the original list is modified directly, rather than creating a new list object.

Method 2: Creating a New Rotated List Using Slicing

This method creates a new list containing the rotated elements, leaving the original list unchanged. It’s useful when you need to preserve the original list’s state.

 def rotate_list_new(arr, k):
     """
     Creates a new rotated list by k positions.
     k can be positive (rotate right) or negative (rotate left).
     """
     n = len(arr)
     k %= n
     return arr[k:] + arr[:k]
 

 # Example usage:
 my_list = [1, 2, 3, 4, 5]
 rotated_list = rotate_list_new(my_list, 2)
 print(rotated_list)
 # Output: [3, 4, 5, 1, 2]
 print(my_list)
 # Output: [1, 2, 3, 4, 5]  # Original list remains unchanged

 my_list = [1, 2, 3, 4, 5]
 rotated_list = rotate_list_new(my_list, -1)  # Rotate left
 print(rotated_list)
 # Output: [2, 3, 4, 5, 1]
 print(my_list)
 # Output: [1, 2, 3, 4, 5] # Original list remains unchanged
 

Explanation:

• The rotate_list_new function takes the list arr and the rotation amount k as input.
• k %= n normalizes k to handle rotations exceeding the list’s length.
• return arr[k:] + arr[:k] creates and returns a new list. It concatenates the slice from index k to the end of the list with the slice from the beginning to index k. The original list arr is not modified.

Method 3: Rotating In-Place Using `collections.deque`

The collections.deque object provides an efficient way to rotate lists in-place. It’s especially useful for repeated rotations or scenarios where performance is critical.

 from collections import deque

 def rotate_list_deque(arr, k):
     """
     Rotates a list in-place using collections.deque.
     """
     d = deque(arr)
     d.rotate(k)
     arr[:] = list(d)  # Update the original list
 

 # Example usage:
 from collections import deque

 my_list = [1, 2, 3, 4, 5]
 rotate_list_deque(my_list, 2)
 print(my_list)
 # Output: [3, 4, 5, 1, 2]

 my_list = [1, 2, 3, 4, 5]
 rotate_list_deque(my_list, -1) # Rotate left
 print(my_list)
 # Output: [2, 3, 4, 5, 1]
 

Explanation:

• This method imports the deque object from the collections module.
• A deque is created from the input list arr.
• d.rotate(k) rotates the deque in-place by k positions. Positive k rotates to the right, and negative k rotates to the left.
• arr[:] = list(d) updates the original list arr with the elements from the rotated deque. The [:] is crucial to modify the original list and not just reassign the variable.

Method 4: Rotating In-Place Using Reversal Algorithm

This method rotates the list by reversing specific segments. It’s an in-place algorithm and can be more space-efficient in some scenarios.

 def reverse_list(arr, start, end):
     """Reverses a portion of the list in-place."""
     while start < end:
         arr[start], arr[end] = arr[end], arr[start]
         start += 1
         end -= 1

 def rotate_list_reversal(arr, k):
     """Rotates a list in-place using the reversal algorithm."""
     n = len(arr)
     k %= n
     reverse_list(arr, 0, n - 1)  # Reverse the entire list
     reverse_list(arr, 0, k - 1)  # Reverse the first k elements
     reverse_list(arr, k, n - 1)  # Reverse the remaining elements
 

 # Example usage:
 my_list = [1, 2, 3, 4, 5]
 rotate_list_reversal(my_list, 2)
 print(my_list)
 # Output: [3, 4, 5, 1, 2]

 my_list = [1, 2, 3, 4, 5]
 rotate_list_reversal(my_list, -1)
 print(my_list)
 # Output: [2, 3, 4, 5, 1]
 

Explanation:

• The reverse_list function reverses a portion of the list in-place, from start to end indices.
• The rotate_list_reversal function first normalizes k.
• It then reverses the entire list.
• Next, it reverses the first k elements and the remaining elements separately. This sequence of reversals effectively rotates the list by k positions.