Snippets
Created by
Camilo Rocha
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 | 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
class stack(object):
"""stack implementation using deep embedding on double-linked list
implementation with sentinel from clist
"""
def __init__(self):
"""creates an empty stack in O(1)"""
self.__stack = clist()
def __len__(self):
"""return the number of elements in the stack in O(1)"""
return len(self.__stack)
def push(self,x):
"""adds x to the top of the stack in O(1)"""
self.__stack.insert_last(x)
def top(self):
"""return the element last inserted in the stack in O(1)"""
assert len(self)>0
return self.__stack.get_last()
def pop(self):
"""remove the element last inserted in the stack in O(1)"""
assert len(self)>0
self.__stack.remove_last()
def __str__(self):
"""return the string representation of the stack in O(N)"""
return str(self.__stack)
|
Comments (0)
You can clone a snippet to your computer for local editing. Learn more.