python: How come list element lookup is O(1)

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
6
down vote

favorite
2












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 4 items ie:



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







share|improve this question



















  • 6




    What makes you think that arrays are linearly allocated rather than a list of pointers. - [me confused by your profile description]
    – Morrison Chang
    3 hours ago







  • 9




    Don't confuse item access, which is O(1), with item lookup / search, which is O(n).
    – Mike Scotty
    3 hours ago







  • 1




    Lists don't physically contain other objects. It's almost impossible to have one object physically contain another object in Python.
    – user2357112
    3 hours ago






  • 2




    Some relevant reading material: Python list implementation, How is Python's List Implemented?, What is the underlying data structure for Python lists?.
    – Warren Weckesser
    3 hours ago










  • Python list objects are implemented as array-lists, not a linked-list structure. They are essentially arrays of PyObject pointers, in CPython.
    – juanpa.arrivillaga
    2 hours ago














up vote
6
down vote

favorite
2












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 4 items ie:



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







share|improve this question



















  • 6




    What makes you think that arrays are linearly allocated rather than a list of pointers. - [me confused by your profile description]
    – Morrison Chang
    3 hours ago







  • 9




    Don't confuse item access, which is O(1), with item lookup / search, which is O(n).
    – Mike Scotty
    3 hours ago







  • 1




    Lists don't physically contain other objects. It's almost impossible to have one object physically contain another object in Python.
    – user2357112
    3 hours ago






  • 2




    Some relevant reading material: Python list implementation, How is Python's List Implemented?, What is the underlying data structure for Python lists?.
    – Warren Weckesser
    3 hours ago










  • Python list objects are implemented as array-lists, not a linked-list structure. They are essentially arrays of PyObject pointers, in CPython.
    – juanpa.arrivillaga
    2 hours ago












up vote
6
down vote

favorite
2









up vote
6
down vote

favorite
2






2





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 4 items ie:



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







share|improve this question















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 4 items ie:



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






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited 27 mins ago

























asked 3 hours ago









Teererai Marange

62621331




62621331







  • 6




    What makes you think that arrays are linearly allocated rather than a list of pointers. - [me confused by your profile description]
    – Morrison Chang
    3 hours ago







  • 9




    Don't confuse item access, which is O(1), with item lookup / search, which is O(n).
    – Mike Scotty
    3 hours ago







  • 1




    Lists don't physically contain other objects. It's almost impossible to have one object physically contain another object in Python.
    – user2357112
    3 hours ago






  • 2




    Some relevant reading material: Python list implementation, How is Python's List Implemented?, What is the underlying data structure for Python lists?.
    – Warren Weckesser
    3 hours ago










  • Python list objects are implemented as array-lists, not a linked-list structure. They are essentially arrays of PyObject pointers, in CPython.
    – juanpa.arrivillaga
    2 hours ago












  • 6




    What makes you think that arrays are linearly allocated rather than a list of pointers. - [me confused by your profile description]
    – Morrison Chang
    3 hours ago







  • 9




    Don't confuse item access, which is O(1), with item lookup / search, which is O(n).
    – Mike Scotty
    3 hours ago







  • 1




    Lists don't physically contain other objects. It's almost impossible to have one object physically contain another object in Python.
    – user2357112
    3 hours ago






  • 2




    Some relevant reading material: Python list implementation, How is Python's List Implemented?, What is the underlying data structure for Python lists?.
    – Warren Weckesser
    3 hours ago










  • Python list objects are implemented as array-lists, not a linked-list structure. They are essentially arrays of PyObject pointers, in CPython.
    – juanpa.arrivillaga
    2 hours ago







6




6




What makes you think that arrays are linearly allocated rather than a list of pointers. - [me confused by your profile description]
– Morrison Chang
3 hours ago





What makes you think that arrays are linearly allocated rather than a list of pointers. - [me confused by your profile description]
– Morrison Chang
3 hours ago





9




9




Don't confuse item access, which is O(1), with item lookup / search, which is O(n).
– Mike Scotty
3 hours ago





Don't confuse item access, which is O(1), with item lookup / search, which is O(n).
– Mike Scotty
3 hours ago





1




1




Lists don't physically contain other objects. It's almost impossible to have one object physically contain another object in Python.
– user2357112
3 hours ago




Lists don't physically contain other objects. It's almost impossible to have one object physically contain another object in Python.
– user2357112
3 hours ago




2




2




