8

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.

Improve this question
4
  • 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. Commented Feb 24, 2018 at 18:37
  • arrays in Python (as in array.array for instance) is a homogeneous container of a certain type. lists 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: docs.python.org/3/library/stdtypes.html#memoryview for instance or even numpy.arrays Commented Feb 24, 2018 at 18:37
  • arrays generally contain elements of the same datatype. But, lists, on the other hand, can contain elements of all datatypes. Commented Feb 24, 2018 at 18:39
  • 1
    They're named after the list abstract data type, not linked lists. Commented Feb 24, 2018 at 18:53

3 Answers 3

Reset to default
10

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>.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

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.

Improve this answer

Comments

-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

Improve this answer

4 Comments

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".
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.
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.
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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.