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

            Is the Concept of Multiple Fantasy Races Scientifically Flawed? [closed]

            Image
            Clash Royale CLAN TAG #URR8PPP up vote 2 down vote favorite Many fantasy worlds have multiple humanoid species (elves, orcs, humans, etc) living in the same world, in addition to that, they often have the ability to interbreed. And I can't help but question their believability... fantasy-races reproduction interspecies-relations share | improve this question edited Aug 9 at 14:46 Michael Kjörling ♦ 21.1k 10 85 161 asked Aug 9 at 13:13 Chlodio 118 6 closed as unclear what you're asking by MichaelK, Gryphon, John, Vincent, Frostfyre Aug 9 at 15:25 Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question. 3 Stack Exchange exist to
            Read more

            Long meetings (6-7 hours a day): Being “babysat” by supervisor

            Image
            Clash Royale CLAN TAG #URR8PPP .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0; up vote 31 down vote favorite 4 I hold a PhD in mechanical engineering with a 7 year background in self-guided, self-paced research including 2 years as a graduate level course instructor and a subject matter expert for various engineering projects in a university setting in the United States. For the last 10-11 months, I am working in a research industry in France where my task is to debug C++ spaghetti code written over a period of several years by my current supervisor. It is a team of 2: just I and my supervisor. Diurnally, I am posed with a "bug of the day" to get out of this C++ code. My supervisor generally gives me about 15-30 minutes to solve it and then accosts me about whether or not the task is completed and then rinses and repeats this until the end of the day. Off-late, my supervisor has been holding 6-7 hour long "meetin
            Read more

            Confectionery

            Image
            Prepared foods made with a lot of sugar or other cabohydrates "Sweetmeat" redirects here. For the racehorse, see Sweetmeat (horse). Not to be confused with Sweetbread. This Kransekake is a traditional Scandinavian baker's confection. Confectionery is the art of making confections , which are food items that are rich in sugar and carbohydrates. Exact definitions are difficult. [1] In general, though, confectionery is divided into two broad and somewhat overlapping categories, bakers' confections and sugar confections. [2] Bakers' confectionery, also called flour confections , includes principally sweet pastries, cakes, and similar baked goods. Sugar confectionery includes candies ( sweets in British English), candied nuts, chocolates, chewing gum, bubble gum, pastillage, and other confections that are made primarily of sugar. In some cases, chocolate confections (confections made of chocolate) are treated as a separate category, as are sugar-free versions of
            Read more