In-place Algorithm for Reversing a List in Perl, Python, Lisp, Mathematica

Xah Lee, 2012-02-29

This page tells you what's “In-place algorithm”, using {python, perl, emacs lisp, Mathematica} code to illustrate.

Here's Wikipedia In-place algorithm excerpt:

In computer science, an in-place algorithm (or in Latin in situ) is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space. The input is usually overwritten by the output as the algorithm executes. An algorithm which is not in-place is sometimes called not-in-place or out-of-place.

Python

Here's a python code for reversing a list. Done by creating a new list, NOT using in-place:

# python
# reverse a list

list_a = ["a", "b", "c", "d", "e", "f", "g"]

list_length = len(list_a)
list_b = [0] * list_length

for i in range(list_length):
    list_b[i] = list_a[list_length -1 - i]

print list_b

Here's in-place algorithm for reversing a list:

# python
# in-place algorithm for reversing a list

list_a = ["a", "b", "c", "d", "e", "f", "g"]

list_length = len(list_a)

for i in range(list_length//2):
    list_a[i], list_a[ list_length -1 - i] = list_a[ list_length -1 - i], list_a[i]
 
print list_a

The a//b is for floor(a/b).

Perl

Here's a perl version.

# perl

use strict;
use Data::Dumper;

my @listA = qw(a b c d e f g);

my $listLength = scalar @listA;
my @listB = ();

for ( my $i = 0; $i < $listLength; $i++ ) {
 $listB[$i] = $listA[ $listLength - 1 - $i];
}

print Dumper(\@listB);

# perl
# in-place algorithm for reversing a list.

use strict;
use Data::Dumper;
use POSIX; # for “floor”

my @listA = qw(a b c d e f g);

my $listLength = scalar @listA;

for ( my $i = 0; $i < floor($listLength/2); $i++ ) {
 ($listA[$i], $listA[ $listLength - 1 - $i]) = ($listA[ $listLength - 1 - $i], $listA[$i]);
}

print Dumper(\@listA);
__END__

emacs lisp

;; emacs lisp
;; reverse a array

(setq arrayA ["a" "b" "c" "d" "e" "f" "g"])

(setq arrayLength (length arrayA))

(setq arrayB (make-vector arrayLength 0))

(dotimes (i arrayLength ) 
  (aset arrayB i (aref arrayA (- (1- arrayLength) i)) )
  )

(print (format "%S" arrayB))

;; emacs lisp
;; in-place algorithm for reversing a array

(setq arrayA ["a" "b" "c" "d" "e" "f" "g"])

(setq arrayLength (length arrayA))

(dotimes (i (floor (/ arrayLength 2)))
  (let (x)
    (setq x (aref arrayA i))
    (aset arrayA i (aref arrayA (- (1- arrayLength) i)))
    (aset arrayA (- (1- arrayLength) i) x) ) )

(print (format "%S" arrayA))

Mathematica

(*reverse a list*)
listA = {"a", "b", "c", "d", "e", "f", "g"};
listLength = Length@listA;
listB = Range@listLength;

listB = (listB[[#]] = listA[[listLength - # + 1]]) & /@ listB

(* reverse a list, in-place. *)

listA = {"a", "b", "c", "d", "e", "f", "g"};
listLength = Length[listA];

({listA[[#]], listA[[listLength - # + 1]]} = {listA[[listLength - # + 1]], listA[[#]]}) & /@ Range@Floor[Length@listA/2];

listA

Note: in-place algorithm are not encouraged in functional programing. So, in functional language such as {lisp, Mathematica}, the constructs above are a bit forced. The examples here are only for illustrating the concept of in-place algorithm. All the above langs have built-in functions for reversing a list.

2012-02-29 Thanks to Steven D'Aprano, Dan Stromberg.