classclist(object):"""double-linked list implementation with sentinel"""def__init__(self):"""create an empty list in O(1)"""self.__len=0self.__sentinel=node()self.__sentinel._next=self.__sentinelself.__sentinel._prev=self.__sentineldef__len__(self):"""return the length of the list in O(1)"""returnself.__lendef__contains__(self,x):"""return if x is in the list in O(N)"""returnself.__contains_aux(x,self.__sentinel._next)def__contains_aux(self,x,nd):"""auxiliary search function in O(N)"""ans=Noneifnd==self.__sentinel:ans=Falseelifnd._val==x:ans=Trueelse:ans=self.__contains_aux(x,nd._next)returnansdef__str__(self):"""return the string representation of the list in O(N)"""ans=list()self.__str_aux(ans,self.__sentinel._next)returnstr(ans)def__str_aux(self,ans,nd):ifnd!=self.__sentinel:ans.append(nd._val)self.__str_aux(ans,nd._next)definsert_last(self,x):"""insert an element to the end of the list in O(1)"""prev=self.__sentinel._prevnd=node(prev,x,self.__sentinel)prev._next=self.__sentinel._prev=ndself.__len+=1definsert_first(self,x):"""insert an element to the head of the list in O(1)"""nxt=self.__sentinel._nextnd=node(self.__sentinel,x,nxt)nxt._prev=self.__sentinel._next=ndself.__len+=1defremove_last(self):"""delete the element last in the list, if any in O(1)"""assertnot(self.is_empty())last=self.__sentinel._prevprev=self.__sentinel._prev=last._prevprev._next=self.__sentinellast._next=last._prev=Noneself.__len-=1defremove_first(self):"""delete the element first in the list, if any in O(1)"""assertnot(self.is_empty())first=self.__sentinel._nextnxt=self.__sentinel._next=first._nextnxt._prev=self.__sentinelfirst._next=first._prev=Noneself.__len-=1defis_empty(self):"""return if the list is empty in O(1)"""returnself.__len==0defget_last(self):"""return the element last in the list, if any, in O(1)"""assertnot(self.is_empty())returnself.__sentinel._prev._valdefget_first(self):"""return the element first in the list, if any, in O(1)"""assertnot(self.is_empty())returnself.__sentinel._next._valclassnode(object):"""node implementation with previous, value, and next fields"""def__init__(self,prev=None,val=None,nxt=None):"""creates an empty node in O(1)"""self._prev=prevself._val=valself._next=nxtdef__str__(self):"""return the string representation of the node in O(1)"""returnself._val
Comments (0)
HTTPSSSH
You can clone a snippet to your computer for local editing.
Learn more.