How come list element lookup is O(1) in Python?
Clash Royale CLAN TAG#URR8PPP
up vote
19
down vote
favorite
Today in class, we learned that retrieving an element from a list is O(1)
in Python. Why is this the case? Suppose I have a list of four items, for example:
li = ["perry", 1, 23.5, "s"]
These items have different sizes in memory. And so it is not possible to take the memory location of li[0]
and add three times the size of each element to get the memory location of li[3]
. So how does the interpreter know where li[3]
is without having to traverse the list in order to retrieve the element?
python arrays list
 |Â
show 4 more comments
up vote
19
down vote
favorite
Today in class, we learned that retrieving an element from a list is O(1)
in Python. Why is this the case? Suppose I have a list of four items, for example:
li = ["perry", 1, 23.5, "s"]
These items have different sizes in memory. And so it is not possible to take the memory location of li[0]
and add three times the size of each element to get the memory location of li[3]
. So how does the interpreter know where li[3]
is without having to traverse the list in order to retrieve the element?
python arrays list
14
What makes you think that arrays are linearly allocated rather than a list of pointers. - [me confused by your profile description]
â Morrison Chang
2 days ago
22
Don't confuse item access, which isO(1)
, with item lookup / search, which isO(n)
.
â Mike Scotty
2 days ago
4
Some relevant reading material: Python list implementation, How is Python's List Implemented?, What is the underlying data structure for Python lists?.
â Warren Weckesser
2 days ago
2
It is not good to ask the same question on two different SE sites (when answers will be within the same context).
â rus9384
yesterday
2
Cross-posted to Computer Science (where, IMO, it's off-topic). Please don't post the same question to multiple Stack Exchange sites. It fragments answers and wastes people's time when they put effort into answering questions that already have answers elsewhere.
â David Richerby
yesterday
 |Â
show 4 more comments
up vote
19
down vote
favorite
up vote
19
down vote
favorite
Today in class, we learned that retrieving an element from a list is O(1)
in Python. Why is this the case? Suppose I have a list of four items, for example:
li = ["perry", 1, 23.5, "s"]
These items have different sizes in memory. And so it is not possible to take the memory location of li[0]
and add three times the size of each element to get the memory location of li[3]
. So how does the interpreter know where li[3]
is without having to traverse the list in order to retrieve the element?
python arrays list
Today in class, we learned that retrieving an element from a list is O(1)
in Python. Why is this the case? Suppose I have a list of four items, for example:
li = ["perry", 1, 23.5, "s"]
These items have different sizes in memory. And so it is not possible to take the memory location of li[0]
and add three times the size of each element to get the memory location of li[3]
. So how does the interpreter know where li[3]
is without having to traverse the list in order to retrieve the element?
python arrays list
python arrays list
edited yesterday
Peter Mortensen
13.1k1983111
13.1k1983111
asked 2 days ago
Teererai Marange
74021334
74021334
14
What makes you think that arrays are linearly allocated rather than a list of pointers. - [me confused by your profile description]
â Morrison Chang
2 days ago
22
Don't confuse item access, which isO(1)
, with item lookup / search, which isO(n)
.
â Mike Scotty
2 days ago
4
Some relevant reading material: Python list implementation, How is Python's List Implemented?, What is the underlying data structure for Python lists?.
â Warren Weckesser
2 days ago
2
It is not good to ask the same question on two different SE sites (when answers will be within the same context).
â rus9384
yesterday
2
Cross-posted to Computer Science (where, IMO, it's off-topic). Please don't post the same question to multiple Stack Exchange sites. It fragments answers and wastes people's time when they put effort into answering questions that already have answers elsewhere.
â David Richerby
yesterday
 |Â
show 4 more comments
14
What makes you think that arrays are linearly allocated rather than a list of pointers. - [me confused by your profile description]
â Morrison Chang
2 days ago
22
Don't confuse item access, which isO(1)
, with item lookup / search, which isO(n)
.
â Mike Scotty
2 days ago
4
Some relevant reading material: Python list implementation, How is Python's List Implemented?, What is the underlying data structure for Python lists?.
â Warren Weckesser
2 days ago
2
It is not good to ask the same question on two different SE sites (when answers will be within the same context).
â rus9384
yesterday
2
Cross-posted to Computer Science (where, IMO, it's off-topic). Please don't post the same question to multiple Stack Exchange sites. It fragments answers and wastes people's time when they put effort into answering questions that already have answers elsewhere.
â David Richerby
yesterday
14
14
What makes you think that arrays are linearly allocated rather than a list of pointers. - [me confused by your profile description]
â Morrison Chang
2 days ago
What makes you think that arrays are linearly allocated rather than a list of pointers. - [me confused by your profile description]
â Morrison Chang
2 days ago
22
22
Don't confuse item access, which is
O(1)
, with item lookup / search, which is O(n)
.â Mike Scotty
2 days ago
Don't confuse item access, which is
O(1)
, with item lookup / search, which is O(n)
.â Mike Scotty
2 days ago
4
4
Some relevant reading material: Python list implementation, How is Python's List Implemented?, What is the underlying data structure for Python lists?.
â Warren Weckesser
2 days ago
Some relevant reading material: Python list implementation, How is Python's List Implemented?, What is the underlying data structure for Python lists?.
â Warren Weckesser
2 days ago
2
2
It is not good to ask the same question on two different SE sites (when answers will be within the same context).
â rus9384
yesterday
It is not good to ask the same question on two different SE sites (when answers will be within the same context).
â rus9384
yesterday
2
2
Cross-posted to Computer Science (where, IMO, it's off-topic). Please don't post the same question to multiple Stack Exchange sites. It fragments answers and wastes people's time when they put effort into answering questions that already have answers elsewhere.
â David Richerby
yesterday
Cross-posted to Computer Science (where, IMO, it's off-topic). Please don't post the same question to multiple Stack Exchange sites. It fragments answers and wastes people's time when they put effort into answering questions that already have answers elsewhere.
â David Richerby
yesterday
 |Â
show 4 more comments
3 Answers
3
active
oldest
votes
up vote
46
down vote
accepted
A list in Python is implemented as an array of pointers1. So, what's really happening when you create the list:
["perry", 1, 23.5, "s"]
is that you are actually creating an array of pointers like so:
[0xa3d25342, 0x635423fa, 0xff243546, 0x2545fade]
Each pointer "points" to the respective objects in memory, so that the string "perry"
will be stored at address 0xa3d25342
and the number 1
will be stored at 0x635423fa
, etc.
Since all pointers are the same size, the interpreter can in fact add 3 times the size of an element to the address of li[0]
to get to the pointer stored at li[3]
.
1 Get more details from: the horse's mouth (CPython source code on GitHub).
I am sorry, but according to Mark Lutz book I've got the impression list stores references, which is a bit different than pointers, is it the same thing there and different elsewhere, or references is pointers in python? I've heard what in C it's different with a complex explanation of difference.
â Dmitry Verhoturov
yesterday
4
@DmitryVerhoturov That's right but makes no practical difference for this answer. References are reference-counted, docs.python.org/3/c-api/structures.html#c.PyVarObject
â pipe
yesterday
6
Reference is implemented as pointers in every language I know. Semantics may differ slightly (e.g. differences in memory management, or references in C++ being immutable), but in the end they are still pointers.
â Frax
yesterday
Note that in practice retrieving an element from the list is actually more like O(log n)... and in theory physical constraints limit it to no better than O(sqrt n).
â TLW
yesterday
5
@TLW I've never seen those before. Where'd you find them?
â Cort Ammon
23 hours ago
 |Â
show 5 more comments
up vote
15
down vote
When you say a = [...]
, a
is effectively a pointer to a PyObject
containing an array of pointers to PyObject
s.
When you ask for a[2]
, the interpreter first follows the pointer to the list's PyObject
, then adds 2
to the address of the array inside it, then returns that pointer. The same happens if you ask for a[0]
or a[9999]
.
Basically, all Python objects are accessed by reference instead of by value, even integer literals like 2
. There are just some tricks in the pointer system to keep this all efficient. And pointers have a known size, so they can be stored conveniently in C-style arrays.
4
what is ''terp''?
â hkBst
yesterday
@hkBst I infer that it's short for "interpreter".
â Mario Carneiro
yesterday
add a comment |Â
up vote
5
down vote
Short answer: Python lists are arrays.
Long answer: The computer science term list usually means either a singly-linked list (as used in functional programming) or a doubly-linked list (as used in procedural programming). These data structures support O(1) insertion at either the head of the list (functionally) or at any position that does not need to be searched for (procedurally). A Python ``list'' has none of these characteristics. Instead it supports (amortized) O(1) appending at the end of the list (like a C++ std::vector or Java ArrayList). Python lists are really resizable arrays in CS terms.
1
IâÂÂve never heard of singly-linked lists being specifically associated with functional programming, or doubly-linked lists being specifically associated with procedural programming. Both types of list are valid and have their use-cases for both programming paradigms (and other programming paradigms besides). Can you back up that claim? I find it quite dubious.
â KRyan
yesterday
@KRyan I'm pretty sure that Lisp, Haskell, Ocaml are all generally using singly-linked lists, especially with the more convenient primitives in the languages. Lisp in particular has a bunch of shorthand like car/cdr for getting the various parts of the list elements. Of course they're used everywhere else, but, Lisp and functional company often makes much heavier use of them. C++'s list, for example is a doubly linked list, and only recently did they get a forward_list(which is singly typed)
â jaked122
yesterday
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
46
down vote
accepted
A list in Python is implemented as an array of pointers1. So, what's really happening when you create the list:
["perry", 1, 23.5, "s"]
is that you are actually creating an array of pointers like so:
[0xa3d25342, 0x635423fa, 0xff243546, 0x2545fade]
Each pointer "points" to the respective objects in memory, so that the string "perry"
will be stored at address 0xa3d25342
and the number 1
will be stored at 0x635423fa
, etc.
Since all pointers are the same size, the interpreter can in fact add 3 times the size of an element to the address of li[0]
to get to the pointer stored at li[3]
.
1 Get more details from: the horse's mouth (CPython source code on GitHub).
I am sorry, but according to Mark Lutz book I've got the impression list stores references, which is a bit different than pointers, is it the same thing there and different elsewhere, or references is pointers in python? I've heard what in C it's different with a complex explanation of difference.
â Dmitry Verhoturov
yesterday
4
@DmitryVerhoturov That's right but makes no practical difference for this answer. References are reference-counted, docs.python.org/3/c-api/structures.html#c.PyVarObject
â pipe
yesterday
6
Reference is implemented as pointers in every language I know. Semantics may differ slightly (e.g. differences in memory management, or references in C++ being immutable), but in the end they are still pointers.
â Frax
yesterday
Note that in practice retrieving an element from the list is actually more like O(log n)... and in theory physical constraints limit it to no better than O(sqrt n).
â TLW
yesterday
5
@TLW I've never seen those before. Where'd you find them?
â Cort Ammon
23 hours ago
 |Â
show 5 more comments
up vote
46
down vote
accepted
A list in Python is implemented as an array of pointers1. So, what's really happening when you create the list:
["perry", 1, 23.5, "s"]
is that you are actually creating an array of pointers like so:
[0xa3d25342, 0x635423fa, 0xff243546, 0x2545fade]
Each pointer "points" to the respective objects in memory, so that the string "perry"
will be stored at address 0xa3d25342
and the number 1
will be stored at 0x635423fa
, etc.
Since all pointers are the same size, the interpreter can in fact add 3 times the size of an element to the address of li[0]
to get to the pointer stored at li[3]
.
1 Get more details from: the horse's mouth (CPython source code on GitHub).
I am sorry, but according to Mark Lutz book I've got the impression list stores references, which is a bit different than pointers, is it the same thing there and different elsewhere, or references is pointers in python? I've heard what in C it's different with a complex explanation of difference.
â Dmitry Verhoturov
yesterday
4
@DmitryVerhoturov That's right but makes no practical difference for this answer. References are reference-counted, docs.python.org/3/c-api/structures.html#c.PyVarObject
â pipe
yesterday
6
Reference is implemented as pointers in every language I know. Semantics may differ slightly (e.g. differences in memory management, or references in C++ being immutable), but in the end they are still pointers.
â Frax
yesterday
Note that in practice retrieving an element from the list is actually more like O(log n)... and in theory physical constraints limit it to no better than O(sqrt n).
â TLW
yesterday
5
@TLW I've never seen those before. Where'd you find them?
â Cort Ammon
23 hours ago
 |Â
show 5 more comments
up vote
46
down vote
accepted
up vote
46
down vote
accepted
A list in Python is implemented as an array of pointers1. So, what's really happening when you create the list:
["perry", 1, 23.5, "s"]
is that you are actually creating an array of pointers like so:
[0xa3d25342, 0x635423fa, 0xff243546, 0x2545fade]
Each pointer "points" to the respective objects in memory, so that the string "perry"
will be stored at address 0xa3d25342
and the number 1
will be stored at 0x635423fa
, etc.
Since all pointers are the same size, the interpreter can in fact add 3 times the size of an element to the address of li[0]
to get to the pointer stored at li[3]
.
1 Get more details from: the horse's mouth (CPython source code on GitHub).
A list in Python is implemented as an array of pointers1. So, what's really happening when you create the list:
["perry", 1, 23.5, "s"]
is that you are actually creating an array of pointers like so:
[0xa3d25342, 0x635423fa, 0xff243546, 0x2545fade]
Each pointer "points" to the respective objects in memory, so that the string "perry"
will be stored at address 0xa3d25342
and the number 1
will be stored at 0x635423fa
, etc.
Since all pointers are the same size, the interpreter can in fact add 3 times the size of an element to the address of li[0]
to get to the pointer stored at li[3]
.
1 Get more details from: the horse's mouth (CPython source code on GitHub).
edited yesterday
answered 2 days ago
DJG
4,03232342
4,03232342
I am sorry, but according to Mark Lutz book I've got the impression list stores references, which is a bit different than pointers, is it the same thing there and different elsewhere, or references is pointers in python? I've heard what in C it's different with a complex explanation of difference.
â Dmitry Verhoturov
yesterday
4
@DmitryVerhoturov That's right but makes no practical difference for this answer. References are reference-counted, docs.python.org/3/c-api/structures.html#c.PyVarObject
â pipe
yesterday
6
Reference is implemented as pointers in every language I know. Semantics may differ slightly (e.g. differences in memory management, or references in C++ being immutable), but in the end they are still pointers.
â Frax
yesterday
Note that in practice retrieving an element from the list is actually more like O(log n)... and in theory physical constraints limit it to no better than O(sqrt n).
â TLW
yesterday
5
@TLW I've never seen those before. Where'd you find them?
â Cort Ammon
23 hours ago
 |Â
show 5 more comments
I am sorry, but according to Mark Lutz book I've got the impression list stores references, which is a bit different than pointers, is it the same thing there and different elsewhere, or references is pointers in python? I've heard what in C it's different with a complex explanation of difference.
â Dmitry Verhoturov
yesterday
4
@DmitryVerhoturov That's right but makes no practical difference for this answer. References are reference-counted, docs.python.org/3/c-api/structures.html#c.PyVarObject
â pipe
yesterday
6
Reference is implemented as pointers in every language I know. Semantics may differ slightly (e.g. differences in memory management, or references in C++ being immutable), but in the end they are still pointers.
â Frax
yesterday
Note that in practice retrieving an element from the list is actually more like O(log n)... and in theory physical constraints limit it to no better than O(sqrt n).
â TLW
yesterday
5
@TLW I've never seen those before. Where'd you find them?
â Cort Ammon
23 hours ago
I am sorry, but according to Mark Lutz book I've got the impression list stores references, which is a bit different than pointers, is it the same thing there and different elsewhere, or references is pointers in python? I've heard what in C it's different with a complex explanation of difference.
â Dmitry Verhoturov
yesterday
I am sorry, but according to Mark Lutz book I've got the impression list stores references, which is a bit different than pointers, is it the same thing there and different elsewhere, or references is pointers in python? I've heard what in C it's different with a complex explanation of difference.
â Dmitry Verhoturov
yesterday
4
4
@DmitryVerhoturov That's right but makes no practical difference for this answer. References are reference-counted, docs.python.org/3/c-api/structures.html#c.PyVarObject
â pipe
yesterday
@DmitryVerhoturov That's right but makes no practical difference for this answer. References are reference-counted, docs.python.org/3/c-api/structures.html#c.PyVarObject
â pipe
yesterday
6
6
Reference is implemented as pointers in every language I know. Semantics may differ slightly (e.g. differences in memory management, or references in C++ being immutable), but in the end they are still pointers.
â Frax
yesterday
Reference is implemented as pointers in every language I know. Semantics may differ slightly (e.g. differences in memory management, or references in C++ being immutable), but in the end they are still pointers.
â Frax
yesterday
Note that in practice retrieving an element from the list is actually more like O(log n)... and in theory physical constraints limit it to no better than O(sqrt n).
â TLW
yesterday
Note that in practice retrieving an element from the list is actually more like O(log n)... and in theory physical constraints limit it to no better than O(sqrt n).
â TLW
yesterday
5
5
@TLW I've never seen those before. Where'd you find them?
â Cort Ammon
23 hours ago
@TLW I've never seen those before. Where'd you find them?
â Cort Ammon
23 hours ago
 |Â
show 5 more comments
up vote
15
down vote
When you say a = [...]
, a
is effectively a pointer to a PyObject
containing an array of pointers to PyObject
s.
When you ask for a[2]
, the interpreter first follows the pointer to the list's PyObject
, then adds 2
to the address of the array inside it, then returns that pointer. The same happens if you ask for a[0]
or a[9999]
.
Basically, all Python objects are accessed by reference instead of by value, even integer literals like 2
. There are just some tricks in the pointer system to keep this all efficient. And pointers have a known size, so they can be stored conveniently in C-style arrays.
4
what is ''terp''?
â hkBst
yesterday
@hkBst I infer that it's short for "interpreter".
â Mario Carneiro
yesterday
add a comment |Â
up vote
15
down vote
When you say a = [...]
, a
is effectively a pointer to a PyObject
containing an array of pointers to PyObject
s.
When you ask for a[2]
, the interpreter first follows the pointer to the list's PyObject
, then adds 2
to the address of the array inside it, then returns that pointer. The same happens if you ask for a[0]
or a[9999]
.
Basically, all Python objects are accessed by reference instead of by value, even integer literals like 2
. There are just some tricks in the pointer system to keep this all efficient. And pointers have a known size, so they can be stored conveniently in C-style arrays.
4
what is ''terp''?
â hkBst
yesterday
@hkBst I infer that it's short for "interpreter".
â Mario Carneiro
yesterday
add a comment |Â
up vote
15
down vote
up vote
15
down vote
When you say a = [...]
, a
is effectively a pointer to a PyObject
containing an array of pointers to PyObject
s.
When you ask for a[2]
, the interpreter first follows the pointer to the list's PyObject
, then adds 2
to the address of the array inside it, then returns that pointer. The same happens if you ask for a[0]
or a[9999]
.
Basically, all Python objects are accessed by reference instead of by value, even integer literals like 2
. There are just some tricks in the pointer system to keep this all efficient. And pointers have a known size, so they can be stored conveniently in C-style arrays.
When you say a = [...]
, a
is effectively a pointer to a PyObject
containing an array of pointers to PyObject
s.
When you ask for a[2]
, the interpreter first follows the pointer to the list's PyObject
, then adds 2
to the address of the array inside it, then returns that pointer. The same happens if you ask for a[0]
or a[9999]
.
Basically, all Python objects are accessed by reference instead of by value, even integer literals like 2
. There are just some tricks in the pointer system to keep this all efficient. And pointers have a known size, so they can be stored conveniently in C-style arrays.
answered yesterday
Draconis
996616
996616
4
what is ''terp''?
â hkBst
yesterday
@hkBst I infer that it's short for "interpreter".
â Mario Carneiro
yesterday
add a comment |Â
4
what is ''terp''?
â hkBst
yesterday
@hkBst I infer that it's short for "interpreter".
â Mario Carneiro
yesterday
4
4
what is ''terp''?
â hkBst
yesterday
what is ''terp''?
â hkBst
yesterday
@hkBst I infer that it's short for "interpreter".
â Mario Carneiro
yesterday
@hkBst I infer that it's short for "interpreter".
â Mario Carneiro
yesterday
add a comment |Â
up vote
5
down vote
Short answer: Python lists are arrays.
Long answer: The computer science term list usually means either a singly-linked list (as used in functional programming) or a doubly-linked list (as used in procedural programming). These data structures support O(1) insertion at either the head of the list (functionally) or at any position that does not need to be searched for (procedurally). A Python ``list'' has none of these characteristics. Instead it supports (amortized) O(1) appending at the end of the list (like a C++ std::vector or Java ArrayList). Python lists are really resizable arrays in CS terms.
1
IâÂÂve never heard of singly-linked lists being specifically associated with functional programming, or doubly-linked lists being specifically associated with procedural programming. Both types of list are valid and have their use-cases for both programming paradigms (and other programming paradigms besides). Can you back up that claim? I find it quite dubious.
â KRyan
yesterday
@KRyan I'm pretty sure that Lisp, Haskell, Ocaml are all generally using singly-linked lists, especially with the more convenient primitives in the languages. Lisp in particular has a bunch of shorthand like car/cdr for getting the various parts of the list elements. Of course they're used everywhere else, but, Lisp and functional company often makes much heavier use of them. C++'s list, for example is a doubly linked list, and only recently did they get a forward_list(which is singly typed)
â jaked122
yesterday
add a comment |Â
up vote
5
down vote
Short answer: Python lists are arrays.
Long answer: The computer science term list usually means either a singly-linked list (as used in functional programming) or a doubly-linked list (as used in procedural programming). These data structures support O(1) insertion at either the head of the list (functionally) or at any position that does not need to be searched for (procedurally). A Python ``list'' has none of these characteristics. Instead it supports (amortized) O(1) appending at the end of the list (like a C++ std::vector or Java ArrayList). Python lists are really resizable arrays in CS terms.
1
IâÂÂve never heard of singly-linked lists being specifically associated with functional programming, or doubly-linked lists being specifically associated with procedural programming. Both types of list are valid and have their use-cases for both programming paradigms (and other programming paradigms besides). Can you back up that claim? I find it quite dubious.
â KRyan
yesterday
@KRyan I'm pretty sure that Lisp, Haskell, Ocaml are all generally using singly-linked lists, especially with the more convenient primitives in the languages. Lisp in particular has a bunch of shorthand like car/cdr for getting the various parts of the list elements. Of course they're used everywhere else, but, Lisp and functional company often makes much heavier use of them. C++'s list, for example is a doubly linked list, and only recently did they get a forward_list(which is singly typed)
â jaked122
yesterday
add a comment |Â
up vote
5
down vote
up vote
5
down vote
Short answer: Python lists are arrays.
Long answer: The computer science term list usually means either a singly-linked list (as used in functional programming) or a doubly-linked list (as used in procedural programming). These data structures support O(1) insertion at either the head of the list (functionally) or at any position that does not need to be searched for (procedurally). A Python ``list'' has none of these characteristics. Instead it supports (amortized) O(1) appending at the end of the list (like a C++ std::vector or Java ArrayList). Python lists are really resizable arrays in CS terms.
Short answer: Python lists are arrays.
Long answer: The computer science term list usually means either a singly-linked list (as used in functional programming) or a doubly-linked list (as used in procedural programming). These data structures support O(1) insertion at either the head of the list (functionally) or at any position that does not need to be searched for (procedurally). A Python ``list'' has none of these characteristics. Instead it supports (amortized) O(1) appending at the end of the list (like a C++ std::vector or Java ArrayList). Python lists are really resizable arrays in CS terms.
answered yesterday
hkBst
844215
844215
1
IâÂÂve never heard of singly-linked lists being specifically associated with functional programming, or doubly-linked lists being specifically associated with procedural programming. Both types of list are valid and have their use-cases for both programming paradigms (and other programming paradigms besides). Can you back up that claim? I find it quite dubious.
â KRyan
yesterday
@KRyan I'm pretty sure that Lisp, Haskell, Ocaml are all generally using singly-linked lists, especially with the more convenient primitives in the languages. Lisp in particular has a bunch of shorthand like car/cdr for getting the various parts of the list elements. Of course they're used everywhere else, but, Lisp and functional company often makes much heavier use of them. C++'s list, for example is a doubly linked list, and only recently did they get a forward_list(which is singly typed)
â jaked122
yesterday
add a comment |Â
1
IâÂÂve never heard of singly-linked lists being specifically associated with functional programming, or doubly-linked lists being specifically associated with procedural programming. Both types of list are valid and have their use-cases for both programming paradigms (and other programming paradigms besides). Can you back up that claim? I find it quite dubious.
â KRyan
yesterday
@KRyan I'm pretty sure that Lisp, Haskell, Ocaml are all generally using singly-linked lists, especially with the more convenient primitives in the languages. Lisp in particular has a bunch of shorthand like car/cdr for getting the various parts of the list elements. Of course they're used everywhere else, but, Lisp and functional company often makes much heavier use of them. C++'s list, for example is a doubly linked list, and only recently did they get a forward_list(which is singly typed)
â jaked122
yesterday
1
1
IâÂÂve never heard of singly-linked lists being specifically associated with functional programming, or doubly-linked lists being specifically associated with procedural programming. Both types of list are valid and have their use-cases for both programming paradigms (and other programming paradigms besides). Can you back up that claim? I find it quite dubious.
â KRyan
yesterday
IâÂÂve never heard of singly-linked lists being specifically associated with functional programming, or doubly-linked lists being specifically associated with procedural programming. Both types of list are valid and have their use-cases for both programming paradigms (and other programming paradigms besides). Can you back up that claim? I find it quite dubious.
â KRyan
yesterday
@KRyan I'm pretty sure that Lisp, Haskell, Ocaml are all generally using singly-linked lists, especially with the more convenient primitives in the languages. Lisp in particular has a bunch of shorthand like car/cdr for getting the various parts of the list elements. Of course they're used everywhere else, but, Lisp and functional company often makes much heavier use of them. C++'s list, for example is a doubly linked list, and only recently did they get a forward_list(which is singly typed)
â jaked122
yesterday
@KRyan I'm pretty sure that Lisp, Haskell, Ocaml are all generally using singly-linked lists, especially with the more convenient primitives in the languages. Lisp in particular has a bunch of shorthand like car/cdr for getting the various parts of the list elements. Of course they're used everywhere else, but, Lisp and functional company often makes much heavier use of them. C++'s list, for example is a doubly linked list, and only recently did they get a forward_list(which is singly typed)
â jaked122
yesterday
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f52684993%2fhow-come-list-element-lookup-is-o1-in-python%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
14
What makes you think that arrays are linearly allocated rather than a list of pointers. - [me confused by your profile description]
â Morrison Chang
2 days ago
22
Don't confuse item access, which is
O(1)
, with item lookup / search, which isO(n)
.â Mike Scotty
2 days ago
4
Some relevant reading material: Python list implementation, How is Python's List Implemented?, What is the underlying data structure for Python lists?.
â Warren Weckesser
2 days ago
2
It is not good to ask the same question on two different SE sites (when answers will be within the same context).
â rus9384
yesterday
2
Cross-posted to Computer Science (where, IMO, it's off-topic). Please don't post the same question to multiple Stack Exchange sites. It fragments answers and wastes people's time when they put effort into answering questions that already have answers elsewhere.
â David Richerby
yesterday