To learn about in place list reversal, you should know the following:
- Python 3
- Python data structures - Lists
- 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:
|Round||alist||left||right||alist after swapping|
|1||[1,2,3,4,5,6,7]||1 ||7 ||[7,2,3,4,5,6,1]|
|4||[7,6,5,4,3,2,1]||4||4||Stop since left == right|
As you can see, now the list is reversed.
- left pointer points to the first index and right pointer points to the last index
- Swap elements pointed by the left and right pointers respectively
- Increment the left pointer by 1 and decrement the right pointer by 1
- Check if left>= right:
- If no, repeat steps 2-4
- 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().
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]))
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.
This is a very commonly asked interview question. Try using the same approach to solve these puzzles and comment below:
- Reverse the string “hello”. Output should be “olleh”
- Reverse the sentence “I love Python Central”. Output should be “Central Python love I”
- 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!