Skip to content

Instantly share code, notes, and snippets.

@DeaconDesperado
Created July 10, 2013 15:46
Show Gist options
  • Save DeaconDesperado/5967427 to your computer and use it in GitHub Desktop.
Save DeaconDesperado/5967427 to your computer and use it in GitHub Desktop.
Linked list ithsmallest from value
class Node:
def __init__(self,val):
self.val = val
self.next = None
class LL:
def __init__(self):
self.first = None
self._n = 0
def insert(self,val):
node = Node(val)
if self.first is None:
self.first = node
return self.first
cur = self.first
while not cur.next is None:
cur = cur.next
cur.next = node
self._n += 1
return cur
def ithsmallest_value(self,i):
cur = self.first
buff = [None] * i
print buff
def ithsmallest(self,query,i):
#make a buffer of None values to count back from
buff = [None] * i
ind = 0
cur = self.first
#While we have not found our query and we have not gone off end of LL
while buff[-1] is not query and ind <= len(self):
#Put the current value at the end of the buff, buff[0] will be n back since it is n max size
buff.append(cur.val)
cur = cur.next
#Enforce buffer size constraint
if len(buff) > i+1:
buff.pop(0)
ind+=1
#return the first buffer value
return buff.pop(0)
def __str__(self):
return '%s many nodes' % len(self)
def __len__(self):
return self._n
if __name__ == '__main__':
vals = [32,46,27,93,1]
ll = LL()
for val in vals:
ll.insert(val)
assert ll.ithsmallest(32,10) is None
assert ll.ithsmallest(46,1) is 32
assert ll.ithsmallest(27,4) is None
assert ll.ithsmallest(93,3) is 32
assert ll.ithsmallest(1,3) is 46
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment