0

Python implements list with references in memory (i.e., pointers if you might say) to its actual elements. These references are contiguous in memory. Example:

# RefX, RefY and RefZ are contiguous memory references to the following elements
list_example = [elementX, elementY, elementZ] 

#insert elementS at (index 1) will shift all the next references (RefY and RefZ in this 
 case) in the memory (assume each ref is  8 bit size)

list_example = [elementX, elementS, elementY, elementZ]

#Therefore insert operation time complexity is O(N)

My question is:

In case of 2D list: If I append an element to the end of the first list:

list_of_lists[0].append(item)

would this case result in shifting the references of elements in second and third list in memory?

My main point: I am asking because I am wondering if implementing list of three stacks (as a list of lists) is costly operation in terms of time complexity in case of append or pop?

Maher Bouidani
  • 41
  • 4
  • 1
    "These references are contiguous in memory." no they aren't – roganjosh Jul 17 '20 at 19:09
  • `list_of_lists[0][1].append(item)` means it's 3-dimensional, since `list_of_lists[0][1]` has to be a list. – Barmar Jul 17 '20 at 19:11
  • Did you mean `list_of_lists[0].append(item)`? – Barmar Jul 17 '20 at 19:11
  • 1
    Even if a list is contiguous, each list is independent. They don't even know that they're referenced by `list_of_lists`. – Barmar Jul 17 '20 at 19:12
  • It's like an array of pointers in C. Calling `realloc()` on one of the pointers doesn't reallocate any of the other pointers. – Barmar Jul 17 '20 at 19:12
  • @Barmar..yeah sorry you are right – Maher Bouidani Jul 17 '20 at 19:13
  • Contagious maybe – roganjosh Jul 17 '20 at 19:13
  • @MaherBouidani I think roganjosh's point is that there's nothing in the language that requires them to be contiguous, it's an implementation detail. – Barmar Jul 17 '20 at 19:13
  • my main point guys, am I safe to assume that append or pop in the first stack is O(1) or it is O(n) because it shifts all next references? – Maher Bouidani Jul 17 '20 at 19:16
  • @roganjosh, they are contiguous man. look at this plz : https://stackoverflow.com/questions/3917574/how-is-pythons-list-implemented – Maher Bouidani Jul 17 '20 at 19:24
  • @MaherBouidani - in cpython an append may realloc the list depending on its current size. A pop shifts all references after the pop point down. Its not O(1). – tdelaney Jul 17 '20 at 19:29
  • @tdelaney, I think man pop() is O(1) because you are poping out the last element. Now in case you pop from within the list(i.e., pass item --> pop(item)), It is O(N) – Maher Bouidani Jul 17 '20 at 19:32
  • @MaherBouidani - I was thinking of "pop" generally. Popping from the end shrinks the list if the used slots fall below half of the total allocated slots. – tdelaney Jul 17 '20 at 19:50

0 Answers0