Created
July 10, 2013 15:46
-
-
Save DeaconDesperado/5967427 to your computer and use it in GitHub Desktop.
Linked list ithsmallest from value
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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