Is it possible to remove the first item in a list in Python and still have O(1) run time?
I'm trying to remove the first item from a list in python, but I can't use pop(),append() or extend(). I tried using list splicing ,del list[index] and the remove method. But I found out that list splicing, the del method and remove method have a run time of O(n). Is there any other way to remove the first element in a list and still have an O(1) run time?
17 Replies
When in doubt, consult chatgpt
I cant import deque unfortunately. I have to use only a python list. Essentially I'm building my deque in python using a list.
I tried asking Chat Gpt that and its response is don't use a list, implement a linked list lol
even though I said I have to use a list
Lol
Yeah idk if what you are trying to accomplish is possible then…
Or you might be approaching the problem wrong….
yeah the run time for my pop_front has to be O(1) for my DSA assignment or I lose marks.
thats the requirements I have to use a python list, no importing deques, no using pop,extend or append
Just ignore the first element lol
Very memory inefficient way though
yeah thats another problem, in my deque i have to implement an index [] and when index [0] is called it must point to the front of the deque
so i cant move the front pointer anywhere, it has to stay at 0 lol
Didn't know you could implement [] methods in python
Or, do you mean deque[0] straight up goes to the inner list?
this is whats it asking me
Oh so you can control what you return
So, if the first item is deleted and k = 0, can't you return (k + 1) element instead?
oh yeah i can do that, thanks
Now I wonder what pop is doing underneath the hood
Since it has constant time
popping from a list in python?
is it constant time?
Oh I meant popping the last element
I think that is contant time
Or was it the first element
its a deque you have to pop from front and back
but you can't use the pop method
hmm, it seems like cuz its the last element, it just shinks the list. No need to "actually" remove anything
Yeah, I realized that after I typed it lol
how do i add elements to the front and back then? if im just shrinking the list and not removing anything?
oh i wait just increase the size again and swap whatever value is there nbm
nvm*