5

I am no expert in how Python lists are implemented but from what I understand, they are implemented as dynamic arrays rather than linked lists. My question is therefore, if python lists are implemented as arrays, why are they called 'lists' and not 'arrays'.

Is this just a semantic issue or is there some deeper technical reason behind this. Is the dynamic array implementation in Python close to a list implementation? Or is it because the dynamic array implementation makes its behaviour closer to a list's behaviour than an array? Or some other reason I do not understand?

To be clear, I am not asking specifically how or why Python lists are implemented as dynamic arrays, although that might be relevant to the answer.

Kevin L.
  • 1,371
  • 11
  • 24
  • It's indeed an array. But my educated guess for the naming is that `array` will usually imply *all of the same type* in many languages. It is not the case in Python. – llllllllll Feb 24 '18 at 18:37
  • `arrays` in Python (as in `array.array` for instance) is a homogeneous container of a certain type. `list`s contain *any* object. Also - arrays because they're normally used for immutable types, can share "views" of sliced ranges such that no copying is made. See: https://docs.python.org/3/library/stdtypes.html#memoryview for instance or even `numpy.array`s – Jon Clements Feb 24 '18 at 18:37
  • arrays generally contain elements of the same datatype. But, lists, on the other hand, can contain elements of all datatypes. – ayrusme Feb 24 '18 at 18:39
  • They're named after the [list abstract data type](https://en.wikipedia.org/wiki/List_(abstract_data_type)), not linked lists. – user2357112 Feb 24 '18 at 18:53

3 Answers3

9

They're named after the list abstract data type, not linked lists. This is similar to the naming of Java's List interface and C#'s List<T>.

user2357112
  • 260,549
  • 28
  • 431
  • 505
1

To further elaborate on user2357112's answer, as pointed out in the wikipedia article:

In computer science, a list or sequence is an abstract data type that represents a countable number of ordered values, where the same value may occur more than once.

Further,

List data types are often implemented using array data structures or linked lists of some sort, but other data structures may be more appropriate for some applications.

In CPython, lists are implemented as dynamic arrays of pointers, and their behaviour is much closer to the List abstract data type than the Array abstract data type. From this perspective, the naming of 'List' is accurate.

Kevin L.
  • 1,371
  • 11
  • 24
-1

At the end of the day when implementing a list what you want is constant(O(1)) access(a[i]), insert(a.append(i)) and delete(a.remove(i)) times. With a linked list some of this operations could be as slow as O(n), i.e. deleting the last element of linked lists if you don't have a pointer to the tail.

With dynamic arrays you get constant delete and access times but what about deleting? Here we get amortized constant time. What is that? If the array is full of N elements, the insert will take O(N) and you'll end up with an array of size 2N. This is a rare event, thus we say we have amortized O(1).

Hope it helps.

Sources: https://docs.python.org/2/faq/design.html

randyjp
  • 1,084
  • 9
  • 8
  • 1
    You have the question backward. It's not "why are they implemented with arrays if they're called lists"; it's "why are they called lists if they're implemented with arrays". – user2357112 Feb 24 '18 at 19:29
  • Also your answer is pretty garbled where it talks about deletion. You say deletion is constant time, and then you say it's amortized constant time, but neither of those things are true. – user2357112 Feb 24 '18 at 19:30
  • How would you describe the time of deleting an element from an list then? If I'm wrong, you should provide some proof to help me understand. – randyjp Feb 24 '18 at 19:33
  • 1
    Deletion by index takes time proportional to the number of elements that have to be shifted to close the gap; deletion by value takes time proportional to the size of the list, because in addition to shifting elements, Python also needs to find the element to remove. – user2357112 Feb 24 '18 at 19:36