2
array = ["A", "B", "C", "D"]

for the given array it takes O(1) to point to the first index which is 0. So if I type array[0], it takes O(1) to point to "A". But if i write array[-1] which points to the last index 3. Does it iterate through the entire array to get the last index or it knows that the array ends at index 3 by default ? In other words how is array[-1] is implemented in python?

ananya
  • 879
  • 1
  • 7
  • 14

2 Answers2

5

Accessing any array element is in constant time, since it is a known by memory location (i.e. a pointer.)

The array does not need to go through prior elements in order to access the nth element (i.e. it is not like a linked list.) The location of all elements is known before hand and can simply be accessed directly.

Updated thanks to comments.

array[-x] is syntactic sugar for array[len(lst) - x]. So it's still a simple constant access to a pointer and takes no time.

You can see this answer for a bit more info. While it is about C, the concepts should be the same.

Rietty
  • 1,116
  • 9
  • 24
  • 1
    `lst[-x]` is syntactic sugar for `lst[len(lst) - x]` – Primusa Jan 30 '19 at 02:23
  • Thank you. That helped a lot. I also did not know that `len()` takes O(1) – ananya Jan 30 '19 at 02:36
  • @ananya: If you know C++, you can think of Python's `list` as being equivalent to `std::vector`, or for Java, to `ArrayList`. It's just the Python name for a dynamically sized array. Despite the name, it's not a linked list. – ShadowRanger Jan 30 '19 at 02:57
4

Native Python lists are arrays of pointers and accessing any element is O(1).

Note that this is an implementation detail specific to the standard Python implementation, known as CPython. Other language implementations may implement lists differently.

kindall
  • 178,883
  • 35
  • 278
  • 309
  • Thank you for your reply. I agree. Accessing any element takes O(1). But when I want to access the last element, how does it go to last element directly ? Does not the pointer has to iterate through the entire array to know that this is the last element ? – ananya Jan 30 '19 at 02:23
  • 1
    The list knows its length, so it is trivial to access items by negative index. – kindall Jan 30 '19 at 02:41