21

Is there a way to make an automatically growing list in Python? What I mean is to make a list that would grow when an index that does not yet exist is referenced. Basically the behaviour of Ruby arrays.

Thanks in advance!

Anonymous
  • 221
  • 1
  • 2
  • 4
  • Umm, you're describing the way lists work. What are you trying that isn't working? – Falmarri Dec 28 '10 at 08:18
  • What I mean is that if the context is out of range, it will raise an error. I want the list to grow to a size where the index is accommodated; in Ruby this will fill all the intermediary spots with Nulls. – Anonymous Dec 28 '10 at 08:20
  • 1
    What do you want the contents of the not-yet-existing index to be when it is first referenced (and all the elements before it)? Should it be `None` or some other default value? – Tim Pietzcker Dec 28 '10 at 08:23
  • 1
    It should be what it is assigned; so a[100]=20 for example. I don't care what the empty spots are assigned, as these are overwritten later. – Anonymous Dec 28 '10 at 08:25
  • 1
    OK, and what do you want to happen if someone asks for the value of `a[1000]` if it doesn't exist yet? `IndexError` or should the list grow to this size, too? – Tim Pietzcker Dec 28 '10 at 08:27
  • Whats the Ruby's behaviour when you request an unexisting reference from the array? What value does it return? – ismail Dec 28 '10 at 08:41
  • It returns Null for the "empty" spots. I don't usually program in Ruby, but I thought this was a nice feature. – Anonymous Dec 28 '10 at 08:49
  • Did you consider using a Hash Table? – Ash Upadhyay Jan 21 '18 at 05:06

3 Answers3

45

Sure it's possible, you just have to use a subclass of list to do it.

class GrowingList(list):
    def __setitem__(self, index, value):
        if index >= len(self):
            self.extend([None]*(index + 1 - len(self)))
        list.__setitem__(self, index, value)

Usage:

>>> grow = GrowingList()
>>> grow[10] = 4
>>> len(grow)
11
>>> grow
[None, None, None, None, None, None, None, None, None, None, 4]
dan_waterworth
  • 6,261
  • 1
  • 30
  • 41
  • 5
    Just note that this is only really useful for dense arrays, if you need a structure for sparse arrays then you are better off with a dictionary based solution. – dan_waterworth Dec 28 '10 at 09:04
  • add a 'fillvalue' argument in the function...so you can do grow.__setitem__(10, 4, True) for example – Ant Dec 28 '10 at 13:56
  • @Ant, `__setitem__` is a special method, it's not often called via it's name, but like in the example `grow[10] = 4`. – dan_waterworth Dec 28 '10 at 14:04
  • i know, but if i really want that behaviour, i should be able to do that without rewriting the func. and doing def __setitem__(self, index, value, fillvalue=None) won't affect the normal usage ;) – Ant Dec 28 '10 at 14:06
  • @Ant, you can use it like that if you like, but I'm not modifying my answer. – dan_waterworth Dec 28 '10 at 14:10
  • ok, no problem..i think it would be better, but if you dont want to (without explainig why) i don't care at all – Ant Dec 28 '10 at 14:14
  • 3
    I don't think it is good python to add parameters (even default parameters) to special functions, what if the specification changes and it adds another parameter. I think if you need a fillvalue then you should add it to the `__init__` function, but that wouldn't play well with being inherited from list, you'd need to change the `__new__` method, but I'm just trying to write a simple example. – dan_waterworth Dec 28 '10 at 14:31
  • If you really want fillvalue, it may be easier to put the class definition in a function taking fillvalue and returning the GrowingList class, but I don't think there's a problem with just using `None`. That is, after all, what the OP wanted. – dan_waterworth Dec 28 '10 at 14:35
  • If want the list to grow whenever an out-of-bounds element is referenced, you'll also need to redefine the `__getitem__` function. Otherwise, something like `grow = GrowingList(); x = grow[5]` will still produce an error. – Patrick Brinich-Langlois Mar 22 '13 at 10:02
  • I wouldn't add a parameter to `__setitem__()`, but simply add a `fillvalue` parameter to the constructor `__init__()` of growlist and use that within the `__setitem__()` function to determine the default value. – Benjamin B. Jul 17 '15 at 10:25
  • Note: performance-wise it is considered good practice for an auto-resizing array to **double in size instead of growing by one element**, whenever you are unsure what maximal length your array might achieve. Increasing your array dynamically requires memory allocation, which is expensive if your array as to be moved in memory. – user228395 Aug 03 '17 at 14:31
  • Therefore, the proposed solution should not be considered when you are dynamically growing your array/list by a fixed amount of elements at the time. – user228395 Aug 03 '17 at 14:38
2

Lists are dynamic in python. It will automatically grow always (up until you hit sys.maxsize) in your program.

  l = list()
  l.append(item)

Keep doing that.

Senthil Kumaran
  • 54,681
  • 14
  • 94
  • 131
-1

No, but you could use a dictionary (hash table) to achieve the same thing.

Keith
  • 42,110
  • 11
  • 57
  • 76
  • Thanks, but I need it to be ordered. – Anonymous Dec 28 '10 at 08:19
  • 1
    Then you might try the [OrderedDict](http://docs.python.org/library/collections.html#collections.OrderedDict) object. ;-) – Keith Dec 28 '10 at 08:29
  • 1
    They have keys which would act like indices. Not much difference, but saves memory on sparse arrays. The extended list (alternative) approach would also allocate a bunch of unused objects, and also add run time cost to list traversal. – Keith Dec 28 '10 at 08:36
  • I see what you mean. However, the reason I wanted this is for implementing a mathematical algorithm where the values of indeces are significant. – Anonymous Dec 28 '10 at 08:42