How to grow a list to fit a given capacity in Python

Question

I'm a Python newbie. I have a series of objects that need to be inserted at specific indices of a list, but they come out of order, so I can't just append them. How can I grow the list whenever necessary to avoid IndexErrors?

def set(index, item):
    if len(nodes) <= index:
        # Grow list to index+1
    nodes[index] = item

I know you can create a list with an initial capacity via nodes = (index+1) * [None] but what's the usual way to grow it in place? The following doesn't seem efficient:

for _ in xrange(len(nodes), index+1):
    nodes.append(None)

In addition, I suppose there's probably a class in the Standard Library that I should be using instead of built-in lists?

http://stackoverflow.com/questions/725782/in-python-what-is-the-difference-between-append-and — Anders Lindahl, Apr 14 '12 at 17:03

score 7 · Accepted Answer · answered Apr 14 '12 at 17:06

7

This is the best way to of doing it.

>>> lst.extend([None]*additional_size)

answered Apr 14 '12 at 17:06

luke14free

2,529
1
17
25

Is that any faster than `lst += [None]*additional_size`? – Neil Traft Apr 14 '12 at 17:17
Marginally faster, but it's a cleaner syntax in my opinion, if there's a method, let's use it. $ python -m timeit 'additional_size=100000; lst=[]; lst += [None] * additional_size' 1000 loops, best of 3: 907 usec per loop $ python -m timeit 'additional_size=100000; lst=[]; lst.extend([None]*additional_size)' 1000 loops, best of 3: 889 usec per loop – luke14free Apr 14 '12 at 17:25
how about defaultdict with indexes as keys? – Joel Cornett Apr 14 '12 at 17:33
That approach can be dangerous: If you `meow = [[]] * 2` and then `meow[0].append('hi')` then the value becomes `[['hi'], ['hi']]` which might be unintentional – Shannon Jul 26 '23 at 22:08

David Z · Answer 2 · 2012-04-14T17:21:18.550

oops seems like I misunderstood your question at first. If you are asking how to expand the length of a list so you can insert something at an index larger than the current length of the list, then lst.extend([None]*(new_size - len(lst)) would probably be the way to go, as others have suggested. Of course, if you know in advance what the maximum index you will be needing is, it would make sense to create the list in advance and fill it with Nones.

For reference, I leave the original text: to insert something in the middle of the existing list, the usual way is not to worry about growing the list yourself. List objects come with an insert method that will let you insert an object at any point in the list. So instead of your set function, just use

lst.insert(item, index)

or you could do

lst[index:index] = item

which does the same thing. Python will take care of resizing the list for you.

There is not necessarily any class in the standard library that you should be using instead of list, especially if you need this sort of random-access insertion. However, there are some classes in the collections module which you should be aware of, since they can be useful for other situations (e.g. if you're always appending to one end of the list, and you don't know in advance how many items you need, deque would be appropriate).

score 1 · Answer 3 · answered Apr 14 '12 at 17:03

1

Perhaps something like:

lst += [None] * additional_size

(you shouldn't call your list variable list, since it is also the name of the list constructor).

answered Apr 14 '12 at 17:03

thebjorn

26,297
11
96
138

Yeah, sorry, it was actually called 'nodes' in the real code. – Neil Traft Apr 14 '12 at 17:12

How to grow a list to fit a given capacity in Python

3 Answers3