List in Python: How To Implement in Place Reversal

Prerequisites

To learn about in place list reversal, you should know the following:

  1. Python 3
  2. Python data structures – Lists
  3. Swapping values

What is in place list reversal?

In the previous posts, you might have learned how to read a list in reverse in Python which is quite fun. You can check this out here. However, the motive of this tutorial is quite different. We are not going to read a list in reverse but we are going to change an existing list to its reversed self. Note that this is a language agnostic approach.

Let’s look at an example:

alist = [1,2,3,4,5,6,7]

print(alist[::-1]) #prints [7,6,5,4,3,2,1]

print(alist) #prints [1,2,3,4,5,6,7]

So you are merely reading alist in the reverse order when you do alist[::-1]. What we want to achieve is to make alist = [7,6,5,4,3,2,1].

How to implement this?

The idea behind this is to use two pointers, left and right. The left pointer points to the first index of the list and the right pointer points to the last index of the list. Now we swap the elements pointed to by these pointers. Then, we move the pointer to the next indices. The terminating condition of this would be when the left pointer equals or crosses over the right pointer. Let us see this using an example:

Roundalistleftrightalist after swapping
1[1,2,3,4,5,6,7]1 [0]7 [6][7,2,3,4,5,6,1]
2[7,2,3,4,5,6,1]2[1]6[5][7,6,3,4,5,2,1]
3[7,2,3,4,5,6,1]3[2]5[4][7,6,5,4,3,2,1]
4[7,6,5,4,3,2,1]4[3]4[3]Stop since left == right

As you can see, now the list is reversed.

Algorithm

  1. left pointer points to the first index and right pointer points to the last index
  2. Swap elements pointed by the left and right pointers respectively
  3. Increment the left pointer by 1 and decrement the right pointer by 1
  4. Check if left>= right:
    1. If no, repeat steps 2-4
    2. If yes, stop. The list reversal is complete

Note: Although this algorithm is explained for lists, you can use this on strings as well. In that case, you might have to convert the string to a list by typecasting it. Do not forget to reconstruct the string back from the list format. This can be done by using some of the formatting commands like replace().

Code

def reverse(alist):

   #intializing pointers
   left = 0
   right = len(alist)-1

   #condition for termination
   while left<right:

       #swapping
       temp = alist[left]
       alist[left] = alist[right]
       alist[right] = temp

       #updating pointers
       left += 1
       right -= 1

   return alist

print(reverse([1,2,3,4,5]))

Efficiency

You might think that instead of going through all this trouble, you can create a new list with reversed contents. Something like this:

alist = [1,2,3,4,5,6,7]
blist = list()
for item in alist[::-1]:
blist.append(item)
print(blist) #prints [7,6,5,4,3,2,1]

Although the above approach works, you are using additional memory (blist) to store the reversed list. This might be a serious concern if the number of elements in the list is large. That is when the in place reversal will come in handy. The efficiency of in place reversal is O(n) since we visit all the elements of the list at least once.

Conclusion

This is a very commonly asked interview question. Try using the same approach to solve these puzzles and comment below:

  1. Reverse the string “hello”. Output should be “olleh”
  2. Reverse the sentence “I love Python Central”. Output should be “Central Python love I”
  3. Check if “madam” is a palindrome or not

We will use this concept in future tutorials like linked list reversal. That’s it for this tutorial. Happy Pythoning!