Snippet revisions — Bitbucket

+class clist(object):

+  """double-linked list implementation with sentinel"""

+  def __init__(self):

+    """create an empty list in O(1)"""

+    self.__len = 0

+    self.__sentinel = node()

+    self.__sentinel._next = self.__sentinel

+    self.__sentinel._prev = self.__sentinel

+  def __len__(self):

+    """return the length of the list in O(1)"""

+    return self.__len

+  def __contains__(self,x):

+    """return if x is in the list in O(N)"""

+    return self.__contains_aux(x,self.__sentinel._next)

+  def __contains_aux(self,x,nd):

+    """auxiliary search function in O(N)"""

+    ans = None

+    if nd == self.__sentinel:

+      ans = False

+    elif nd._val == x:

+      ans = True

+    else:

+      ans = self.__contains_aux(x,nd._next)

+    return ans

+  def __str__(self):

+    """return the string representation of the list in O(N)"""

+    ans = list()

+    self.__str_aux(ans,self.__sentinel._next)

+    return str(ans)

+  def __str_aux(self,ans,nd):

+    if nd != self.__sentinel:

+      ans.append(nd._val)

+      self.__str_aux(ans,nd._next)

+  def insert_last(self,x):

+    """insert an element to the end of the list in O(1)"""

+    prev = self.__sentinel._prev

+    nd = node(prev,x,self.__sentinel)

+    prev._next = self.__sentinel._prev = nd

+    self.__len += 1

+  def insert_first(self,x):

+    """insert an element to the head of the list in O(1)"""

+    nxt = self.__sentinel._next

+    nd = node(self.__sentinel,x,nxt)

+    nxt._prev = self.__sentinel._next = nd

+    self.__len += 1

+  def remove_last(self):

+    """delete the element last in the list, if any in O(1)"""

+    assert not(self.is_empty())

+    last = self.__sentinel._prev

+    prev = self.__sentinel._prev = last._prev

+    prev._next = self.__sentinel

+    last._next = last._prev = None

+    self.__len -= 1

+  def remove_first(self):

+    """delete the element first in the list, if any in O(1)"""

+    assert not(self.is_empty())

+    first = self.__sentinel._next

+    nxt = self.__sentinel._next = first._next

+    nxt._prev = self.__sentinel

+    first._next = first._prev = None

+    self.__len -= 1

+  def is_empty(self):

+    """return if the list is empty in O(1)"""

+    return self.__len==0

+  def get_last(self):

+    """return the element last in the list, if any, in O(1)"""

+    assert not(self.is_empty())

+    return self.__sentinel._prev._val

+  def get_first(self):

+    """return the element first in the list, if any, in O(1)"""

+    assert not(self.is_empty())

+    return self.__sentinel._next._val

+class node(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 = prev

+    self._val = val

+    self._next = nxt

+  def __str__(self):

+    """return the string representation of the node in O(1)"""

+    return self._val

Snippets