# LRU with a linkedlist (single) , LRU is the same as FIFO (i.e. older items or "least used" are evicted first)
# items are added to the head, they are removed from the tail
# loop = 2 pointers, one jumps 1 node and one jumps 2 nodes, if on the same node
# Find loop start=
# 3rd element from the end = 2 pointers, start the second when the first is at node 3
# Delete middle node: curr.data = next.data, until finally delete the last
# Sum 1 digit per node, just use a carryover
# DEDUPE: OR 2 ptrs: curr and scan all prev for dup N^2
ASC5=[0,1,2,3,4]
ASC6=[0,1,2,3,4,5]
DUP=[3,6,4,7,9,2,7,5,3]
class Node():
def __init__( self, data ):
self.data = data
self.next = None
class LinkedList():
def __init__( self ):
self.head = None
def build( self, input_array ):
self.head = Node( input_array[0] )
current = self.head
for i in xrange( 1, len( input_array ) ):
current.next = Node( input_array[i] )
current = current.next
def push( self, data ):
if not self.head:
self.head = Node( data )
return self.head
else:
prev = self.head
current = self.head.next
while current:
prev = current
current = current.next
prev.next = Node( data )
return prev.next
def show( self , current ):
while current:
print current.data,
current = current.next
print
def get( self, index):
if index < 0: return None
count=0
current = self.head
while current and count != index:
current = current.next
count += 1
return current
def middle( self ):
mid = self.head
end = self.head.next
while end != None:
mid = mid.next
end = end.next
if end:
end = end.next
return mid
def frequency( self ):
count = dict()
current=self.head
while current:
if count.get( current.data ):
count[ current.data ]+=1
else:
count[ current.data ] = 1
current = current.next
return count
def dedupe( self ):
count = dict()
current = self.head
prev = self.head
while current:
if count.get( current.data ):
prev.next = current.next
else:
count[ current.data ] = 1
prev = current
current = current.next
# TODO: bug that adds None to the end of the list
def reverse( self, current ):
temp = None
previous = None
while current:
temp = current.next
current.next = previous
previous = current
current = temp
self.head = previous
def dequeue( self ): # need to set previous of current to be None, return current
if not self.head: # raise an exception?
result = None
elif not self.head.next:
result = self.head
self.head = None
else:
current = self.head
result = self.head.next # we have guaranteed by above that this exists
peek = current.next.next
while peek:
result = result.next
current = current.next
peek = peek.next
current.next = None
return result
asc = LinkedList()
print "empty: ",
asc.show( asc.head )
asc.build( ASC5 )
print "ascending: ",
asc.show( asc.head )
asc.reverse( asc.head )
print "reversed: ",
asc.show( asc.head )
print 'getting element at index 0:', asc.get( 0 ).data
print 'getting element at index 4:', asc.get( 4 ).data
mid = asc.middle()
print 'mid (odd length of 5) calculated two different ways', mid.data, ASC5[ len(ASC5)/2]
asc6 = LinkedList()
asc6.build( ASC6 )
asc6.show( asc6.head )
mid6 = asc6.middle()
print 'mid (even length of 6) calculated two different ways', mid6.data, ASC6[ len(ASC6)/2]
single = LinkedList()
current = single.push( 10 )
print 'single: ',
single.show( single.head )
current.next = Node( 11 )
print 'pushed externally',
single.show( single.head )
# dequeue when size 2
removed = single.dequeue()
print 'removed: ', removed.data
single.show( single.head )
# dequeue when size 1
removed = single.dequeue()
print 'removed: ', removed.data
single.show( single.head )
removed = single.dequeue()
print 'removed when empty: ', removed
single.show( single.head )
ex = LinkedList()
ex.build( DUP )
print 'with duplicates',
ex.show( ex.head )
print 'frequency (data: count)', ex.frequency()
ex.dedupe()
print 'deduplicated ',
ex.show( ex.head )