0

How are the lists implemented in python? I mean how is it possible to append an element in constant time and also get an item in constant time? Can anyone please tell how to do it in C?

Chandan
  • 749
  • 1
  • 8
  • 11
  • Your question is wayyy too broad. You should just look it up on google unless you have a specific question. And yes all those things are possible in amortized constant time otherwise how is python able to do it? – jamylak Apr 15 '13 at 07:04
  • 5
    This should help: http://www.laurentluce.com/posts/python-list-implementation/ – Maroun Apr 15 '13 at 07:05
  • 1
    See [here](http://hg.python.org/cpython/file/a88310d86455/Objects/listobject.c) for the C source code. – BioGeek Apr 15 '13 at 07:07
  • Heard of search engines? Try searching for "comparison of list implementations"? Then, if you don't understand it, come back and ask. – class stacker Apr 15 '13 at 07:08
  • 1
    Please limit your questions to only ONE question. This question as it currently stands is not suited to the format of this site. Please read the [FAQ], specifically on [ask]. – Inbar Rose Apr 15 '13 at 07:18

1 Answers1

0

A simple implementation is to use a preallocated buffer and a counter for the number of elements. When the buffer is filled up and you want to append element, then you allocate a bigger buffer (e.g. twice as big) and copy the old one's data into the new one.

Thus the append operation is not strictly O(1), but it's amortized O(1), namely on average it's O(1).

Petar Ivanov
  • 91,536
  • 11
  • 82
  • 95
  • It starts off twice as big but then the overallocation dies down to about 1/8. The data doesn't always need to be copied unless it needs to be moved so as to not run into other used memory – jamylak Apr 15 '13 at 07:08
  • Let's assume that we're growing the array by a constant size, let's assume it's 5, and that's where we start. Then we have 5 appends, after that the allocation and deallocation of memory (which is super expensive as compared to the append itself), plus copying 5 entries. Then, after another 5 appends, we have to re-allocate and copy 10 entries. I don't have the _slightest_ idea how you conclude O(1) here. It's more like O(n), no? And you're getting O(log(n)) if you double the size. – class stacker Apr 15 '13 at 07:17
  • @ClassStacker Your initial assumption is completely unrelated to lists which **don't** grow at a constant rate. Also they do not need to copy all the objects each time as Petar said, see my comment above. – jamylak Apr 15 '13 at 07:33
  • The new size is not additive constant but multiplicative - e.g. the new size is 2x the old size (or 1/8x as jamylak suggested) – Petar Ivanov Apr 15 '13 at 07:34
  • From the source code: *The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...* @Petar it's not always 2x – jamylak Apr 15 '13 at 07:34
  • @jamylak For lists for which you know that they grow only rarely, an effort estimation is somewhat pointless. That's just like Bubble Sort being always the fastest sorting algorithm for up to a dozen elements. The question was, how can I have a list which grows with O(1). – class stacker Apr 15 '13 at 07:36
  • @ClassStacker Linked list does that, is that what you are asking? I don't understand your question though, we specifically stated that it's amortized. It is practically very fast though. – jamylak Apr 15 '13 at 07:39
  • @ClassStacker You just have to do the math right :(. Without loss of generality, assume we have inserted a = 2^n elements, and we now have to double our table to 2^(n+1) size. That means we're currently doing 2^(n+1) operations. Last copy, we did 2^n operations. Before that we did 2^(n-1)... all the way down to 8,4,2,1. Now, if we add these up, we get 1 + 2 + 4 + 8 + ... + 2^(n+1) = 2^(n+2) - 1 < 4*2^n = O(2^n) = O(a) total insertions (i.e. O(1) amortized time). Also, it should be noted that if the table allows deletions the table shrinking has to be done at a different factor (e.g 3x) – RussellStewart Jun 19 '13 at 13:09