# lang comparison: in-place algorithm for reversing a list in Perl, Python, Lisp

WJ w_a_x_man at yahoo.com
Fri Mar 2 08:17:34 CET 2012

```Xah Lee wrote:

> fun example.
>
> in-place algorithm for reversing a list in Perl, Python, Lisp
> http://xahlee.org/comp/in-place_algorithm.html
>
> plain text follows
> ----------------------------------------
>
> What's “In-place Algorithm”?
>
> Xah Lee, 2012-02-29
>
> This page tells you what's “In-place algorithm”, using {python, perl,
> emacs lisp} 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):
>     x = list_a[i]
>     list_a[i] = list_a[ list_length -1 - i]
>     list_a[ list_length -1 - i] = x
>
> print list_a
> Perl
>
> Here's a perl code for reversing a list. Done by creating a new list,
> NOT using in-place:
>
> # 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++ ) {
>   my \$x = \$listA[\$i];
>   \$listA[\$i] = \$listA[ \$listLength - 1 - \$i];
>   \$listA[ \$listLength - 1 - \$i] = \$x;
> }
>
> 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))
>
>  Xah

NewLisp:

> (setq lst '(2 3 5 8))
(2 3 5 8)
> (reverse lst)
(8 5 3 2)
> lst
(8 5 3 2)

```