Some relevant reading material: Python list implementation, How is Python's List Implemented?, What is the underlying data structure for Python lists?.
– Warren Weckesser
3 hours 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
3 hours ago












Python list objects are implemented as array-lists, not a linked-list structure. They are essentially arrays of PyObject pointers, in CPython.
– juanpa.arrivillaga
2 hours ago




Python list objects are implemented as array-lists, not a linked-list structure. They are essentially arrays of PyObject pointers, in CPython.
– juanpa.arrivillaga
2 hours ago












1 Answer
1






active

oldest

votes

















up vote
9
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).






share|improve this answer






















    Your Answer





    StackExchange.ifUsing("editor", function ()
    StackExchange.using("externalEditor", function ()
    StackExchange.using("snippets", function ()
    StackExchange.snippets.init();
    );
    );
    , "code-snippets");

    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "1"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    convertImagesToLinks: true,
    noModals: false,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );













     

    draft saved


    draft discarded


















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f52684993%2fpython-how-come-list-element-lookup-is-o1%23new-answer', 'question_page');

    );

    Post as a guest

















    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes








    up vote
    9
    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).






    share|improve this answer


























      up vote
      9
      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).






      share|improve this answer
























        up vote
        9
        down vote



        accepted







        up vote
        9
        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).






        share|improve this answer














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







        share|improve this answer














        share|improve this answer



        share|improve this answer








        edited 2 hours ago

























        answered 3 hours ago









        DJG

        3,84232040




        3,84232040



























             

            draft saved


            draft discarded















































             


            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f52684993%2fpython-how-come-list-element-lookup-is-o1%23new-answer', 'question_page');

            );

            Post as a guest
































































            Comments

            Post a Comment

            Popular posts from this blog

            What does second last employer means? [closed]

            Image
            Clash Royale CLAN TAG #URR8PPP .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0; up vote -3 down vote favorite Say, for example I have worked in the following companies, Company A => 2010 - 2011 Company B => 2011 - 2012 Company C => 2012 - Till Date Company D => Have offer Now assume Company D is asking to submit documents from my second last employer. So from the list of companies given, which company would be qualified as second last employer? software-industry employer share | improve this question asked Aug 10 '14 at 5:16 Rajaprabhu Aravindasamy 559 1 6 13 closed as off-topic by Jim G., jmort253 ♦ Aug 11 '14 at 1:58 This question appears to be off-topic. The users who voted to close gave this specific reason: "Questions seeking advice on company-specific regulations, agreements, or policies should be directed to your manager or HR department. Questions that address...
            Read more

            Installing NextGIS Connect into QGIS 3?

            Image
            Clash Royale CLAN TAG #URR8PPP .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0; up vote 1 down vote favorite Just acquired free version of NEXTGIS and trying to install the plugin for QGIS. It tells me it was not designed for version 3 of QGIS. How do I set up the QGIS-NEXTGIS interface then? qgis qgis-plugins nextgis share | improve this question edited 3 hours ago PolyGeo ♦ 51.9k 17 77 233 asked 4 hours ago IanGS 16 4 New contributor IanGS is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct. add a comment  |  up vote 1 down vote favorite Just acquired free version of NEXTGIS and trying to install the plugin for QGIS. It tells me it was not designed for version 3 of QGIS. How do I set up the QGIS-NEXTGIS interface then? qgis qgis-plugin...
            Read more

            One-line joke

            A one-liner is a joke that is delivered in a single line. A good one-liner is said to be pithy - concise and meaningful. [1] Comedians and actors use this comedic method as part of their act, e.g. Jimmy Carr, Tommy Cooper, Rodney Dangerfield, Norm Macdonald, Ken Dodd, Stewart Francis, Zach Galifianakis, Mitch Hedberg, Anthony Jeselnik, Milton Jones, Shappi Khorsandi, Jay London, Mark Linn-Baker, Demetri Martin, Groucho Marx, Dan Mintz, Emo Philips, Tim Vine, Steven Wright and Henny Youngman and Arnold Schwarzenegger. [ citation needed ] Many fictional characters are also known to deliver one-liners, including James Bond, who usually includes pithy and laconic quips after disposing of a villain. [ citation needed ] Examples "A baby seal walks into a club." "A dyslexic man walks into a bra." (Anonymous) "There are three types of people, those who can count and those who can't." "Venison's dear, isn't it?" (Jimmy Carr) "An escala...
            Read more