51

I am wondering why the default list in Python does not have any shift, unshift methods. Maybe there is an obvious reason for it like the way the lists are ordered in memory.

So currently, I know that I can use append to add an item at the end of a list and pop to remove an element from the end. However, I can only use list concatenation to imitate the behavior of a missing shift or unshift method. 

>>> a = [1,2,3,4,5]
>>> a = [0] + a  # Unshift / Push
>>> a
[0,1,2,3,4,5]
>>> a = a[1:]  # Shift / UnPush
>>> a
[1,2,3,4,5]

Did I miss something?

wim
  • 338,267
  • 99
  • 616
  • 750
nowox
  • 25,978
  • 39
  • 143
  • 293
  • 30
    `pop(0)`, `insert(0,x)` ? – C.B. Dec 10 '15 at 20:20
  • Are you demonstrating with this code that you can easily shift and unshift without dedicated methods? – khelwood Dec 10 '15 at 20:20
  • I think he is asking from maybe a software eng perspective why certain operations don't have their logical opposites. – C.B. Dec 10 '15 at 20:21
  • @C.B. Not really because you are adressing your list by value, not by index :( – nowox Dec 10 '15 at 20:22
  • 2
    @nowox No, those are by index. – Morgan Thrapp Dec 10 '15 at 20:23
  • Well, with slice you get that same thing, don't you? `shift left by 2 : a = a[2:]+a[:2]`, `shift right by 2 : a = a[-2:]+a[:-2]`. Or isn't that what you asked? – tglaria Dec 10 '15 at 20:26
  • 4
    It might be worth noting that Python's `list` type isn't actually a linked list, it's an array. Thus, adding a value at the start of a list is more computationally expensive than for a regular linked list, and it might lead to (even more) confusion. – Vincent Savard Dec 10 '15 at 20:26
  • 2
    @VincentSavard To go further, Python lists are arrays *of names* (essentially like an array of pointers), which is also very different than a contiguous memory array like in C. In Python, the space allocated for the list elements is contiguous (usually), but the list elements themselves can just be names that point off to all sorts of crazy corners of memory. Often if you need to be doing operations that would be efficient for traditional arrays, it means you should be using something that implements the buffer protocol, like array.array or NumPy ndarray, instead of list. – ely Dec 10 '15 at 20:36
  • @VincentSavard But perl solved that problem by putting the list in the middle of the array, so that unshifting and pushing take the same amount of time (as long as you don't do it so much that you need a new array). But these type of questions usually boil down to "ask the authors". – Teepeemm Dec 10 '15 at 20:37
  • It gets a little tricky when you put a small integer or an interned string into a list, since then the list entry, say my_list[i] is a *name* that refers to one singular entity representing the value. But for larger integers and un-interned strings, it can be the case that the only name that exists in a given program for that entity is the name "my_list[i]", which sort of tricks you into believing that the object sort of "lives" in the list's allocated memory, but actually only a name for it lives in the list. – ely Dec 10 '15 at 20:38
  • why not just `def popfirst(l): l.reverse() l.pop() l.reverse() return l` – d8aninja Oct 02 '16 at 18:07

2 Answers2

65

Python lists were optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation. Actually, the "list" datatype in CPython works differently as to what many other languages might call a list (e.g. a linked-list) - it is implemented more similarly to what other languages might call an array, though there are some differences here too.

You may be interested instead in collections.deque, which is a list-like container with fast appends and pops on either end.

Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

It provides the missing methods you appear to be asking about under the names appendleft and popleft:

appendleft(x)

Add x to the left side of the deque.

popleft()

Remove and return an element from the left side of the deque. If no elements are present, raises an IndexError.

Of course there are trade-offs: indexing or inserting/removing near the middle of the deque is slow. In fact deque.insert(index, object) wasn't even possible before Python 3.5, you would need to rotate, insert/pop, and rotate back. deques also don't support slicing, for similar functionality you'll have to write something annoying with e.g. itertools.islice instead.

For further discussion of the advantages and disadvantages of deque vs list data structures, see How are deques in Python implemented, and when are they worse than lists?

wim
  • 338,267
  • 99
  • 616
  • 750
0

in Python3

we have insert method on a list. takes the value you require to add and also the index where you want to add it.

arrayOrList  = [1,2,3,4,5]
arrayOrList.insert(0 , 0) 
print(arrayOrList)
Shakeeb Ahmed
  • 29
  • 3