I'm currently working on implementing a Fibonacci heap in Python for my own personal development. While writing up the object class for a circular, doubly linked-list, I ran into an issue that I wasn't sure of.
For fast membership testing of the linked-list (in order to perform operations like 'remove' and 'merge' faster), I was thinking of adding a hash-table (a python 'set' object) to my linked-list class. See my admittedly very imperfect code below for how I did this:
class Node:
def __init__(self,value):
self.value = value
self.degree = 0
self.p = None
self.child = None
self.mark = False
self.next = self
self.prev = self
def __lt__(self,other):
return self.value < other.value
class Linked_list:
def __init__(self):
self.root = None
self.nNodes = 0
self.members = set()
def add_node(self,node):
if self.root == None:
self.root = node
else:
self.root.next.prev = node
node.next = self.root.next
self.root.next = node
node.prev = self.root
if node < self.root:
self.root = node
self.members.add(node)
self.nNodes = len(self.members)
def find_min():
min = None
for element in self.members:
if min == None or element<min:
min = element
return min
def remove_node(self,node):
if node not in self.members:
raise ValueError('node not in Linked List')
node.prev.next, node.next.prev = node.next, node.prev
self.members.remove(node)
if self.root not in self.members:
self.root = self.find_min()
self.nNodes -=1
def merge_linked_list(self,LL2):
for element in self.members&LL2.members:
self.remove_node(element)
self.root.prev.next = LL2.root
LL2.root.prev.next = self.root
self.root.prev, LL2.root.prev = LL2.root.prev, self.root.prev
if LL2.root < self.root:
self.root = LL2.root
self.members = self.members|LL2.members
self.nNodes = len(self.members)
def print_values(self):
print self.root.value
j = self.root.next
while j is not self.root:
print j.value
j = j.next
My question is, does the hash table take up double the amount of space that just implementing the linked list without the hash table? When I look at the Node objects in the hash table, they seem to be in the exact same memory location that they are when just independent node objects. For example, if I create a node:
In: n1 = Node(5)
In: print n1
Out: <__main__.Node instance at 0x1041aa320>
and then put this node in a set:
In: s1 = set()
In: s1.add(n1)
In: print s1
Out: <__main__.Node instance at 0x1041aa320>
which is the same memory location. So it seems like the set doesn't copy the node.
My question is, what is the space complexity for a linked list of size n with a hash-table that keeps track of elements. Is it n or 2n? Is there anything elementary wrong about using a hash table to keep track of elements.
I hope this isn't a duplicate. I tried searching for a post that answered this question, but didn't find anything satisfactory.
