CS 3723   Programming Languages     3.2 Lists

Reference links given below will be to the online book: Building skills in Python

• As a linked list, we can insert or delete an item at the beginning or the end or anywhere in the middle. We can concatenate lists.
• As an array, we can use the index to directly access any item in the list, from first to last. We can form sublists. We can iterate through the list.

The link above gives details on the large number of functions and methods.

List are implemented more as an extensible array of pointers than as a linked list. The power and flexibility of Python lists comes at the price of added storage and run-time requirements. Here are two examples of using lists:

1
2
3
4
5
6
7
8
9
10
11
12

# cubes.py: find sum of cubes
import sys # for sys.stdout.write
n = 20
ave = [] # empty list
for i in range(1,n+1):
    ave.append(i**3) # add to end of list
tot = 0
for av in ave: # iterate through array
    tot += av # add items
sys.stdout.write("Total: %i\n" % tot)
sys.stdout.write("Formula: (n(n+1)/2)**2: %i\n"
      %  ((n*(n+1)/2)**2) )

# cubes2.py: find sum of cubes
import sys # for sys.stdout.write
n = 20
ave = [None] * (n+1) # array of size n+1
for i in range(1,n+1):
    ave[i] = (i**3)
tot = 0
for i in range(1,len(ave)): # iterate
    tot += ave[i] # add items
sys.stdout.write("Total: %i\n" % tot)
sys.stdout.write("Formula: (n(n+1)/2)**2: %i\n"
      %  ((n*(n+1)/2)**2) )

% python cubes.py
Total: 44100
Formula: (n(n+1)/2)**2: 44100

The second example is a "mystery" program that uses a list:

#!/usr/bin/python
import sys
N, A, M  = 32, 16, 32
s, g = 0, 1 # sum, sign
P = [ ] # create empty list
for k in range(0, N):
    t = 1/(2.0*k + 1) # kth term
    s += g*t # Gregory's series, 32 terms
    g = -g # terms have alternating signs
    P.append(4*s) # append P[k] to list
for d in range(0, A): # repeatedly ave adj terms
    for j in range(0, M-1):
        P[j] = (P[j] + P[j+1])/2
    M -= 1
sys.stdout.write(("%18.15f" % P[A-1]) + "\n")
Output:  3.141592653589793
    pi = 3.141592653589793238462643383279
(See Averaging.)

Items of Interest or for study:

• The algorithm above was translated from Java. Basic to the algorithm is an array of N doubles:

  double P[ ] = new double [N]; // Java
  double P[N]; // C, but need N a constant

  This was my first Python program with an array, and I wondered how I could declare one. If you think of a Python list as a linked list, then you realize that you don't "declare" an entire linked list but you build it up element at a time. The line P = [ ] creates an empty list. Then the line P.append(4*s) adds another item at the end of P and fills it with 4*s. This happens N times in the loop, so I ended up with a list of length N as I wanted. This list could be used just like an array in the rest of the program. In order to create a list of length N with all zeros in it, you can write:

  P = [ ]
  for k in range(0, N):
      P.append(0.0)

  or just

  P = [0.0]*N

  The null object None would be a better choice than 0.0:

  % python >>> P = [ None ]*5 >>> P[2] = 4.5 >>> P [None, None, 4.5, None, None] >>> P[4] = range(1,3) >>> P [None, None, 4.5, None, [1, 2]] >>> P[4][1] 2

• In the for loop, the item range(0,N) gives a list of integers from 0 to N-1, and then the for iterates over this list. The item range(N) gives the same thing.

• If you have an unchanging list, a tuple is easier to use, and uses far fewer resources.

• Python has an array module, which is like a list except that all items in it must be of a single simple type (one of the standard constant types). The book by Beazely gives the example: "Storing 10 million integers in a list requires about 160MB of memory, whereas an array of 10 million integers requires only 40MB." However these are no particular run-time savings.

• For serious numeric work, even the array module is not suitable, but instead you should use the numpy extension.