Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why are Python Lists called 'lists' when they are implemented as dynamic arrays

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.

like image 426
Kevin L. Avatar asked Feb 24 '18 18:02

Kevin L.


2 Answers

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

like image 157
user2357112 supports Monica Avatar answered Oct 13 '22 22:10

user2357112 supports Monica


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.

like image 30
Kevin L. Avatar answered Oct 13 '22 21:10

Kevin L.